JP4114600B2 - 可変長文字列検索装置及び可変長文字列検索方法並びにプログラム - Google Patents

Description

本発明は、可変長文字列データの情報検索技術に関し、特に可変長文字列に対する前方または後方最大一致検索の検索効率を向上させる技術に関する。

初めに、本発明の主たる適用対象である前方最大一致検索(Longest Prefix Match)の一般形について図１２を用いて説明する。前方最大一致検索では、パターンリストの中から検索キー(検索文字列)と先頭文字から一致するもののうち最も一致する部分が長いパターンが検索結果となる。図１２の例では、検索キーと先頭文字から一致するパターンは「ＡＢＣＤ」「ＡＢＣＤＥＦＧＨ」「ＡＢＣＤＥ」の３パターンがあるが、最もマッチする部分が長いパターン「ＡＢＣＤＥＦＧＨ」が検索結果として出力される。このとき、検索キーのパターンよりも長い部分はどのような文字列であっても構わず、一方、パターン「ＢＣＤＥ」のように、検索キーの部分文字列であっても先頭が一致していないパターンは前方一致の条件を満たさない。

可変長文字列データの情報検索、特に可変長文字列の前方一致検索、後方一致検索を行うシステムにおいて、大量のパターンの中から検索キーに一致するパターンを高速に検索する方法として、従来、次のような技術が知られている（例えば、特許文献１参照）。

この特許文献１に記載された従来の技術は、前方一致検索に関するものであり、文字列データの先頭ｎ文字（ｎ：自然数）からインデックス表を作成するインデックス作成手段と、インデックス表を走査して前方一致する文字列を抽出するデータ検索手段から構成されている。データ検索手段において、検索条件に指定された文字列がインデックスデータの文字列よりも長い場合、抽出した文字列データの残り部分の各文字を比較して検索条件に一致する文字列の検索を行う。
特開平４−２０９０６９号公報

この従来技術の問題点を図１３を用いて説明する。従来技術では、インデックスデータを文字列データの先頭ｎ文字から作成している。そのため、パターン1301〜1304のみが登録されているような検索においては、パターン1301〜1304は先頭４文字が共通なので、先頭から５文字（区切り1351より左側）をインデックスとすることで、インデックスによる登録パターンの絞り込みが効率的に行うことができる。同様に、パターン1305〜1310のみから構成されるパターンに対する検索においては、各パターンは先頭から９文字目までは共通なので、先頭から１０文字（区切り1352より左側）をインデックスとすればよい。

ところが、上記の両方のパターン1301〜1310が検索対象となる場合には、不都合が生じる。パターン1301〜1304を効率的に絞り込むためには、先頭から５文字をインデックスとするのが望ましいが、その場合にはパターン1305〜1310のインデックスは全て同じになってしまう。このため、検索キーとして「ＰＱＲＳＰＱＲＳＰ」から始まる文字列が入力された場合には、インデックスによる絞り込みが十分に行われず、その後に行うサフィックス部分の比較コストが大きくなり、検索効率が低下する。このように、従来技術では、登録パターンの重複部分の長さにばらつきがあるような場合にはインデックスによる絞り込みが十分に行われず、文字列の残りの部分の比較のコストが大きくなるという問題がある。

〔発明の目的〕
そこで、本発明の目的は、登録パターンの重複部分の長さにばらつきがある場合においても、高い検索効率を得られるようにすることにある。

本発明にかかる第１の可変長文字列検索装置は、
パターン格納部と、
可変長文字列データである登録パターンが入力される毎に、予め定められている複数の異なる長さの中から前記登録パターンの長さ以下で且つ最長の長さを選択し、前記登録パターンの先頭から該選択した長さ分の文字データをプレフィックスとして抽出すると共に、抽出した該プレフィックスを前記登録パターンに対するインデックス要素として前記パターン格納部に登録するパターン登録部と、
可変長文字列データである検索キーが入力される毎に、前記検索キーから前記予め定められている複数の異なる長さのプレフィックスを抽出し、前記パターン格納部に登録されているインデックス要素を、該抽出した各長さのプレフィックスを使用して検索することにより、検索対象となる登録パターンを絞り込む検索実行部と
を備えたことを特徴とする。

本発明にかかる第２の可変長文字列検索装置は、
パターン格納部と、
可変長文字列データである登録パターンが入力される毎に、前記登録パターンの先頭から末尾に向かって区切り文字の検出処理を行い、予め定められた個数の区切り文字を検出した場合は、前記登録パターンの先頭文字から該検出した区切り文字の直前の文字までの文字列によって構成されるプレフィックスを前記登録パターンに対するインデックス要素として前記パターン格納部に登録する一方、前記登録パターンの末尾まで区切り文字の検出処理を行っても前記予め定められた個数の区切り文字を検出できなかった場合は、前記登録パターンの先頭文字から最後に検出した区切り文字の直前の文字までの文字列によって構成されるプレフィックスを前記登録パターンに対するインデックス要素として前記パターン格納部に登録するパターン登録部と、
可変長文字列データである検索キーが入力される毎に、前記予め定められた個数の区切り文字を検出するまで、前記検索キーの先頭から末尾に向かって区切り文字の検出処理を行い、区切り文字を検出する毎に、前記パターン格納部に登録されているインデックス要素を、前記検索キーの先頭文字から検出した区切り文字の直前の文字までの文字列によって構成されるプレフィックスを使用して検索することにより、検索対象となる登録パターンを絞り込む検索実行部と
を備えたことを特徴とする。

本発明にかかる第３の可変長文字列検索装置は、第１または第２の可変長文字列検索装置において、
前記パターン登録部は、前記登録パターンのプレフィックスを前記パターン格納部に登録する際、前記登録パターンからプレフィックスを除いたサフィックスを前記プレフィックスに関連付けて登録し、
前記検索実行部は、
前記検索キーから前記各プレフィックスを抽出するプレフィックス抽出部と、
該プレフィックス抽出部によって抽出した前記各プレフィックスを使用して前記パターン格納部を検索するプレフィックス検索部と、
該プレフィックス検索部によって検索されたプレフィックスに関連付けて登録されている登録パターンのサフィックスについて、前記検索キーのサフィックスとの一致検証を行うサフィックス照合部と
を含むことを特徴とする。

本発明にかかる第４の可変長文字列検索装置は、第１乃至第３の何れかの可変長文字列検索装置において、
前記パターン登録部は、前記登録パターンのプレフィックスを前記パターン格納部に登録する際、前記プレフィックスに対してハッシュ関数を適用することにより得られるハッシュ値に応じた位置に登録し、
前記プレフィックス検索部は、前記プレフィックス抽出部によって抽出された各プレフィックスに対するハッシュ値を前記ハッシュ関数を用いて求め、該求めた各ハッシュ値を使用して前記パターン格納部を検索する
ことを特徴とする。

本発明にかかる第５の可変長文字列検索装置は、
パターン格納部と、
可変長文字列データである登録パターンが入力される毎に、予め定められている複数の異なる長さの中から、前記登録パターンの長さ以下で且つ最長の長さを選択し、前記登録パターンの末尾から該選択した長さ分の文字データをサフィックスとして抽出すると共に、抽出した該サフィックスを前記登録パターンに対するインデックス要素として前記パターン格納部に登録するパターン登録部と、
可変長文字列データである検索キーが入力される毎に、前記検索キーから前記予め定められている複数の異なる長さのサフィックスを抽出し、前記パターン格納部に登録されているインデックス要素を、該抽出した各長さのサフィックスを使用して検索することにより、検索対象となる登録パターンを絞り込む検索実行部と
を備えたことを特徴とする。

