(57)【特許請求の範囲】
【請求項１】
検索キーデータの特定位置のデータが任意のデータであることを示す情報とされることによって検索対象とする範囲が規定された検索範囲規定データの当該特定位置のデータを予め定められた固定値に置き換え、所定のハッシュ関数により変換することにより対応付けられたアドレスに、所定の情報が記憶された第１記憶手段と、
前記特定位置を示す位置情報が記憶された第２記憶手段と、
検索対象とする検索キーデータが入力された際に、前記第２記憶手段から前記位置情報を読み出し、前記第１記憶手段から、当該検索キーデータの当該位置情報により示される特定位置のデータを前記固定値に置き換え、前記ハッシュ関数により変換することにより対応付けられたアドレスに記憶された情報を読み出す読出手段と、
前記読出手段により読み出された情報が前記所定の情報であるか否かを判定する判定手段と、
備えた情報検索装置。
【請求項２】
前記第１記憶手段は、前記検索キーデータを前記ハッシュ関数を用いて変換することにより対応付けられたアドレスに、当該検索キーデータに対応させる情報が記憶され、
前記読出手段は、検索対象とする検索キーデータが入力された際に、前記第１記憶手段から、当該検索キーデータを前記ハッシュ関数を用いて変換することにより対応付けられたアドレスに記憶された情報をさらに読み出す
請求項１記載の情報検索装置。
【請求項３】
前記位置情報は、前記特定位置が同一の検索範囲データが複数登録される場合、１つのみ記憶される
請求項１又は請求項２記載の情報検索装置。       
【請求項４】
前記位置情報は、前記特定位置をビット位置により示した情報である
請求項１〜請求項３の何れか１項記載の情報検索装置。
【請求項５】
前記位置情報は、前記特定位置を最下位ビットからのビット数により示した情報である
請求項１又は請求項２記載の情報検索装置。
【請求項６】
検索キーデータの特定位置のデータが任意のデータであることを示す情報とされることによって検索対象とする範囲が規定された検索範囲規定データの当該特定位置のデータを予め定められた固定値に置き換え、所定のハッシュ関数により変換することにより対応付けられた第１記憶手段のアドレスに、所定の情報が記憶されると共に、前記特定位置を示す位置情報が第２記憶手段に記憶されており、
検索対象とする検索キーデータが入力された際に、前記第２記憶手段から前記位置情報を読み出し、前記第１記憶手段から、当該検索キーデータの当該位置情報により示される特定位置のデータを前記固定値に置き換え、前記ハッシュ関数により変換することにより対応付けられたアドレスに記憶された情報を読み出し、
当該読み出された情報が前記所定の情報であるか否かを判定する
情報検索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、情報検索装置及び情報検索方法に関するものである。
【背景技術】
【０００２】
例えば、図１４に示されるようなインターネットにおいてパケットデータの中継を行なうルーター１０’では、高速なテーブル検索が行なわれている。このテーブル検索の例としてＮＡＰＴ（Ｎｅｔｗｏｒｋ  Ａｄｄｒｅｓｓ  Ｐｏｒｔ  Ｔｒａｎｓｌａｔｉｏｎ）処理を説明する。
【０００３】
ＮＡＰＴ処理は、ルーター１０’が行う処理で、インターネット接続時のプライベートＩＰ（＝ローカルＩＰ）とグローバルＩＰを変換する処理である。この処理によって１個のグローバルＩＰを使用して複数のＰＣが同時にインターネット接続することを可能としている。以下に仕組みを示す。
【０００４】
ルーター１０’内のＮＡＰＴは（１）のＩＰパケットのソースアドレスを“ローカル１ＩＰ：２０”から“自分ＩＰ：２２０”に変更している。（１）のパケットヘの返信である（３）のパケットでは送り先アドレスを“自分ＩＰ：２２０”から“ローカル１ＩＰ：２０”に変更している。
【０００５】
これにより１つのグローバルＩＰを複数のＰＣが使用することを可能としている。
【０００６】
この処理は高速で行う必要があり、且つテーブルサイズは１０００を超えるため、ハッシュ関数を使用する装置が提案されている。
【０００７】
図１５には、一般的なハッシュ関数を使用したテーブル検索装置のブロック図の一例が示されている。
【０００８】
ここで、Ｍａｉｎ  Ｔａｂｌｅ  ＲＡＭ３４’にはＮＡＰＴ  Ｄａｔａが入っている。
【０００９】
Ｐｏｉｎｔｅｒ  Ｔａｂｌｅ  ＲＡＭ２４’にはＭａｉｎ  Ｔａｂｌｅ  ＲＡＭ３４’のアドレスが入っている。
【００１０】
動作は以下のようになる。
【００１１】
ＮＡＰＴデータ入力時
（１）検索の鍵となる検索キーデータをアドレス変換部２２’においてハッシュ関数に入力し、ハッシュ値を得る。
【００１２】
（２）ハッシュ値をＰｏｉｎｔｅｒ  Ｔａｂｌｅ  ＲＡＭ２４’のアドレスとしてＰｏｉｎｔｅｒ  Ｔａｂｌｅ  ＲＡＭ２４’を読み出し、空ならばＮｅｘＰｏｉｎｔＧｅｎ３０’の発生する値をそのアドレスに入れる。空で無いならばハッシュ値に１加算した上で（２）の処理を行う。
【００１３】
（３）ＮｅｘＰｏｉｎｔＧｅｎ３０’の発生する値をＭａｉｎ  Ｔａｂｌｅ  ＲＡＭ３４’のアドレスとしてＮＡＰＴ  Ｄａｔａを入力する。（その後Ｎｅｘｔ  Ｐｏｉｎｔｅｒを加算する）
【００１４】
ＮＡＰＴデータ読み出し時
（１）検索キーデータをハッシュ関数に入力し、ハッシュ値を得る。
【００１５】
（２）ハッシュ値をＰｏｉｎｔｅｒ  Ｔａｂｌｅ  ＲＡＭ２４’のアドレスとしてＰｏｉｎｔｅｒ  Ｔａｂｌｅ  ＲＡＭ２４’を読み出す。
【００１６】
（３）読み出された値をＭａｉｎ  Ｔａｂｌｅ  ＲＡＭ３４’のアドレスとしてＭａｉｎ  Ｔａｂｌｅ  ＲＡＭ３４’を読み出す。
【００１７】
（４）読み出された値が検索キーデータに対応するデータならば終了する。
検索キーデータに対応するデータでないならばハッシュ値に１加算した上で（２）の処理を行う。
【００１８】
ＮＡＰＴデータ削除時
（１）検索キーデータをハッシュ関数に入力し、ハッシュ値を得る。
【００１９】
（２）ハッシュ値をＰｏｉｎｔｅｒ  Ｔａｂｌｅ  ＲＡＭ２４’のアドレスとしてＰｏｉｎｔｅｒ  Ｔａｂｌｅ  ＲＡＭ２４’を読み出す。
【００２０】
（３）読み出された値をＭａｉｎ  Ｔａｂｌｅ  ＲＡＭ３４’のアドレスとしてＭａｉｎ  Ｔａｂｌｅ  ＲＡＭ３４’を読み出す。
【００２１】
（４）読み出された値が、検索キーデータに対応するデータならばハッシュ値がアドレスのＰｏｉｎｔｅｒ  Ｔａｂｌｅ  ＲＡＭ２４’のデータ及びそのＰｏｉｎｔｅｒ  Ｔａｂｌｅ  ＲＡＭ２４’の内容がアドレスのＭａｉｎ  Ｔａｂｌｅ  ＲＡＭ３４’のデータを削除する。
検索キーデータに対応するデータでないならばハッシュ値に１加算した上で（２）の処理を行う。
【００２２】
ＮＡＰＴ処理の場合は検索キーデータと検索キーデータに対応するデータが１対１対応しているのでハッシュを利用したハッシュを利用したＴａｂｌｅ検索方式で問題なく実現できる。
【００２３】
なお、本発明に関連する技術として、特許文献１には、ワイルドカードを用いて入力されたキーワードに対して近似する名標を検索・出力可能な名標検索装置が開示されている。
【特許文献１】特開平９−２２３１５４号公報
【発明の開示】
【発明が解決しようとする課題】
【００２４】
ところで、入力した検索キーデータが特定の範囲に属するものであるかの範囲検索を必要とする場合がある。例えば、ルーター１０’では、ＩＰフィルタ処理のように入力されたＩＰアドレスが特定の範囲のものである場合に、データの中継を行なわないようにする場合などがある。
【００２５】
しかしながら、ＩＰフィルタ処理のように入力した検索キーデータが特定の範囲に属するかの範囲検索を必要とする検索の場合、ハッシュを利用したＴａｂｌｅ検索方式を使用できなかった。
【００２６】
言い換えればハッシュ検索は高速な検索が可能であるが基本的に１対１の検索であるため、ワイルドカード（ある範囲を持つ特殊文字）を使用した検索には適用できない問題があった。
【００２７】
なお、特許文献１の技術は、テーブル内からワイルドカード（例えば「＊」）での検索を行なうための技術であり、技術的に用いられる場面が異なる。また、特許文献１の技術では、例えば、検索ａｂ＊ｘｙを行なった場合、検索結果がａｂ１ｘｙもａｂ２２ｘｙもａｂ３３３ｘｙとなり、不要なデータまで検索されてしまい、処理も煩雑である。
【００２８】
本発明は上記事実を鑑みてなされたものであり、ハッシュ関数を用いて入力した検索キーデータが特定の範囲内のデータであるか否かを判定することができる情報検索装置及び情報検索方法を提供することを目的とする。
【課題を解決するための手段】
【００２９】
上記目的を達成するため、請求項１記載の発明は、検索キーデータの特定位置のデータが任意のデータであることを示す情報とされることによって検索対象とする範囲が規定された検索範囲規定データの当該特定位置のデータを予め定められた固定値に置き換え、所定のハッシュ関数により変換することにより対応付けられたアドレスに、所定の情報が記憶された第１記憶手段と、前記特定位置を示す位置情報が記憶された第２記憶手段と、検索対象とする検索キーデータが入力された際に、前記第２記憶手段から前記位置情報を読み出し、前記第１記憶手段から、当該検索キーデータの当該位置情報により示される特定位置のデータを前記固定値に置き換え、前記ハッシュ関数により変換することにより対応付けられたアドレスに記憶された情報を読み出す読出手段と、前記読出手段により読み出された情報が前記所定の情報であるか否かを判定する判定手段と、備えている。
【００３０】
請求項１記載の発明は、検索キーデータの特定位置のデータが任意のデータであることを示す情報とされることによって検索対象とする範囲が規定された検索範囲規定データの当該特定位置のデータを予め定められた固定値に置き換え、所定のハッシュ関数により変換することにより対応付けられた第１記憶手段のアドレスに、所定の情報が記憶されると共に、第２記憶手段に特定位置を示す位置情報が記憶されている。
【００３１】
そして、本発明では、検索対象とする検索キーデータが入力された際に、読出手段により、第２記憶手段から位置情報が読み出され、第１記憶手段から、当該検索キーデータの当該位置情報により示される特定位置のデータを固定値に置き換え、ハッシュ関数により変換することにより対応付けられたアドレスに記憶された情報が読み出され、判定手段により、読出手段により読み出された情報が所定の情報であるか否かが判定される。
【００３２】
このように請求項１記載の発明よれば、検索範囲規定データの特定位置のデータを予め定められた固定値に置き換え、所定のハッシュ関数により変換することにより対応付けられた第１記憶手段のアドレスに、所定の情報を記憶させておき、検索対象とする検索キーデータが入力した際に、当該検索キーデータの位置情報により示される特定位置のデータを固定値に置き換えて、ハッシュ関数により変換することにより対応付けられた第１記憶手段のアドレスに記憶された情報を読み出し、読み出された情報が所定の情報であるか否かを判定することにより、ハッシュ関数を用いて入力した検索キーデータが特定の範囲内のデータであるか否かを判定することができる。
【００３３】
なお、本発明は、請求項２記載の発明のように、前記第１記憶手段により、前記検索キーデータを前記ハッシュ関数を用いて変換することにより対応付けられたアドレスに、当該検索キーデータに対応させる情報が記憶され、前記読出手段が、検索対象とする検索キーデータが入力された際に、前記第１記憶手段から、当該検索キーデータを前記ハッシュ関数を用いて変換することにより対応付けられたアドレスに記憶された情報をさらに読み出すようにしてもよい。
【００３４】
また、本発明は、請求項３記載の発明のように、前記位置情報が、前記特定位置が同一の検索範囲データが複数登録される場合、１つのみ記憶されることが好ましい。
【００３５】
また、請求項１乃至請求項３記載の発明は、請求項４記載の発明のように、前記位置情報が、前記特定位置をビット位置により示した情報であってもよい。
【００３６】
さらに、請求項１乃至請求項３記載の発明は、請求項５記載の発明のように、前記位置情報が、前記特定位置を最下位ビットからのビット数により示した情報であってもよい。
【００３７】
一方、上記目的を達成するため、請求項６記載の発明は、検索キーデータの特定位置のデータが任意のデータであることを示す情報とされることによって検索対象とする範囲が規定された検索範囲規定データの当該特定位置のデータを予め定められた固定値に置き換え、所定のハッシュ関数により変換することにより対応付けられた第１記憶手段のアドレスに、所定の情報が記憶されると共に、前記特定位置を示す位置情報が第２記憶手段に記憶されており、検索対象とする検索キーデータが入力された際に、前記第２記憶手段から前記位置情報を読み出し、前記第１記憶手段から、当該検索キーデータの当該位置情報により示される特定位置のデータを前記固定値に置き換え、前記ハッシュ関数により変換することにより対応付けられたアドレスに記憶された情報を読み出し、当該読み出された情報が前記所定の情報であるか否かを判定する。
【００３８】
よって、請求項６に記載の発明は、請求項１に記載の発明と同様に作用するので、請求項１記載の発明と同様に、ハッシュ関数を用いて入力した検索キーデータが特定の範囲内のデータであるか否かを判定することができる。
【発明の効果】
【００３９】
以上説明したように、本発明によれば、ハッシュ関数を用いて入力した検索キーデータが特定の範囲内のデータであるか否かを判定することができる、という優れた効果を有する。
【発明を実施するための最良の形態】
【００４０】
以下、図面を参照して、本発明の実施の形態について詳細に説明する。なお、以下では、本発明をルーターによるＮＡＰＴ処理に適用した場合について説明する。
【００４１】
［第１の実施の形態］
図１には、本実施の形態に係るルーターによるＮＡＰＴ処理に関係する部分の概略構成が示されている。
【００４２】
本実施の形態に係るルーター１０は、ＫＥＹマスク回路２０と、アドレス変換部２２と、Ｐｏｉｎｔｅｒ  Ｔａｂｌｅ  ＲＡＭ（Ｈａｓｈ）２４と、Ｐｏｉｎｔｅｒ  Ｔａｂｌｅ  ＲＡＭ（ＥＸＴ）２６と、ＮｅｘＰｏｉｎｔＧｅｎ３０と、ＥｘｔＰｏｉｎｔＧｅｎ３２と、Ｍａｉｎ  Ｔａｂｌｅ  ＲＡＭ３４と、マスクＴａｂｌｅ４０と、データ選択部４２と、を備えている。
【００４３】
ＫＥＹマスク回路２０には、検索キーデータや、検索対象とする範囲を規定する索範囲規定データが、各データの登録、検索、削除を指示する指示情報と共に入力される。なお、本実施の形態に係る検索範囲規定データは、検索キーデータの特定位置が任意のデータであることを示すワイルドカード（本実施の形態では「＊」）とされることによって検索対象とする範囲が規定されている。
【００４４】
ＫＥＹマスク回路２０は、入力された指示情報に応じて、入力された検索キーデータや検索範囲規定データに対してマスク処理等の各種処理等を行い、処理後の検索キーデータや検索範囲規定データを指示情報と共にアドレス変換部２２へ出力する。
【００４５】
アドレス変換部２２は、入力された検索キーデータや検索範囲規定データを所定のハッシュ関数により変換することにより当該検索キーデータや検索範囲規定データに対応付けられたマスクＴａｂｌｅ４０のアドレスを導出する。
【００４６】
Ｐｏｉｎｔｅｒ  Ｔａｂｌｅ  ＲＡＭ（Ｈａｓｈ）２４、及びＰｏｉｎｔｅｒ  Ｔａｂｌｅ  ＲＡＭ（ＥＸＴ）２６には、ハッシュ値に対応させてデータ登録済みのＭａｉｎ  Ｔａｂｌｅ  ＲＡＭ３４の記憶領域のアドレスが記憶される。
【００４７】
ＮｅｘＰｏｉｎｔＧｅｎ３０は、データ未登録のＭａｉｎ  Ｔａｂｌｅ  ＲＡＭ３４の記憶領域のアドレスをアドレス順に生成する。
【００４８】
ＥｘｔＰｏｉｎｔＧｅｎ３２は、データ未登録のＰｏｉｎｔｅｒ  Ｔａｂｌｅ  ＲＡＭ（ＥＸＴ）２６の記憶領域のアドレスをアドレス順に生成する。
【００４９】
Ｍａｉｎ  Ｔａｂｌｅ  ＲＡＭ３４には、検索キーデータや検索範囲規定データをハッシュ関数により変換することにより対応付けられたアドレスに、当該検索キーデータや検索範囲規定データに対応させる情報が記憶される。なお、本実施の形態では、対応させる情報として、変換するＩＰアドレス等のアドレス情報や制御情報などのＮＡＰＴ  Ｄａｔａが記憶される。
【００５０】
マスクＴａｂｌｅ４０には、登録された検索範囲規定データのワイルドカードの位置を示す位置情報が記憶される。
【００５１】
データ選択部４２は、Ｍａｉｎ  Ｔａｂｌｅ  ＲＡＭ３４から検索されたデータが検索キーデータに対応するデータであるか否かの判定を行なう。
【００５２】
次に、本実施の形態に係るルーター１０の基本的な動作について説明する。
【００５３】
最初に図２を参照して、検索キーデータの登録を行う検索キー登録処理の流れを説明する。
【００５４】
検索キーデータの登録を行なう場合、ＫＥＹマスク回路２０には、検索の鍵となる検索キーデータ（例えば、ＩＰアドレス）及び登録を指示する指示情報が入力される。
【００５５】
ＫＥＹマスク回路２０は、検索キーデータ及び登録を指示する指示情報が入力すると、検索キーデータ及び指示情報をそのままアドレス変換部２２へ出力する（ステップＳ１００）。
【００５６】
アドレス変換部２２は、検索キーデータをハッシュ関数を用いて変換し、ハッシュ値を得る（ステップＳ１０２）。
【００５７】
そして、アドレス変換部２２は、ステップＳ１０２により得られたハッシュ値を記憶領域のアドレスとしてＰｏｉｎｔｅｒ  Ｔａｂｌｅ  ＲＡＭ（Ｈａｓｈ）２４を読み出す（ステップＳ１０４）。
【００５８】
アドレス変換部２２は、読み出したアドレスのデータが空を示であるか否か判定し（ステップＳ１０６）、読み出したアドレスのデータが空ならばＮｅｘＰｏｉｎｔＧｅｎ３０の発生する値を当該読み出したアドレスに記憶させる（ステップＳ１０８）。一方、読み出したアドレスのデータが空で無いならばＥｘｔＰｏｉｎｔＧｅｎ３２の発生する値をＰｏｉｎｔｅｒ  Ｔａｂｌｅ  ＲＡＭ（ＥＸＴ）２６の記憶領域のアドレスとしてＮｅｘＰｏｉｎｔＧｅｎ３０の発生する値をＰｏｉｎｔｅｒ  Ｔａｂｌｅ  ＲＡＭ（ＥＸＴ）２６に入力する（ステップＳ１１０）。ＥｘｔＰｏｉｎｔＧｅｎ３２は、発生する値を記憶領域のアドレス順に次のデータ未登録領域のアドレスとする（例えば、発生する値（Ｐｏｉｎｔｅｒ）に１加算する。）。
【００５９】
データ選択部４２は、ＮｅｘＰｏｉｎｔＧｅｎ３０の発生する値をＭａｉｎ  Ｔａｂｌｅ  ＲＡＭ３４のアドレスとしてＮＡＰＴ  Ｄａｔａ及び検索キーデータをＭａｉｎ  Ｔａｂｌｅ  ＲＡＭ３４に記憶させる（ステップＳ１１２）。ＮｅｘＰｏｉｎｔＧｅｎ３０は、発生する値を記憶領域のアドレス順に次のデータ未登録領域のアドレスとする（例えば、発生する値（Ｐｏｉｎｔｅｒ）に１加算する。）。
【００６０】
これにより、Ｍａｉｎ  Ｔａｂｌｅ  ＲＡＭ３４には、検索キーデータをハッシュ関数を用いて変換することにより対応付けられたアドレスに、変換するＩＰアドレスなどのＮＡＰＴ  Ｄａｔａ及び検索キーデータが記憶される。
【００６１】
次に図３を参照して、検索範囲規定データの登録を行う検索範囲登録処理の流れを説明する。
【００６２】
検索範囲規定データを登録を行なう場合、ＫＥＹマスク回路２０には、検索範囲規定データ及び登録を指示する指示情報が入力される。
【００６３】
ＫＥＹマスク回路２０は、検索範囲規定データのワイルドカード部分の位置を特定し、特定したワイルドカード部分の位置を示す位置情報をマスクＴａｂｌｅ４０に登録する（ステップＳ２００）。
【００６４】
また、ＫＥＹマスク回路２０は、検索範囲規定データのワイルドカード部分のデータを予め定められた固定値（例えば“０”）に変換し、変換した検索範囲規定データ及び指示情報をアドレス変換部２２へ出力する（ステップＳ２０１）。
【００６５】
アドレス変換部２２は、検索範囲規定データをハッシュ関数を用いて変換し、ハッシュ値を得る（ステップＳ２０２）。
【００６６】
そして、アドレス変換部２２は、ステップＳ２０２により得られたハッシュ値を記憶領域のアドレスとしてＰｏｉｎｔｅｒ  Ｔａｂｌｅ  ＲＡＭ（Ｈａｓｈ）２４を読み出す（ステップＳ２０４）。
【００６７】
アドレス変換部２２は、読み出したアドレスのデータが空を示であるか否か判定し（ステップＳ２０６）、読み出したアドレスのデータが空ならばＮｅｘＰｏｉｎｔＧｅｎ３０の発生する値を読み出したアドレスに入れる（ステップＳ２０８）。一方、読み出したアドレスのデータが空で無いならばＥｘｔＰｏｉｎｔＧｅｎ３２の発生する値をＰｏｉｎｔｅｒ  Ｔａｂｌｅ  ＲＡＭ（ＥＸＴ）２６の記憶領域のアドレスとしてＮｅｘＰｏｉｎｔＧｅｎ３０の発生する値をＰｏｉｎｔｅｒ  Ｔａｂｌｅ  ＲＡＭ（ＥＸＴ）２６に入力する（ステップＳ２１０）。ＥｘｔＰｏｉｎｔＧｅｎ３２は、発生する値を記憶領域のアドレス順に次のデータ未登録領域のアドレスとする（例えば、発生する値（Ｐｏｉｎｔｅｒ）に１加算する。）。
【００６８】
データ選択部４２は、ＮｅｘＰｏｉｎｔＧｅｎ３０の発生する値をＭａｉｎ  Ｔａｂｌｅ  ＲＡＭ３４のアドレスとして制御情報及び検索範囲規定データをＭａｉｎ  Ｔａｂｌｅ  ＲＡＭ３４に記憶させる（ステップＳ２１２）。ＮｅｘＰｏｉｎｔＧｅｎ３０は、発生する値を記憶領域のアドレス順に次のデータ未登録領域のアドレスとする（例えば、発生する値（Ｐｏｉｎｔｅｒ）に１加算する。）。
【００６９】
これにより、Ｍａｉｎ  Ｔａｂｌｅ  ＲＡＭ３４には、検索範囲規定データのワイルドカード部分のデータを固定値でマスクしてハッシュ関数を用いて変換することにより対応付けられたアドレスに、制御情報及び検索範囲規定データが記憶される。
【００７０】
ここで、具体例をあげて動作を説明する。
【００７１】
なお、説明を簡易にする為、検索範囲規定データを８ｂｉｔ、対応させる対応情報を８ｂｉｔとする。
（１）データセット動作
検索範囲規定データ＝０ｂ１０００＊＊＊＊，対応情報＝０ｘ０１
検索範囲規定データ＝０ｂ１１０１１＊＊＊，対応情報＝０ｘ０２
検索範囲規定データ＝０ｂ１０１０＊＊＊＊，対応情報＝０ｘ０３
注意：＊はワイルドカード部分
上記のような検索範囲規定データをセットするとマスクＴａｂｌｅ４０には図４に示すような検索範囲規定データのワイルドカード部分のビット位置を示した位置情報が記憶される。
【００７２】
本実施の形態に係る位置情報は、検索範囲規定データのワイルドカード部分のビット位置を‘１’とし、ワイルドカード以外のビット位置を‘０’としてワイルドカード部分のビット位置を示してる。
【００７３】
また、本実施の形態に係るマスクＴａｂｌｅ４０には、データ数領域が設けられており、データ数領域には、ワイルドカード部分を示す位置が同一の検索範囲規定データが複数登録された場合、登録された登録数が記憶される。
【００７４】
本実施の形態に係るＫＥＹマスク回路２０は、ワイルドカード部分の位置を示す位置情報をマスクＴａｂｌｅ４０に登録する際に、当該位置情報が既にマスクＴａｂｌｅ４０に存在する場合、当該位置情報に対応するデータ数領域の値を１カウントアップする。
【００７５】
次に図５を参照して、検索キーデータによる検索を行なう際の検索処理の流れを説明する。
【００７６】
検索キーデータによる検索を行なう場合、ＫＥＹマスク回路２０には、検索キーデータ及び検索を指示する指示情報が入力される。
【００７７】
ＫＥＹマスク回路２０では、検索キーデータ及び指示情報をそのままアドレス変換部２２へ出力すると共に、マスクＴａｂｌｅ４０から各位置情報をそれぞれ読み出し、各位置情報毎に、位置情報に基づいて検索キーデータの位置情報により示されるビット位置のデータを予め定められた固定値（例えば“０”）に変換した各検索キーデータ（以下、「変換検索キーデータ」という。）をアドレス変換部２２へ出力する（ステップＳ３００）。
【００７８】
アドレス変換部２２は、検索キーデータ及び変換検索キーデータをそれぞれハッシュ関数を用いて変換し、それぞれハッシュ値を得る（ステップＳ３０２）。
【００７９】
そして、アドレス変換部２２は、ステップＳ３０２により得られた各ハッシュ値をＰｏｉｎｔｅｒ  Ｔａｂｌｅ  ＲＡＭ（Ｈａｓｈ）２４のアドレスとしてＰｏｉｎｔｅｒ  Ｔａｂｌｅ  ＲＡＭ（Ｈａｓｈ）２４を読み出す（ステップＳ３０４）。
【００８０】
そして、読み出された値をＭａｉｎ  Ｔａｂｌｅ  ＲＡＭ３４のアドレスとしてＭａｉｎ  Ｔａｂｌｅ  ＲＡＭ３４を読み出す。（ステップＳ３０６）。
【００８１】
データ選択部４２は、ステップＳ３０６により読み出された情報が検索キーデータに対応するＮＡＰＴ  Ｄａｔａや制御情報か否か判定し（ステップＳ３０８）、対応するならばＮＡＰＴ  Ｄａｔａや制御情報を外部へ出力して処理を終了する。一方、検索キーデータに対応するＮＡＰＴ  Ｄａｔａや制御情報でないならばアドレス０から順にＰｏｉｎｔｅｒ  Ｔａｂｌｅ  ＲＡＭ（ＥＸＴ）２６を読み出した（ステップＳ３１０）うえで上記Ｓ３０６の処理を行う。
【００８２】
これにより、検索対象とする検索キーデータがＭａｉｎ  Ｔａｂｌｅ  ＲＡＭ３４に登録されている場合、Ｍａｉｎ  Ｔａｂｌｅ  ＲＡＭ３４から、検索対象とする検索キーデータをハッシュ関数を用いて変換することにより対応付けられたアドレスに記憶された情報が読み出される。
【００８３】
また、検索範囲規定データが登録されている場合、検索対象とする検索キーデータが登録された検索範囲規定データにより指定された範囲であるか否かを判定できる。
【００８４】
ここで、具体例をあげて動作を説明する。
【００８５】
例えば、マスクＴａｂｌｅ４０には図４に示すような状態であり、検索対象として検索キーデータ＝１０００１０１０を検索すると
ＫＥＹマスク回路２０では検索キーデータ＝１０００１０１０とマスクＴａｂｌｅ４０のＮＯ．０の値＝００００１１１１から変換検索キーデータ＝１０００００００が生成された上でハッシュ関数を用いて変換される。
【００８６】
この結果、データ選択部４２には、変換検索キーデータ＝１０００００００とＤａｔａ＝０ｘ０１が読み出される。
【００８７】
このデータは検索対象として検索キーデータ＝１０００１０１０とマスクＴａｂｌｅ４０  ＮＯ．０の値＝００００１１１１から一致していると判断され、一致している場合、指定された範囲内データであると特定できる。その後、マスクＴａｂｌｅ４０  ＮＯ．１，に対しても実施される。
【００８８】
これらの動作によりワイルドカードを持つデータの検索が実現できる。
【００８９】
次に図６を参照して、検索キーデータの削除を行う検索キー削除処理の流れを説明する。
【００９０】
検索キーデータを削除する場合、ＫＥＹマスク回路２０には、検索キーデータ及び削除を指示する指示情報が入力される。
【００９１】
ＫＥＹマスク回路２０では検索キーデータ及び削除を指示する指示情報が入力すると、検索キーデータ及び指示情報をそのままアドレス変換部２２へ出力する（ステップＳ４００）。
【００９２】
アドレス変換部２２は、検索キーデータをハッシュ関数を用いて変換し、ハッシュ値を得る（ステップＳ４０２）。
【００９３】
そして、アドレス変換部２２は、ステップＳ４０２により得られた各ハッシュ値をＰｏｉｎｔｅｒ  Ｔａｂｌｅ  ＲＡＭ（Ｈａｓｈ）２４のアドレスとしてＰｏｉｎｔｅｒ  Ｔａｂｌｅ  ＲＡＭ（Ｈａｓｈ）２４を読み出す（ステップＳ４０４）。
【００９４】
そして、読み出された値をＭａｉｎ  Ｔａｂｌｅ  ＲＡＭ３４のアドレスとしてＭａｉｎ  Ｔａｂｌｅ  ＲＡＭ３４を読み出す。（ステップＳ４０６）。
【００９５】
データ選択部４２は、ステップＳ４０６により読み出された情報が検索キーデータに対応するＮＡＰＴ  Ｄａｔａや制御情報か否か判定し（ステップＳ４０８）、対応するならばそのＰｏｉｎｔｅｒ  Ｔａｂｌｅ  ＲＡＭ（Ｈａｓｈ）２４のデータ及びＭａｉｎ  Ｔａｂｌｅ  ＲＡＭ３４のデータを削除（ステップＳ４１０）して終了する。一方、検索キーデータに対応するＮＡＰＴ  Ｄａｔａや制御情報でないならばアドレス０から順にＰｏｉｎｔｅｒ  Ｔａｂｌｅ  ＲＡＭ（ＥＸＴ）２６を読み出した（ステップＳ４１２）うえで上記Ｓ４０６の処理を行う。
【００９６】
次に図７を参照して、検索範囲規定データの削除を行う検索範囲削除処理の流れを説明する。
【００９７】
検索範囲規定データを削除する場合、ＫＥＹマスク回路２０には、検索範囲規定データ及び削除を指示する指示情報が入力される。
【００９８】
ＫＥＹマスク回路２０は、検索範囲規定データのワイルドカード部分の位置を特定し、特定したワイルドカード部分の位置を示す位置情報がマスクＴａｂｌｅ４０に登録されているか検索を行う。そして、ＫＥＹマスク回路２０は、マスクＴａｂｌｅ４０に位置情報が登録されており、位置情報に対応するデータ数領域の値が‘１’以下の場合、当該位置情報のレコードを削除し、データ数領域の値が‘１’よりも大きい場合、データ数領域の値から１減算する（ステップＳ５００）。
【００９９】
また、ＫＥＹマスク回路２０は、検索範囲規定データのワイルドカード部分のデータを予め定められた固定値（例えば“０”）に変換し、変換した検索範囲規定データ及び指示情報をアドレス変換部２２へ出力する（ステップＳ５０１）。
【０１００】
アドレス変換部２２は、検索範囲規定データをハッシュ関数を用いて変換し、ハッシュ値を得る（ステップＳ５０２）。
【０１０１】
そして、アドレス変換部２２は、ステップＳ５０２により得られたハッシュ値を記憶領域のアドレスとしてＰｏｉｎｔｅｒ  Ｔａｂｌｅ  ＲＡＭ（Ｈａｓｈ）２４を読み出す（ステップＳ５０４）。
【０１０２】
そして、読み出された値をＭａｉｎ  Ｔａｂｌｅ  ＲＡＭ３４のアドレスとしてＭａｉｎ  Ｔａｂｌｅ  ＲＡＭ３４を読み出す。（ステップＳ５０６）。
【０１０３】
データ選択部４２は、ステップＳ５０６により読み出された情報が検索範囲規定データに対応するＮＡＰＴ  Ｄａｔａや制御情報か否か判定し（ステップＳ５０８）、対応するならばそのＰｏｉｎｔｅｒ  Ｔａｂｌｅ  ＲＡＭ（Ｈａｓｈ）２４のデータ及びＭａｉｎ  Ｔａｂｌｅ  ＲＡＭ３４のデータを削除（ステップＳ５１０）して終了する。一方、検索キーデータに対応するＮＡＰＴ  Ｄａｔａや制御情報でないならばアドレス０から順にＰｏｉｎｔｅｒ  Ｔａｂｌｅ  ＲＡＭ（ＥＸＴ）２６を読み出した（ステップＳ５１２）うえで上記Ｓ５０６の処理を行う。
【０１０４】
ここで、具体例をあげて動作を説明する。
【０１０５】
例えば、図４に示したマスクＴａｂｌｅ４０から検索範囲規定データ＝０ｂ１０００＊＊＊＊のデータを削除した場合、マスクＴａｂｌｅ４０で同じマスクパターンを持つデータの個数を１減少させる。この処理実行後のマスクＴａｂｌｅ４０は図８に示すようになる。
【０１０６】
以上のように、本実施の形態によれば、検索範囲規定データの特定位置のデータを予め定められた固定値に置き換え、所定のハッシュ関数により変換することにより対応付けられたＭａｉｎ  Ｔａｂｌｅ  ＲＡＭ３４のアドレスに、所定の情報を記憶させておき、検索対象とする検索キーデータが入力した際に、当該検索キーデータの位置情報により示される特定位置のデータを固定値に置き換えて、ハッシュ関数により変換することにより対応付けられたＭａｉｎ  Ｔａｂｌｅ  ＲＡＭ３４のアドレスに記憶された情報を読み出し、読み出された情報が所定の情報であるか否かを判定することにより、ハッシュ関数を用いて入力した検索キーデータが特定の範囲内のデータであるか否かを判定することができる。
【０１０７】
また、本実施の形態によれば、検索キーデータの範囲検索と対応データの検索を平行して行なうことができる。
【０１０８】
また、本実施の形態によれば、検索範囲規定データのワイルドカード部分が同一の場合、ワイルドカード部分の位置を示す位置情報が１つのみ記憶されるため、使用される記憶領域を少なく抑えることができる。また、上述した検索処理では、各位置情報に対応して変換検索キーデータが１ずつ生成されるため、ワイルドカード部分が同一の場合に位置情報を１つのみ記憶させることにより、範囲検索の検索速度が向上する。
【０１０９】
さらに、本実施の形態によれば、位置情報が、特定位置をビット位置により示した情報であるため、ワイルドカードとして、例えば、１００＊＊０＊０、などと連続しない複数の位置を指定することができる。
【０１１０】
［第２の実施の形態］
第２の実施の形態に係るルーター１０は、検索範囲規定データとして検索キーデータとワイルドカード部分の最下位ビットからのビット数が入力するものとされている。
【０１１１】
第２の実施の形態に係るルーター１０の構成は上記第１の実施の形態（図１参照）と同一であるので、ここでの説明は省略する。
【０１１２】
次に図９を参照して、検索範囲規定データの登録を行う検索範囲登録処理の流れを説明する。なお、同図における図３と同一処理については同一の符号を付して、ここでの説明は省略する。
【０１１３】
検索範囲規定データを登録する場合、ＫＥＹマスク回路２０には、検索範囲規定データとして検索キーデータとワイルドカード部分の最下位ビットからのビット数を示す情報、及び登録を指示する指示情報が入力される。
【０１１４】
ＫＥＹマスク回路２０は、ワイルドカード部分の最下位ビットからのビット数を位置情報としてマスクＴａｂｌｅ４０に登録する（ステップＳ２００Ａ）。
【０１１５】
また、ＫＥＹマスク回路２０は、最下位ビットからのビット数に基づいて検索範囲規定データのワイルドカード部分のデータを予め定められた固定値（例えば“０”）に変換し、変換した検索キーデータをアドレス変換部２２へ出力する（ステップＳ２０１Ａ）。
【０１１６】
ここで、具体例をあげて動作を説明する。
（１）データセット動作
検索キーデータ＝０ｂ１０００１１１１、ワイルドカード部分のビット数＝４、対応情報＝０ｘ０１
検索キーデータ＝０ｂ１１０１１０００、ワイルドカード部分のビット数＝３、対応情報＝０ｘ０２
検索キーデータ＝０ｂ１０１０００００、ワイルドカード部分のビット数＝４、対応情報＝０ｘ０３
上記のような検索範囲規定データをセットするとマスクＴａｂｌｅ４０には図１０に示すようなワイルドカード部分の最下位ビットからのビット数が位置情報として記憶される。
【０１１７】
次に図１１を参照して、検索キーデータによる検索を行なう際の検索処理の流れを説明する。なお、同図における図５と同一処理については同一の符号を付して、ここでの説明は省略する。
【０１１８】
検索キーデータによる検索を行なう場合、ＫＥＹマスク回路２０には、検索キーデータ及び検索を指示する指示情報が入力される。
【０１１９】
ＫＥＹマスク回路２０では、検索キーデータ及び指示情報をそのままアドレス変換部２２へ出力すると共に、マスクＴａｂｌｅ４０から各位置情報をそれぞれ読み出し、各位置情報毎に、位置情報に基づいて検索キーデータの最下位ビットから位置情報により示されるビット数のデータを予め定められた固定値（例えば“０”）に変換した変換検索キーデータを生成し、各変換検索キーデータをアドレス変換部２２へ出力する（ステップＳ３００Ａ）。
【０１２０】
ここで、具体例をあげて動作を説明する。
【０１２１】
例えば、マスクＴａｂｌｅ４０には図１０に示すような状態であり、検索キーデータ＝１０００１０１０を検索すると、ＫＥＹマスク回路２０では、マスクＴａｂｌｅ４０のＮＯ．０の値＝４からマスク値＝００００１１１１を発生する。
【０１２２】
そして、ＫＥＹマスク回路２０ではｋｅｙ＝１０００１０１０とマスク値＝００００１１１１から変換検索キーデータ＝１０００００００を生成して検索を行う。
【０１２３】
この結果、データ選択部４２には、変換検索キーデータ＝１０００００００とＤａｔａ＝０ｘ０１が読み出される。
【０１２４】
このデータはｋｅｙ＝１０００１０１０とマスク値＝００００１１１１から一致していると判断される。その後、Ｔａｂｌｅ  ＮＯ．１、に対しても実施される。
【０１２５】
これらの動作によりワイルドカードを持つデータの検索が実現できる。
【０１２６】
次に図１２を参照して、検索範囲規定データの削除を行う検索キー削除処理の流れを説明する。なお、同図における図７と同一処理については同一の符号を付して、ここでの説明は省略する。
【０１２７】
検索範囲規定データを削除する場合、ＫＥＹマスク回路２０には、検索範囲規定データとして検索キーデータとワイルドカード部分の最下位ビットからのビット数を示す情報、及び削除を指示する指示情報が入力される。
【０１２８】
ＫＥＹマスク回路２０は、入力する検索キーデータ及びワイルドカード部分の最下位ビットからのビット数のうち、ワイルドカード部分の最下位ビットからのビット数がマスクＴａｂｌｅ４０に位置情報として登録されているか検索を行う。そして、ＫＥＹマスク回路２０は、マスクＴａｂｌｅ４０に位置情報が登録されており、位置情報に対応するデータ数領域の値が‘１’以下の場合、当該位置情報のレコードを削除し、データ数領域の値が‘１’よりも大きい場合、データ数領域の値から１減算する（ステップＳ５００Ａ）。
【０１２９】
また、ＫＥＹマスク回路２０は、最下位ビットからのビット数に基づいて検索キーデータのワイルドカード部分のデータを予め定められた固定値（例えば“０”）に変換し、変換した検索キーデータをアドレス変換部２２へ出力する（ステップＳ５０１Ａ）。
【０１３０】
ここで、具体例をあげて動作を説明する。
【０１３１】
例えば、図１０に示したマスクＴａｂｌｅ４０から検索範囲規定データとして入力された検索キーデータ＝０ｂ１０００１１１１、ビット数＝４のデータを削除する時、マスクＴａｂｌｅで同じマスクｂｉｔ位置を持つデータの個数を１減少させる。この処理実行後のマスクＴａｂｌｅは図１３に示すようになる。
【０１３２】
以上のように、本実施の形態によれば、位置情報が、特定位置を最下位ビットからのビット数により示した情報であるため、特定位置を示す情報のデータ量を少なく抑えることができる。
【０１３３】
なお、本実施の形態では、Ｐｏｉｎｔｅｒ  Ｔａｂｌｅ  ＲＡＭ（Ｈａｓｈ）２４とＰｏｉｎｔｅｒ  Ｔａｂｌｅ  ＲＡＭ（ＥＸＴ）２６の２つのＲＡＭを用いてハッシュ値に対応させてアドレスを記憶する場合について説明したが、本発明はこれに限定されるものではなく、例えば、背景技術において説明したように、１つのＰｏｉｎｔｅｒ  Ｔａｂｌｅ  ＲＡＭを用いてハッシュ値が重複した場合、ハッシュ値に１加算する形態の情報検索装置に適用してもよい。
【０１３４】
また、本実施の形態では、ルーター１０に適用した場合について説明したが、本発明はこれに限定されるものではない。
【０１３５】
その他、本実施の形態で説明したルーター１０の構成（図１参照。）は一例であり、本発明の主旨を逸脱しない範囲内において適宜変更可能であることは言うまでもない。
【０１３６】
また、本実施の形態で説明した各処理（図２、図３、図５〜図７、図９、図１１、図１２）の流れは一例であり、本発明の主旨を逸脱しない範囲内において適宜変更可能であることは言うまでもない。
【図面の簡単な説明】
【０１３７】
【図１】実施の形態に係るルーターの概略構成を示すブロック図である。
【図２】実施の形態に係る検索キー登録処理の流れを示すフローチャートである。
【図３】第１の実施の形態に係る検索範囲登録処理の流れを示すフローチャートである。
【図４】第１の実施の形態に係るマスクＴａｂｌｅに記憶されたデータのデータ構造の一例を示す図である。
【図５】第１の実施の形態に係る検索処理の流れを示すフローチャートである。
【図６】実施の形態に係る検索キー削除処理の流れを示すフローチャートである。
【図７】第１の実施の形態に係る検索範囲削除処理の流れを示すフローチャートである。
【図８】第１の実施の形態に係るマスクＴａｂｌｅに記憶されたデータのデータ構造の一例を示す図である。
【図９】第２の実施の形態に係る検索範囲登録処理の流れを示すフローチャートである。
【図１０】第２の実施の形態に係るマスクＴａｂｌｅに記憶されたデータのデータ構造の一例を示す図である。
【図１１】第２の実施の形態に係る検索処理の流れを示すフローチャートである。
【図１２】第２の実施の形態に係る検索範囲削除処理の流れを示すフローチャートである。
【図１３】第２の実施の形態に係るマスクＴａｂｌｅに記憶されたデータのデータ構造の一例を示す図である。
【図１４】従来のパケットデータの中継を行なうルーターを示す模式図である。
【図１５】実施の形態に係るルーターの概略構成を示すブロック図である。
【符号の説明】
【０１３８】
３４  Ｍａｉｎ  Ｔａｂｌｅ  ＲＡＭ（第１記憶手段）
４０  マスクＴａｂｌｅ（第２記憶手段）
４２  データ選択部（読出手段、判定手段）
【図１】
0004369505.tif 000002
【図２】
0004369505.tif 000003
【図３】
0004369505.tif 000004
【図４】
0004369505.tif 000005
【図５】
0004369505.tif 000006
【図６】
0004369505.tif 000007
【図７】
0004369505.tif 000008
【図８】
0004369505.tif 000009
【図９】
0004369505.tif 000010
【図１０】
0004369505.tif 000011
【図１１】
0004369505.tif 000012
【図１２】
0004369505.tif 000013
【図１３】
0004369505.tif 000014
【図１４】
0004369505.tif 000015
【図１５】
0004369505.tif 000016