(57)【要約】【課題】  インデックスを利用した前方最長一致検索において、登録パターンの重複部分の長さにばらつきがある場合においても、高い検索効率を得られるようにする。【解決手段】  リスト121には各登録パターンに対するインデックス要素として、その登録パターンから抽出ルールに従って抽出可能な、複数の長さのプレフィックスの内の、最長のプレフィックスが登録されている。リスト122には登録パターンからプレフィックスを除いたサフィックスが登録されている。プレフィックス検索部112は、検索キー114から上記抽出ルールに従って抽出した各長さのプレフィックスを使用してリスト121を検索し、各プレフィックスの内の何れかと一致する登録パターンを探し出し、サフィックス照合部113は、リスト122中のサフィックスの内の、プレフィックス検索部112で検索された登録パターンのサフィックスについて検索キーのサフィックスとの一致検証を行う。【選択図】      図１
2005165598.tif 000002
【特許請求の範囲】
【請求項１】
登録パターンから所定の抽出ルールに従って抽出可能な複数の部分文字列の内の、所定の選択ルールに従って選択した部分文字列を前記登録パターンに対するインデックス要素とし、検索キーに従った検索時には、前記検索キーから前記抽出ルールに従って抽出した各長さの部分文字列を使用して前記インデックス要素を検索し、検索対象となる登録パターンを絞り込むことを特徴とする可変長文字列検索装置。
【請求項２】
複数の登録パターンが登録されると共に、前記各登録パターンに対するインデックス要素として、その登録パターンから所定の抽出ルールに従って抽出可能な複数の部分文字列の内の、所定の選択ルールに従って選択した部分文字列が登録されたパターン格納部と、
検索キーから前記抽出ルールに従って抽出した各長さの部分文字列を使用して、前記パターン格納部上のインデックス要素を検索し、検索対象となる登録パターンを絞り込む検索実行部とを備えたことを特徴とする可変長文字列検索装置。
【請求項３】
複数の登録パターンが登録されると共に、前記各登録パターンに対するインデックス要素として、その登録パターンから所定の抽出ルールに従って抽出可能な、登録パターン先頭部分からの長さがそれぞれ異なる複数のプレフィックスの内の、最長のプレフィックスが登録されたパターン格納部と、
検索キーから前記抽出ルールに従って抽出した各長さのプレフィックスを使用して、前記パターン格納部上のインデックス要素を検索し、検索対象となる登録パターンを絞り込む検索実行部とを備えたことを特徴とする可変長文字列検索装置。
【請求項４】
請求項３記載の可変長文字列検索装置において、
前記パターン格納部には、
前記各登録パターンそれぞれの、インデックス要素となるプレフィックスを収容したプレフィックスパターンリストと、
前記各登録パターンそれぞれの、登録パターンからインデックス要素となるプレフィックスを除いたサフィックスを収容したサフィックスパターンリストとが登録され、
前記検索実行部が、
検索キーから前記抽出ルールに従って各長さのプレフィックスを抽出するプレフィックス抽出部と、
該プレフィックス抽出部で抽出された各長さのプレフィックスを使用して前記プレフィックスパターンリストを検索し、前記各長さのプレフィックスの内の何れかと一致するインデックス要素を有する登録パターンを探し出すプレフィックス検索部と、
前記サフィックスパターンリストに収容されているサフィックスの内の、前記プレフィックス検索部で探し出された登録パターンのサフィックスについて、前記検索キーのサフィックスとの一致検証を行うサフィックス照合部とを備えたことを特徴とする可変長文字列検索装置。
【請求項５】
請求項４記載の可変長文字列検索装置において、
前記プレフィックスパターンリストにおける、前記各登録パターンのインデックス要素となるプレフィックスの収容位置が、そのプレフィックスに対してハッシュ関数を適用することにより得られるハッシュ値に応じた位置であり、且つ、
前記プレフィックス検索部が、前記プレフィックス抽出部で抽出された各長さのプレフィックスに対するハッシュ値を前記ハッシュ関数を用いて求め、該求めた各ハッシュ値を使用して前記プレフィックスパターンリストを検索する構成を有することを特徴とする可変長文字列検索装置。
【請求項６】
請求項４記載の可変長文字列検索装置において、
前記抽出ルールが、抽出する複数のプレフィックスを登録パターン先頭部分からの文字数により指定するものであるか、或いは区切り文字により指定するものであることを特徴とする可変長文字列検索装置。
【請求項７】
複数の登録パターンが登録されると共に、前記各登録パターンに対するインデックス要素として、その登録パターンから所定の抽出ルールに従って抽出可能な、登録パターン末尾部分からの長さがそれぞれ異なる複数のサフィックスの内の、最長のサフィックスが登録されたパターン格納部と、
検索キーから前記抽出ルールに従って抽出した各長さのサフィックスを使用して、前記パターン格納部上のインデックス要素を検索し、検索対象となる登録パターンを絞り込む検索実行部とを備えたことを特徴とする可変長文字列検索装置。
【請求項８】
請求項７記載の可変長文字列検索装置において、
前記パターン格納部には、
前記各登録パターンそれぞれの、インデックス要素となるサフィックスを収容したサフィックスパターンリストと、
前記各登録パターンそれぞれの、登録パターンからインデックス要素となるサフィックスを除いたプレフィックスを収容したプレフィックスパターンリストとが登録され、
前記検索実行部が、
検索キーから前記抽出ルールに従って各長さのサフィックスを抽出するサフィックス抽出部と、
該サフィックス抽出部で抽出された各長さのサフィックスを使用して前記サフィックスパターンリストを検索し、前記各長さのサフィックスの内の何れかと一致するインデックス要素を有する登録パターンを探し出すサフィックス検索部と、
前記プレフィックスパターンリストに収容されているプレフィックスの内の、前記サフィックス検索部で探し出された登録パターンのプレフィックスについて、前記検索キーのプレフィックスとの一致検証を行うプレフィックス照合部とを備えたことを特徴とする可変長文字列検索装置。
【請求項９】
請求項８記載の可変長文字列検索装置において、
前記サフィックスパターンリストにおける、前記各登録パターンのインデックス要素となるサフィックスの収容位置が、そのサフィックスに対してハッシュ関数を適用することにより得られるハッシュ値に応じた位置であり、且つ、
前記サフィックス検索部が、前記サフィックス抽出部で抽出された各長さのサフィックスに対するハッシュ値を前記ハッシュ関数を用いて求め、該求めた各ハッシュ値を使用して前記サフィックスパターンリストを検索する構成を有することを特徴とする可変長文字列検索装置。
【請求項１０】
請求項８記載の可変長文字列検索装置において、
前記抽出ルールが、抽出する複数のサフィックスを登録パターン末尾部分からの文字数により指定するものであるか、或いは区切り文字により指定するものであることを特徴とする可変長文字列検索装置。
【請求項１１】
登録パターンから所定の抽出ルールに従って抽出可能な複数の部分文字列の内の、所定の選択ルールに従って選択した部分文字列を前記登録パターンに対するインデックス要素とし、
検索キーに従った検索時には、前記検索キーから前記抽出ルールに従って抽出した各長さの部分文字列を使用して前記インデックス要素を検索し、検索対象となる登録パターンを絞り込むことを特徴とする可変長文字列検索方法。
【請求項１２】
登録パターンの登録時、パターン格納部に、登録パターンを登録すると共に、前記登録パターンに対するインデックス要素として、その登録パターンから所定の抽出ルールに従って抽出可能な複数の部分文字列の内の、所定の選択ルールに従って選択した部分文字列を登録し、
登録パターンの検索時、検索キーから前記抽出ルールに従って抽出した各長さの部分文字列を使用して、前記パターン格納部上のインデックス要素を検索し、検索対象となる登録パターンを絞り込むことを特徴とする可変長文字列検索方法。
【請求項１３】
登録パターンの登録時、パターン格納部に、登録パターンを登録すると共に、前記登録パターンに対するインデックス要素として、その登録パターンから所定の抽出ルールに従って抽出可能な、登録パターン先頭部分からの長さがそれぞれ異なる複数のプレフィックスの内の、最長のプレフィックスを登録し、
登録パターンの検索時、検索キーから前記抽出ルールに従って抽出した各長さのプレフィックスを使用して、前記パターン格納部上のインデックス要素を検索し、検索対象となる登録パターンを絞り込むことを特徴とする可変長文字列検索方法。
【請求項１４】
登録パターンの登録時、パターン格納部に、登録パターンを登録すると共に、前記登録パターンに対するインデックス要素として、その登録パターンから所定の抽出ルールに従って抽出可能な、登録パターン末尾部分からの長さがそれぞれ異なる複数のサフィックスの内の、最長のサフィックスを登録し、
登録パターンの検索時、検索キーから前記抽出ルールに従って抽出した各長さのサフィックスを使用して、前記パターン格納部上のインデックス要素を検索し、検索対象となる登録パターンを絞り込むことを特徴とする可変長文字列検索方法。
【請求項１５】
コンピュータに、
登録パターンから所定の抽出ルールに従って抽出可能な複数の部分文字列の内の、所定の選択ルールに従って選択した部分文字列を前記登録パターンに対するインデックス要素とする処理、
検索キーから前記抽出ルールに従って抽出した各長さの部分文字列を使用して前記インデックス要素を検索し、検索対象となる登録パターンを絞り込む処理を行わせるためのプログラム。
【請求項１６】
複数の登録パターンが登録されると共に、前記各登録パターンに対するインデックス要素として、その登録パターンから所定の抽出ルールに従って抽出可能な複数の部分文字列の内の、所定の選択ルールに従って抽出した部分文字列が登録されたパターン格納部を備えたコンピュータを可変長文字列検索装置として機能させるためのプログラムであって、
前記コンピュータを、
検索キーから前記抽出ルールに従って抽出した各長さの部分文字列を使用して、前記パターン格納部上のインデックス要素を検索し、検索対象となる登録パターンを絞り込む検索実行部として機能させるためのプログラム。
【請求項１７】
複数の登録パターンが登録されると共に、前記各登録パターンに対するインデックス要素として、その登録パターンから所定の抽出ルールに従って抽出可能な、登録パターン先頭部分からの長さがそれぞれ異なる複数のプレフィックスの内の、最長のプレフィックスが登録されたパターン格納部を備えたコンピュータを可変長文字列検索装置として機能させるためのプログラムであって、
前記コンピュータを、
検索キーから前記抽出ルールに従って抽出した各長さのプレフィックスを使用して、前記パターン格納部上のインデックス要素を検索し、検索対象となる登録パターンを絞り込む検索実行部として機能させるためのプログラム。
【請求項１８】
複数の登録パターンが登録されると共に、前記各登録パターンに対するインデックス要素として、その登録パターンから所定の抽出ルールに従って抽出可能な、登録パターン末尾部分からの長さがそれぞれ異なる複数のサフィックスの内の、最長のサフィックスが登録されたパターン格納部を備えたコンピュータを可変長文字列検索装置として機能させるためのプログラムであって、
前記コンピュータを、
検索キーから前記抽出ルールに従って抽出した各長さのサフィックスを使用して、前記パターン格納部上のインデックス要素を検索し、検索対象となる登録パターンを絞り込む検索実行部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、可変長文字列データの情報検索技術に関し、特に可変長文字列に対する前方または後方最大一致検索の検索効率を向上させる技術に関する。
【背景技術】
【０００２】
初めに、本発明の主たる適用対象である前方最大一致検索(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に一致するサフィックスが見つかった登録パターンに関してのみプレフィックスパターンリスト１２２ａに格納されているプレフィックスの照合を行う。以上の手順により、後方一致検索を行うことができる。
【００９９】
このように、第三の実施の形態は、第一の実施例のプレフィックスとサフィックスに関する部分を入れ換えた形になっている。パターンの登録も、第一の実施例におけるパターン登録方法においてプレフィックスとサフィックスにを入れ換えて第一の実施例の登録を実行することで行うことができる。
【０１００】
なお、上述した各実施の形態では、ハッシュ関数を利用して検索する場合を例に挙げて説明したが、検索方法はこれに限られるものではなく、線形探索法や二分木法などを採用することもできる。
【図面の簡単な説明】
【０１０１】
【図１】第一の実施の形態の全体構成を示すブロック図である。
【図２】第一の実施の形態におけるパターン登録時の動作を説明するための図である。
【図３】パターン登録部１３１の処理例を示すフローチャートである。
【図４】第一の実施の形態の検索時の動作を説明するための図である。
【図５】第二の実施の形態の検索時の動作を説明するための図である。
【図６】第二の実施の形態の検索時の処理例を示すフローチャートである。
【図７】第二の実施の形態の登録時の動作を用いて説明するための図である。
【図８】第二の実施の形態の登録時の処理例を示すフローチャートである。
【図９】第二の実施の形態の応用例を示す図である。
【図１０】第三の実施の形態の全体構成を示すブロック図である。
【図１１】第三の実施の形態の動作を説明するための図である。
【図１２】前方最大一致検索を説明するための図である。
【図１３】従来の技術の問題点を説明するための図である。
【符号の説明】
【０１０２】
１、１ａ…可変長文字列検索装置
１１、１１ａ…検索実行部
１１１…プレフィックス抽出部
１１１ａ…サフィックス抽出部
１１２…プレフィックス検索部
１１２ａ…サフィックス検索部
１１３…サフィックス照合部
１１３ａ…プレフィックス照合部
１２、１２ａ…パターン格納部
１２１、１２２ａ…プレフィックスパターンリスト
１２１ａ、１２２…サフィックスパターンリスト
１３１、１３１ａ…パターン登録部
【図１】
2005165598.tif 000003
【図２】
2005165598.tif 000004
【図３】
2005165598.tif 000005
【図４】
2005165598.tif 000006
【図５】
2005165598.tif 000007
【図６】
2005165598.tif 000008
【図７】
2005165598.tif 000009
【図８】
2005165598.tif 000010
【図９】
2005165598.tif 000011
【図１０】
2005165598.tif 000012
【図１１】
2005165598.tif 000013
【図１２】
2005165598.tif 000014
【図１３】
2005165598.tif 000015