本発明にかかる第６の可変長文字列検索装置は、
パターン格納部と、
可変長文字列データである登録パターンが入力される毎に、前記登録パターンの末尾から先頭に向かって区切り文字の検出処理を行い、予め定められた個数の区切り文字を検出した場合は、前記登録パターンの末尾文字から該検出した区切り文字の直後の文字までの文字列によって構成されるサフィックスを前記登録パターンに対するインデックス要素として前記パターン格納部に登録する一方、前記登録パターンの先頭まで区切り文字の検出処理を行っても前記予め定められた個数の区切り文字を検出できなかった場合は、前記登録パターンの末尾文字から最後に検出した区切り文字の直後の文字までの文字列によって構成されるサフィックスを前記登録パターンに対するインデックス要素として前記パターン格納部に登録するパターン登録部と、
可変長文字列データである検索キーが入力される毎に、前記予め定められた個数の区切り文字を検出するまで、前記検索キーの末尾から先頭に向かって区切り文字の検出処理を行い、区切り文字を検出する毎に、前記パターン格納部に登録されているインデックス要素を、前記検索キーの末尾文字から検出した区切り文字の直後の文字までの文字列によって構成されるサフィックスを使用して検索することにより、検索対象となる登録パターンを絞り込む検索実行部と
を備えたことを特徴とする。

本発明にかかる第７の可変長文字列検索装置は、第５または第６の可変長文字列検索装置において、
前記パターン登録部は、前記登録パターンのサフィックスを前記パターン格納部に登録する際、前記登録パターンからサフィックスを除いたプレフィックスを前記サフィックスに関連付けて登録し、
前記検索実行部は、
前記検索キーから前記各サフィックスを抽出するサフィックス抽出部と、
該サフィックス抽出部によって抽出した前記各サフィックスを使用して前記パターン格納部を検索するサフィックス検索部と、
該サフィックス検索部によって検索されたサフィックスに関連付けて登録されている登録パターンのプレフィックスについて、前記検索キーのプレフィックスとの一致検証を行うプレフィックス照合部と
を含むことを特徴とする。

本発明にかかる第８の可変長文字列検索装置は、第５乃至第７の何れかの可変長文字列検索装置において、
前記パターン登録部は、前記登録パターンのサフィックスを前記パターン格納部に登録する際、前記サフィックスに対してハッシュ関数を適用することにより得られるハッシュ値に応じた位置に登録し、
前記サフィックス検索部は、前記サフィックス抽出部によって抽出された各サフィックスに対するハッシュ値を前記ハッシュ関数を用いて求め、該求めた各ハッシュ値を使用して前記パターン格納部を検索する
ことを特徴とする。

本発明にかかる第１の可変長文字列検索方法は、
可変長文字列データである登録パターンが入力される毎に、予め定められている複数の異なる長さの中から、前記登録パターンの長さ以下で且つ最長の長さを選択し、
前記登録パターンの先頭から該選択した長さ分の文字データをプレフィックスとして抽出すると共に、抽出した該プレフィックスを前記登録パターンに対するインデックス要素としてパターン格納部に登録し、
可変長文字列データである検索キーが入力される毎に、前記検索キーから前記予め定められている複数の異なる長さのプレフィックスを抽出し、
前記パターン格納部に登録したインデックス要素を、該抽出した各長さのプレフィックスを使用して検索することにより、検索対象となる登録パターンを絞り込む
ことを特徴とする。

本発明にかかる第２の可変長文字列検索方法は、
可変長文字列データである登録パターンが入力される毎に、前記登録パターンの先頭から末尾に向かって区切り文字の検出処理を行い、
予め定められた個数の区切り文字を検出した場合は、前記登録パターンの先頭文字から該検出した区切り文字の直前の文字までの文字列によって構成されるプレフィックスを前記登録パターンに対するインデックス要素としてパターン格納部に登録する一方で、
前記登録パターンの末尾まで区切り文字の検出処理を行っても前記予め定められた個数の区切り文字を検出できなかった場合は、前記登録パターンの先頭文字から最後に検出した区切り文字の直前の文字までの文字列によって構成されるプレフィックスを前記登録パターンに対するインデックス要素としてパターン格納部に登録し、
可変長文字列データである検索キーが入力される毎に、前記予め定められた個数の区切り文字を検出するまで、前記検索キーの先頭から末尾に向かって区切り文字の検出処理を行い、区切り文字を検出する毎に、前記パターン格納部に登録したインデックス要素を、前記検索キーの先頭文字から検出した区切り文字の直前の文字までの文字列によって構成されるプレフィックスを使用して検索することにより、検索対象となる登録パターンを絞り込む
ことを特徴とする。

本発明にかかる第３の可変長文字列検索方法は、
可変長文字列データである登録パターンが入力される毎に、予め定められている複数の異なる長さの中から、前記登録パターンの長さ以下で且つ最長の長さを選択し、前記登録パターンの末尾から該選択した長さ分の文字データをサフィックスとして抽出すると共に、抽出した該サフィックスを前記登録パターンに対するインデックス要素としてパターン格納部に登録し、
可変長文字列データである検索キーが入力される毎に、前記検索キーから前記予め定められている複数の異なる長さのサフィックスを抽出し、前記パターン格納部に登録したインデックス要素を、該抽出した各長さのサフィックスを使用して検索することにより、検索対象となる登録パターンを絞り込む
ことを特徴とする。

本発明にかかる第４の可変長文字列検索方法は、
可変長文字列データである登録パターンが入力される毎に、前記登録パターンの末尾から先頭に向かって区切り文字の検出処理を行い、
予め定められた個数の区切り文字を検出した場合は、前記登録パターンの末尾文字から該検出した区切り文字の直後の文字までの文字列によって構成されるサフィックスを前記登録パターンに対するインデックス要素としてパターン格納部に登録する一方で、
前記登録パターンの先頭まで区切り文字の検出処理を行っても前記予め定められた個数の区切り文字を検出できなかった場合は、前記登録パターンの末尾文字から最後に検出した区切り文字の直後の文字までの文字列によって構成されるサフィックスを前記登録パターンに対するインデックス要素としてパターン格納部に登録し、
可変長文字列データである検索キーが入力される毎に、前記予め定められた個数の区切り文字を検出するまで、前記検索キーの末尾から先頭に向かって区切り文字の検出処理を行い、区切り文字を検出する毎に、前記パターン格納部に登録したインデックス要素を、前記検索キーの末尾文字から検出した区切り文字の直後の文字までの文字列によって構成されるサフィックスを使用して検索することにより、検索対象となる登録パターンを絞り込む
ことを特徴とする。

本発明にかかる第１のプログラムは、
パターン格納部を備えたコンピュータを可変長文字列検索装置として機能させるためのプログラムであって、前記コンピュータを、
可変長文字列データである登録パターンが入力される毎に、予め定められている複数の異なる長さの中から、前記登録パターンの長さ以下で且つ最長の長さを選択し、前記登録パターンの先頭から該選択した長さ分の文字データをプレフィックスとして抽出すると共に、抽出した該プレフィックスを前記登録パターンに対するインデックス要素として前記パターン格納部に登録するパターン登録部と、
可変長文字列データである検索キーが入力される毎に、前記検索キーから前記予め定められている複数の異なる長さのプレフィックスを抽出し、前記パターン格納部に登録されているインデックス要素を、該抽出した各長さのプレフィックスを使用して検索することにより、検索対象となる登録パターンを絞り込む検索実行部として機能させる。

本発明にかかる第２のプログラムは、
パターン格納部を備えたコンピュータを可変長文字列検索装置として機能させるためのプログラムであって、前記コンピュータを、
可変長文字列データである登録パターンが入力される毎に、前記登録パターンの先頭から末尾に向かって区切り文字の検出処理を行い、予め定められた個数の区切り文字を検出した場合は、前記登録パターンの先頭文字から該検出した区切り文字の直前の文字までの文字列によって構成されるプレフィックスを前記登録パターンに対するインデックス要素として前記パターン格納部に登録する一方、前記登録パターンの末尾まで区切り文字の検出処理を行っても前記予め定められた個数の区切り文字を検出できなかった場合は、前記登録パターンの先頭文字から最後に検出した区切り文字の直前の文字までの文字列によって構成されるプレフィックスを前記登録パターンに対するインデックス要素として前記パターン格納部に登録するパターン登録部と、
可変長文字列データである検索キーが入力される毎に、前記予め定められた個数の区切り文字を検出するまで、前記検索キーの先頭から末尾に向かって区切り文字の検出処理を行い、区切り文字を検出する毎に、前記パターン格納部に登録されているインデックス要素を、前記検索キーの先頭文字から検出した区切り文字の直前の文字までの文字列によって構成されるプレフィックスを使用して検索することにより、検索対象となる登録パターンを絞り込む検索実行部として機能させる。

