(57)【特許請求の範囲】
【請求項１】
登録パターンとして入力された文字列を分割することによって第１文字列と第２文字列とからなる組を１つ以上生成し、
前記第１文字列に対して複数のハッシュ関数を適用することによって複数のハッシュ値を求め、前記第２文字列の長さに対応するオフセットを決定し、前記複数のハッシュ値と前記オフセットとに所定の演算を施して複数の数値を算出し、
前記算出した複数の数値を、数値の配列であるベクトルの複数のアドレスとし、前記複数のアドレスに対応する前記ベクトル中の数値それぞれを、初期値と異なる数値に更新することを特徴とする検索装置。
【請求項２】
文字列を分割するための分割位置を複数格納するリストの中から、前記登録パターンの長さを超えない最大の分割位置を１つ選択し、
前記選択した分割位置を境として、前記登録パターンを、第１文字列と第２文字列とに分割することを特徴とする請求項１記載の検索装置。
【請求項３】
前記第１文字列は、所定の文字数の倍数の長さを持つことを特徴とする請求項１記載の検索装置。
【請求項４】
前記第２文字列の長さに対応するオフセットは、前記第２文字列の長さに等しいことを特徴とする請求項１記載の検索装置。
【請求項５】
文字列の長さとオフセットとの関係が記載された表を参照して、前記第２文字列の長さに対応するオフセットを求めることを特徴とする請求項１記載の検索装置。
【請求項６】
検索キーとして入力された文字列を分割することによって、第１文字列と第２文字列とからなる組を１つ以上生成し、
前記第１文字列に対して複数のハッシュ関数を適用して複数のハッシュ値を求め、前記複数のハッシュ値とオフセットとに所定の演算を施して複数の数値を算出し、
前記算出した複数の数値を、数値の配列であるベクトルの複数のアドレスとし、前記複数のアドレスに対応する前記ベクトル中の数値の全てが初期値と異なっている場合、前記オフセットに対応する長さと前記第１文字列の長さとの和を一致候補の長さとして算出し、
前記検索キーの先頭もしくは末尾から、前記一致候補の長さに等しい長さの部分文字列を取り出し、前記取り出した部分文字列が登録済みであるかを判定することを特徴とする検索装置。
【請求項７】
文字列を分割するための分割位置を複数格納するリストの中から、前記検索キーの長さを超えない分割位置を降順に選択し、前記選択した分割位置を境にして前記検索キーを、前記第１文字列と前記第２文字列とに分割することを特徴とする請求項６記載の検索装置。
【請求項８】
前記第１文字列は所定の文字数の倍数の長さを有し、前記第１文字列の長さが昇順になるように前記検索キーを第１文字列と第２文字列とに分割することを特徴とする請求項６記載の検索装置。
【請求項９】
前記オフセットに対応する長さは、前記オフセットに等しいことを特徴とする請求項６記載の検索装置。
【請求項１０】
文字列の長さとオフセットとの関係が記載された表を参照して、前記オフセットに対応する長さを求めることを特徴とする請求項６記載の検索装置。
【請求項１１】
文字列である登録パターンと検索キーとに基づいて、前方最長一致検索を行う検索装置であって、
文字列を分割するための分割位置を複数格納する分割位置リストと、
数値の配列であるベクトルと、
前記登録パターンを格納するハッシュ表と、
前記分割位置リストの中から、入力された登録パターンの長さを超えない最大の分割位置を１つ選択し、前記選択した分割位置を境にして前記入力された登録パターンからプレフィックスを抽出するとともに、前記入力された登録パターンの長さから前記プレフィックスの長さを減算してサフィックス長を求める第１プレフィックス抽出部と、
前記第１プレフィックス抽出部で抽出されたプレフィックスに対して複数のハッシュ関数を適用し、複数のハッシュ値を算出する第１ハッシュ演算部と、
前記第１ハッシュ演算部で算出された複数のハッシュ値と前記サフィックス長とを加算して複数の数値を算出し、前記算出した複数の数値を前記ベクトルの複数のアドレスとし、前記複数のアドレスに対応する前記ベクトル中の数値それぞれを、初期値と異なる数値に更新するベクトル更新部と、
前記入力された登録パターンを前記ハッシュ表に格納するハッシュ表登録部と、
前記分割位置リストの中から、入力された検索キーの長さを超えない分割位置を降順に選択し、前記選択した分割位置を境にして前記入力された検索キーから１つ以上のプレフィックスを抽出する第２プレフィックス抽出部と、
前記第２プレフィックス抽出部で抽出されたプレフィックスに対して、前記第１ハッシュ演算部で用いたものと同じ複数のハッシュ関数を適用し、複数のハッシュ値を算出する第２ハッシュ演算部と、
前記第２ハッシュ演算部で算出された複数のハッシュ値とオフセットとを加算して複数の数値を算出し、前記算出した複数の数値を前記ベクトルの複数のアドレスとし、前記複数のアドレスに対応する前記ベクトル中の数値の全てが初期値と異なっている場合、前記第２プレフィックス抽出部で抽出されたプレフィックスの長さと前記オフセットとの和を一致候補の長さとして算出するパターン長推定部と、
前記パターン長推定部で算出された一致候補の長さに等しい文字列を、前記入力された検索キーの先頭から取り出し、前記取り出した文字列に完全一致する登録パターンを前記ハッシュ表の中から検索するハッシュ表検索部と、
を有することを特徴とする検索装置。
【請求項１２】
文字列である登録パターンと検索キーとに基づいて、前方最長一致検索を行う検索装置であって、
数値の配列であるベクトルと、
前記登録パターンを格納するハッシュ表と、
入力された登録パターンから、所定の文字数の倍数の長さを持つプレフィックスを１つ以上抽出するとともに、前記入力された登録パターンの長さから前記プレフィックスの長さを減算してサフィックス長を求める第１プレフィックス抽出部と、
前記第１プレフィックス抽出部で抽出されたプレフィックスに対して複数のハッシュ関数を適用し、複数のハッシュ値を算出する第１ハッシュ演算部と、
長さとオフセットの関係が記載された対応表と、
前記長さとオフセットの関係が記載された対応表を参照して、前記サフィックス長から第１オフセットを決定するオフセット決定部と、
前記第１ハッシュ演算部で算出された複数のハッシュ値と、前記オフセット決定部で決定された第１オフセットとに所定の演算を施して複数の数値を算出し、前記算出した複数の数値を前記ベクトルの複数のアドレスとし、前記複数のアドレスに対応する前記ベクトル中の数値それぞれを、初期値と異なる数値に更新するベクトル更新部と、
前記入力された登録パターンを前記ハッシュ表に格納するハッシュ表登録部と、
入力された検索キーから、前記所定の文字数の倍数の長さを持つプレフィックスを短いものから順に抽出する第２プレフィックス抽出部と、
前記第２プレフィックス抽出部で抽出されたプレフィックスに対して、前記第１ハッシュ演算部で用いたものと同じ複数のハッシュ関数を適用し、複数のハッシュ値を算出する第２ハッシュ演算部と、
前記長さとオフセットの関係が記載された対応表で定義される第２オフセットそれぞれについて、前記第２ハッシュ演算部で算出された複数のハッシュ値と前記第２オフセットとに所定の演算を施して複数の数値を算出し、前記算出した複数の数値を前記ベクトルの複数のアドレスとし、前記複数のアドレスに対応する前記ベクトル中の数値の全てが初期値と異なっている場合、前記第２プレフィックス抽出部で抽出されたプレフィックスの長さと前記第２オフセットに対応する長さとの和を一致候補の長さとして算出するパターン長推定部と、
前記パターン長推定部で算出された一致候補の長さに等しい文字列を、前記入力された検索キーの先頭から取り出し、前記取り出した文字列に完全一致する登録パターンを前記ハッシュ表の中から検索するハッシュ表検索部と、
を有することを特徴とする検索装置。
【請求項１３】
文字列である登録パターンと検索キーとに基づいて、後方最長一致検索を行う検索装置であって、
文字列を分割するための分割位置を複数格納する分割位置リストと、
数値の配列であるベクトルと、
前記登録パターンを格納するハッシュ表と、
前記分割位置リストの中から、入力された登録パターンの長さを超えない最大の分割位置を１つ選択し、前記選択した分割位置を境にして前記入力された登録パターンからサフィックスを抽出するとともに、前記入力された登録パターンの長さから前記サフィックスの長さを減算してプレフィックス長を求める第１サフィックス抽出部と、
前記第１サフィックス抽出部で抽出されたサフィックスに対して複数のハッシュ関数を適用し、複数のハッシュ値を算出する第１ハッシュ演算部と、
前記第１ハッシュ演算部で算出された複数のハッシュ値と前記プレフィックス長とを加算して複数の数値を算出し、前記算出した複数の数値を前記ベクトルの複数のアドレスとし、前記複数のアドレスに対応する前記ベクトル中の数値それぞれを、初期値と異なる数値に更新するベクトル更新部と、
前記入力された登録パターンを前記ハッシュ表に格納するハッシュ表登録部と、
前記分割位置リストの中から、入力された検索キーの長さを超えない分割位置を降順に選択し、前記選択した分割位置を境にして前記入力された検索キーから１つ以上のサフィックスを抽出する第２サフィックス抽出部と、
前記第２サフィックス抽出部で抽出されたサフィックスに対して、前記第１ハッシュ演算部で用いたものと同じ複数のハッシュ関数を適用し、複数のハッシュ値を算出する第２ハッシュ演算部と、
前記第２ハッシュ演算部で算出された複数のハッシュ値とオフセットとを加算して複数の数値を算出し、前記算出した複数の数値を前記ベクトルの複数のアドレスとし、前記複数のアドレスに対応する前記ベクトル中の数値の全てが初期値と異なっている場合、前記第２サフィックス抽出部で抽出されたサフィックスの長さと前記オフセットとの和を一致候補の長さとして算出するパターン長推定部と、
前記パターン長推定部で算出された一致候補の長さに等しい文字列を、前記入力された検索キーの末尾から取り出し、前記取り出した文字列に完全一致する登録パターンを前記ハッシュ表の中から検索するハッシュ表検索部と、
を有することを特徴とする検索装置。
【請求項１４】
文字列である登録パターンと検索キーとに基づいて、後方最長一致検索を行う検索装置であって、
数値の配列であるベクトルと、
前記登録パターンを格納するハッシュ表と、
入力された登録パターンから、所定の文字数の倍数の長さを持つサフィックスを１つ以上抽出するとともに、前記入力された登録パターンの長さから前記サフィックスの長さを減算してプレフィックス長を求める第１サフィックス抽出部と、
前記第１サフィックス抽出部で抽出されたサフィックスに対して複数のハッシュ関数を適用し、複数のハッシュ値を算出する第１ハッシュ演算部と、
長さとオフセットの関係が記載された対応表と、
前記長さとオフセットの関係が記載された対応表を参照して、前記プレフィックス長から第１オフセットを決定するオフセット決定部と、
前記第１ハッシュ演算部で算出された複数のハッシュ値と、前記オフセット決定部で決定された第１オフセットとに所定の演算を施して複数の数値を算出し、前記算出した複数の数値を前記ベクトルの複数のアドレスとし、前記複数のアドレスに対応する前記ベクトル中の数値それぞれを、初期値と異なる数値に更新するベクトル更新部と、
前記入力された登録パターンを前記ハッシュ表に格納するハッシュ表登録部と、
入力された検索キーから、前記所定の文字数の倍数の長さを持つサフィックスを短いものから順に抽出する第２サフィックス抽出部と、
前記第２サフィックス抽出部で抽出されたサフィックスに対して、前記第１ハッシュ演算部で用いたものと同じ複数のハッシュ関数を適用し、複数のハッシュ値を算出する第２ハッシュ演算部と、
前記長さとオフセットの関係が記載された対応表で定義される第２オフセットそれぞれについて、前記第２ハッシュ演算部で算出された複数のハッシュ値と前記第２オフセットとに所定の演算を施して複数の数値を算出し、前記算出した複数の数値を前記ベクトルの複数のアドレスとし、前記複数のアドレスに対応する前記ベクトル中の数値の全てが初期値と異なっている場合、前記第２サフィックス抽出部で抽出されたサフィックスの長さと前記第２オフセットに対応する長さとの和を一致候補の長さとして算出するパターン長推定部と、
前記パターン長推定部で算出された一致候補の長さに等しい文字列を、前記入力された検索キーの末尾から取り出し、前記取り出した文字列に完全一致する登録パターンを前記ハッシュ表の中から検索するハッシュ表検索部と、
を有することを特徴とする検索装置。
【請求項１５】
登録パターンとして入力された文字列を分割することによって第１文字列と第２文字列とからなる組を１つ以上生成し、
前記第１文字列に対して複数のハッシュ関数を適用することによって複数のハッシュ値を求め、前記第２文字列の長さに対応するオフセットを決定し、前記複数のハッシュ値と前記オフセットとに所定の演算を施して複数の数値を算出し、
前記算出した複数の数値を、数値の配列であるベクトルの複数のアドレスとし、前記複数のアドレスに対応する前記ベクトル中の数値それぞれを、初期値と異なる数値に更新することを特徴とする検索方法。
【請求項１６】
検索キーとして入力された文字列を分割することによって、第１文字列と第２文字列とからなる組を１つ以上生成し、
前記第１文字列に対して複数のハッシュ関数を適用して複数のハッシュ値を求め、前記複数のハッシュ値とオフセットとに所定の演算を施して複数の数値を算出し、
前記算出した複数の数値を、数値の配列であるベクトルの複数のアドレスとし、前記複数のアドレスに対応する前記ベクトル中の数値の全てが初期値と異なっている場合、前記オフセットに対応する長さと前記第１文字列の長さとの和を一致候補の長さとして算出し、
前記検索キーの先頭もしくは末尾から、前記一致候補の長さに等しい長さの部分文字列を取り出し、前記取り出した部分文字列が登録済みであるかを判定することを特徴とする検索方法。
【請求項１７】
登録パターンとして入力された文字列を分割することによって第１文字列と第２文字列とからなる組を１つ以上生成する処理と、
前記第１文字列に対して複数のハッシュ関数を適用することによって複数のハッシュ値を求め、前記第２文字列の長さに対応するオフセットを決定し、前記複数のハッシュ値と前記オフセットとに所定の演算を施して複数の数値を算出する処理と、
前記算出した複数の数値を、数値の配列であるベクトルの複数のアドレスとし、前記複数のアドレスに対応する前記ベクトル中の数値それぞれを、初期値と異なる数値に更新する処理と、
をコンピュータに実行させることを特徴とするプログラム。
【請求項１８】
検索キーとして入力された文字列を分割することによって、第１文字列と第２文字列とからなる組を１つ以上生成する処理と、
前記第１文字列に対して複数のハッシュ関数を適用して複数のハッシュ値を求め、前記複数のハッシュ値とオフセットとに所定の演算を施して複数の数値を算出する処理と、
前記算出した複数の数値を、数値の配列であるベクトルの複数のアドレスとし、前記複数のアドレスに対応する前記ベクトル中の数値の全てが初期値と異なっている場合、前記オフセットに対応する長さと前記第１文字列の長さとの和を一致候補の長さとして算出する処理と、
前記検索キーの先頭もしくは末尾から、前記一致候補の長さに等しい長さの部分文字列を取り出し、前記取り出した部分文字列が登録済みであるかを判定する処理と、
をコンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、入力された情報に基づいて検索を行う情報検索技術に関し、特に前方または後方の最長一致を検索する検索装置、検索方法およびプログラムに関する。
【背景技術】
【０００２】
検索は情報処理分野における重要な技術の１つであり、用途に応じて多種多様な検索方法が存在する。検索方法の１つとして、前方または後方の最長一致検索がある。最長一致検索は、現実世界の住所やインターネット上の場所を示すＵＲＩ（Uniform Resource Identifier）などの、階層構造を有する文字列に対して用いられることが多い。例えば、「○○県△△市」という住所においては、「○○県」は「△△市」を含むという包含関係が成立している。このことから住所が階層構造を持つことが分かる。【０００３】
最長一致検索の必要性について説明する。例として、「Ａ県Ｂ市」と「Ａ県Ｂ市Ｃ区」という２つの地域が登録されたデータベースがあると仮定し、「Ａ県Ｂ市Ｃ区ＸＸＸ」という住所に最も近い地域を、そのデータベースの中から探すことを考える。上記の２つの地域は両方ともその住所を包含するが、「Ａ県Ｂ市Ｃ区」のほうが詳細である。言い換えると、「Ａ県Ｂ市」よりも「Ａ県Ｂ市Ｃ区」のほうが住所と一致している文字数が多い。【０００４】
このように文字列の先頭から末尾に向かってパターンと検索キーを照合しながら、一致している部分が最も長いパターンをデータベースの中から探す検索を、前方最長一致検索（Longest Prefix Match）という。また、後方最長一致検索（Longest Suffix Match）は、文字列の末尾から先頭に向かって照合していく点を除けば、前方最長一致検索と同じである。【０００５】
なお、前方あるいは後方の最長一致検索を実施する技術としては、例えば特許文献１に記載のものがある。【０００６】
ここで、図面を用いて、本発明に関連する技術例（以下、関連技術例という）の動作を説明する。２つの登録パターン１００である”ＡＢＣＤＥＦＧＨＩＪ”と”ＶＷＸＹＺ”をデータベースに登録する例を図２８に示す。【０００７】
まず、登録パターン１００を、前半部分のプレフィックス１０１と後半部分のサフィックス１０２に分割する。登録パターン１００の”ＡＢＣＤＥＦＧＨＩＪ”は、８文字のプレフィックス１０１と、２文字のサフィックス１０２に分割される。同様に、登録パターン１００の”ＶＷＸＹＺ”は、４文字のプレフィックス１０１と、１文字のサフィックス１０２に分割される。プレフィックス１０１の長さは、所定値Ｎの倍数の文字数であって（Ｎは自然数であり、分割位置の間隔を示す）、かつ、登録パターン１００の長さを超えない最大の長さである。本例ではＮ＝４とした。【０００８】
次に、登録パターン１００それぞれについて、プレフィックス１０１にハッシュ関数をかけてハッシュ値１０３を求め、そのハッシュ値１０３が指すハッシュ表１０４のバケットに登録パターン１００を追加する。この際、登録パターン１００はプレフィックス１０１とサフィックス１０２に分離されてハッシュ表１０４に収められる。プレフィックス１０１が共通であってサフィックス１０２が異なるような複数の登録パターン１００がハッシュ表１０４に存在するとき、それらのサフィックス１０２は長いものから順に連結リストで接続される。【０００９】
検索キー１１０として”ＶＷＸＹＺＡＢＣＤ”が与えられたときの検索手順を図２９に示す。【００１０】
まず、登録時と同様に、検索キー１１０をプレフィックス１１１とサフィックス１１２に分割し、８文字のプレフィックス１１１の”ＶＷＸＹＺＡＢＣ”と、１文字のサフィックス１１２の”Ｄ”を得る。【００１１】
次に、プレフィックス１１１にハッシュ関数をかけてハッシュ値１１３を求める。このハッシュ関数は、登録時に使用したものと同一である。その後、そのハッシュ値１１３が指すハッシュ表１０４のバケットに１つ以上の登録パターン１００が格納されているかを調べる。この時点でのハッシュ値１１３は２であって、それに対応するバケットは空であるので、”ＶＷＸＹＺＡＢＣ”から始まる登録パターン１００はデータベースに存在しないことが分かる。【００１２】
次に、プレフィックス１１１とサフィックス１１２を区切っている分割位置を、Ｎ文字（Ｎ＝４）だけ左に移動させる。つまり、プレフィックス１１１を４文字短くし、サフィックス１１２を４文字長くする。新たなプレフィックス１１１は”ＶＷＸＹ”となり、新たなサフィックス１１２は“ＺＡＢＣＤ”となる。【００１３】
次に、プレフィックス１１１にハッシュ関数をかけてハッシュ値１１３を求めたのち、そのハッシュ値１１３が指すハッシュ表１０４のバケットに１つ以上の登録パターン１００が格納されているかを調べる。この時点でのハッシュ値１１３は３であり、それに対応するバケットには登録パターン１００の”ＶＷＸＹＺ”が格納されている。その登録パターン１００と検索キー１１０とを照合すると、登録パターン１００の”ＶＷＸＹＺ”は、検索キー１１０の”ＶＷＸＹＺＡＢＣＤ”の前半部分に一致しているので、”ＶＷＸＹＺ”が前方最長一致検索の結果となる。
【先行技術文献】
【特許文献】
【００１４】
【特許文献１】特開２００５−１６５５９８号公報
【発明の概要】
【発明が解決しようとする課題】
【００１５】
さて、上述した関連技術例には問題点が２つ存在する。【００１６】
第１の問題点は、検索に失敗する場合、すなわち、検索キー１１０に前方一致する登録パターン１００がデータベースに登録されていなかったときに、検索の失敗を判定するまでに多くの処理量を要するということである。【００１７】
第２の問題点は、共通のプレフィックス１０１を持つ登録パターン１００が多数存在するときに、検索速度が低下するということである。【００１８】
関連技術例の第１の問題点は、その検索方法から容易に導かれる。【００１９】
上述のように検索時には、検索キー１１０がプレフィックス１１１とサフィックス１１２に分割される。初回のプレフィックス１１１の長さは、所定値Ｎの倍数の文字数であってかつ、検索キー１１０の長さを超えない最大の長さである。【００２０】
プレフィックス１１１にハッシュ関数をかけてハッシュ値１１３を求め、そのハッシュ値１１３が指すハッシュ表１０４のバケットを調べた結果、検索キー１１０に前方一致する登録パターン１００が発見されなければ、プレフィックス１１１の長さをＮ文字短くする。このプロセスは、検索キー１１０に前方一致する登録パターン１００が発見されるか、または、プレフィックス１１１の長さが０になるまで繰り返される。特に、検索キー１１０に前方一致する登録パターン１００がデータベースに登録されていなかった場合は、このプロセスはプレフィックス１１１の長さが０になるまで繰り返される。【００２１】
つまり、関連技術例は、上記のプロセスを（検索キー１１０の長さ÷Ｎ）回（端数切捨て）繰り返さなければ、検索の失敗を知ることができない。例えば、検索キー１１０の長さが１００文字で、Ｎが４のとき、検索が終了して失敗が確定するまで２５回の繰り返しが必要となる。【００２２】
上記のプロセスには、ハッシュ表１０４の探索というメモリアクセスを伴う処理が含まれている。一般的に現在のコンピュータにおいては、メモリアクセスにかかる時間的コストは、純粋な演算と比較して大きい。従って、ここに示した関連技術例の第１の問題点は矮小なものではない。【００２３】
関連技術例の第２の問題点について図３０を用いて説明する。図３０は、プレフィックス１０１が全て共通であってサフィックス１０２が互いに異なっている９つの登録パターン１００が、データベースに登録されている様子を示している。このとき、プレフィックス１０１が全て共通であるため、ハッシュ値１０３の衝突が起き、ハッシュ表１０４においてサフィックス１０２の連結リストが構築される。【００２４】
ここで、検索キー１１０として例えば”ＡＢＣＤＸ”が与えられたとき、連結リスト中のサフィックス１０２と”Ｘ”との照合が、計９回行われる。つまり、ハッシュの効果を一切受けられず、低速な全件検索になってしまっている。【００２５】
共通のプレフィックス１０１を持つ登録パターン１００が多く含まれるデータベースは、決して珍しくない。住所データベースがその代表例である。例えば、「○○県△△市」、「○○県◇◇市」、「○○県××市」のように、「○○県」のみが共通の場合などがある。【００２６】
関連技術例においては、分割位置の間隔であるＮの数値を小さくすることで、プレフィックス１０１が共通になる確率を下げることは可能である。その結果、ハッシュ表１０４の中の連結リストの平均長が短くなり、ハッシュ表１０４の１回の検索あたりの処理時間は減少する。特に、Ｎを１にすれば、サフィックス１０２の長さは常に０になり、プレフィックス１０１と登録パターン１００は完全に一致するようになるため、ハッシュ値１０３の衝突確率は極めて小さくなる。【００２７】
しかし、Ｎを小さくしてもトータルの検索速度は改善されない。その理由は、例えば検索キー１１０の長さが１３文字であるとき、Ｎ＝４であれば１２文字、８文字、４文字の３通りの長さのプレフィックス１１１を評価するだけで済むが、Ｎ＝２のときは１２文字、１０文字、…、２文字の６通りの長さのプレフィックス１１１を評価する必要があるからである。すなわち、Ｎの減少率に反比例してハッシュ表１０４の検索回数が増加してしまうため、結果としてＮの値を小さくしても検索速度は向上しない。従って、関連技術例においては、Ｎを調整してトータルの検索速度を改善することは不可能である。【００２８】
本発明は、上述の事情に鑑みてなされたものであり、前方または後方の最長一致検索において、ハッシュ値の衝突確率を小さくしてトータルの検索速度を向上させるとともに、検索の失敗を高速に判定可能な検索装置、検索方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【００２９】
かかる目的を達成するために、本発明の検索装置は、第１の態様として、登録パターンとして入力された文字列を分割することによって第１文字列と第２文字列とからなる組を１つ以上生成し、第１文字列に対して複数のハッシュ関数を適用することによって複数のハッシュ値を求め、第２文字列の長さに対応するオフセットを決定し、複数のハッシュ値とオフセットとに所定の演算を施して複数の数値を算出し、算出した複数の数値をベクトル中の複数のアドレスとし、複数のアドレスに対応する内容それぞれを初期値と異なる数値に更新することを特徴とする。【００３０】
本発明の検索装置は、第２の態様として、検索キーとして入力された文字列を分割することによって、第１文字列と第２文字列とからなる組を１つ以上生成し、第１文字列に対して複数のハッシュ関数を適用して複数のハッシュ値を求め、複数のハッシュ値とオフセットとに所定の演算を施して複数の数値を算出し、算出した複数の数値をベクトル中の複数のアドレスとし、複数のアドレスに対応する内容の全てが初期値と異なっている場合、オフセットに対応する長さと第１文字列の長さとの和を一致候補の長さとして算出し、検索キーの先頭もしくは末尾から、一致候補の長さに等しい長さの部分文字列を取り出し、取り出した部分文字列が登録済みであるかを判定することを特徴とする。【００３１】
本発明の検索装置は、第３の態様として、文字列である登録パターンと検索キーとに基づいて、前方最長一致検索を行う検索装置であって、文字列を分割するための分割位置を複数格納する分割位置リストと、数値の配列であるベクトルと、登録パターンを格納するハッシュ表と、分割位置リストの中から、入力された登録パターンの長さを超えない最大の分割位置を１つ選択し、選択した分割位置を境にして入力された登録パターンからプレフィックスを抽出するとともに、入力された登録パターンの長さからプレフィックスの長さを減算してサフィックス長を求める第１プレフィックス抽出部と、第１プレフィックス抽出部で抽出されたプレフィックスに対して複数のハッシュ関数を適用し、複数のハッシュ値を算出する第１ハッシュ演算部と、第１ハッシュ演算部で算出された複数のハッシュ値とサフィックス長とを加算して複数の数値を算出し、算出した複数の数値をベクトル中の複数のアドレスとし、複数のアドレスに対応する内容それぞれを初期値と異なる数値に更新するベクトル更新部と、入力された登録パターンをハッシュ表に格納するハッシュ表登録部と、分割位置リストの中から、入力された検索キーの長さを超えない分割位置を降順に選択し、選択した分割位置を境にして入力された検索キーから１つ以上のプレフィックスを抽出する第２プレフィックス抽出部と、第２プレフィックス抽出部で抽出されたプレフィックスに対して、第１ハッシュ演算部で用いたものと同じ複数のハッシュ関数を適用し、複数のハッシュ値を算出する第２ハッシュ演算部と、第２ハッシュ演算部で算出された複数のハッシュ値とオフセットとを加算して複数の数値を算出し、算出した複数の数値をベクトル中の複数のアドレスとし、複数のアドレスに対応する内容の全てが初期値と異なっている場合、第２プレフィックス抽出部で抽出されたプレフィックスの長さとオフセットとの和を一致候補の長さとして算出するパターン長推定部と、パターン長推定部で算出された一致候補の長さに等しい文字列を、入力された検索キーの先頭から取り出し、取り出した文字列に完全一致する登録パターンをハッシュ表の中から検索するハッシュ表検索部と、を有することを特徴とする。【００３２】
本発明の検索装置は、第４の態様として、文字列である登録パターンと検索キーとに基づいて、前方最長一致検索を行う検索装置であって、数値の配列であるベクトルと、登録パターンを格納するハッシュ表と、入力された登録パターンから、所定の文字数の倍数の長さを持つプレフィックスを１つ以上抽出するとともに、入力された登録パターンの長さからプレフィックスの長さを減算してサフィックス長を求める第１プレフィックス抽出部と、第１プレフィックス抽出部で抽出されたプレフィックスに対して複数のハッシュ関数を適用し、複数のハッシュ値を算出する第１ハッシュ演算部と、長さとオフセットの関係が記載された対応表と、長さとオフセットの関係が記載された対応表を参照して、サフィックス長から第１オフセットを決定するオフセット決定部と、第１ハッシュ演算部で算出された複数のハッシュ値と、オフセット決定部で決定された第１オフセットとに所定の演算を施して複数の数値を算出し、算出した複数の数値をベクトル中の複数のアドレスとし、複数のアドレスに対応する内容それぞれを初期値と異なる数値に更新するベクトル更新部と、入力された登録パターンをハッシュ表に格納するハッシュ表登録部と、入力された検索キーから、所定の文字数の倍数の長さを持つプレフィックスを短いものから順に抽出する第２プレフィックス抽出部と、第２プレフィックス抽出部で抽出されたプレフィックスに対して、第１ハッシュ演算部で用いたものと同じ複数のハッシュ関数を適用し、複数のハッシュ値を算出する第２ハッシュ演算部と、長さとオフセットの関係が記載された対応表で定義される第２オフセットそれぞれについて、第２ハッシュ演算部で算出された複数のハッシュ値と第２オフセットとに所定の演算を施して複数の数値を算出し、算出した複数の数値をベクトル中の複数のアドレスとし、複数のアドレスに対応する内容の全てが初期値と異なっている場合、第２プレフィックス抽出部で抽出されたプレフィックスの長さと第２オフセットに対応する長さとの和を一致候補の長さとして算出するパターン長推定部と、パターン長推定部で算出された一致候補の長さに等しい文字列を、入力された検索キーの先頭から取り出し、取り出した文字列に完全一致する登録パターンをハッシュ表の中から検索するハッシュ表検索部と、を有することを特徴とする。【００３３】
本発明の検索装置は、第５の態様として、文字列である登録パターンと検索キーとに基づいて、後方最長一致検索を行う検索装置であって、文字列を分割するための分割位置を複数格納する分割位置リストと、数値の配列であるベクトルと、登録パターンを格納するハッシュ表と、分割位置リストの中から、入力された登録パターンの長さを超えない最大の分割位置を１つ選択し、選択した分割位置を境にして入力された登録パターンからサフィックスを抽出するとともに、入力された登録パターンの長さからサフィックスの長さを減算してプレフィックス長を求める第１サフィックス抽出部と、第１サフィックス抽出部で抽出されたサフィックスに対して複数のハッシュ関数を適用し、複数のハッシュ値を算出する第１ハッシュ演算部と、第１ハッシュ演算部で算出された複数のハッシュ値とプレフィックス長とを加算して複数の数値を算出し、算出した複数の数値をベクトル中の複数のアドレスとし、複数のアドレスに対応する内容それぞれを初期値と異なる数値に更新するベクトル更新部と、入力された登録パターンをハッシュ表に格納するハッシュ表登録部と、分割位置リストの中から、入力された検索キーの長さを超えない分割位置を降順に選択し、選択した分割位置を境にして入力された検索キーから１つ以上のサフィックスを抽出する第２サフィックス抽出部と、第２サフィックス抽出部で抽出されたサフィックスに対して、第１ハッシュ演算部で用いたものと同じ複数のハッシュ関数を適用し、複数のハッシュ値を算出する第２ハッシュ演算部と、第２ハッシュ演算部で算出された複数のハッシュ値とオフセットとを加算して複数の数値を算出し、算出した複数の数値をベクトル中の複数のアドレスとし、複数のアドレスに対応する内容の全てが初期値と異なっている場合、第２サフィックス抽出部で抽出されたサフィックスの長さとオフセットとの和を一致候補の長さとして算出するパターン長推定部と、パターン長推定部で算出された一致候補の長さに等しい文字列を、入力された検索キーの末尾から取り出し、取り出した文字列に完全一致する登録パターンをハッシュ表の中から検索するハッシュ表検索部と、を有することを特徴とする。【００３４】
本発明の検索装置は、第６の態様として、文字列である登録パターンと検索キーとに基づいて、後方最長一致検索を行う検索装置であって、数値の配列であるベクトルと、登録パターンを格納するハッシュ表と、入力された登録パターンから、所定の文字数の倍数の長さを持つサフィックスを１つ以上抽出するとともに、入力された登録パターンの長さからサフィックスの長さを減算してプレフィックス長を求める第１サフィックス抽出部と、第１サフィックス抽出部で抽出されたサフィックスに対して複数のハッシュ関数を適用し、複数のハッシュ値を算出する第１ハッシュ演算部と、長さとオフセットの関係が記載された対応表と、長さとオフセットの関係が記載された対応表を参照して、プレフィックス長から第１オフセットを決定するオフセット決定部と、第１ハッシュ演算部で算出された複数のハッシュ値と、オフセット決定部で決定された第１オフセットとに所定の演算を施して複数の数値を算出し、算出した複数の数値をベクトル中の複数のアドレスとし、複数のアドレスに対応する内容それぞれを初期値と異なる数値に更新するベクトル更新部と、入力された登録パターンをハッシュ表に格納するハッシュ表登録部と、入力された検索キーから、所定の文字数の倍数の長さを持つサフィックスを短いものから順に抽出する第２サフィックス抽出部と、第２サフィックス抽出部で抽出されたサフィックスに対して、第１ハッシュ演算部で用いたものと同じ複数のハッシュ関数を適用し、複数のハッシュ値を算出する第２ハッシュ演算部と、長さとオフセットの関係が記載された対応表で定義される第２オフセットそれぞれについて、第２ハッシュ演算部で算出された複数のハッシュ値と第２オフセットとに所定の演算を施して複数の数値を算出し、算出した複数の数値をベクトル中の複数のアドレスとし、複数のアドレスに対応する内容の全てが初期値と異なっている場合、第２サフィックス抽出部で抽出されたサフィックスの長さと第２オフセットに対応する長さとの和を一致候補の長さとして算出するパターン長推定部と、パターン長推定部で算出された一致候補の長さに等しい文字列を、入力された検索キーの末尾から取り出し、取り出した文字列に完全一致する登録パターンをハッシュ表の中から検索するハッシュ表検索部と、を有することを特徴とする。【００３５】
本発明の検索方法は、第１の態様として、登録パターンとして入力された文字列を分割することによって第１文字列と第２文字列とからなる組を１つ以上生成し、第１文字列に対して複数のハッシュ関数を適用することによって複数のハッシュ値を求め、第２文字列の長さに対応するオフセットを決定し、複数のハッシュ値とオフセットとに所定の演算を施して複数の数値を算出し、算出した複数の数値をベクトル中の複数のアドレスとし、複数のアドレスに対応する内容それぞれを初期値と異なる数値に更新することを特徴とする。【００３６】
本発明の検索方法は、第２の態様として、検索キーとして入力された文字列を分割することによって、第１文字列と第２文字列とからなる組を１つ以上生成し、第１文字列に対して複数のハッシュ関数を適用して複数のハッシュ値を求め、複数のハッシュ値とオフセットとに所定の演算を施して複数の数値を算出し、算出した複数の数値をベクトル中の複数のアドレスとし、複数のアドレスに対応する内容の全てが初期値と異なっている場合、オフセットに対応する長さと第１文字列の長さとの和を一致候補の長さとして算出し、検索キーの先頭もしくは末尾から、一致候補の長さに等しい長さの部分文字列を取り出し、取り出した部分文字列が登録済みであるかを判定することを特徴とする。【００３７】
本発明のプログラムは、第１の態様として、登録パターンとして入力された文字列を分割することによって第１文字列と第２文字列とからなる組を１つ以上生成する処理と、第１文字列に対して複数のハッシュ関数を適用することによって複数のハッシュ値を求め、第２文字列の長さに対応するオフセットを決定し、複数のハッシュ値とオフセットとに所定の演算を施して複数の数値を算出する処理と、算出した複数の数値をベクトル中の複数のアドレスとし、複数のアドレスに対応する内容それぞれを初期値と異なる数値に更新する処理と、をコンピュータに実行させることを特徴とする。【００３８】
本発明のプログラムは、第２の態様として、検索キーとして入力された文字列を分割することによって、第１文字列と第２文字列とからなる組を１つ以上生成する処理と、第１文字列に対して複数のハッシュ関数を適用して複数のハッシュ値を求め、複数のハッシュ値とオフセットとに所定の演算を施して複数の数値を算出する処理と、算出した複数の数値をベクトル中の複数のアドレスとし、複数のアドレスに対応する内容の全てが初期値と異なっている場合、オフセットに対応する長さと第１文字列の長さとの和を一致候補の長さとして算出する処理と、検索キーの先頭もしくは末尾から、一致候補の長さに等しい長さの部分文字列を取り出し、取り出した部分文字列が登録済みであるかを判定する処理と、をコンピュータに実行させることを特徴とする。
【発明の効果】
【００３９】
本発明によれば、前方または後方の最長一致検索において、ハッシュ値の衝突確率を小さくしてトータルの検索速度を向上させるとともに、検索の失敗を高速に判定することができる。
【図面の簡単な説明】
【００４０】
【図１】本発明の一実施形態に係る、前方最長一致検索を実現する構成の例を示すブロック図である。
【図２】登録部１０の動作例を示すフローチャートである。
【図３】プレフィックス抽出部２０の動作例を示す説明図である。
【図４】ハッシュ演算部２１およびビットベクトル更新部２２の動作例を示す説明図である。
【図５】ハッシュ表１３にパターンを登録する具体例を示す説明図である。
【図６】検索部１１の動作例を示すフローチャートである。
【図７】検索部１１の動作例を示すフローチャートである。
【図８】ハッシュ演算部３１およびパターン長推定部３２の動作例を示す説明図である。
【図９】プレフィックス抽出部３０の動作例を示す説明図である。
【図１０】本発明の一実施形態に係る検索装置を情報処理装置に適用した構成の例を示すブロック図である。
【図１１】本発明の一実施形態に係る、前方最長一致検索を実現する構成の例を示すブロック図である。
【図１２】登録部４０内の長さ−オフセット対応表６７の具体例を示す説明図である。
【図１３】登録部４０の動作例を示すフローチャートである。
【図１４】ハッシュ表１３にパターンを登録する具体例を示す説明図である。
【図１５】登録部４０内の登録オフセットビットマップ更新部６９の動作例を示す説明図である。
【図１６】登録部４０内のハッシュ演算部２１およびビットベクトル更新部６２の動作例を示す説明図である。
【図１７】登録部４０内のハッシュ演算部２１およびビットベクトル更新部６２の動作例を示す説明図である。
【図１８】登録部４０内のハッシュ演算部２１およびビットベクトル更新部６２の動作例を示す説明図である。
【図１９】登録部４０内の登録オフセットビットマップ更新部６９の動作例を示す説明図である。
【図２０】登録部４０内のハッシュ演算部２１およびビットベクトル更新部６２の動作例を示す説明図である。
【図２１】検索部４１の動作例を示すフローチャートである。
【図２２】検索部４１の動作例を示すフローチャートである。
【図２３】検索部４１内の累積オフセットビットマップ８９の具体例を示す説明図である。
【図２４】検索部４１内のハッシュ演算部３１およびパターン長推定部８２の動作例を示す説明図である。
【図２５】検索部４１内のハッシュ演算部３１およびパターン長推定部８２の動作例を示す説明図である。
【図２６】検索部４１内のハッシュ演算部３１およびパターン長推定部８２の動作例を示す説明図である。
【図２７】本発明の一実施形態に係る検索装置を情報処理装置に適用した構成の例を示すブロック図である。
【図２８】関連技術例における、ハッシュ表にパターンを登録する具体例を示す説明図である。
【図２９】関連技術例における、ハッシュ表を用いて前方最長一致検索する具体例を示す説明図である。
【図３０】関連技術例の問題点を示す説明図である。
【発明を実施するための形態】
【００４１】
以下、本発明を実施するための最良の形態（以下、実施形態という）について添付図面を参照して詳細に説明する。まず、第１の実施形態について図１〜図１０を用いて説明し、その後、第２の実施形態について図１１〜図２７を用いて説明する。
【００４２】
〔第１の実施形態〕
図１は、文字列に対する前方最長一致検索を行う検索装置１の構成を示すブロック図である。
【００４３】
なお、本実施形態において、文字列を構成する各々の文字は、人間が認識可能な文字に限定されずバイナリデータであってもよい。また、１文字を表現するために必要なビット数に制限はなく、必ずしも１文字が１バイトで表される必要はない。
【００４４】
検索装置１の構成要素は、登録パターン２を登録する登録部１０と、登録済みの１つ以上の登録パターン２の中から検索キー３に前方最長一致するものを探す検索部１１と、１つ以上の登録パターン２が格納されるハッシュ表１３と、検索キー３に最長一致する可能性のある登録パターン２の長さを推定するための情報源であるビットベクトル１２と、プレフィックスの長さを決定する分割位置リスト１４と、である。これら各部は、ハードウェア構成として、回路基板やメモリチップなどのデバイスによって実現されるようにしてもよい。
【００４５】
なお、検索装置１は、ハードウェア構成として、例えば、ＣＰＵ（Central Processing Unit）、ＣＰＵを制御するプログラム（本発明の一実施形態である検索プログラム）等の固定的なデータを予め格納したＲＯＭ（Read Only Memory）、各種データを一時的に記憶するエリアを形成するＲＡＭ（Random Access Memory）、ＨＤＤ（Hard Disk Drive）等の記録媒体を有するようにしてもよい。よって、登録部１０と検索部１１は、ＣＰＵ、ＲＯＭ、ＲＡＭによって実現されるようにしてもよい。また、ハッシュ表１３、ビットベクトル１２および分割位置リスト１４は、ＲＡＭ又は記録媒体によって実現されるようにしてもよい。
【００４６】
ハッシュ表１３は、後述の検索部１１のハッシュ表検索部３３において、登録パターン２の完全一致（Exact Match）検索に使用される。ハッシュを使ったデータ構造および完全一致検索方法は公知のものである。従って、ハッシュ表１３は既存のハッシュ法により容易に実現できる。初期状態ではハッシュ表１３の内容は空（Empty）である。
【００４７】
ビットベクトル１２は、ビット（数値）の１次元配列であり、その内容の初期値は全て０である。
【００４８】
登録部１０は、未登録の文字列である登録パターン２を入力とし、それをビットベクトル１２とハッシュ表１３に登録する動作を行う。
【００４９】
登録部１０の構成要素は、ハッシュ計算対象となる部分文字列（文字列の一部分）を登録パターン２の中から抽出するプレフィックス抽出部２０、その部分文字列に対して複数のハッシュ関数をかけて複数のハッシュ値を計算するハッシュ演算部２１、ハッシュ値が指し示すビットベクトル１２の内容を更新するビットベクトル更新部２２、ハッシュ表１３に登録パターン２を登録するハッシュ表登録部２３、である。
【００５０】
プレフィックス抽出部２０は、登録パターン２の先頭から部分文字列を切り出し、その部分文字列をプレフィックス２４としてハッシュ演算部２１に出力する。この部分文字列すなわちプレフィックス２４の長さは、分割位置リスト１４の内容から一意に決定される。
【００５１】
分割位置リスト１４は自然数の集合であって、その各要素はプレフィックス２４の長さの候補を表す。プレフィックス２４の長さは、分割位置リスト１４に含まれる要素のうち、登録パターン２の長さを超えない最大の要素である。例えば、分割位置リスト１４が｛１０、６、３、１｝であって、登録パターン２の長さが７のとき、プレフィックス２４の長さは６となる。
【００５２】
分割位置リスト１４の内容に関する制約は４点ある。
【００５３】
１点目の制約は、分割位置リスト１４の最大の要素は、登録部１０が処理できる登録パターン２の最大長に１を加えた数値に等しい、ということである。例えば、分割位置リスト１４が｛１０、６、３、１｝のとき、登録部１０が処理できる登録パターン２の長さの上限は９文字である。
【００５４】
２点目の制約は、分割位置リスト１４の最小の要素は、登録部１０が処理できる登録パターン２の最小長に等しい、ということである。例えば、分割位置リスト１４が｛１０、６、３、１｝のとき、登録部１０が処理できる登録パターン２の長さの下限は１文字である。
【００５５】
３点目の制約は、分割位置リスト１４の要素は互いに異なっていなければならない、ということである。例えば、｛１０、６、６、１｝という集合は分割位置リスト１４として不適切である。
【００５６】
４点目の制約は、分割位置リスト１４において各要素が降順に並んでいなければならない、ということである。この制約は上記３点とは異なり本質的なものではなく、説明を簡易にするための形式的なものである。
【００５７】
プレフィックス抽出部２０は、分割位置リスト１４に基づいてプレフィックス２４を抽出したのち、登録パターン２の長さからプレフィックス２４の長さを減算してサフィックス長２５を求め、それをビットベクトル更新部２２に出力する。このように、プレフィックス抽出部２０は、登録パターン２をプレフィックス（第１文字列）とサフィックス（第２文字列）とに分割するので、登録パターン分割部あるいはサフィックス抽出部と呼ぶこともできる。
【００５８】
ハッシュ演算部２１は、プレフィックス２４に対して、Ｍ個のハッシュ関数をかけてＭ個のハッシュ値２６−１〜２６−Ｍを求め、それらをビットベクトル更新部２２に送出する。ここで、Ｍは２以上の整数である。ハッシュの衝突を抑えるため、Ｍ個のハッシュ関数は互いに相関の無いハッシュ値２６−１〜２６−Ｍを生成するものであることが望ましい。
【００５９】
ビットベクトル更新部２２は、ビットベクトル１２の中のＭ個のビットを１にセットする。１にセットされるビットのアドレスは、ハッシュ値２６−１〜２６−Ｍとサフィックス長２５から決まる。ビットベクトル更新部２２の動作の詳細は後述する。
【００６０】
ハッシュ表登録部２３は、登録パターン２をハッシュ表１３に追加する。この際、登録パターン２の全域に対してハッシュ関数をかけてハッシュ値を計算する。なお、ハッシュ表登録部２３で用いられるハッシュ関数と、ハッシュ演算部２１で使われるハッシュ関数との間に関連はない。
【００６１】
検索部１１は、文字列である検索キー３を入力とし、検索キー３に前方最長一致する登録パターン２を特定するためにビットベクトル１２とハッシュ表１３を探索して、その結果を検索結果４として出力する。
【００６２】
検索部１１の構成要素は、ハッシュ計算対象となる１つ以上の部分文字列（文字列の一部分）を検索キー３の中から抽出するプレフィックス抽出部３０、その部分文字列に対して複数のハッシュ関数をかけて複数のハッシュ値を計算するハッシュ演算部３１、ハッシュ値が指し示すビットベクトル１２の内容を参照して検索キー３に前方最長一致する可能性のある登録パターン２の長さを推定するパターン長推定部３２、推定された長さに等しい部分文字列を検索キー３の先頭から取り出してその部分文字列に完全一致する登録パターン２がハッシュ表１３の中に存在するか否かを判定するハッシュ表検索部３３、である。
【００６３】
プレフィックス抽出部３０は、検索キー３の先頭から部分文字列を切り出し、その部分文字列をプレフィックス３４としてハッシュ演算部３１に出力する。この部分文字列すなわちプレフィックス３４の長さは、分割位置リスト１４の内容から決定される。
【００６４】
プレフィックス３４の長さは、分割位置リスト１４に含まれる要素のうち、検索キー３の長さを超えない要素に等しい。この条件を満たす要素が複数存在する場合は、同数のプレフィックス３４を長いものから順に出力する。例えば、分割位置リスト１４が｛１０、６、３、１｝であって、検索キー３の長さが７のときは、６文字のプレフィックス３４、３文字のプレフィックス３４、１文字のプレフィックス３４の順に出力する。
【００６５】
プレフィックス抽出部３０は、プレフィックス３４を抽出するたびに分割間隔３５を計算して、それをパターン長推定部３２に出力する。分割間隔３５の計算は下記の式で行われる。
分割間隔３５＝Ｘ−（プレフィックス３４の長さ）
上記式におけるＸは、分割位置リスト１４に含まれる要素のうち、プレフィックス３４の長さより大きい最小の要素である。このように、プレフィックス抽出部３０は、検索キー３をプレフィックス（第１文字列）と分割間隔（サフィックス。第２文字列）とに分割するので、検索キー分割部あるいはサフィックス抽出部と呼ぶこともできる。
【００６６】
例えば、分割位置リスト１４が｛１０、６、３、１｝であるとき、プレフィックス３４の長さが６文字であれば分割間隔３５は４（＝１０−６）になり、プレフィックス３４の長さが３文字であれば分割間隔３５は３（＝６−３）になる。
【００６７】
ハッシュ演算部３１は、プレフィックス３４に対してＭ個のハッシュ関数をかけてＭ個のハッシュ値３６−１〜３６−Ｍを求め、それらをパターン長推定部３２に送出する。ハッシュ関数の個数すなわちＭとハッシュ関数の形状は、登録部１０のハッシュ演算部２１のものと同一でなければならない。
【００６８】
パターン長推定部３２は、Ｍ個のハッシュ値３６−１〜３６−Ｍが指し示すＭ箇所のビットベクトル１２の内容を参照し、得られた値に所定の演算を施すことにより、検索キー３に前方最長一致する可能性のある登録パターン２の長さを推定し、その推定された長さを一致候補の長さ３７としてハッシュ表検索部３３に出力する。パターン長推定部３２の動作の詳細は後述する。
【００６９】
ハッシュ表検索部３３は、一致候補の長さ３７に等しい長さの部分文字列を検索キー３の先頭から取り出し、その部分文字列を一致候補５３とする。その後、ハッシュ表検索部３３はハッシュ表１３を検索し、一致候補５３に完全一致する登録パターン２がハッシュ表１３の中に存在しているか否かを判定する。なお、この検索で用いられるハッシュ関数およびハッシュアルゴリズムは、登録部１０のハッシュ表登録部２３と同一でなければならない。一致候補５３に完全一致する登録パターン２が発見された場合は、一致候補５３を検索結果４として出力する。発見されなければ検索失敗を意味する検索結果４を出力する。
【００７０】
次に、文字列に対する前方最長一致検索を行う検索装置１の動作を述べる。
【００７１】
まず、登録パターン２の登録を行う登録部１０の説明から開始する。図２は、登録部１０の動作を表すフローチャートである。図３〜図５の具体例を併用して、図２のフローチャートを説明する。
【００７２】
本例では、図３に示す２つの登録パターン２である”ＡＢＣＤＥＦＧ”と”ＸＹＺ”が、順に１つずつ検索装置１に登録される。また、分割位置リスト１４の内容は、｛１０、６、３、１｝とする。
【００７３】
プレフィックス抽出部２０及びハッシュ表登録部２３は、登録パターン２の入力を待つ（ステップＳ１００）。本例では、登録パターン２は”ＡＢＣＤＥＦＧ”の７文字になる。
【００７４】
ステップＳ１００の後は、ステップＳ１０１とステップＳ１０６へ進む。ステップＳ１０１〜ステップＳ１０５とステップＳ１０６は、並列実行可能である。なお、並列実行は必須ではない。また、ステップＳ１０１〜ステップＳ１０５は、順序通りに逐次実行されなければならない。
【００７５】
まず、ステップＳ１０１〜Ｓ１０５の動作説明を先行する。
【００７６】
プレフィックス抽出部２０は、Ｌすなわちプレフィックス２４の長さを決定する（ステップＳ１０１）。前述の通り、プレフィックス２４の長さは、分割位置リスト１４に含まれる要素のうち、登録パターン２の長さを超えない最大の要素である。本例では図３（上）のように、登録パターン２の長さが７文字であるから、プレフィックス２４の長さは６文字になる。なお本明細書において、例えば「図３（上）」という表記は「図３の上方部分」を意味し、同様に、例えば「図３（下）」という表記は「図３の下方部分」を意味する。
【００７７】
プレフィックス抽出部２０は、登録パターン２の先頭からＬ文字を取り出し、その部分文字列をプレフィックス２４とする（ステップＳ１０２）。本例では図３（上）のように、プレフィックス２４の長さが６文字（Ｌ＝６）であるから、プレフィックス２４は”ＡＢＣＤＥＦ”になる。
【００７８】
プレフィックス抽出部２０は、登録パターン２の長さからＬを減算してサフィックス長２５を求める（ステップＳ１０３）。本例では、サフィックス長２５は１（＝７−Ｌ＝７−６）になる。
【００７９】
ハッシュ演算部２１は、プレフィックス２４にＭ個のハッシュ関数をかけて、Ｍ個のハッシュ値２６−１〜２６−Ｍを計算する（ステップＳ１０４）。本例では図４（左）のように、ハッシュ関数の個数Ｍを２とし、プレフィックス２４の”ＡＢＣＤＥＦ”から計算されたハッシュ値２６−１〜２６−２がそれぞれ１と８になると仮定する。なお本明細書において、例えば「図４（左）」という表記は「図４の左側部分」を意味し、同様に、例えば「図４（右）」という表記は「図４の右側部分」を意味する。
【００８０】
ビットベクトル更新部２２は、ビットベクトル１２の中のＭ個のビットを１にセットする（ステップＳ１０５）。ビットベクトル１２において１がセットされるビットのアドレスは、ハッシュ値２６−１とサフィックス長２５を加算した数値をＢで割った剰余、ハッシュ値２６−２とサフィックス長２５を加算した数値をＢで割った剰余、（中略）、ハッシュ値２６−Ｍとサフィックス長２５を加算した数値をＢで割った剰余、のＭ個である。ここでＢは、ビットベクトル１２の要素数である。
【００８１】
剰余を使用している理由は、ハッシュ値２６−Ｘ（１≦Ｘ≦Ｍ）とサフィックス長２５を加算した数値がビットベクトル１２の長さを超えてしまい、１にセットされるアドレスがビットベクトル１２の範囲外になる事態を防ぐためである。
【００８２】
本例では図４（左）のように、１にセットされるアドレスは、２（＝（１＋１）mod １６）と９（＝（８＋１）mod １６）である。
【００８３】
ハッシュ表登録部２３は、ハッシュ表１３に登録パターン２を追加する（ステップＳ１０６）。
【００８４】
ステップＳ１０５とステップＳ１０６の処理がともに終了した時点で、１つの登録パターン２の登録が完了する。本例では、この時点で登録パターン２の”ＡＢＣＤＥＦＧ”の登録が完了する。もう１つの登録パターン２の”ＸＹＺ”の登録も上記同様に行われるため、ここでの説明は省略する。
【００８５】
２つの登録パターン２である”ＡＢＣＤＥＦＧ”と”ＸＹＺ”の登録が完了した時点での、ハッシュ表１３の例を図５（下）に示す。
【００８６】
次に、検索キー３に前方最長一致する登録パターン２を特定する検索部１１の動作を説明する。図６〜図７は、検索部１１の動作を表すフローチャートである。図８〜図９の具体例を併用して、図６、図７のフローチャートを順に説明する。
【００８７】
本例では、図３に示す２つの登録パターン２である”ＡＢＣＤＥＦＧ”と”ＸＹＺ”が登録済みであると仮定する。すなわち、ビットベクトル１２の内容は図４（下）の状態に、ハッシュ表１３の内容は図５（下）の状態に、それぞれ設定されているものとする。また、分割位置リスト１４の内容は｛１０、６、３、１｝である。分割位置リスト１４の各要素を、分割位置５０−Ｘ（Ｘ≧１）と表記する。分割位置５０−１は、分割位置リスト１４の第一要素に対応し、本例では分割位置５０−１は１０である。
【００８８】
プレフィックス抽出部３０及びハッシュ表検索部３３は、検索キー３の入力を待つ（ステップＳ２００）。本例では、検索キー３を”ＡＢＣＤＥＦＧＨ”とする。
【００８９】
プレフィックス抽出部３０は、ループカウンタ”ｉ”を２に初期化する。ループカウンタ”ｉ”は現在着目している分割位置５０のインデックスを表す（ステップＳ２０１）。
【００９０】
プレフィックス抽出部３０は、変数Ｌに分割位置５０−ｉを代入する（ステップＳ２０２）。本例のこの時点ではｉ＝２であるから、Ｌ＝分割位置５０−２＝６になる。
【００９１】
プレフィックス抽出部３０は、検索キー３の長さがＬ以上であるか判定する（ステップＳ２０３）。条件が満たされれば（ステップＳ２０３／Yes）ステップＳ２０４に分岐し、そうでなければ（ステップＳ２０３／No）ステップＳ２１７に分岐する。本例のこの時点では、検索キー３の長さは８であってＬ＝６であるから、条件が成立し（ステップＳ２０３／Yes）、ステップＳ２０４に分岐する。
【００９２】
プレフィックス抽出部３０は、検索キー３の先頭からＬ文字を取り出し、その部分文字列をプレフィックス３４とする（ステップＳ２０４）。本例のこの時点ではＬ＝６であるから、プレフィックス３４は”ＡＢＣＤＥＦ”となる。
【００９３】
プレフィックス抽出部３０は、分割位置５０−（ｉ−１）からＬを減算して分割間隔３５を求める（ステップＳ２０５）。本例のこの時点では、ｉ＝２、Ｌ＝６であるから、分割間隔３５＝（分割位置５０−１）−６＝１０−６＝４になる。
【００９４】
ハッシュ演算部３１は、プレフィックス３４にＭ個のハッシュ関数をかけて、Ｍ個のハッシュ値３６−１〜３６−Ｍを計算する（ステップＳ２０６）。本例では図８（上）のように、プレフィックス３４の”ＡＢＣＤＥＦ”から計算されたハッシュ値３６−１〜３６−２はそれぞれ１と８になる。
【００９５】
パターン長推定部３２は、ビットベクトル１２とハッシュ値３６−１〜３６−Ｍ、分割間隔３５から、オフセットビットマップ５２を算出する（ステップＳ２０７）。オフセットビットマップ５２の有効なビット幅は分割間隔３５に等しい。本例では、分割間隔３５は４であるから、オフセットビットマップ５２の幅は４ビットになる。
【００９６】
オフセットビットマップ５２の左から（Ｘ＋１）ビット目（０≦Ｘ＜分割間隔３５）の値は、ビットベクトル１２の、ハッシュ値３６−１にＸを加算した値に等しいアドレスの内容と、ビットベクトル１２の、ハッシュ値３６−２にＸを加算した値に等しいアドレスの内容と、（中略）、ビットベクトル１２の、ハッシュ値３６−ＭにＸを加算した値に等しいアドレスの内容との論理積である。
【００９７】
ここで、パターン長推定部３２は、参照されるアドレスがビットベクトル１２の範囲外にならないようにするため、ハッシュ値３６とＸの加算結果をビットベクトル１２の要素数で割った剰余を、実際にアクセスするビットベクトル１２のアドレスとして用いる。
【００９８】
本例では、ハッシュ値３６−１〜３６−２がそれぞれ１と８であるから、オフセットビットマップ５２は、図８（下）のように、ビットベクトル１２のアドレス”１”からアドレス”４”までの４ビットと、アドレス”８”からアドレス”１１”までの４ビットとの論理積、すなわち”０１００”になる。
【００９９】
パターン長推定部３２は、ループカウンタ”ｊ”を、分割間隔３５から１を減じた数値に初期化する（ステップＳ２０８）。ループカウンタ”ｊ”は、現在着目しているオフセットビットマップ５２のビットのインデックスを表す。本例では、分割間隔３５は４であるから、ｊ＝３になる。
【０１００】
パターン長推定部３２は、オフセットビットマップ５２の左から（ｊ＋１）ビット目が１であるか否かを判定する（ステップＳ２０９）。１であれば（ステップＳ２０９／Yes）、ステップＳ２１０に分岐し、０であれば（ステップＳ２０９／No）、ステップＳ２１５に分岐する。本例のこの時点では、オフセットビットマップ５２＝”０１００”、ｊ＝３であるから、オフセットビットマップ５２の左から４ビット目が参照される。その値は０であるから（ステップＳ２０９／No）、ステップＳ２１５に分岐する。
【０１０１】
パターン長推定部３２は、ループカウンタ”ｊ”から１を減算する（ステップＳ２１５）。本例のこの時点では、ｊは３から２に変化する。
【０１０２】
パターン長推定部３２は、ループカウンタ”ｊ”に対応するループの継続を判定する（ステップＳ２１６）。ｊが０以上であれば（ステップＳ２１６／Yes）、ステップＳ２０９に戻り、そうでなければ（ステップＳ２１６／No）、ループを抜けて図６のステップＳ２１７に遷移する。本例のこの時点では、ｊ＝２であるから（ステップＳ２１６／Yes）、ループは継続されてステップＳ２０９に戻る。
【０１０３】
ステップＳ２０９の動作は説明済みであるので省略する。本例のこの時点では、オフセットビットマップ５２＝”０１００”、ｊ＝２であるから、パターン長推定部３２により、オフセットビットマップ５２の左から３ビット目が参照される。その値は０であるから（ステップＳ２０９／No）、ステップＳ２１５に分岐する。
【０１０４】
パターン長推定部３２は、ループカウンタ”ｊ”を１減算する（ステップＳ２１５）。本例のこの時点では、ｊは２から１に変化する。
【０１０５】
ステップＳ２１６の動作は説明済みであるので省略する。本例のこの時点では、ｊ＝１であるから（ステップＳ２１６／Yes）、ループは継続されてステップＳ２０９に戻る。
【０１０６】
ステップＳ２０９の動作は説明済みであるので省略する。本例のこの時点では、オフセットビットマップ５２＝”０１００”、ｊ＝１であるから、パターン長推定部３２により、オフセットビットマップ５２の左から２ビット目が参照される。その値は１であるから（ステップＳ２０９／Yes）、今度はステップＳ２１０に分岐する。
【０１０７】
パターン長推定部３２は、プレフィックス３４の長さにループカウンタ”ｊ”を加算した数値を、一致候補の長さ３７とする（ステップＳ２１０）。本例のこの時点では、プレフィックス３４は”ＡＢＣＤＥＦ”であって、その長さは６である。また、ｊ＝１であるから、一致候補の長さ３７は７（＝６＋１）になる。
【０１０８】
ハッシュ表検索部３３は、一致候補の長さ３７が検索キー３の長さ以下であるか否かを判定する（ステップＳ２１１）。条件が成立すれば（ステップＳ２１１／Yes）、ステップＳ２１２に分岐し、そうでなければ（ステップＳ２１１／No）、ステップＳ２１５に分岐する。本例のこの時点では、一致候補の長さ３７は７であって検索キー３の”ＡＢＣＤＥＦＧＨ”の長さは８であるから、本ステップの条件は満たされて（ステップＳ２１１／Yes）、ステップＳ２１２に分岐する。
【０１０９】
ハッシュ表検索部３３は、検索キー３の先頭から、一致候補の長さ３７に等しい文字数の部分文字列を取り出し、その部分文字列を一致候補５３とする（ステップＳ２１２）。本例のこの時点では、一致候補の長さ３７は７であり、検索キー３は”ＡＢＣＤＥＦＧＨ”であるから、一致候補５３はその先頭７文字の”ＡＢＣＤＥＦＧ”になる。
【０１１０】
ハッシュ表検索部３３は、ハッシュ表１３を検索して、一致候補５３に完全一致する登録パターン２がハッシュ表１３の中に存在するか否かを判定する（ステップＳ２１３）。存在していれば（ステップＳ２１３／Yes）、ステップＳ２１４に分岐し、そうでなければ（ステップＳ２１３／No）、ステップＳ２１５に分岐する。本例のこの時点では、一致候補５３は”ＡＢＣＤＥＦＧ”であり、ハッシュ表１３の内容は図５（下）の状態になっている。図５（下）のハッシュ表１３の中には登録パターン２の”ＡＢＣＤＥＦＧ”が存在しているから、本ステップの条件は成立し（ステップＳ２１３／Yes）、ステップＳ２１４に分岐する。
【０１１１】
ハッシュ表検索部３３は、検索成功の通知を行う（ステップＳ２１４）。本ステップに到達したとき、一致候補５３は検索キー３に前方最長一致する登録パターン２に等しいから、ハッシュ表検索部３３は、一致候補５３を検索結果４として出力する。本例のこの時点では、一致候補５３が”ＡＢＣＤＥＦＧ”であるから、検索結果４は”ＡＢＣＤＥＦＧ”になる。
【０１１２】
ステップＳ２１４は検索成功時の最終ステップである。
【０１１３】
上述した本例では、ループカウンタ”ｉ”の１回目のループの実行中に検索成功と判断され検索処理が終了したため、図６のステップＳ２１７〜Ｓ２１９は一度も実行されなかった。以下、それらのステップの動作を説明する。
【０１１４】
パターン長推定部３２は、ループカウンタ”ｉ”に１を加算する（ステップＳ２１７）。
【０１１５】
パターン長推定部３２は、ループカウンタ”ｉ”に対応するループの継続を判定する（ステップＳ２１８）。ｉが分割位置リスト１４の要素数以下であれば（ステップＳ２１８／Yes）、ステップＳ２０２に戻り、そうでなければ（ステップＳ２１８／No）、ループを抜けてステップＳ２１９に遷移する。本例では分割位置リスト１４の内容は｛１０、６、３、１｝であって、その要素数は４であるから、ｉが４以下であれば（ステップＳ２１８／Yes）、ループが継続されることになる。
【０１１６】
ループカウンタ”ｉ”に対応するループが繰り返し実行されるたびに、プレフィックス３４の長さは１段階ずつ短くなっていく。本例では図９に示すように、１回目のループではｉ＝２であるから、プレフィックス３４の長さは分割位置５０−２に等しくなり６文字になる。２回目のループではｉ＝３であるから、プレフィックス３４の長さは分割位置５０−３に等しくなり３文字になる。長いプレフィックス３４から順に評価していく理由は、最長一致検索を行うためである。
【０１１７】
ハッシュ表検索部３３は、検索失敗の通知を行う（ステップＳ２１９）。本ステップに到達したということは、検索キー３に前方最長一致する登録パターン２が存在しないことを意味する。そこで、ハッシュ表検索部３３は、検索失敗を意味する検索結果４を出力する。
【０１１８】
ステップＳ２１９は検索失敗時の最終ステップである。
【０１１９】
以上が本実施形態の検索装置１の構成および動作の詳細であるが、上述した詳細を簡単にまとめると以下のようになる。
【０１２０】
登録を行う場合、まず検索装置１は、登録パターン２または検索キー３の複数の分割位置を格納する分割位置リスト１４の中から登録パターン２の長さを超えない最大の分割位置を１つ選択し、その分割位置を境にして登録パターン２をプレフィックス２４とサフィックスに分割する。次に検索装置１は、プレフィックス２４に対してＭ個（Ｍ≧２）のハッシュ関数を適用してＭ個のハッシュ値２６−１〜２６−Ｍを求め、ハッシュ値２６−１〜２６−Ｍのそれぞれにサフィックス長２５を加算してＭ個の数値を計算する。次に検索装置１は、それらＭ個の数値をビットベクトル１２のＭ個のアドレスとし、それぞれのアドレスの内容を１にセットする。また検索装置１は、登録パターン２をハッシュ表１３に登録する。
【０１２１】
検索を行う場合、まず検索装置１は、分割位置リスト１４の中から検索キー３の長さを超えない分割位置を降順に選択し、その分割位置を境にして検索キー３をプレフィックス３４とサフィックスに分割する。また検索装置１は、隣接する分割位置の差を分割間隔３５とする。次に検索装置１は、プレフィックス３４に対してＭ個のハッシュ関数を適用してＭ個のハッシュ値３６−１〜３６−Ｍを求め、ハッシュ値３６−１〜３６−Ｍのそれぞれに０以上かつ分割間隔３５未満のオフセットを加算してＭ個の数値を計算する。次に検索装置１は、それらＭ個の数値をビットベクトル１２のＭ個のアドレスとし、それらアドレスの内容が全て１であればプレフィックス３４の長さとオフセットを加算して、その加算値を一致候補の長さ３７とする。次に検索装置１は、検索キー３の先頭から一致候補の長さ３７に等しい長さの部分文字列を取り出し、その部分文字列がハッシュ表１３の中に存在するかを判定する。
【０１２２】
ここで、背景技術で説明した関連技術例に対する本実施形態の優位性を説明する。
【０１２３】
本実施形態と関連技術例のいずれもハッシュ表に登録パターンを格納するが、その際のハッシュ値の計算対象が本実施形態と関連技術例とで異なっている。
【０１２４】
関連技術例では図２８のように、登録パターン１００のプレフィックス１０１にハッシュ関数をかけてハッシュ値１０３を計算し、ハッシュ値１０３に対応するハッシュ表１０４のバケットに登録パターン１００を格納する。
【０１２５】
一方、本実施形態では図５のように、登録パターン２の全域にハッシュ関数をかけてハッシュ値を計算し、そのハッシュ値に対応するハッシュ表１３のバケットに登録パターン２を格納する。
【０１２６】
関連技術例では、ハッシュ値の計算対象がプレフィックス１０１に限られているため、プレフィックス１０１が共通でサフィックス１０２が異なるような登録パターン１００が多数存在していると、ハッシュ表１０４においてハッシュ値１０３の衝突が頻発し、長大な連結リストが構築される。例えば、図３０のような状態になる。ハッシュ法においては、広く知られているように、ハッシュ値の衝突確率もしくは連結リストの平均長は、登録および検索の速度を大きく左右する。
【０１２７】
一方、本実施形態では、ハッシュ値の計算対象は登録パターン２の全域であるから、プレフィックス２４が共通でサフィックス５１が異なるような登録パターン２が多数存在していても、ハッシュ表１３においてハッシュ値の衝突が頻発する確率は極めて小さい。その理由は、サフィックス５１の部分もハッシュ値の計算対象に含まれているために、ハッシュ値が偏らずに一様に分布しやすいからである。
【０１２８】
さて、本実施形態では、登録時にビットベクトル１２を更新する必要があり、また、検索時にオフセットビットマップ５２の算出のためにビットベクトル１２を参照する必要がある。これらの処理は関連技術例には含まれない。これらの処理量について言及する。
【０１２９】
ビットベクトル１２の更新は図２のフローチャートのステップＳ１０１〜ステップＳ１０５にて行われ、オフセットビットマップ５２の算出は図６のフローチャートのステップＳ２０４〜ステップＳ２０７にて行われる。処理の内容から明らかなように、これらの処理量は、プレフィックスが共通でサフィックスが異なるような登録パターンが多数存在しているか否かに関わらず、ほぼ一定である。
【０１３０】
ゆえに、関連技術例の効率が登録パターン２の形状の分布に影響されやすいこととは対照的に、本実施形態による検索装置１はその影響をほとんど受けずに安定した性能を発揮するという利点を有する。
【０１３１】
以上のことから、本実施形態によれば、前方または後方の最長一致検索において、ハッシュ値の衝突確率を小さくしてトータルの検索速度を向上させることができる。その理由は、検索キーに最長一致する可能性のある登録パターンの長さを事前に推定し、検索キーと照合すべきパターンの個数を絞り込むので、何の事前情報も無しにハッシュ表を探索する場合と比べて、ハッシュ表の参照回数を減少させることができる為である。また、同じ理由により、検索キーの一部分とハッシュ表の中にある登録パターンとを直接的に照合できるため、登録パターンをプレフィックスとサフィックスに分離してハッシュ表に登録する必要が無くなり、共通のプレフィックスを持つ登録パターンが多数存在していても検索速度が低下しなくなる。
【０１３２】
なお、本実施形態による検索装置１は前方最長一致検索を行うものであるが、僅かな変更で後方最長一致検索に転用できる。具体的には、図２のフローチャートのステップＳ１０２と、図６のフローチャートのステップＳ２０４、図７のフローチャートのステップＳ２１２の３箇所にある「〜の先頭からＸ文字を〜」という記述を「〜の末尾からＸ文字を〜」に置換するだけで、検索装置１は後方最長一致の検索器として機能するようになる。なお、上述した前方最長一致検索の場合では、プレフィックスを第１文字列、サフィックスを第２文字列と呼ぶことができるが、後方最長一致検索の場合では、サフィックスを第１文字列、プレフィックスを第２文字列と呼ぶことができる。
【０１３３】
検索装置１のビットベクトル１２の各要素は２値のビットではなく多値の数値であっても良い。多値にした場合、図２のフローチャートのステップＳ１０５においてビットベクトル１２を更新する際に、対象のアドレスの内容を増減させる。例えば１を加算する。また、図６のフローチャートのステップＳ２０７においてビットベクトル１２を参照する際に、対象のアドレスの内容が０であればビット“０”、０以外であればビット“１”とみなして論理積を計算する。
【０１３４】
検索装置１のハッシュ表１３の代わりに、完全一致検索を実施できる別の検索手段を用いても良い。例えば、二分探索木などを採用できる。
【０１３５】
以上、本発明の実施形態について説明したが、上記実施形態に限定されるものではなく、その要旨を逸脱しない範囲において種々の変形が可能である。
【０１３６】
例えば、上記実施形態の検索装置１では、図１において、登録部１０と検索部１１とで各部をそれぞれ設ける構成としたが、両部を統合し、登録時と検索時とで上述した機能、動作を切り替えるようにしてもよい。例えば、プレフィックス抽出部２０とプレフィックス抽出部３０を一つに統合し、また、ハッシュ演算部２１とハッシュ演算部３１も一つに統合する。また、ハッシュ表登録部２３とハッシュ表検索部３３はともに、ハッシュ表１３へアクセス（更新・参照）する機能が共通であるので一つに統合する。また、ビットベクトル更新部２２とパターン長推定部３２はともに、ビットベクトル１２へアクセス（更新・参照）する機能が共通であるので一つに統合する。
【０１３７】
また、例えば、上記実施形態の検索装置１は、例えばＰＣ（Personal Computer）等の情報処理装置に適用できる。図１０は、本発明の検索装置を情報処理装置に適用した構成例を示すブロック図である。
【０１３８】
図１０に示す例では、データ処理装置２０１と、記憶装置２０２とで構成される。データ処理装置２０１は、ＣＰＵ等の制御装置である。データ処理装置２０１は、登録手段２１０と、検索手段２１１とを有している。登録手段２１０および検索手段２１１は、図１に示す登録部１０および検索部１１と同様に機能、動作するので、ここでの説明は省略する。登録手段２１０は、プレフィックス抽出手段２２０、ハッシュ演算手段２２１、ビットベクトル更新手段２２２、ハッシュ表登録手段２２３を有する。これら登録手段２１０内の各手段は、図１に示す各部（プレフィックス抽出部２０、ハッシュ演算部２１、ビットベクトル更新部２２、ハッシュ表登録部２３）と同様に機能、動作するので、ここでの説明は省略する。また、検索手段２１１は、プレフィックス抽出手段２３０、ハッシュ演算手段２３１、パターン長推定手段２３２、ハッシュ表検索手段２３３を有する。これら検索手段２１１内の各手段は、図１に示す各部（プレフィックス抽出部３０、ハッシュ演算部３１、パターン長推定部３２、ハッシュ表検索部３３）と同様に機能、動作するので、ここでの説明は省略する。また、記憶装置２０２には、図１で説明したものと同じである、分割位置リスト１４、ビットベクトル１２、ハッシュ表１３がそれぞれ格納される。記憶装置２０２は、ＨＤＤ等の記録媒体である。
【０１３９】
例えば、上述した実施形態における動作（各フローチャートに示す動作）は、ハードウェア、または、ソフトウェア、あるいは、両者の複合構成によって実行することも可能である。
【０１４０】
ソフトウェアによる処理を実行する場合には、処理シーケンスを記録したプログラムを、専用のハードウェアに組み込まれているコンピュータ内のメモリにインストールして実行させてもよい。あるいは、各種処理が実行可能な汎用コンピュータにプログラムをインストールして実行させてもよい。
【０１４１】
例えば、プログラムは、記録媒体としてのハードディスクやＲＯＭ（Read Only Memory）に予め記録しておくことが可能である。あるいは、プログラムは、ＣＤ−ＲＯＭ(Compact Disc Read Only Memory)，ＭＯ(Magneto optical)ディスク，ＤＶＤ(Digital Versatile Disc)、磁気ディスク、半導体メモリなどのリムーバブル記録媒体に、一時的、あるいは、永続的に格納（記録）しておくことが可能である。このようなリムーバブル記録媒体は、いわゆるパッケージソフトウエアとして提供することが可能である。
【０１４２】
なお、プログラムは、上述したようなリムーバブル記録媒体からコンピュータにインストールする他、ダウンロードサイトから、コンピュータに無線転送してもよい。または、ＬＡＮ(Local Area Network)、インターネットといったネットワークを介して、コンピュータに有線で転送してもよい。コンピュータでは、転送されてきたプログラムを受信し、内蔵するハードディスク等の記録媒体にインストールすることが可能である。
【０１４３】
また、上記実施形態で説明した処理動作に従って時系列的に実行されるのみならず、処理を実行する装置の処理能力、あるいは、必要に応じて並列的にあるいは個別に実行するように構築することも可能である。
【０１４４】
〔第２の実施形態〕
図１１は、文字列に対する前方最長一致検索を行う検索装置５の構成を示すブロック図である。
【０１４５】
なお、本実施形態において、文字列を構成する各々の文字は、人間が認識可能な文字に限定されずバイナリデータであってもよい。また、１文字を表現するために必要なビット数に制限はなく、必ずしも１文字が１バイトで表される必要はない。
【０１４６】
検索装置５の構成要素は、登録パターン２を登録する登録部４０と、登録済みの１つ以上の登録パターン２の中から検索キー３に前方最長一致するものを探す検索部４１と、１つ以上の登録パターン２が格納されるハッシュ表１３と、検索キー３に最長一致する可能性のある登録パターン２の長さを推定するための情報源であるビットベクトル１２と、登録済みの１つ以上の登録パターン２の長さを記録する登録オフセットビットマップ４５、である。これら各部は、ハードウェア構成として、回路基板やメモリチップなどのデバイスによって実現されるようにしてもよい。
【０１４７】
なお、検索装置５は、ハードウェア構成として、例えば、ＣＰＵ（Central Processing Unit）、ＣＰＵを制御するプログラム（本発明の一実施形態である検索プログラム）等の固定的なデータを予め格納したＲＯＭ（Read Only Memory）、各種データを一時的に記憶するエリアを形成するＲＡＭ（Random Access Memory）、ＨＤＤ（Hard Disk Drive）等の記録媒体を有するようにしてもよい。よって、登録部４０と検索部４１は、ＣＰＵ、ＲＯＭ、ＲＡＭによって実現されるようにしてもよい。また、ハッシュ表１３、ビットベクトル１２および登録オフセットビットマップ４５は、ＲＡＭ又は記録媒体によって実現されるようにしてもよい。
【０１４８】
ハッシュ表１３は、後述の検索部４１のハッシュ表検索部８３において、登録パターン２の完全一致（Exact Match）検索に使用される。ハッシュを使ったデータ構造および完全一致検索方法は公知のものである。従って、ハッシュ表１３は既存のハッシュ法により容易に実現できる。初期状態ではハッシュ表１３の内容は空（Empty）である。
【０１４９】
ビットベクトル１２は、ビット（数値）の１次元配列であり、その内容の初期値は全て０である。
【０１５０】
登録オフセットビットマップ４５は、ビット（数値）の１次元配列であり、その内容の初期値は全て０である。
【０１５１】
登録部４０は、未登録の文字列である登録パターン２を入力とし、それをビットベクトル１２とハッシュ表１３、登録オフセットビットマップ４５に登録する動作を行う。
【０１５２】
登録部４０の構成要素は、ハッシュ計算対象となる１つ以上の部分文字列（文字列の一部分）を登録パターン２の中から抽出するプレフィックス抽出部６０、その部分文字列に対して複数のハッシュ関数をかけて複数のハッシュ値を計算するハッシュ演算部２１、ビットベクトル１２および後述されるオフセットビットマップにおけるビット単位のオフセットと文字列の長さとの関係が格納される長さ−オフセット対応表６７、長さ−オフセット対応表６７を参照して登録パターン２のうちハッシュ計算対象にならなかった部分文字列の長さに対応するオフセットを求めるオフセット決定部６８、ハッシュ値とオフセットが指し示すビットベクトル１２中のビットの内容を更新するビットベクトル更新部６２、長さ−オフセット対応表６７を参照して登録パターン２の長さに対応するオフセットを求めそのオフセットが指し示す登録オフセットビットマップ４５中のビットの内容を更新する登録オフセットビットマップ更新部６９、ハッシュ表１３に登録パターン２を登録するハッシュ表登録部２３、である。
【０１５３】
プレフィックス抽出部６０は、登録パターン２の先頭から部分文字列を切り出し、その部分文字列をプレフィックス２４としてハッシュ演算部２１に出力する。プレフィックス２４の長さは、ストライド５４の倍数かつ、登録パターン２の長さ以下である。
【０１５４】
ストライド５４は２以上の整数であり、プレフィックス２４の長さの増分である。ストライド５４は長さ−オフセット対応表６７の内容と密接に関係する。
【０１５５】
ストライド５４が３のときの、長さ−オフセット対応表６７の一例を図１２に示す。長さ−オフセット対応表６７は、長さの列とオフセットの列から構成される。オフセットの列の内容は表の上から順に０、１、２、…、のように連番になる。長さの列の１行目からＳ行目までの内容は、０、１、２、…、のように連番になる。ここで、Ｓはストライド５４である。長さの列の（Ｓ＋Ｎ）行目の内容は「（Ｓ×Ｎ）以上｛Ｓ×（Ｎ＋１）｝未満」である。ここで、Ｎは自然数である。長さの列の最終行の内容は「｛Ｓ×（Ｗ−Ｓ）｝以上」である。ここで、Ｗはウィンドウサイズ５５である。ウィンドウサイズ５５は、長さ−オフセット対応表６７の行数に等しい。ウィンドウサイズ５５は（Ｓ＋２）以上でなければならない。図１２の長さ−オフセット対応表６７においては、ウィンドウサイズ５５は６である。
【０１５６】
プレフィックス抽出部６０は、１つの登録パターン２について１つ以上のプレフィックス２４を生成する。プレフィックス抽出部６０は、プレフィックス２４を１つ生成するたびに、登録パターン２の長さからプレフィックス２４の長さを減算してサフィックス長２５を求め、それをオフセット決定部６８に出力する。このように、プレフィックス抽出部６０は、登録パターン２をプレフィックス（第１文字列）とサフィックス（第２文字列）とに分割するので、サフィックス抽出部と呼ぶこともできる。
【０１５７】
ハッシュ演算部２１は、プレフィックス２４に対して、Ｍ個のハッシュ関数をかけてＭ個のハッシュ値２６−１〜２６−Ｍを求め、それらをビットベクトル更新部６２に送出する。ここで、Ｍは２以上の整数である。ハッシュの衝突を抑えるため、Ｍ個のハッシュ関数は互いに相関の無いハッシュ値２６−１〜２６−Ｍを生成するものであることが望ましい。
【０１５８】
オフセット決定部６８は、長さ−オフセット対応表６７を参照して、サフィックス長２５に対応するオフセット７０を求め、それをビットベクトル更新部６２に出力する。例えば、図１２の長さ−オフセット対応表６７の場合、サフィックス長２５が５のときオフセット７０は３になる。
【０１５９】
ビットベクトル更新部６２は、ビットベクトル１２の中のＭ個のビットを１にセットする。１にセットされるビットのアドレスは、ハッシュ値２６−１〜２６−Ｍとオフセット７０から決まる。ビットベクトル更新部６２の動作の詳細は後述する。
【０１６０】
登録オフセットビットマップ更新部６９は、長さ−オフセット対応表６７を参照して、登録パターン２の長さに対応するオフセットを求め、そのオフセットが指し示す登録オフセットビットマップ４５中のビットを１にセットする。登録オフセットビットマップ４５の要素数は、ウィンドウサイズ５５に等しい。例えば、登録パターン２の長さが２のとき、図１２の長さ−オフセット対応表６７を参照するとオフセットは２であるから、登録オフセットビットマップ更新部６９は登録オフセットビットマップ４５のビット”２”すなわち左から３（＝２＋１）番目のビットを１にセットする。
【０１６１】
このように、登録オフセットビットマップ４５の左から（Ｘ＋１）番目のビットの内容は、長さ−オフセット対応表６７におけるオフセット”Ｘ”に対応する長さの登録パターン２が検索装置５に１つでも登録されているときに１になり、１つも登録されていないときに０になる。
【０１６２】
ハッシュ表登録部２３は、登録パターン２をハッシュ表１３に追加する。この際、登録パターン２の全域に対してハッシュ関数をかけてハッシュ値を計算する。なお、ハッシュ表登録部２３で用いられるハッシュ関数と、ハッシュ演算部２１で使われるハッシュ関数との間に関連はない。
【０１６３】
検索部４１は、文字列である検索キー３を入力とし、検索キー３に前方最長一致する登録パターン２を特定するためにビットベクトル１２とハッシュ表１３を探索して、その結果を検索結果４として出力する。
【０１６４】
検索部４１の構成要素は、ハッシュ計算対象となる１つ以上の部分文字列（文字列の一部分）を検索キー３の中から抽出するプレフィックス抽出部８０、その部分文字列に対して複数のハッシュ関数をかけて複数のハッシュ値を計算するハッシュ演算部３１、ハッシュ値が指し示すビットベクトル１２の内容を参照して検索キー３に前方最長一致する可能性のある登録パターン２の長さを推定するパターン長推定部８２、推定された長さに等しい部分文字列を検索キー３の先頭から取り出してその部分文字列に完全一致する登録パターン２がハッシュ表１３の中に存在するか否かを判定するハッシュ表検索部８３、プレフィックス抽出部８０において抽出される部分文字列の長さを決定するための情報源である累積オフセットビットマップ８９、累積オフセットビットマップ８９の更新を制御する累積オフセットビットマップ管理部８８、である。
【０１６５】
プレフィックス抽出部８０は、検索キー３の先頭から部分文字列を切り出し、その部分文字列をプレフィックス３４としてハッシュ演算部３１に出力する。プレフィックス３４の長さは、ストライド５４の倍数に等しく、累積オフセットビットマップ８９の内容から決定される。
【０１６６】
累積オフセットビットマップ８９は、ビットの１次元配列であり、その要素数はウィンドウサイズ５５に等しい。基本的には、累積オフセットビットマップ８９の左から（Ｓ＋Ｎ）番目のビットの内容が１のとき、プレフィックス３４の長さは（Ｓ×Ｎ）文字になる。ここで、Ｓはストライド５４であり、Ｎは自然数である。
【０１６７】
累積オフセットビットマップ８９において１が立っているビットが複数存在する場合、プレフィックス抽出部８０は、それらのうち最も左のビットに対応する長さのプレフィックス３４を出力する。すなわち、プレフィックス抽出部８０は、１つの検索キー３について、１つ以上のプレフィックス３４を短いものから順に生成する。
【０１６８】
後述するが、累積オフセットビットマップ８９は、累積オフセットビットマップ管理部８８によって１ビットずつ左方向にシフトされる。このシフトが行われる度に、プレフィックス３４の長さがＳずつプラス方向に補正される。
【０１６９】
このように、プレフィックス抽出部８０は、検索キー３をプレフィックス（第１文字列）とサフィックス（第２文字列）とに分割するので、サフィックス抽出部と呼ぶこともできる。
【０１７０】
ハッシュ演算部３１は、プレフィックス３４に対してＭ個のハッシュ関数をかけてＭ個のハッシュ値３６−１〜３６−Ｍを求め、それらをパターン長推定部８２に送出する。ハッシュ関数の個数すなわちＭとハッシュ関数の形状は、登録部４０のハッシュ演算部２１のものと同一でなければならない。
【０１７１】
パターン長推定部８２は、Ｍ個のＷビット幅のビット列をビットベクトル１２から読み出し、それらビット列の論理積を求め、その論理積をオフセットビットマップ５２として累積オフセットビットマップ管理部８８に送出する。ここで、Ｗはウィンドウサイズ５５である。オフセットビットマップ５２は、ビットの１次元配列であり、その要素数はウィンドウサイズ５５に等しい。参照されるビットベクトル１２のＭ箇所のアドレスは、Ｍ個のハッシュ値３６−１〜３６−Ｍによって決まる。さらにパターン長推定部８２は、求めたオフセットビットマップ５２から、検索キー３に前方最長一致する可能性のある登録パターン２の長さを推定し、その推定された長さを一致候補の長さ３７としてハッシュ表検索部８３に出力する。
【０１７２】
ハッシュ表検索部８３は、一致候補の長さ３７に等しい長さの部分文字列を検索キー３の先頭から取り出し、その部分文字列を一致候補５３とする。その後、ハッシュ表検索部８３はハッシュ表１３を検索し、一致候補５３に完全一致する登録パターン２がハッシュ表１３の中に存在しているか否かを判定する。なお、この検索で用いられるハッシュ関数およびハッシュアルゴリズムは、登録部４０のハッシュ表登録部２３と同一でなければならない。一致候補５３に完全一致する登録パターン２が発見された場合は、一致候補５３を検索結果４として出力する。発見されなければ検索失敗を意味する検索結果４を出力する。
【０１７３】
累積オフセットビットマップ管理部８８は、検索キー３が検索部４１に入力されたとき、累積オフセットビットマップ８９の内容を登録オフセットビットマップ４５の内容で初期化する。また、累積オフセットビットマップ管理部８８は、プレフィックス抽出部８０の動作中に、累積オフセットビットマップ８９を１ビットずつ左方向にシフトする。ただし、このシフトの際、累積オフセットビットマップ８９の最右ビットの内容が前置保持されるようにする。さらに、累積オフセットビットマップ管理部８８は、パターン長推定部８２からオフセットビットマップ５２を受け取るたびに、そのオフセットビットマップ５２の内容と累積オフセットビットマップ８９の内容の論理積を計算し、その論理積を累積オフセットビットマップ８９に代入する。
【０１７４】
次に、文字列に対する前方最長一致検索を行う検索装置５の動作を述べる。
【０１７５】
まず、登録パターン２の登録を行う登録部４０の説明から開始する。図１３は、登録部４０の動作を表すフローチャートである。図１４〜図２０の具体例を併用して、図１３のフローチャートを説明する。
【０１７６】
本例では、２つの登録パターン２である”ＡＢＣＤＥＦＧＨＩＪ”（長さ１０文字）と”ＸＹＺ”が、順に１つずつ検索装置５に登録されると仮定する。また、ストライド５４を３とし、登録部４０の長さ−オフセット対応表６７の内容が図１２に示される通りであるとする。ウィンドウサイズ５５は６である。
【０１７７】
１つ目の登録パターン２の登録処理を開始する。
【０１７８】
プレフィックス抽出部６０およびハッシュ表登録部２３、登録オフセットビットマップ更新部６９は、登録パターン２の入力を待つ（ステップＳ３００）。本例では、登録パターン２は”ＡＢＣＤＥＦＧＨＩＪ”の１０文字になる。
【０１７９】
ステップＳ３００の後は、ステップＳ３０１とステップＳ３０２、ステップＳ３０３へ進む。ステップＳ３０１とステップＳ３０２、ステップＳ３０３〜ステップＳ３１０は、並列実行可能である。なお、並列実行は必須ではない。
【０１８０】
ハッシュ表登録部２３は、ハッシュ表１３に登録パターン２を追加する（ステップＳ３０１）。本例では、図１４のように登録パターン２がハッシュ表１３に追加される。
【０１８１】
登録オフセットビットマップ更新部６９は、長さ−オフセット対応表６７を参照して、登録パターン２の長さに対応するオフセットを求め、登録オフセットビットマップ４５の左から（Ｘ＋１）番目のビットを１にセットする（ステップＳ３０２）。ここでＸは、求めたオフセットである。本例では、登録パターン２の長さは１０文字であり、図１２の長さ−オフセット対応表６７を参照すると、長さ”１０”に対応するオフセットが５であることが分かる。従って、図１５のように登録オフセットビットマップ４５の左から６（＝５＋１）番目のビットが１にセットされる。
【０１８２】
プレフィックス抽出部６０は、プレフィックス２４の長さ”Ｌ”をストライド５４で初期化する（ステップＳ３０３）。本例ではストライド５４は３であるから、Ｌ＝３となる。
【０１８３】
プレフィックス抽出部６０は、登録パターン２の長さがＬ以上であるか否かを判定する（ステップＳ３０４）。登録パターン２の長さがＬ以上であればステップＳ３０５およびステップＳ３０７に遷移し、そうでなければステップＳ３０１とステップＳ３０２の処理の完了を待って登録部４０の処理を終了させる。本例では、登録パターン２の長さが１０文字であってＬ＝３であるからステップＳ３０４の条件は成立し、ステップＳ３０５およびステップＳ３０７に遷移する。
【０１８４】
ステップＳ３０５〜ステップＳ３０６とステップＳ３０７〜ステップＳ３０８は、並列実行可能である。なお、並列実行は必須ではない。
【０１８５】
プレフィックス抽出部６０は、登録パターン２の先頭からＬ文字を取り出し、その部分文字列をプレフィックス２４とする（ステップＳ３０５）。本例では、プレフィックス２４の長さが３文字（Ｌ＝３）であるから、プレフィックス２４は図１６（上）のように”ＡＢＣ”になる。
【０１８６】
ハッシュ演算部２１は、プレフィックス２４にＭ個のハッシュ関数をかけて、Ｍ個のハッシュ値２６−１〜２６−Ｍを計算する（ステップＳ３０６）。本例ではハッシュ関数の個数Ｍを２とし、プレフィックス２４”ＡＢＣ”から計算されたハッシュ値２６−１〜２６−２が図１６のように、それぞれ１と３になると仮定する。
【０１８７】
プレフィックス抽出部６０は、登録パターン２の長さからＬを減算してサフィックス長２５を求める（ステップＳ３０７）。本例では、サフィックス長２５は７（＝１０−３）になる。
【０１８８】
オフセット決定部６８は、長さ−オフセット対応表６７を参照して、サフィックス長２５に対応するオフセット７０を求める（ステップＳ３０８）。本例では、サフィックス長２５は７であるから、図１２の長さ−オフセット対応表６７を参照するとオフセットとして４が得られ、オフセット７０は４となる。
【０１８９】
ステップＳ３０６とステップＳ３０８の処理がともに終了した時点で、ステップＳ３０９に遷移する。
【０１９０】
ビットベクトル更新部６２は、ビットベクトル１２の中のＭ個のビットを１にセットする（ステップＳ３０９）。ビットベクトル１２において１がセットされるビットのアドレスは、ハッシュ値２６−１とオフセット７０の和をＢで割った剰余、ハッシュ値２６−２とオフセット７０の和をＢで割った剰余、（中略）、ハッシュ値２６−Ｍとオフセット７０の和をＢで割った剰余、のＭ個である。ここでＢは、ビットベクトル１２の要素数である。剰余を使用している理由は、ハッシュ値２６−Ｘ（１≦Ｘ≦Ｍ）とオフセット７０の和がビットベクトル１２の長さを超えてしまい、１にセットされるアドレスがビットベクトル１２の範囲外になる事態を防ぐためである。本例では図１６（下）のように、１にセットされるアドレスは、５（＝（１＋４）mod １６）と７（＝（３＋４）mod １６）である。
【０１９１】
プレフィックス抽出部６０は、プレフィックス２４の長さ”Ｌ”にストライド５４を加算する（ステップＳ３１０）。本例ではＬ＝６（＝３＋３）になる。その後、ステップＳ３０４へ戻る。
【０１９２】
本例では、登録パターン２の長さが１０文字であってＬ＝６であるからステップＳ３０４の条件は成立し、ステップＳ３０５およびステップＳ３０７に遷移する。
【０１９３】
ステップＳ３０５〜ステップＳ３１０の説明は既に終えているので、本例での結果のみを記す。
【０１９４】
ステップＳ３０５において、Ｌ＝６であるからプレフィックス２４は”ＡＢＣＤＥＦ”になる。
【０１９５】
ステップＳ３０６において、プレフィックス２４の”ＡＢＣＤＥＦ”から計算されたハッシュ値２６−１〜２６−２が図１７のように、それぞれ３と１０になると仮定する。
【０１９６】
ステップＳ３０７において、登録パターン２の長さが１０文字であってＬ＝６であるから、サフィックス長２５は４（＝１０−６）になる。
【０１９７】
ステップＳ３０８において、図１２の長さ−オフセット対応表６７を参照してサフィックス長２５（＝４）に対応するオフセット７０を求めると、３が得られる。
【０１９８】
ステップＳ３０９において、ビットベクトル１２の中で１にセットされるアドレスは図１７（下）のように、６（＝（３＋３）mod １６）と１３（＝（１０＋３）mod １６）になる。
【０１９９】
ステップＳ３１０において、プレフィックス２４の長さ”Ｌ”にストライド５４を加算し、Ｌ＝９（＝６＋３）となる。その後、ステップＳ３０４へ戻る。
【０２００】
Ｌ＝９であるからステップＳ３０４の条件は成立し、ステップＳ３０５およびステップＳ３０７に遷移する。
【０２０１】
ステップＳ３０５〜ステップＳ３１０の処理が完了すると、ビットベクトル１２の内容は図１８（下）になり、Ｌ＝１２となる。その後、ステップＳ３０４へ戻る。
【０２０２】
この時点ではＬ＝１２であるから、ステップＳ３０４の条件は成立しない。また、ステップＳ３０１とステップＳ３０２の処理は完了しているため、登録部４０の処理は終了し、登録パターン２の”ＡＢＣＤＥＦＧＨＩＪ”の登録が完了する。
【０２０３】
２つ目の登録パターン２の”ＸＹＺ”の登録は上記同様に行われるため、説明は省略し、結果のみを記す。２つの登録パターン２の”ＡＢＣＤＥＦＧＨＩＪ”と”ＸＹＺ”の登録が完了した時点での登録オフセットビットマップ４５とビットベクトル１２の内容は、それぞれ図１９（下）と図２０（下）のようになる。また、このときのハッシュ表１３の内容の例を図１４（下）に示す。
【０２０４】
次に、検索キー３に前方最長一致する登録パターン２を特定する検索部４１の動作を説明する。図２１〜図２２は、検索部４１の動作を表すフローチャートである。図２３〜図２６の具体例を併用して、図２１〜図２２のフローチャートを説明する。
【０２０５】
本例では、登録部４０の動作の説明で使用した２つの登録パターン２の”ＡＢＣＤＥＦＧＨＩＪ”と”ＸＹＺ”が登録済みであると仮定する。すなわち、登録オフセットビットマップ４５の内容は図１９（下）のように”０００１０１”に、ビットベクトル１２の内容は図２０（下）の状態に、ハッシュ表１３の内容は図１４（下）の状態に、それぞれ設定されているものとする。また、登録時と同様にストライド５４は３であり、ウィンドウサイズ５５は６である。
【０２０６】
本例では、２つの検索キー３である”ＡＢＣＤＥＦＧＨＩＪＫ”（長さ１１文字）と”ＺＺＺＺＺＺＺＺＺＺＺＺＺＺＺＺＺＺＺＺ”（長さ２０文字）が、順に１つずつ検索装置５に入力されると仮定する。
【０２０７】
１つ目の検索キー３に対する検索処理を開始する。
【０２０８】
プレフィックス抽出部８０及びハッシュ表検索部８３は、検索キー３の入力を待つ（ステップＳ４００）。本例では、検索キー３は”ＡＢＣＤＥＦＧＨＩＪＫ”になる。
【０２０９】
プレフィックス抽出部８０はプレフィックス３４の長さ”Ｌ”をストライド５４で初期化して、累積オフセットビットマップ管理部８８は累積オフセットビットマップ８９の内容を登録オフセットビットマップ４５の内容で初期化し、さらに、ハッシュ表検索部８３は１つ以上の一致候補の長さ３７を一時的に蓄積するスタックを空に初期化する（ステップＳ４０１）。本例では、Ｌ＝３になり、累積オフセットビットマップ８９の内容は図２３のＡ段のように”０００１０１”になる。
【０２１０】
プレフィックス抽出部８０は、検索キー３の長さがＬ以上であるか否かを判定する（ステップＳ４０２）。検索キー３の長さがＬ以上であればステップＳ４０３に遷移し、そうでなければステップＳ４１７に遷移する。本例では、検索キー３の長さが１１文字であってＬ＝３であるから条件は成立し、ステップＳ４０３に遷移する。
【０２１１】
累積オフセットビットマップ管理部８８は累積オフセットビットマップ８９の内容を１ビット左方向にシフトする（ステップＳ４０３）。ただし、この際、累積オフセットビットマップ８９の最右ビットの内容がシフトの前後で変化しないようにする。本例では、累積オフセットビットマップ８９の内容は、図２３のＢ段のように”００１０１１”になる。
【０２１２】
プレフィックス抽出部８０は、累積オフセットビットマップ８９の左からＳ番目のビットの内容が１であるか否かを判定する（ステップＳ４０４）。ここで、Ｓはストライド５４である。そのビットの内容が１であればステップＳ４０５に分岐し、そうでなければステップＳ４１６に分岐する。本例では、累積オフセットビットマップ８９の内容は”００１０１１”であって、その左から３番目のビットの内容は１であるから、ステップＳ４０４の条件は成立してステップＳ４０５に遷移する。
【０２１３】
プレフィックス抽出部８０は、検索キー３の先頭からＬ文字を取り出し、その部分文字列をプレフィックス３４とする（ステップＳ４０５）。本例ではＬ＝３であるから、プレフィックス３４は”ＡＢＣ”となる。
【０２１４】
ハッシュ演算部３１は、プレフィックス３４にＭ個のハッシュ関数をかけて、Ｍ個のハッシュ値３６−１〜３６−Ｍを計算する（ステップＳ４０６）。本例では、プレフィックス３４の”ＡＢＣ”から計算されたハッシュ値３６−１〜３６−２は図２４のように、それぞれ１と３になる。
【０２１５】
パターン長推定部８２は、Ｍ個のＷビット幅のビット列をビットベクトル１２から読み出し、それらビット列の論理積を算出して、その論理積をオフセットビットマップ５２とする（ステップＳ４０７）。ここで、Ｗはウィンドウサイズ５５である。参照されるビットベクトル１２のＭ箇所のアドレスは、Ｍ個のハッシュ値３６−１〜３６−Ｍによって決まる。具体的には、オフセットビットマップ５２の左から（Ｘ＋１）番目（０≦Ｘ＜Ｗ）のビットの内容は、ビットベクトル１２の、ハッシュ値３６−１とＸの和に等しいアドレスの内容と、ビットベクトル１２の、ハッシュ値３６−２とＸの和に等しいアドレスの内容と、（中略）、ビットベクトル１２の、ハッシュ値３６−ＭとＸの和に等しいアドレスの内容との論理積である。
【０２１６】
ここで、パターン長推定部８２は、参照するアドレスがビットベクトル１２の範囲外にならないようにするため、ハッシュ値３６とＸの和をビットベクトル１２の要素数で割った剰余を、実際にアクセスするビットベクトル１２のアドレスとして用いる。
【０２１７】
本例では、ハッシュ値３６−１〜３６−２がそれぞれ１と３であるから、オフセットビットマップ５２の内容は図２４（下）のように、ビットベクトル１２のアドレス”１”からアドレス”６”までの６ビットの内容と、アドレス”３”からアドレス”８”までの６ビットの内容との論理積、すなわち”００００１０”になる。
【０２１８】
累積オフセットビットマップ管理部８８は、オフセットビットマップ５２の内容と累積オフセットビットマップ８９の内容の論理積を計算し、その論理積を累積オフセットビットマップ８９に代入する（ステップＳ４０８）。本例では、累積オフセットビットマップ８９の内容は、図２３のＣ段のように”００００１０”になる。
【０２１９】
パターン長推定部８２は、ループカウンタ”ｊ”を０に初期化する（ステップＳ４０９）。ループカウンタ”ｊ”は、現在着目しているオフセットビットマップ５２のビットのインデックスを表す。
【０２２０】
パターン長推定部８２は、オフセットビットマップ５２の左から（ｊ＋１）番目のビットの内容が１であるか否かを判定する（ステップＳ４１０）。そのビットの内容が１であればステップＳ４１１に分岐し、そうでなければステップＳ４１４に分岐する。本例では、ｊ＝０であるからオフセットビットマップ５２の左から１番目のビットが参照される。オフセットビットマップ５２の内容は”００００１０”であり、その左から１番目のビットの内容は０であってステップＳ４１０の条件は成立しないため、ステップＳ４１４に遷移する。
【０２２１】
パターン長推定部８２は、ループカウンタ”ｊ”に１を加算する（ステップＳ４１４）。本例では、ｊは０から１に変化する。
【０２２２】
パターン長推定部８２は、ループカウンタ”ｊ”に対応するループの継続を判定する（ステップＳ４１５）。ｊがストライド５４より小さければループ先頭のステップＳ４１０に戻り、そうでなければステップＳ４１６に遷移する。本例では、ｊ＝１であってストライド５４は３であるから、ループは継続されてステップＳ４１０に戻る。
【０２２３】
本例では、オフセットビットマップ５２の内容が”００００１０”であり、その左から２番目と３番目のビットの内容はともに０であるため、ｊ＝１またはｊ＝２のときもステップＳ４１０の条件は成立しない。従って、ステップＳ４１１〜ステップＳ４１３は一度も実行されることなく、ループカウンタ”ｊ”に対応するループが終了してステップＳ４１６に遷移する。
【０２２４】
プレフィックス抽出部８０は、プレフィックス３４の長さ”Ｌ”にストライド５４を加算する（ステップＳ４１６）。本例ではＬ＝６（＝３＋３）になる。その後、ステップＳ４０２へ戻る。
【０２２５】
Ｌ＝６であるからステップＳ４０２の条件は成立し、ステップＳ４０３に遷移する。
【０２２６】
ステップＳ４０３において、累積オフセットビットマップ８９の内容が１ビット左方向にシフトされ、図２３のＤ段のように”０００１００”になる。
【０２２７】
ステップＳ４０４において、累積オフセットビットマップ８９の内容は”０００１００”であって、その左から３番目のビットの内容は０であるから、条件は成立せずステップＳ４１６に遷移する。
【０２２８】
ステップＳ４１６において、プレフィックス３４の長さ”Ｌ”にストライド５４が加算され、Ｌ＝９（＝６＋３）になる。その後、ステップＳ４０２へ戻る。
【０２２９】
Ｌ＝９であるからステップＳ４０２の条件は成立し、ステップＳ４０３に遷移する。
【０２３０】
ステップＳ４０３において、累積オフセットビットマップ８９の内容が１ビット左方向にシフトされ、図２３のＥ段のように”００１０００”になる。
【０２３１】
ステップＳ４０４において、累積オフセットビットマップ８９の内容は”００１０００”であって、その左から３番目のビットの内容は１であるから、条件は成立してステップＳ４０５に遷移する。
【０２３２】
ステップＳ４０５において、Ｌ＝９であるから、検索キー３の先頭から９文字の部分文字列、すなわち”ＡＢＣＤＥＦＧＨＩ”がプレフィックス３４になる。
【０２３３】
ステップＳ４０６において、プレフィックス３４の”ＡＢＣＤＥＦＧＨＩ”から計算されたハッシュ値３６−１〜３６−２は図２５のように、それぞれ８と６になる。
【０２３４】
ステップＳ４０７において、ハッシュ値３６−１〜３６−２がそれぞれ８と６であるから、オフセットビットマップ５２の内容は図２５（下）のように、ビットベクトル１２のアドレス”８”からアドレス”１３”までの６ビットの内容と、アドレス”６”からアドレス”１１”までの６ビットの内容との論理積、すなわち”０１００００”になる。
【０２３５】
ステップＳ４０８において、累積オフセットビットマップ８９の内容は、オフセットビットマップ５２の内容と累積オフセットビットマップ８９の内容の論理積に更新され、図２３のＦ段のように”００００００”になる。
【０２３６】
ステップＳ４０９において、ループカウンタ”ｊ”は０に初期化される。
【０２３７】
ステップＳ４１０において、ｊ＝０であるからオフセットビットマップ５２の左から１番目のビットが参照される。オフセットビットマップ５２の内容は”０１００００”であり、その左から１番目のビットの内容は０であって条件は成立しないため、ステップＳ４１４に遷移する。
【０２３８】
ステップＳ４１４において、ｊに１が加算されて１になる。
【０２３９】
ステップＳ４１５において、ｊはストライド５４より小さいので、ループカウンタ”ｊ”に対応するループは継続され、ステップＳ４１０へ戻る。
【０２４０】
ステップＳ４１０において、ｊ＝１であるからオフセットビットマップ５２の左から２番目のビットが参照される。オフセットビットマップ５２の内容は”０１００００”であり、その左から２番目のビットの内容は１であって条件が成立するため、ステップＳ４１１に遷移する。
【０２４１】
パターン長推定部８２は、プレフィックス３４の長さにループカウンタ”ｊ”を加算した数値を求め、その数値を一致候補の長さ３７とする（ステップＳ４１１）。本例では、プレフィックス３４は”ＡＢＣＤＥＦＧＨＩ”であり、その長さは９である。また、ｊ＝１であるから、一致候補の長さ３７は１０（＝９＋１）になる。
【０２４２】
ハッシュ表検索部８３は、一致候補の長さ３７が検索キー３の長さ以下であるか否かを判定する（ステップＳ４１２）。一致候補の長さ３７が検索キー３の長さ以下であればステップＳ４１３に分岐し、そうでなければステップＳ４１６に分岐する。本例では、一致候補の長さ３７は１０であって検索キー３の”ＡＢＣＤＥＦＧＨＩＪＫ”の長さは１１であるから、ステップＳ４１２の条件は満たされてステップＳ４１３に遷移する。
【０２４３】
ハッシュ表検索部８３は、一致候補の長さ３７をスタックにプッシュする（ステップＳ４１３）。本例では、スタックの内容は｛１０｝になる。
【０２４４】
ステップＳ４１４において、ｊに１が加算されて２になる。
【０２４５】
ステップＳ４１５において、ｊはストライド５４より小さいので、ループカウンタ”ｊ”に対応するループは継続され、ステップＳ４１０へ戻る。
【０２４６】
ステップＳ４１０において、ｊ＝２であるからオフセットビットマップ５２の左から３番目のビットが参照される。オフセットビットマップ５２の内容は”０１００００”であり、その左から３番目のビットの内容は０であって条件は成立しないため、ステップＳ４１４に遷移する。
【０２４７】
ステップＳ４１４において、ｊに１が加算されて３になる。
【０２４８】
ステップＳ４１５において、ｊはストライド５４より小さくないので、ループカウンタ”ｊ”に対応するループは終了し、ステップＳ４１６に遷移する。
【０２４９】
ステップＳ４１６において、プレフィックス３４の長さ”Ｌ”にストライド５４が加算され、Ｌ＝１２（＝９＋３）になる。その後、ステップＳ４０２へ戻る。
【０２５０】
検索キー３の長さが１１文字であってＬ＝１２であるからステップＳ４０２の条件は成立せず、ステップＳ４１７に遷移する。
【０２５１】
ハッシュ表検索部８３は、スタックが空であるか否かを判定する（ステップＳ４１７）。スタックが空であればステップＳ４２２に分岐し、そうでなければステップＳ４１８に分岐する。本例では、スタックの内容は｛１０｝であって空でないのでステップＳ４１７の条件は成立せず、ステップＳ４１８に遷移する。
【０２５２】
ハッシュ表検索部８３は、スタックから一致候補の長さ３７を１つポップする（ステップＳ４１８）。本例では、ポップされた一致候補の長さ３７は１０となり、スタックは空になる。
【０２５３】
ハッシュ表検索部８３は、検索キー３の先頭からＣ文字の部分文字列を取り出し、その部分文字列を一致候補５３とする（ステップＳ４１９）。ここでＣは、ステップＳ４１８にてスタックからポップされた一致候補の長さ３７である。本例では、ポップされた一致候補の長さ３７は１０であり、検索キー３は ”ＡＢＣＤＥＦＧＨＩＪＫ”であるから、一致候補５３はその先頭１０文字の”ＡＢＣＤＥＦＧＨＩＪ”になる。
【０２５４】
ハッシュ表検索部８３は、ハッシュ表１３を検索して、一致候補５３に完全一致する登録パターン２がハッシュ表１３の中に存在するか否かを判定する（ステップＳ４２０）。存在していればステップＳ４２１に分岐し、そうでなければステップＳ４１７に分岐する。本例では、一致候補５３は”ＡＢＣＤＥＦＧＨＩＪ”であり、ハッシュ表１３の内容は図１４（下）の状態になっている。図１４（下）のハッシュ表１３の中には登録パターン２の１つである”ＡＢＣＤＥＦＧＨＩＪ”が存在しているから、ステップＳ４２０の条件は成立してステップＳ４２１に分岐する。
【０２５５】
ハッシュ表検索部８３は、検索成功の通知を行う（ステップＳ４２１）。ステップＳ４２１に到達したとき、一致候補５３は検索キー３に前方最長一致する登録パターン２に等しいから、ハッシュ表検索部８３は一致候補５３を検索結果４として出力する。本例では、検索結果４は”ＡＢＣＤＥＦＧＨＩＪ”になる。
【０２５６】
ステップＳ４２１は検索成功時の最終ステップである。以上で、検索キー３の”ＡＢＣＤＥＦＧＨＩＪＫ”に対する検索処理は終了する。
【０２５７】
続いて、２つ目の検索キー３に対する検索処理を開始する。
【０２５８】
ステップＳ４００において、検索キー３は”ＺＺＺＺＺＺＺＺＺＺＺＺＺＺＺＺＺＺＺＺ”となる。
【０２５９】
ステップＳ４０１において、プレフィックス３４の長さ”Ｌ”はストライド５４で初期化され、３になる。また、累積オフセットビットマップ８９の内容は登録オフセットビットマップ４５の内容で初期化され、”０００１０１”になる。さらに、１つ以上の一致候補の長さ３７を一時的に蓄積するスタックは空に初期化される。
【０２６０】
検索キー３の長さは２０文字であってＬ＝３であるから、ステップＳ４０２の条件は成立し、ステップＳ４０３に遷移する。
【０２６１】
ステップＳ４０３において、累積オフセットビットマップ８９の内容が１ビット左方向にシフトされ、”００１０１１”になる。
【０２６２】
ステップＳ４０４において、累積オフセットビットマップ８９の内容は”００１０１１”であって、その左から３番目のビットの内容は１であるから、条件は成立してステップＳ４０５に遷移する。
【０２６３】
ステップＳ４０５において、検索キー３の先頭から３文字の部分文字列、すなわち”ＺＺＺ”がプレフィックス３４になる。
【０２６４】
ステップＳ４０６において、プレフィックス３４の”ＺＺＺ”から計算されたハッシュ値３６−１〜３６−２が図２６のように、それぞれ４と１０になると仮定する。
【０２６５】
ステップＳ４０７において、ハッシュ値３６−１〜３６−２がそれぞれ４と１０であるから、オフセットビットマップ５２の内容は図２６（下）のように、ビットベクトル１２のアドレス”４”からアドレス”９”までの６ビットの内容と、アドレス”１０”からアドレス”１５”までの６ビットの内容との論理積、すなわち”０００１００”になる。
【０２６６】
ステップＳ４０８において、累積オフセットビットマップ８９の内容は、オフセットビットマップ５２の内容と累積オフセットビットマップ８９の内容の論理積に更新され、”００００００”になる。
【０２６７】
オフセットビットマップ５２の内容が”０００１００”であり、その左から１〜３番目のビットの内容は全て０であるため、とりうるｊの値すべて（０≦ｊ＜３）についてステップＳ４１０の条件は成立しない。従って、ステップＳ４１１〜ステップＳ４１３は一度も実行されることなく、ループカウンタ”ｊ”に対応するループが終了してステップＳ４１６に遷移する。
【０２６８】
また、累積オフセットビットマップ８９の内容が”００００００”であり、その左から（Ｓ＋１）番目からＷ番目までのビットの内容は全て０である。ここで、Ｓはストライド５４（＝３）であり、Ｗはウィンドウサイズ５５（＝６）である。この状況は、ステップＳ４０３において累積オフセットビットマップ８９の左シフトが何度繰り返されても変わらない。従って以後、ステップＳ４０４の条件は満たされることはなく、ステップＳ４１６においてプレフィックス３４の長さ”Ｌ”の増加が繰り返される。
【０２６９】
Ｌが２１まで到達するとステップＳ４０２の条件が満たされなくなり、ステップＳ４１７へ遷移する。
【０２７０】
スタックは空のままであるからステップＳ４１７の条件は満たされ、ステップＳ４２２へ遷移する。
【０２７１】
ハッシュ表検索部８３は、検索失敗の通知を行う（ステップＳ４２２）。ステップＳ４２２に到達したということは、検索キー３に前方一致する登録パターン２が１つも存在しないことを意味する。そこで、ハッシュ表検索部８３は、検索失敗を意味する検索結果４を出力する。
【０２７２】
ステップＳ４２２は検索失敗時の最終ステップである。
【０２７３】
２つ目の検索キー３に対する検索は失敗に終わったが、このときの図２１のフローチャートのステップＳ４０７の実行回数、すなわちビットベクトル１２の参照回数は１回に抑えられている。
【０２７４】
背景技術で述べたように関連技術例は、検索に失敗する場合、すなわち、検索キー１１０に前方一致する登録パターン１００がデータベースに登録されていなかったときに、検索の失敗を判定するまでに多くのメモリアクセスを発生させるという問題点を有している。一方、本実施形態では、上記説明したように、検索に失敗する場合に発生するメモリアクセスの回数は少ない。
【０２７５】
本実施形態が、検索に失敗する状況下でメモリアクセス回数を低減できている理由は、２つある。１つ目の理由は、検索部４１が短いプレフィックス３４から順に評価するからである。２つ目の理由は、登録部４０が登録パターン２の長さに関する情報をプレフィックス２４ごとにビットベクトル１２に格納し、検索部４１がプレフィックス３４ごとにビットベクトル１２を参照して、そのプレフィックス３４から始まる登録パターン２の存在可能性を判定するからである。
【０２７６】
検索部４１がビットベクトル１２を参照した結果、現在のプレフィックス３４から始まる登録パターン２がデータベースに存在しないことが判明した場合、次回以降のプレフィックス３４に対する処理を中止し、即座に検索の失敗を通知できる。なぜならば、現在のプレフィックス３４から始まる登録パターン２が存在しないとき、次のプレフィックス３４から始まる登録パターン２は存在し得ないからである。繰り返しになるが、プレフィックス３４は短いものから順に評価されるため、現在のプレフィックス３４よりも次のプレフィックス３４のほうが常に長くなる。
【０２７７】
例えば、上述の検索部４１の動作説明における２つ目の検索キー３に対する検索処理では、検索部４１が初回のプレフィックス３４の”ＺＺＺ”についてビットベクトル１２を参照した結果、”ＺＺＺ”から始まる登録パターン２がデータベースに存在しないことが判明する。そこで、検索部４１は、２回目以降のプレフィックス３４の”ＺＺＺＺＺＺ”や”ＺＺＺＺＺＺＺＺＺ”等についてビットベクトル１２を参照する処理をスキップし、メモリアクセス回数を削減している。
【０２７８】
さて、背景技術で述べたように関連技術例には、共通のプレフィックス１０１を持つ登録パターン１００が多数存在するときに、検索速度が低下するという問題点もある。この問題点を本実施形態がどのように解決しているかを述べる。
【０２７９】
本実施形態と関連技術例のいずれもハッシュ表に登録パターンを格納するが、その際のハッシュ値の計算対象が本実施形態と関連技術例とで異なっている。
【０２８０】
関連技術例では図２８のように、登録パターン１００のプレフィックス１０１にハッシュ関数をかけてハッシュ値１０３を計算し、ハッシュ値１０３に対応するハッシュ表１０４のバケットに登録パターン１００を格納する。
【０２８１】
一方、本実施形態では図１４のように、登録パターン２の全域にハッシュ関数をかけてハッシュ値を計算し、そのハッシュ値に対応するハッシュ表１３のバケットに登録パターン２を格納する。
【０２８２】
関連技術例では、ハッシュ値の計算対象がプレフィックス１０１に限られているため、プレフィックス１０１が共通でサフィックス１０２が異なるような登録パターン１００が多数存在していると、ハッシュ表１０４においてハッシュ値１０３の衝突が頻発し、長大な連結リストが構築される。例えば、図３０のような状態になる。ハッシュ法においては、広く知られているように、ハッシュ値の衝突確率もしくは連結リストの平均長は、登録および検索の速度を大きく左右する。
【０２８３】
一方、本実施形態では、ハッシュ値の計算対象は登録パターン２の全域であるから、プレフィックス２４が共通でサフィックス５１が異なるような登録パターン２が多数存在していても、ハッシュ表１３においてハッシュ値の衝突が頻発する確率は極めて小さい。その理由は、サフィックス５１の部分もハッシュ値の計算対象に含まれているために、ハッシュ値が偏らずに一様に分布しやすいからである。
【０２８４】
ゆえに、本実施形態は、関連技術例とは異なり、プレフィックス２４が共通でサフィックス５１が異なるような登録パターン２が多数存在している状況下でも、検索速度の低下を引き起こさない。
【０２８５】
なお、本実施形態による検索装置５は前方最長一致検索を行うものであるが、僅かな変更で後方最長一致検索に転用できる。具体的には、図１３のフローチャートのステップＳ３０５と、図２１のフローチャートのステップＳ４０５、図２２のフローチャートのステップＳ４１９の３箇所にある「〜の先頭からＸ文字を〜」という記述を「〜の末尾からＸ文字を〜」に置換するだけで、検索装置５は後方最長一致の検索器として機能するようになる。なお、上述した前方最長一致検索の場合では、プレフィックスを第１文字列、サフィックスを第２文字列と呼ぶことができるが、後方最長一致検索の場合では、サフィックスを第１文字列、プレフィックスを第２文字列と呼ぶことができる。
【０２８６】
検索装置５のビットベクトル１２の各要素は２値のビットではなく多値の数値であっても良い。多値にした場合、図１３のフローチャートのステップＳ３０９においてビットベクトル１２を更新する際に、対象のアドレスの内容を増減させる。例えば１を加算する。また、図２１のフローチャートのステップＳ４０７においてビットベクトル１２を参照する際に、対象のアドレスの内容が０であればビット“０”、０以外であればビット“１”とみなして論理積を計算する。
【０２８７】
同様に、検索装置５の登録オフセットビットマップ４５の各要素は２値のビットではなく多値の数値であっても良い。多値にした場合、図１３のフローチャートのステップＳ３０２において登録オフセットビットマップ４５を更新する際に、対象のインデックスが指す内容を増減させる。例えば１を加算する。また、図２１のフローチャートのステップＳ４０１において、登録オフセットビットマップ４５の各要素の内容が０であればビット“０”、０以外であればビット“１”とみなして、それを累積オフセットビットマップ８９の各ビットに代入する。
【０２８８】
検索装置５の登録部４０のビットベクトル更新部６２は、オフセット７０とハッシュ値２６−１〜２６−Ｍとの和を求め、その和をビットベクトル１２のアドレスとしている（図１３のフローチャートのステップＳ３０９）。同様に、検索装置５の検索部４１のパターン長推定部８２は、０以上かつウィンドウサイズ５５未満のオフセットとハッシュ値３６−１〜３６−Ｍとの和を求め、その和をビットベクトル１２のアドレスとしている（図２１のフローチャートのステップＳ４０７）。このように本実施形態では、ビットベクトル１２のアドレスを求める際に、ハッシュ値とオフセットを単純に加算しているが、加算以外の演算も利用可能である。一般化すると、ハッシュ値とオフセットからビットベクトル１２のアドレスを求めるための計算式は、少なくともハッシュ値とオフセットを引数とする関数の形状をとる。例えば、この関数は「（ハッシュ値）×２−（オフセット）×３＋４５６」であっても良い（本例には格別な意味はない）。この関数は、任意のハッシュ値とオフセットに対し、値が一意に定まらなければならない。また、登録部４０のビットベクトル更新部６２で使用される関数と、検索部４１のパターン長推定部８２で使用される関数は、同一でなければならない。
【０２８９】
検索装置５のハッシュ表１３の代わりに、完全一致検索を実施できる別の検索手段を用いても良い。例えば、二分探索木などを利用できる。
【０２９０】
以上、本発明の実施形態について説明したが、上記実施形態に限定されるものではなく、その要旨を逸脱しない範囲において種々の変形が可能である。
【０２９１】
例えば、上記実施形態の検索装置５では、図１１において、登録部４０と検索部４１とで各部をそれぞれ設ける構成としたが、両部を統合し、登録時と検索時とで上述した機能、動作を切り替えるようにしてもよい。例えば、プレフィックス抽出部６０とプレフィックス抽出部８０を一つに統合し、また、ハッシュ演算部２１とハッシュ演算部３１も一つに統合する。また、ハッシュ表登録部２３とハッシュ表検索部８３はともに、ハッシュ表１３へアクセス（更新・参照）する機能が共通であるので一つに統合する。また、ビットベクトル更新部６２とパターン長推定部８２はともに、ビットベクトル１２へアクセス（更新・参照）する機能が共通であるので一つに統合する。
【０２９２】
また、例えば、上記実施形態の検索装置５は、例えばＰＣ（Personal Computer）等の情報処理装置に適用できる。図２７は、本発明の検索装置５を情報処理装置に適用した構成例を示すブロック図である。
【０２９３】
図２７に示す例では、本発明の検索装置５はデータ処理装置２０１と記憶装置２０２とで構成される。
【０２９４】
データ処理装置２０１は、ＣＰＵ等の制御装置である。データ処理装置２０１は、登録手段２４０と、検索手段２４１とを有している。
【０２９５】
登録手段２４０および検索手段２４１は、それぞれ図１１に示す登録部４０および検索部４１と同様に機能、動作するので、ここでの説明は省略する。
【０２９６】
登録手段２４０は、プレフィックス抽出手段２６０、ハッシュ演算手段２２１、オフセット決定手段２６８、ビットベクトル更新手段２６２、ハッシュ表登録手段２２３、登録オフセットビットマップ更新手段２６９を有する。
【０２９７】
これら登録手段２４０内の各手段は、図１１に示す各部（プレフィックス抽出部６０、ハッシュ演算部２１、オフセット決定部６８、ビットベクトル更新部６２、ハッシュ表登録部２３、登録オフセットビットマップ更新部６９）と同様に機能、動作するので、ここでの説明は省略する。
【０２９８】
また、検索手段２４１は、プレフィックス抽出手段２８０、ハッシュ演算手段２３１、パターン長推定手段２８２、ハッシュ表検索手段２８３、累積オフセットビットマップ管理手段２８８を有する。
【０２９９】
これら検索手段２４１内の各手段は、図１１に示す各部（プレフィックス抽出部８０、ハッシュ演算部３１、パターン長推定部８２、ハッシュ表検索部８３、累積オフセットビットマップ管理部８８）と同様に機能、動作するので、ここでの説明は省略する。
【０３００】
また、記憶装置２０２には、図１１で説明したものと同じである、ビットベクトル１２、ハッシュ表１３、登録オフセットビットマップ４５、長さ−オフセット対応表６７、累積オフセットビットマップ８９がそれぞれ格納される。記憶装置２０２は、ＲＡＭやＨＤＤ等の記録媒体である。
【０３０１】
例えば、上述した実施形態における動作（各フローチャートに示す動作）は、ハードウェア、または、ソフトウェア、あるいは、両者の複合構成によって実行することも可能である。
【０３０２】
ソフトウェアによる処理を実行する場合には、処理シーケンスを記録したプログラムを、専用のハードウェアに組み込まれているコンピュータ内のメモリにインストールして実行させてもよい。あるいは、各種処理が実行可能な汎用コンピュータにプログラムをインストールして実行させてもよい。
【０３０３】
例えば、プログラムは、記録媒体としてのハードディスクやＲＯＭ（Read Only Memory）に予め記録しておくことが可能である。あるいは、プログラムは、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＭＯ（Magneto optical）ディスク、ＤＶＤ（Digital Versatile Disc）、磁気ディスク、半導体メモリなどのリムーバブル記録媒体に、一時的、あるいは、永続的に格納（記録）しておくことが可能である。このようなリムーバブル記録媒体は、いわゆるパッケージソフトウエアとして提供することが可能である。
【０３０４】
なお、プログラムは、上述したようなリムーバブル記録媒体からコンピュータにインストールする他、ダウンロードサイトから、コンピュータに無線転送してもよい。または、ＬＡＮ（Local Area Network）、インターネットといったネットワークを介して、コンピュータに有線で転送してもよい。コンピュータでは、転送されてきたプログラムを受信し、内蔵するハードディスク等の記録媒体にインストールすることが可能である。
【０３０５】
また、上記実施形態で説明した処理動作に従って時系列的に実行されるのみならず、処理を実行する装置の処理能力、あるいは、必要に応じて並列的にあるいは個別に実行するように構築することも可能である。
【０３０６】
この出願は、２００８年８月２２日に出願された日本出願特願２００８−２１４２１１を基礎とする優先権を主張し、その開示を全てここに取り込む。
【符号の説明】
【０３０７】
１    検索装置
２    登録パターン
３    検索キー
４    検索結果
５    検索装置
１０    登録部
１１    検索部
１２    ビットベクトル
１３    ハッシュ表
１４    分割位置リスト
２０    プレフィックス抽出部（第１プレフィックス抽出部）
２１    ハッシュ演算部（第１ハッシュ演算部）
２２    ビットベクトル更新部
２３    ハッシュ表登録部
２４    プレフィックス
２５    サフィックス長
２６−１〜２６−Ｍ    ハッシュ値
３０    プレフィックス抽出部（第２プレフィックス抽出部）
３１    ハッシュ演算部（第２ハッシュ演算部）
３２    パターン長推定部
３３    ハッシュ表検索部
３４    プレフィックス
３５    分割間隔
３６−１〜３６−Ｍ    ハッシュ値
３７    一致候補の長さ
４０    登録部
４１    検索部
４５    登録オフセットビットマップ
５０    分割位置
５１    サフィックス
５２    オフセットビットマップ
５３    一致候補
６０    プレフィックス抽出部（第１プレフィックス抽出部）
６２    ビットベクトル更新部
６７    長さ−オフセット対応表
６８    オフセット決定部
６９    登録オフセットビットマップ更新部
７０    オフセット
８０    プレフィックス抽出部（第２プレフィックス抽出部）
８２    パターン長推定部
８３    ハッシュ表検索部
８８    累積オフセットビットマップ管理部
８９    累積オフセットビットマップ
１００    登録パターン
１０１    プレフィックス
１０２    サフィックス
１０３    ハッシュ値
１０４    ハッシュ表
１１０    検索キー
１１１    プレフィックス
１１２    サフィックス
１１３    ハッシュ値
２０１    データ処理装置
２０２    記憶装置
２１０    登録手段
２２０    プレフィックス抽出手段
２２１    ハッシュ演算手段
２２２    ビットベクトル更新手段
２２３    ハッシュ表登録手段
２３０    プレフィックス抽出手段
２３１    ハッシュ演算手段
２３２    パターン長推定手段
２３３    ハッシュ表検索手段
２６０    プレフィックス抽出手段
２６２    ビットベクトル更新手段
２６８    オフセット決定手段
２６９    登録オフセットビットマップ更新手段
２８０    プレフィックス抽出手段
２８２    パターン長推定手段
２８３    ハッシュ表検索手段
２８８    累積オフセットビットマップ管理手段
【図１】
0005472108.tif 000002
【図２】
0005472108.tif 000003
【図３】
0005472108.tif 000004
【図４】
0005472108.tif 000005
【図５】
0005472108.tif 000006
【図６】
0005472108.tif 000007
【図７】
0005472108.tif 000008
【図８】
0005472108.tif 000009
【図９】
0005472108.tif 000010
【図１０】
0005472108.tif 000011
【図１１】
0005472108.tif 000012
【図１２】
0005472108.tif 000013
【図１３】
0005472108.tif 000014
【図１４】
0005472108.tif 000015
【図１５】
0005472108.tif 000016
【図１６】
0005472108.tif 000017
【図１７】
0005472108.tif 000018
【図１８】
0005472108.tif 000019
【図１９】
0005472108.tif 000020
【図２０】
0005472108.tif 000021
【図２１】
0005472108.tif 000022
【図２２】
0005472108.tif 000023
【図２３】
0005472108.tif 000024
【図２４】
0005472108.tif 000025
【図２５】
0005472108.tif 000026
【図２６】
0005472108.tif 000027
【図２７】
0005472108.tif 000028
【図２８】
0005472108.tif 000029
【図２９】
0005472108.tif 000030
【図３０】
0005472108.tif 000031