本発明にかかる第３のプログラムは、
パターン格納部を備えたコンピュータを可変長文字列検索装置として機能させるためのプログラムであって、前記コンピュータを、
可変長文字列データである登録パターンが入力される毎に、予め定められている複数の異なる長さの中から、前記登録パターンの長さ以下で且つ最長の長さを選択し、前記登録パターンの末尾から該選択した長さ分の文字データをサフィックスとして抽出すると共に、抽出した該サフィックスを前記登録パターンに対するインデックス要素として前記パターン格納部に登録するパターン登録部と、
可変長文字列データである検索キーが入力される毎に、前記検索キーから前記予め定められている複数の異なる長さのサフィックスを抽出し、前記パターン格納部に登録されているインデックス要素を、該抽出した各長さのサフィックスを使用して検索することにより、検索対象となる登録パターンを絞り込む検索実行部として機能させる。

本発明にかかる第４のプログラムは、
パターン格納部を備えたコンピュータを可変長文字列検索装置として機能させるためのプログラムであって、前記コンピュータを、
可変長文字列データである登録パターンが入力される毎に、前記登録パターンの末尾から先頭に向かって区切り文字の検出処理を行い、予め定められた個数の区切り文字を検出した場合は、前記登録パターンの末尾文字から該検出した区切り文字の直後の文字までの文字列によって構成されるサフィックスを前記登録パターンに対するインデックス要素として前記パターン格納部に登録する一方、前記登録パターンの先頭まで区切り文字の検出処理を行っても前記予め定められた個数の区切り文字を検出できなかった場合は、前記登録パターンの末尾文字から最後に検出した区切り文字の直後の文字までの文字列によって構成されるサフィックスを前記登録パターンに対するインデックス要素として前記パターン格納部に登録するパターン登録部と、
可変長文字列データである検索キーが入力される毎に、前記予め定められた個数の区切り文字を検出するまで、前記検索キーの末尾から先頭に向かって区切り文字の検出処理を行い、区切り文字を検出する毎に、前記パターン格納部に登録されているインデックス要素を、前記検索キーの末尾文字から検出した区切り文字の直後の文字までの文字列によって構成されるサフィックスを使用して検索することにより、検索対象となる登録パターンを絞り込む検索実行部として機能させる。

本発明にかかる第１の可変長文字列検索装置、可変長文字列検索方法およびプログラムは、登録パターンの重複部分の長さにばらつきがある場合であっても、前方最長一致検索において高い検索効率を得られるという効果を有する。

その理由は、登録パターンから抽出可能な複数の異なる長さのプレフィックスの内の、最長のプレフィックスを登録パターンに対するインデックス要素とし、検索キーに従った検索時には、検索キーから抽出した各長さのプレフィックスを使用してインデックス要素を検索し、検索対象となる登録パターンを絞り込むようにしているからである。つまり、各登録パターンについて、抽出可能な複数の異なる長さのプレフィックスの内の、最長のプレフィックスをその登録パターンに対するインデックス要素としているので、各登録パターンのインデックス要素が同じものになってしまう確率を低くすることができ、その結果、インデックス検索による絞り込み効率を高くし、それ以後に行う登録パターンと検索キーのインデックス要素以外の部分の比較照合処理のコストを削減することができるからである。また、最長のプレフィックスをインデックス要素としたので、上記比較照合処理で比較対象にする文字が少なくなり、検索効率を高いものにすることができる。

本発明にかかる第２の可変長文字列検索装置、可変長文字列検索方法およびプログラムは、第１の可変長文字列検索装置、可変長文字列検索方法およびプログラムと同様の効果を有する。特に区切り文字“／”により抽出する複数のプレフィックスを指定した場合には、インターネットのWWWページのURLの検索を行う際の検索効率を高いものにすることができる。

本発明にかかる第３の可変長文字列検索装置は、第１、第２の可変長文字列検索装置と同様の効果を有する。

その理由は、パターン登録部が、登録パターンのプレフィックスをパターン格納部に登録する際、登録パターンのサフィックスをプレフィックスに関連付けてパターン格納部に登録する構成を有し、検索実行部が、検索キーから各プレフィックスを抽出するプレフィックス抽出部と、プレフィックス抽出部で抽出した各プレフィックスを使用してパターン格納部を検索するプレフィックス検索部と、プレフィックス検索部で検索されたプレフィックスに関連付けて登録されている登録パターンのサフィックスについて、検索キーのサフィックスとの一致検証を行うサフィックス照合部とを備えているからである。

本発明にかかる第４の可変長文字列検索装置は、前方最長一致検索の検索効率を更に高めることができるという効果を有する。

その理由は、インデックス要素となるプレフィックスをパターン格納部に登録する際、その収容位置を、そのプレフィックスに対してハッシュ関数を適用することにより得られるハッシュ値に応じた位置としているからである。

本発明にかかる第５の可変長文字列検索装置、第３の可変長文字列検索方法および第３のプログラムは、登録パターンの重複部分の長さにばらつきがある場合であっても、後方最長一致検索において高い検索効率を得られるという効果を有する。

その理由は、登録パターンから抽出可能な、登録パターン末尾部分からの長さがそれぞれ異なる複数のサフィックスの内の、最長のサフィックスを登録パターンに対するインデックス要素としてパターン格納部に登録し、検索キーに従った検索時には、検索キーから抽出可能な各長さのサフィックスを使用してインデックス要素を検索し、検索対象となる登録パターンを絞り込むようにしているからである。

本発明にかかる第６の可変長文字列検索装置、第４の可変長文字列検索方法および第４のプログラムは、第５の可変長文字列検索装置、可変長文字列検索方法およびプログラムと同様の効果を有する。特に区切り文字“／”により抽出する複数のプレフィックスを指定した場合には、インターネットのWWWページのURLの検索を行う際の検索効率を高いものにすることができる。

本発明にかかる第７の可変長文字列検索装置は、第５または第６の可変長文字列検索装置と同様の効果を有する。

その理由は、パターン登録部が、登録パターンのサフィックスをパターン格納部に登録する際、登録パターンのプレフィックスをサフィックスに関連付けてパターン格納部に登録する構成を有し、検索実行部が、検索キーから各サフィックスを抽出するサフィックス抽出部と、サフィックス抽出部で抽出した各サフィックスを使用してパターン格納部を検索するサフィックス検索部と、サフィックス検索部で検索されたサフィックスに関連付けて登録されている登録パターンのプレフィックスについて、検索キーのプレフィックスとの一致検証を行うプレフィックス照合部とを備えているからである。

本発明にかかる第８の可変長文字列検索装置は、第５乃至第７の何れかの可変長文字列検索装置よりも後方最長一致検索の検索効率を高いものにできるという効果を有する。

その理由は、インデックス要素となるサフィックスをパターン格納部に登録する際、その収容位置を、そのサフィックスに対してハッシュ関数を適用することにより得られるハッシュ値に応じた位置としているからである。

本発明は可変長文字列データの検索、特に可変長文字列の前方最長一致検索を行う方法及びそれを利用した装置に関する発明である。あらかじめ登録された複数のパターンリストの中から、検索キーとして指定された可変長文字列データに一致するパターンを検索する。可変長文字列データを構成する個々の文字は、人間が認識可能な文字だけでなく、バイナリデータでもよい。また、１文字を表現するために必要なビット数に制限はなく、必ずしも１バイトである必要はない（１ビットであっても２バイトであっても構わない）。

次に本発明の実施の形態について図面を参照して詳細に説明する。

〔第一の実施の形態の構成の説明〕
本発明にかかる可変長文字列検索装置の第一の実施の形態について図１を参照して説明する。本実施の形態の可変長文字列検索装置１は、大別してパターン登録部１３１と検索実行部１１とパターン格納部１２とから構成される。

パターン登録部１３１は、登録パターン１３２が入力されると、所定の抽出ルールに基づいて長さが異なるＮ個（Ｎ：自然数）のプレフィックスを抽出し、更に、その中から所定の選択ルールに従って１個のプレフィックスを選択し、それを登録パターン１３２に対するインデックス要素とする。その後、インデックス要素とするプレフィックスに対して、予め定めたハッシュ関数を適用し、得られたハッシュ値に応じたプレフィックスパターンリスト１２１上の位置にプレフィックスを登録する。つまり、プレフィックスパターンリスト１２１上には、個々のプレフィックスをインデックス要素とするインデックスが構成されることになる。一方、登録パターン１３２からプレフィックスを除いたサフィックスは、サフィックスパターンリスト１２２に登録する。

ここで、本実施の形態で使用する抽出ルールおよび選択ルールについて説明しておく。抽出ルールは、登録パターン先頭部分からの長さがＬ１〜ＬＮ（Ｌ１〜ＬＮはいずれも自然数）のＮ種類のプレフィックスを、登録パターンから抽出（作成）するルールである。抽出するプレフィックスの長さは、予め定めておく必要があるが、長さの組み合わせはどのようなものであっても良い。長さの組み合わせ方の一例としては、例えば、Ｌｋ＝ｋ＊Ｍ（Ｍ：自然数、ｋ＝１、２・・・Ｎ）のようにＮ種類のＭの倍数を使用する方法を採用することができる。本実施の形態では、上記方法を採用するものとする。また、選択ルールは、抽出ルールに従って抽出した複数のプレフィックスの中から１つのプレフィックスを選択するルールであり、本実施の形態では、抽出ルールに従って抽出した複数のプレフィックスの内の、最長のプレフィックスを選択するものとする。

検索実行部１１は、検索キー１１４を受信すると、プレフィックスパターンリスト１２１及びサフィックスパターンリスト１２２から検索キー１１４に一致する登録パターンを検索し、検索結果１１５を出力する。このような機能を有する検索実行部１１は、プレフィックス抽出部１１１とプレフィックス検索部１１２とサフィックス照合部１１３とから構成されている。

プレフィックス抽出部１１１は、入力された検索キー１１４から上述した所定の抽出ルールに基づいて、Ｎ個のプレフィックスを抽出し、プレフィックス情報１１６として出力する。

プレフィックス検索部１１２は、プレフィックス抽出部１１１から受信したプレフィックス情報１１６のそれぞれについて、予め定めたハッシュ関数を適用し、得られたハッシュ値に基づいてプレフィックスパターンリスト１２１に対して検索を行い、プレフィックス検索結果１１７を出力する。

サフィックス照合部１１３は、プレフィックス検索結果１１７を受信し、前段のプレフィックス検索部１１２において一致するプレフィックスが見つかった場合に、サフィックスパターンリスト１２２から当該プレフィックスに対応するエントリを読み出し、検索キー１１４のプレフィックス以外の部分（サフィックス）が登録パターンと一致しているかどうかの検証を行い、一致している場合は、上記登録パターンを検索結果１１５として出力する。

なお、上述した構成を有する可変長文字列検索装置１は、コンピュータによって実現可能である。可変長文字列検索装置１をコンピュータによって実現する場合には、ディスク、半導体メモリ、その他の記録媒体に可変長文字列検索装置用のプログラムを記録しておく。コンピュータは、上記プログラムを読み込み、それに従って自身の動作を制御することにより、自コンピュータ上に、検索実行部１１、パターン格納部１２およびパターン登録部１３１を実現する。

〔第一の実施の形態の動作説明〕
次に、本実施の形態の動作について詳細に説明する。先ず、パターン登録時の動作を説明し、次に検索時の動作について説明する。なお、以下の説明では、抽出ルールとして、Ｎ＝４、Ｍ＝４とした抽出ルールを使用するものとする。即ち、長さが４、８、１２、１６となる４種類のプレフィックスを抽出する抽出ルールを使用するものとする。

パターン登録部１３１に長さ１１の新規登録パターン２０１「ＡＢＣＤＥＦＧＨＸＹＺ」が入力された場合について図２、図３を用いて説明する。

登録パターン２０１が入力されると、最初に登録パターン２０１に対するインデックス要素とするプレフィックス２０２の長さを決定する（図３のＳ３１）。抽出ルールに従って抽出可能なＮ種類のプレフィックス長の中から、選択ルールに従って、登録パターン以下で最も長い値を、登録パターンのプレフィックスの長さとする。図２の例では、プレフィックスの長さが４、８、１２、１６の４種類で、登録パターン２０１の長さは１１なので、登録パターン２０１のプレフィックス長は８となる。

その後、プレフィックス２０２及びサフィックス２０３を抽出する（Ｓ３２）。この例の場合、プレフィックス２０２は「ＡＢＣＤＥＦＧＨ」、サフィックス２０３は「ＸＹＺ」となる。

次に、サフィックス２０３をサフィックスパターンリスト１２２に登録する（Ｓ３３）。サフィックスパターンリスト１２２のデータ構造はどのようなものを用いても構わない。

その後、プレフィックス２０２に対して予め定められたハッシュ関数Ｈｐ（ｘ）を適用してハッシュ値Ｘｈを得る（Ｓ３４）。そして、最後に、プレフィックスパターンリスト１２１上の、上記ハッシュ値Ｘｈと対応するアドレスにプレフィックス２０２とサフィックスパターンリスト１２２内に格納されているサフィックス２０３へのポインタ情報を登録する（Ｓ３５）。

なお、ステップＳ３５において、プレフィックスパターンリスト１２１上のハッシュ値Ｘｈと対応するアドレスに、既にプレフィックス及びポインタ情報が登録されている場合は、例えば、次のような処理を行う。先ず、ポインタ情報が指し示しているサフィックスパターンリスト１２２中のエントリに注目する。そして、注目エントリに、次のエントリを指し示すポインタ情報が登録されていない場合は、ステップＳ３３でサフィックスを登録したエントリを指し示すポインタ情報を上記注目エントリに登録し、処理を終了する。これに対して、注目エントリに、次のエントリを指し示すポインタ情報が登録されている場合には、上記次のエントリに注目する。そして、新たな注目エントリにポインタ情報が登録されているか否かに従って、前述した処理と同様の処理を行う。

また、登録パターン２０１の長さとプレフィックス２０２の長さが同じ場合は、登録パターン２０１全体をプレフィックスとし、サフィックスは長さ０として扱う。サフィックスパターンリスト１２２には長さ０のサフィックスとして登録する（プレフィックスの登録は上記の説明の通りである）。

以上で、パターンの登録処理は完了する。

次に、パターン検索時の動作について図４を用いて説明する。

プレフィックスパターンリスト１２１及びサフィックスパターンリスト１２２からなるパターンリストに、登録パターン４２１“ＡＢＣＤＥＦ”、登録パターン４２２“ＢＣＤＥＦＧＨ”及び登録パターン４２３“ＡＢＣＤＥＦＧＨＸＹＺ”の３つの登録パターンが登録されているものとする。これらの登録パターンは、前述したパターン登録方法に従って、プレフィックスパターンリスト１２１とサフィックスパターンリスト１２２に分かれて格納されている。このパターンリストに対し前方最長一致検索を行う。具体的にはパターンリストに登録された登録パターンのうち、検索キー４０１“ＡＢＣＤＥＦＧＨＩＪＫＬＭＮ”の部分文字列で且つ前方一致する登録パターンの中で最長のパターンを検索をする。

検索時の動作説明に入る前にハッシュ値の定義を行う。プレフィックスに対するハッシュ値を計算するハッシュ関数をＨｐ（ｘ）としたとき、プレフィックスとハッシュ値の対応関係を以下のように定義する：Ｈ１＝Ｈｐ（“ＡＢＣＤ”）、Ｈ２＝Ｈｐ（“ＡＢＣＤＥＦＧＨ”）、Ｈ３＝Ｈｐ（“ＡＢＣＤＥＦＧＨＩＪＫＬ”）、Ｈ４＝Ｈｐ（“ＢＣＤＥ”）。

プレフィックス抽出部１１１は、検索キー４０１“ＡＢＣＤＥＦＧＨＩＪＫＬＭＮ”が入力されると、抽出ルールに従って検索キー４０１からＮ種類の長さのプレフィックスを作成する（Ｓ４１）。基本的にはＮ種類の長さのプレフィックスすべてを作成するが、検索キー４０１よりも長いプレフィックスについてはプレフィックスの作成を行わない。図４の例では、４種類の長さのプレフィックスが存在するが、入力された検索キー４０１の長さは１４文字なので、長さが４、８、１２であるプレフィックス４１１、４１２、４１３についてはプレフィックス作成を行うが、長さ１６のプレフィックスは作成しない。作成した３種類の長さのプレフィックス４１１〜４１３をプレフィックス検索部１１２に通知する。

プレフィックス検索部１１２の処理は、プレフィックスに対するハッシュ値の計算（Ｓ４２）と、得られたハッシュ値によるプレフィックスパターンリスト１２１の検索（Ｓ４３）の二段階で行われる。最初のハッシュ値の計算ステップ（Ｓ４２）では、プレフィクス抽出部１１１で作成されたプレフィックス４１１〜４１３の各々に、予め定めたハッシュ関数Ｈｐ（ｘ）を適用し、プレフィックスに対するハッシュ値を得る。Ｈ１、Ｈ２、Ｈ３は、それぞれプレフィックス４１１、４１２、４１３に対するハッシュ値である。

次に、得られたハッシュ値に基づきプレフィックスパターンリスト１２１の検索を行う。プレフィックス４１１のハッシュ値Ｈ１が指しているアドレスにはパターン４２１のプレフィックスが登録されており、検索キー４０１とパターン４２１はプレフィックス検索の段階では前方一致していることが分かる。同様に、プレフィックス４１２のハッシュ値Ｈ２が指しているアドレスにも対応するパターン４２３が登録されている。一方、プレフィックス４１３のハッシュ値Ｈ３に対応するエントリはプレフィックスパターンリスト１２１には登録されていない。したがって、プレフィックス検索の段階で、検索キー４０１と前方一致する登録パターンの候補は、登録パターン４２１と４２３の二つに絞られる。

サフィックス照合部１１３は、検索キー４０１とプレフィックスが一致した登録パターンのサフィックスについて一致検証を行う（Ｓ４４）。上記のプレフィックス検索で検索キー４０１と一致する登録パターンの候補は、登録パターン４２１、４２３の二つなので、この二つの登録パターンについてサフィックス照合を行う（Ｓ４４−１、Ｓ４４−３）。

登録パターン４２１の場合、検索キー４０１と一致したプレフィックスの長さは４なので、検索キー４０１のサフィックスは５文字目以降の「ＥＦＧＨＩＪＫＬＭＮ」、登録パターン４２１のサフィックスは「ＥＦ」である。登録パターン４２１と検索キー４０１はサフィックスの最初の２文字が一致しており、全体としては先頭６文字が一致している。したがって、部分文字列かつ前方一致文字列という検索条件を満たしており、登録パターン４２１は検索キー４０１に一致していることになる。一方、登録パターン４２３の場合、検索キー４０１と一致したプレフィックスの長さは８なので、検索キー４０１のサフィックスは９文字目以降の「ＩＪＫＬＭＮ」、パターン４２３のサフィックスは「ＸＹＺ」である。検索キー４０１とパターン４２３のサフィックスは明らかに異なり、パターン４２３は検索キー４０１と一致していないことになる。検索キー４０１に一致するパターンとしてパターン４２１が見つかったので、パターン４２１を検索結果として出力する。

上記の例では、検索キー４０１と一致するパターンが一つしか見つからなかったが、複数のパターンが見つかることもありえる。例えば、“ＡＢＣＤＥＦＧ”と“ＡＢＣＤＥ”という二つの登録パターンが登録されていた場合には、両者とも検索キー４０１に一致することになるが、この場合は前方最長一致検索の定義に基づき、検索キー４０１により長く一致している方の登録パターンを選択する。従って、“ＡＢＣＤＥＦＧ”が検索結果として選択される。

なお、ステップＳ４４のプレフィックス検索において、既に一致しないことが分かっている登録パターン４２２についてはサフィックス照合は行わない（ステップＳＳ４４−２は行わない）。また、ステップＳ４４−１、Ｓ４４−３のサフィックス照合において、サフィックス照合対象にしているエントリに、次のエントリを指し示すポインタ情報が登録されている場合には、このポインタ情報が指し示すエントリについてもサフィックス照合を行う。

以上で、パターン検索処理が完了する。

〔第一の実施の形態の効果〕
インデックスとしてＮ種類（Ｎ：自然数）の長さのプレフィックスを考え、パターン登録時にはＮ種類の長さのプレフィックスの中で最長のものをインデックス要素として採用し、検索時にはＮ種類のプレフィックス全てについてインデックス検索を行う。インデックスとして複数の長さの文字列を収容できることにより、インデックス検索によるパターンの絞り込みを効率的に行うことができ、登録パターンと検索キーのプレフィックス以外の部分の比較照合処理のコストを削減することが可能になる。

〔発明の第二の実施の形態〕
第一の実施の形態では、プレフィックス抽出部１１１が、検索キーから予め定められたＮ種類の長さのプレフィックスを抽出し、パターン登録部１３１が、登録パターンから予め定められているＮ種類の長さに基づいて、インデックス要素とするプレフィックスを抽出するようにしたが、本発明の第二の実施の形態では、インデックス抽出部１１１が、予め定められた区切り文字に基づいてＮ種類の長さのプレフィックスを抽出し、パターン登録部１３１が、登録パターンから予め定められている区切り文字に基づいてインデックス要素とするプレフィックスを抽出することを特徴とする。

本実施の形態におけるプレフィックス抽出部１１１の動作について、図５及び図６を使用して説明する。本説明では、Ｎ＝４として説明する。また、区切り文字を“／”とし、図５に示すような検索キー５１が入力された場合を考える。

プレフィックス抽出部１１１は、検索キー５１が入力されると、その先頭文字に注目する（図６、Ｓ６１がＹＥＳ、Ｓ６２）。その後、現在注目している文字が区切り文字“／”であるか否かを判断する（Ｓ６３）。

そして、区切り文字でない場合は、次の文字に注目する（Ｓ６２）。これに対して、区切り文字である場合は、検索キー５１の先頭文字から現在注目中の区切り文字の直前の文字までの文字列をプレフィックスとして抽出し、プレフィックス検索部１１２に渡す（Ｓ６４）。但し、注目中の文字が第１文字目である場合は、その前に文字が存在しないので、プレフィックスの抽出処理は行わない。その後、所定数Ｎ＝４個のプレフィックスを抽出したか否かを判断し（Ｓ６５）、抽出していない場合は、ステップＳ６２に戻り、抽出している場合は、処理を終了する。また、ステップＳ６１において、検索キーの次の文字がないと判断した場合も処理を終了する。

図５の例の場合、検索キー５１の第１文字目〜第７文字目には区切り文字が存在しないので、注目文字が第８文字目の区切り文字５３１となるまでは、ステップＳ６１〜Ｓ６３が繰り返し行われる。そして、注目文字が１つ目の区切り文字５３１となると（Ｓ６３がＹＥＳ）、先頭文字“ａ”から上記区切り文字５３１の直前の文字“ｍ”までを、１つめのプレフィックス５２１とする。以下、同様に先頭から２つ目の区切り文字５３２、３つ目の区切り文字５３３の直前の文字までを、それぞれ２つ目のプレフィックス５２２、３つ目のプレフィックス５２３とする（Ｓ６４）。４種類のプレフィックスを作成することになっているが、４つ目の区切り文字は検索キー５１には含まれていないため（Ｓ６１がＮＯ）、プレフィックス抽出手段１１１は、４つ目のプレフィックスは作成せず、処理を終了する。

次に、本実施の形態におけるパターン登録部１３１の動作について、図７及び図８を使用して説明する。本説明では、Ｎ＝４として説明する。また、区切り文字を“／”とし、図７に示すような登録パターン７５１が入力された場合を考える。

パターン登録部１３１は、登録パターン７５１が入力されると、その第１文字目に注目する（図８、Ｓ８１がＹＥＳ、Ｓ８２）。その後、注目した文字が区切り文字“／”であるか否かを判断する（Ｓ８３）。

そして、区切り文字でない場合は、次の文字に注目する（Ｓ８２）。これに対して、区切り文字である場合は、保持しているプレフィックス候補を、登録パターン７５１の先頭文字から現在注目中の区切り文字の直前の文字までの文字列で置き換える（ステップＳ８４）。但し、注目中の文字が第１文字目である場合は、その前に文字が存在しないので、プレフィックス候補の更新は行わない。

その後、置き換えたプレフィックス候補が第Ｎ（＝４）番目のプレフィックス候補であるか否かを判断する。そして、第４番目のプレフィックス候補でない場合（Ｓ８５がＮＯ）は、次の文字に注目する（Ｓ８２）。これに対して、第４番目のプレフィックス候補である場合には、ステップＳ８４で置き換えたプレフィックス候補を登録パターン７５１に対するインデックス要素としてプレフィックスパターンリスト１２１に登録する（ステップＳ８６）。また、ステップＳ８６では、登録パターン７５１のサフィックスをサフィックスパターンリスト１２２に登録する処理や、ポインタ情報の登録処理も行う。なお、ステップＳ８１において、検索キーの次の文字がないと判断した場合も、ステップＳ８６の処理を行う。

図７の例の場合、登録パターン７５１の第１文字目〜第４文字目までは、区切り文字でないので、ステップＳ８１〜Ｓ８３の処理が繰り返し行われる。そして、注目文字が１つ目の区切り文字７３１となると（Ｓ８３がＹＥＳ）、先頭文字“ｘ”から上記区切り文字７３１の直前の文字“ｗ”までの文字列を、第１番目のプレフィックス候補７２１として保持する（Ｓ８４）。その後，注目文字が２つめの区切り文字７３２になると（Ｓ８３がＹＥＳ）、保持している第１番目のプレフィックス候補７２１を、先頭文字“ｘ”から上記区切り文字７３２の直前の文字“ｍ”までの文字列（第２番目のプレフィックス候補７２２）で置き換える（Ｓ８４）。以下、注目文字が３つ目、４つ目の区切り文字７３３、７３４となる毎に同様の処理が行われ、第３番目、第４番目のプレフィックス候補７２３、７２４が保持される（Ｓ８４）。そして、第４番目のプレフィックス候補７２４を保持すると、それを登録パターン７５１に対するインデックス要素として、プレフィックスパターンリスト１２１に登録する（Ｓ８６）。なお、登録パターン７５１には、５つ目の区切り文字７３５も含まれているが、Ｎ＝４としているので、５つめの区切り文字７３５は区切り文字としては使用しない。

以上の説明では、区切り文字の例として“／”を挙げているが、区切り文字の長さ、位置、内容には制約はない。区切り文字の長さは１以上であればどのような長さでも構わず、図９（ａ）に示すように、“：／／”のような文字列を区切り文字として指定することや、同図（ｂ）に示すように、“Ａ”と“Ｂ”の両方を区切り文字として指定することや、同図（ｃ）に示すように、２度目と４度目に現れた“Ｃ”を区切り文字として指定することも可能である。

本実施の形態の区切り文字によるプレフィックスの決定方法は、インターネットのWWWページの場所を示すURLなどのように、長さよりも区切り文字に特徴があるパターンの検索を行う際に、プレフィックスによるパターンの絞り込みを効率的に行うことができる。

〔本発明の第三の実施の形態〕
第一の実施の形態及び第二の実施の形態は、可変長文字列の前方最長一致検索を行うものであるが、第三の実施の形態は後方最長一致検索を行うことを特徴とする。第３の実施の形態の説明は、図１０及び図１１を用いて行う。

図１０は後方最長一致検索を行う可変長文字列検索装置１ａの構成例を示すブロック図である。同図を参照すると、本実施の形態の可変長文字列検索装置１ａは、大別してパターン登録部１３１ａと検索実行部１１ａとパターン格納部１２ａとから構成される。

パターン登録部１３１ａは、登録パターン１３２が入力されると、所定の抽出ルールに基づいて登録パターン１３２の末尾部分からの長さが異なるＮ個（Ｎ：自然数）のサフィックスを抽出し、更に、選択ルールに基づいてその内の最長のものを選択し、それを登録パターンに対するインデックス要素とする。その後、インデックス要素とするサフィックスに対して、予め定めたハッシュ関数を適用し、得られたハッシュ値に応じたサフィックスパターンリスト１２１ａ上の位置に、上記サフィックスを登録する。一方、登録パターン１３２からサフィックスを除いたプレフィックスは、プレフィックスパターンリスト１２２ａに登録する。なお、サフィックスをサフィックスパターンリスト１２１ａに登録する際には、前述した実施の形態と同様に、該当するプレフィックスへのポインタ情報も登録する。

検索実行部１１ａは、サフィックス抽出部１１１ａとサフィックス検索部１１２ａとプレフィックス照合部１１３ａとから構成されている。

サフィックス抽出部１１１ａは、入力された検索キー１１４から上述した所定の抽出ルールに基づいて、Ｎ個のサフィックスを抽出し、サフィックス情報１１６ａとして出力する。

サフィックス検索部１１２ａは、サフィックス抽出部１１１ａから受信したサフィックス情報１１６ａのそれぞれについて、予め定めたハッシュ関数を適用し、得られたハッシュ値に基づいてサフィックスパターンリスト１２１ａに対して検索を行い、サフィックス検索結果１１７ａを出力する。

プレフィックス照合部１１３ａは、サフィックス検索結果１１７ａを受信し、前段のサフィックス検索部１１２ａにおいて一致するサフィックスが見つかった場合に、プレフィックスパターンリスト１２２ａから当該サフィックスに対応するエントリを読み出し、検索キー１１４のサフィックス以外の部分（プレフィックス）が登録パターンのプレフィックスと一致しているかどうかの検証を行い、一致している場合は、上記登録パターンを検索結果１１５として出力する。

なお、上述した構成を有する可変長文字列検索装置１ａは、コンピュータによって実現可能である。コンピュータによって可変長文字列検索装置１ａを実現する場合には、可変長文字列検索装置用のプログラムを記録したディスク、半導体メモリ、その他の記録媒体を用意しておく。コンピュータは、上記プログラムを読み込み、それに従って自身の動作を制御することにより、自コンピュータ上に検索実行部１１ａ、パターン格納部１２ａ及びパターン登録部１３１ａを実現する。

次に、図１１を参照して本実施の形態の動作について説明する。

第一及び第二の実施の形態では複数の長さのプレフィックスを用意しているのに対し、本実施の形態では複数の長さ（長さ４、８、１２、１６）のサフィックスを用意する（Ｓ111）。検索キー1101から作成したサフィックス1111〜1113（長さ１６のサフィックス1114は存在しない）に対してハッシュ値Ｈ１〜Ｈ３を計算し（Ｓ112）、得られたハッシュ値Ｈ１〜Ｈ３にもとづいてサフィックスパターンリスト１２１ａを検索し（Ｓ113）、検索キー1101のサフィックス1111〜1113に一致するサフィックスが見つかった登録パターンに関してのみプレフィックスパターンリスト１２２ａに格納されているプレフィックスの照合を行う。以上の手順により、後方一致検索を行うことができる。

このように、第三の実施の形態は、第一の実施例のプレフィックスとサフィックスに関する部分を入れ換えた形になっている。パターンの登録も、第一の実施例におけるパターン登録方法においてプレフィックスとサフィックスにを入れ換えて第一の実施例の登録を実行することで行うことができる。

なお、上述した各実施の形態では、ハッシュ関数を利用して検索する場合を例に挙げて説明したが、検索方法はこれに限られるものではなく、線形探索法や二分木法などを採用することもできる。

第一の実施の形態の全体構成を示すブロック図である。 第一の実施の形態におけるパターン登録時の動作を説明するための図である。 パターン登録部１３１の処理例を示すフローチャートである。 第一の実施の形態の検索時の動作を説明するための図である。 第二の実施の形態の検索時の動作を説明するための図である。 第二の実施の形態の検索時の処理例を示すフローチャートである。 第二の実施の形態の登録時の動作を用いて説明するための図である。 第二の実施の形態の登録時の処理例を示すフローチャートである。 第二の実施の形態の応用例を示す図である。 第三の実施の形態の全体構成を示すブロック図である。 第三の実施の形態の動作を説明するための図である。 前方最大一致検索を説明するための図である。 従来の技術の問題点を説明するための図である。

符号の説明

１、１ａ…可変長文字列検索装置
１１、１１ａ…検索実行部
１１１…プレフィックス抽出部
１１１ａ…サフィックス抽出部
１１２…プレフィックス検索部
１１２ａ…サフィックス検索部
１１３…サフィックス照合部
１１３ａ…プレフィックス照合部
１２、１２ａ…パターン格納部
１２１、１２２ａ…プレフィックスパターンリスト
１２１ａ、１２２…サフィックスパターンリスト
１３１、１３１ａ…パターン登録部

Claims (16)

1. パターン格納部と、
   可変長文字列データである登録パターンが入力される毎に、予め定められている複数の異なる長さの中から前記登録パターンの長さ以下で且つ最長の長さを選択し、前記登録パターンの先頭から該選択した長さ分の文字データをプレフィックスとして抽出すると共に、抽出した該プレフィックスを前記登録パターンに対するインデックス要素として前記パターン格納部に登録するパターン登録部と、
   可変長文字列データである検索キーが入力される毎に、前記検索キーから前記予め定められている複数の異なる長さのプレフィックスを抽出し、前記パターン格納部に登録されているインデックス要素を、該抽出した各長さのプレフィックスを使用して検索することにより、検索対象となる登録パターンを絞り込む検索実行部と
   を備えたことを特徴とする可変長文字列検索装置。
2. パターン格納部と、
   可変長文字列データである登録パターンが入力される毎に、前記登録パターンの先頭から末尾に向かって区切り文字の検出処理を行い、予め定められた個数の区切り文字を検出した場合は、前記登録パターンの先頭文字から該検出した区切り文字の直前の文字までの文字列によって構成されるプレフィックスを前記登録パターンに対するインデックス要素として前記パターン格納部に登録する一方、前記登録パターンの末尾まで区切り文字の検出処理を行っても前記予め定められた個数の区切り文字を検出できなかった場合は、前記登録パターンの先頭文字から最後に検出した区切り文字の直前の文字までの文字列によって構成されるプレフィックスを前記登録パターンに対するインデックス要素として前記パターン格納部に登録するパターン登録部と、
   可変長文字列データである検索キーが入力される毎に、前記予め定められた個数の区切り文字を検出するまで、前記検索キーの先頭から末尾に向かって区切り文字の検出処理を行い、区切り文字を検出する毎に、前記パターン格納部に登録されているインデックス要素を、前記検索キーの先頭文字から検出した区切り文字の直前の文字までの文字列によって構成されるプレフィックスを使用して検索することにより、検索対象となる登録パターンを絞り込む検索実行部と
   を備えたことを特徴とする可変長文字列検索装置。
3. 請求項１または２記載の可変長文字列検索装置において、
   前記パターン登録部は、前記登録パターンのプレフィックスを前記パターン格納部に登録する際、前記登録パターンからプレフィックスを除いたサフィックスを前記プレフィックスに関連付けて登録し、
   前記検索実行部は、
   前記検索キーから前記各プレフィックスを抽出するプレフィックス抽出部と、
   該プレフィックス抽出部によって抽出した前記各プレフィックスを使用して前記パターン格納部を検索するプレフィックス検索部と、
   該プレフィックス検索部によって検索されたプレフィックスに関連付けて登録されている登録パターンのサフィックスについて、前記検索キーのサフィックスとの一致検証を行うサフィックス照合部と
   を含むことを特徴とする可変長文字列検索装置。
4. 請求項１乃至３の何れか１項に記載の可変長文字列検索装置において、
   前記パターン登録部は、前記登録パターンのプレフィックスを前記パターン格納部に登録する際、前記プレフィックスに対してハッシュ関数を適用することにより得られるハッシュ値に応じた位置に登録し、
   前記プレフィックス検索部は、前記プレフィックス抽出部によって抽出された各プレフィックスに対するハッシュ値を前記ハッシュ関数を用いて求め、該求めた各ハッシュ値を使用して前記パターン格納部を検索する
   ことを特徴とする可変長文字列検索装置。
5. パターン格納部と、
   可変長文字列データである登録パターンが入力される毎に、予め定められている複数の異なる長さの中から、前記登録パターンの長さ以下で且つ最長の長さを選択し、前記登録パターンの末尾から該選択した長さ分の文字データをサフィックスとして抽出すると共に、抽出した該サフィックスを前記登録パターンに対するインデックス要素として前記パターン格納部に登録するパターン登録部と、
   可変長文字列データである検索キーが入力される毎に、前記検索キーから前記予め定められている複数の異なる長さのサフィックスを抽出し、前記パターン格納部に登録されているインデックス要素を、該抽出した各長さのサフィックスを使用して検索することにより、検索対象となる登録パターンを絞り込む検索実行部と
   を備えたことを特徴とする可変長文字列検索装置。
6. パターン格納部と、
   可変長文字列データである登録パターンが入力される毎に、前記登録パターンの末尾から先頭に向かって区切り文字の検出処理を行い、予め定められた個数の区切り文字を検出した場合は、前記登録パターンの末尾文字から該検出した区切り文字の直後の文字までの文字列によって構成されるサフィックスを前記登録パターンに対するインデックス要素として前記パターン格納部に登録する一方、前記登録パターンの先頭まで区切り文字の検出処理を行っても前記予め定められた個数の区切り文字を検出できなかった場合は、前記登録パターンの末尾文字から最後に検出した区切り文字の直後の文字までの文字列によって構成されるサフィックスを前記登録パターンに対するインデックス要素として前記パターン格納部に登録するパターン登録部と、
   可変長文字列データである検索キーが入力される毎に、前記予め定められた個数の区切り文字を検出するまで、前記検索キーの末尾から先頭に向かって区切り文字の検出処理を行い、区切り文字を検出する毎に、前記パターン格納部に登録されているインデックス要素を、前記検索キーの末尾文字から検出した区切り文字の直後の文字までの文字列によって構成されるサフィックスを使用して検索することにより、検索対象となる登録パターンを絞り込む検索実行部と
   を備えたことを特徴とする可変長文字列検索装置。
7. 請求項５または６記載の可変長文字列検索装置において、
   前記パターン登録部は、前記登録パターンのサフィックスを前記パターン格納部に登録する際、前記登録パターンからサフィックスを除いたプレフィックスを前記サフィックスに関連付けて登録し、
   前記検索実行部は、
   前記検索キーから前記各サフィックスを抽出するサフィックス抽出部と、
   該サフィックス抽出部によって抽出した前記各サフィックスを使用して前記パターン格納部を検索するサフィックス検索部と、
   該サフィックス検索部によって検索されたサフィックスに関連付けて登録されている登録パターンのプレフィックスについて、前記検索キーのプレフィックスとの一致検証を行うプレフィックス照合部と
   を含むことを特徴とする可変長文字列検索装置。
8. 請求項５乃至７の何れか１項に記載の可変長文字列検索装置において、
   前記パターン登録部は、前記登録パターンのサフィックスを前記パターン格納部に登録する際、前記サフィックスに対してハッシュ関数を適用することにより得られるハッシュ値に応じた位置に登録し、
   前記サフィックス検索部は、前記サフィックス抽出部によって抽出された各サフィックスに対するハッシュ値を前記ハッシュ関数を用いて求め、該求めた各ハッシュ値を使用して前記パターン格納部を検索する
   ことを特徴とする可変長文字列検索装置。
9. 可変長文字列データである登録パターンが入力される毎に、予め定められている複数の異なる長さの中から、前記登録パターンの長さ以下で且つ最長の長さを選択し、
   前記登録パターンの先頭から該選択した長さ分の文字データをプレフィックスとして抽出すると共に、抽出した該プレフィックスを前記登録パターンに対するインデックス要素としてパターン格納部に登録し、
   可変長文字列データである検索キーが入力される毎に、前記検索キーから前記予め定められている複数の異なる長さのプレフィックスを抽出し、
   前記パターン格納部に登録したインデックス要素を、該抽出した各長さのプレフィックスを使用して検索することにより、検索対象となる登録パターンを絞り込む
   ことを特徴とする可変長文字列検索方法。
10. 可変長文字列データである登録パターンが入力される毎に、前記登録パターンの先頭から末尾に向かって区切り文字の検出処理を行い、
    予め定められた個数の区切り文字を検出した場合は、前記登録パターンの先頭文字から該検出した区切り文字の直前の文字までの文字列によって構成されるプレフィックスを前記登録パターンに対するインデックス要素としてパターン格納部に登録する一方で、
    前記登録パターンの末尾まで区切り文字の検出処理を行っても前記予め定められた個数の区切り文字を検出できなかった場合は、前記登録パターンの先頭文字から最後に検出した区切り文字の直前の文字までの文字列によって構成されるプレフィックスを前記登録パターンに対するインデックス要素としてパターン格納部に登録し、
    可変長文字列データである検索キーが入力される毎に、前記予め定められた個数の区切り文字を検出するまで、前記検索キーの先頭から末尾に向かって区切り文字の検出処理を行い、区切り文字を検出する毎に、前記パターン格納部に登録したインデックス要素を、前記検索キーの先頭文字から検出した区切り文字の直前の文字までの文字列によって構成されるプレフィックスを使用して検索することにより、検索対象となる登録パターンを絞り込む
    ことを特徴とする可変長文字列検索方法。
11. 可変長文字列データである登録パターンが入力される毎に、予め定められている複数の異なる長さの中から、前記登録パターンの長さ以下で且つ最長の長さを選択し、前記登録パターンの末尾から該選択した長さ分の文字データをサフィックスとして抽出すると共に、抽出した該サフィックスを前記登録パターンに対するインデックス要素としてパターン格納部に登録し、
    可変長文字列データである検索キーが入力される毎に、前記検索キーから前記予め定められている複数の異なる長さのサフィックスを抽出し、前記パターン格納部に登録したインデックス要素を、該抽出した各長さのサフィックスを使用して検索することにより、検索対象となる登録パターンを絞り込む
    ことを特徴とする可変長文字列検索方法。
12. 可変長文字列データである登録パターンが入力される毎に、前記登録パターンの末尾から先頭に向かって区切り文字の検出処理を行い、
    予め定められた個数の区切り文字を検出した場合は、前記登録パターンの末尾文字から該検出した区切り文字の直後の文字までの文字列によって構成されるサフィックスを前記登録パターンに対するインデックス要素としてパターン格納部に登録する一方で、
    前記登録パターンの先頭まで区切り文字の検出処理を行っても前記予め定められた個数の区切り文字を検出できなかった場合は、前記登録パターンの末尾文字から最後に検出した区切り文字の直後の文字までの文字列によって構成されるサフィックスを前記登録パターンに対するインデックス要素としてパターン格納部に登録し、
    可変長文字列データである検索キーが入力される毎に、前記予め定められた個数の区切り文字を検出するまで、前記検索キーの末尾から先頭に向かって区切り文字の検出処理を行い、区切り文字を検出する毎に、前記パターン格納部に登録したインデックス要素を、前記検索キーの末尾文字から検出した区切り文字の直後の文字までの文字列によって構成されるサフィックスを使用して検索することにより、検索対象となる登録パターンを絞り込む
    ことを特徴とする可変長文字列検索方法。
13. パターン格納部を備えたコンピュータを可変長文字列検索装置として機能させるためのプログラムであって、前記コンピュータを、
    可変長文字列データである登録パターンが入力される毎に、予め定められている複数の異なる長さの中から、前記登録パターンの長さ以下で且つ最長の長さを選択し、前記登録パターンの先頭から該選択した長さ分の文字データをプレフィックスとして抽出すると共に、抽出した該プレフィックスを前記登録パターンに対するインデックス要素として前記パターン格納部に登録するパターン登録部と、
    可変長文字列データである検索キーが入力される毎に、前記検索キーから前記予め定められている複数の異なる長さのプレフィックスを抽出し、前記パターン格納部に登録されているインデックス要素を、該抽出した各長さのプレフィックスを使用して検索することにより、検索対象となる登録パターンを絞り込む検索実行部として機能させるためのプログラム。
14. パターン格納部を備えたコンピュータを可変長文字列検索装置として機能させるためのプログラムであって、前記コンピュータを、
    可変長文字列データである登録パターンが入力される毎に、前記登録パターンの先頭から末尾に向かって区切り文字の検出処理を行い、予め定められた個数の区切り文字を検出した場合は、前記登録パターンの先頭文字から該検出した区切り文字の直前の文字までの文字列によって構成されるプレフィックスを前記登録パターンに対するインデックス要素として前記パターン格納部に登録する一方、前記登録パターンの末尾まで区切り文字の検出処理を行っても前記予め定められた個数の区切り文字を検出できなかった場合は、前記登録パターンの先頭文字から最後に検出した区切り文字の直前の文字までの文字列によって構成されるプレフィックスを前記登録パターンに対するインデックス要素として前記パターン格納部に登録するパターン登録部と、
    可変長文字列データである検索キーが入力される毎に、前記予め定められた個数の区切り文字を検出するまで、前記検索キーの先頭から末尾に向かって区切り文字の検出処理を行い、区切り文字を検出する毎に、前記パターン格納部に登録されているインデックス要素を、前記検索キーの先頭文字から検出した区切り文字の直前の文字までの文字列によって構成されるプレフィックスを使用して検索することにより、検索対象となる登録パターンを絞り込む検索実行部として機能させるためのプログラム。
15. パターン格納部を備えたコンピュータを可変長文字列検索装置として機能させるためのプログラムであって、前記コンピュータを、
    可変長文字列データである登録パターンが入力される毎に、予め定められている複数の異なる長さの中から、前記登録パターンの長さ以下で且つ最長の長さを選択し、前記登録パターンの末尾から該選択した長さ分の文字データをサフィックスとして抽出すると共に、抽出した該サフィックスを前記登録パターンに対するインデックス要素として前記パターン格納部に登録するパターン登録部と、
    可変長文字列データである検索キーが入力される毎に、前記検索キーから前記予め定められている複数の異なる長さのサフィックスを抽出し、前記パターン格納部に登録されているインデックス要素を、該抽出した各長さのサフィックスを使用して検索することにより、検索対象となる登録パターンを絞り込む検索実行部として機能させるためのプログラム。
16. パターン格納部を備えたコンピュータを可変長文字列検索装置として機能させるためのプログラムであって、前記コンピュータを、
    可変長文字列データである登録パターンが入力される毎に、前記登録パターンの末尾から先頭に向かって区切り文字の検出処理を行い、予め定められた個数の区切り文字を検出した場合は、前記登録パターンの末尾文字から該検出した区切り文字の直後の文字までの文字列によって構成されるサフィックスを前記登録パターンに対するインデックス要素として前記パターン格納部に登録する一方、前記登録パターンの先頭まで区切り文字の検出処理を行っても前記予め定められた個数の区切り文字を検出できなかった場合は、前記登録パターンの末尾文字から最後に検出した区切り文字の直後の文字までの文字列によって構成されるサフィックスを前記登録パターンに対するインデックス要素として前記パターン格納部に登録するパターン登録部と、
    可変長文字列データである検索キーが入力される毎に、前記予め定められた個数の区切り文字を検出するまで、前記検索キーの末尾から先頭に向かって区切り文字の検出処理を行い、区切り文字を検出する毎に、前記パターン格納部に登録されているインデックス要素を、前記検索キーの末尾文字から検出した区切り文字の直後の文字までの文字列によって構成されるサフィックスを使用して検索することにより、検索対象となる登録パターンを絞り込む検索実行部として機能させるためのプログラム。

Images