(57)【要約】【課題】前方一致検索を高速化すること。【解決手段】記憶部１ａは、子ノードと子ノードに対応する文字列部分に含まれる接頭部との対応情報、および、自ノードまでに経由するノードと自ノードとに対応する各文字列部分を経由順に連結した連結文字列を接頭部に含む文字列を示す識別情報をノード毎に記憶する。演算部１ｂは、第１の文字列が入力されると、対応情報を用いて、第１の文字列に含まれる文字列部分に対応するノードを順番に辿る。演算部１ｂは、第１の文字列のうち最後部の文字列部分に対するノードを検出すると、検出したノードに対応する識別情報に基づいて第１の文字列に前方一致する第２の文字列を出力する。【選択図】図１
2017134554.tif 000002
【特許請求の範囲】
【請求項１】
文字列の一部分である文字列部分に対応するノードを複数含み、複数のノードそれぞれの接続関係により複数の文字列を表す木構造のデータを用いて、第１の文字列に前方一致する第２の文字列を検索する検索装置であって、
子ノードと前記子ノードに対応する前記文字列部分に含まれる接頭部との対応情報、および、自ノードまでに経由するノードと自ノードとに対応する各文字列部分を経由順に連結した連結文字列を接頭部に含む文字列を示す識別情報をノード毎に記憶する記憶部と、
前記第１の文字列が入力されると、前記対応情報を用いて、前記第１の文字列に含まれる文字列部分に対応するノードを順番に辿り、前記第１の文字列のうち最後部の文字列部分に対する前記ノードを検出すると、検出した前記ノードに対応する前記識別情報に基づいて前記第２の文字列を出力する演算部と、
を有する検索装置。
【請求項２】
前記対応情報は、前記子ノードへのポインタと前記子ノードに対応する前記文字列部分の接頭部のハッシュ値とをノード毎に対応付けた情報であり、
前記演算部は、前記対応情報に含まれる前記ハッシュ値に基づいて、前記第１の文字列に含まれる文字列部分に対応するノードを辿る、
請求項１記載の検索装置。
【請求項３】
前記演算部は、前記第１の文字列のうち対応するノードを検出済である先頭側の第１の文字列部分を、前記第１の文字列から除去した第２の文字列部分を取得し、前記第２の文字列部分に含まれる接頭部に対応する前記子ノードを前記対応情報により特定することで、前記第１の文字列に含まれる文字列部分に対応するノードを辿る、
請求項１または２記載の検索装置。
【請求項４】
前記演算部は、前記木構造のデータに第３の文字列を追加することで、第１のノードの子ノードである第２のノードが前記木構造のデータに追加されると、前記第２のノードに対応する前記文字列部分の接頭部と前記第２のノードとの前記対応情報を前記第１のノードに対して追加し、前記第１のノードを含む前記第２のノードの上位ノードおよび前記第２のノードに対して前記第３の文字列を示す識別情報を追加する、
請求項１乃至３の何れか１項に記載の検索装置。
【請求項５】
前記演算部は、前記木構造のデータに第４の文字列を追加することで、第３のノードの子ノードである第４のノードに対応付けられる前記文字列部分が変更されると、前記第３のノードの前記対応情報のうちの前記第４のノードに関する情報の一部を当該変更に応じて削除し、前記第３のノードを含む前記第４のノードの上位ノードおよび前記第４のノードに対して前記第４の文字列を示す識別情報を追加する、
請求項１乃至４の何れか１項に記載の検索装置。
【請求項６】
前記演算部は、検出した前記ノードに対応する前記識別情報に基づき、前記第２の文字列として、前記複数の文字列のうち前記第１の文字列に前方一致する全ての文字列を出力する、
請求項１乃至５の何れか１項に記載の検索装置。
【請求項７】
文字列の一部分である文字列部分に対応するノードを複数含み、複数のノードそれぞれの接続関係により複数の文字列を表す木構造のデータを用いて、第１の文字列に前方一致する第２の文字列を検索する検索プログラムであって、コンピュータに、
子ノードと前記子ノードに対応する前記文字列部分に含まれる接頭部との対応情報、および、自ノードまでに経由するノードと自ノードとに対応する各文字列部分を経由順に連結した連結文字列を接頭部に含む文字列の識別情報をノード毎に設定し、
前記第１の文字列が入力されると、前記対応情報を参照して、前記第１の文字列に含まれる文字列部分に対応するノードを順番に辿り、前記第１の文字列のうち最後部の文字列部分に対する前記ノードを検出すると、検出した前記ノードに対応する前記識別情報に基づいて前記第２の文字列を出力する、
処理を実行させる検索プログラム。
【請求項８】
文字列の一部分である文字列部分に対応するノードを複数含み、複数のノードそれぞれの接続関係により複数の文字列を表す木構造のデータを用いて、第１の文字列に前方一致する第２の文字列を検索する検索方法であって、コンピュータが、
子ノードと前記子ノードに対応する前記文字列部分に含まれる接頭部との対応情報、および、自ノードまでに経由するノードと自ノードとに対応する各文字列部分を経由順に連結した連結文字列を接頭部に含む文字列の識別情報をノード毎に設定し、
前記第１の文字列が入力されると、前記対応情報を参照して、前記第１の文字列に含まれる文字列部分に対応するノードを順番に辿り、前記第１の文字列のうち最後部の文字列部分に対する前記ノードを検出すると、検出した前記ノードに対応する前記識別情報に基づいて前記第２の文字列を出力する、
検索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は検索装置、検索プログラムおよび検索方法に関する。
【背景技術】
【０００２】
情報処理の分野では、検索装置が記憶装置に格納されたデータ（例えば文書データ）に、指定された文字列の情報が含まれているか否かを検索することがある。このような検索を行うために、トライ木と呼ばれる木構造のデータを利用する検索装置の提案がある。
【０００３】
トライ木は、ルートノードを除くノードに対して、１文字あたり１ノードを割り当てた木構造のデータである。上記提案では、検索装置は、トライ木の探索処理を実行する際、入力キーから１文字ずつ取り出し、トライ木上の同じ文字のノードを辿る。例えば、検索装置は、入力キー「ｂｌｕｅ」が指定された場合に、トライ木のノードをｂ、ｌ、ｕ、ｅの順に辿ることで、「ｂｌｕｅ」に割り当てられた所定の値を検出する。
【０００４】
また、トライ木に代えて、パトリシア木と呼ばれる木構造のデータが検索に用いられることもある。パトリシア木は、トライ木において子ノードが１つのみであるノードを、当該子ノードと併合したものである。なお、二分木のデータを用いて、検索対象となるパターンのテキスト上での出現位置をもれなく、また、重複なく求める提案もある。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１０−２７７５５６号公報
【特許文献２】特開平８−２７２８２７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上記のように、木構造のデータが検索に用いられることがある。しかし、上記検索方法では、検索対象文字列間の編集距離が近似し（すなわち、検索対象文字列同士の類似度合が高い）、検索対象文字列の総数が大きいほど、検索のステップ数および１ステップの所要時間が増大するおそれがある。
【０００７】
例えば、トライ木やパトリシア木は、完全一致する文字列の検索に向いており、木構造の葉（末端）ノードのデータにのみ対応付けられる文字列をもつ。このため、前方一致検索を行う場合、木構造の途中の深さまで入力キーを検索した後、入力キーに前方一致する文字列に対応するデータ群を集めるために、木構造の葉ノードまで更に探索せねばならず、検索結果を応答するまでの時間が遅延し得る。
【０００８】
１つの側面では、本発明は、前方一致検索を高速化する検索装置、検索プログラムおよび検索方法を提供することを目的とする。
【課題を解決するための手段】
【０００９】
１つの態様では、文字列の一部分である文字列部分に対応するノードを複数含み、複数のノードそれぞれの接続関係により複数の文字列を表す木構造のデータを用いて、第１の文字列に前方一致する第２の文字列を検索する検索装置が提供される。この検索装置は、記憶部と演算部とを含む。記憶部は、子ノードと子ノードに対応する文字列部分に含まれる接頭部との対応情報、および、自ノードまでに経由するノードと自ノードとに対応する各文字列部分を経由順に連結した連結文字列を接頭部に含む文字列を示す識別情報をノード毎に記憶する。演算部は、第１の文字列が入力されると、対応情報を用いて、第１の文字列に含まれる文字列部分に対応するノードを順番に辿り、第１の文字列のうち最後部の文字列部分に対するノードを検出すると、検出したノードに対応する識別情報に基づいて第２の文字列を出力する。
【００１０】
また、１つの態様では、文字列の一部分である文字列部分に対応するノードを複数含み、複数のノードそれぞれの接続関係により複数の文字列を表す木構造のデータを用いて、第１の文字列に前方一致する第２の文字列を検索する検索プログラムが提供される。この検索プログラムは、コンピュータに、子ノードと子ノードに対応する文字列部分に含まれる接頭部との対応情報、および、自ノードまでに経由するノードと自ノードとに対応する各文字列部分を経由順に連結した連結文字列を接頭部に含む文字列の識別情報をノード毎に設定し、第１の文字列が入力されると、対応情報を参照して、第１の文字列に含まれる文字列部分に対応するノードを順番に辿り、第１の文字列のうち最後部の文字列部分に対するノードを検出すると、検出したノードに対応する識別情報に基づいて第２の文字列を出力する、処理を実行させる。
【００１１】
また、１つの態様では、文字列の一部分である文字列部分に対応するノードを複数含み、複数のノードそれぞれの接続関係により複数の文字列を表す木構造のデータを用いて、第１の文字列に前方一致する第２の文字列を検索する検索方法が提供される。この検索方法では、コンピュータが、子ノードと子ノードに対応する文字列部分に含まれる接頭部との対応情報、および、自ノードまでに経由するノードと自ノードとに対応する各文字列部分を経由順に連結した連結文字列を接頭部に含む文字列の識別情報をノード毎に設定し、第１の文字列が入力されると、対応情報を参照して、第１の文字列に含まれる文字列部分に対応するノードを順番に辿り、第１の文字列のうち最後部の文字列部分に対するノードを検出すると、検出したノードに対応する識別情報に基づいて第２の文字列を出力する。
【発明の効果】
【００１２】
１つの側面では、前方一致検索を高速化できる。
【図面の簡単な説明】
【００１３】
【図１】第１の実施の形態の検索装置を示す図である。
【図２】第２の実施の形態の検索装置のハードウェア例を示す図である。
【図３】検索装置の機能例を示す図である。
【図４】木構造データの例を示す図である。
【図５】辞書テーブルの例を示す図である。
【図６】データテーブルの例を示す図である。
【図７】最長プレフィックステーブルの例を示す図である。
【図８】ネームテーブルの例を示す図である。
【図９】格納の例を示すフローチャートである。
【図１０】キー追加の例を示すフローチャートである。
【図１１】兄弟ブロック追加の例を示すフローチャートである。
【図１２】子ブロック追加の例を示すフローチャートである。
【図１３】ブロック分割の例を示すフローチャートである。
【図１４】既存ブロックインデックス調整のフローチャートを示す図である。
【図１５】新規ブロックインデックス調整のフローチャートを示す図である。
【図１６】検索の例を示すフローチャートである。
【図１７】格納例（その１）を示す図である。
【図１８】格納例（その２）を示す図である。
【図１９】格納例（その３）を示す図である。
【図２０】検索例（その１）を示す図である。
【図２１】検索例（その２）を示す図である。
【図２２】トライ木の例を示す図である。
【図２３】パトリシア木の例を示す図である。
【発明を実施するための形態】
【００１４】
以下、本実施の形態を図面を参照して説明する。
［第１の実施の形態］
図１は、第１の実施の形態の検索装置を示す図である。検索装置１は、複数の文字列を含むデータ（例えば、プログラムのソースコードや文書などのデータ）の中から、入力キーに前方一致する文字列を検索し、検索結果を出力する。検索装置１は、文字列を検索するために、検索対象データに含まれる複数の文字列を表す木構造のデータを用いる。木構造のデータは、複数のノードを含む。ノードは、文字列の一部分である文字列部分に対応付けられる。木構造のデータは、複数のノードそれぞれの接続関係により複数の文字列を表す。ノードとノードとの関連を、エッジまたは枝などと称することもある。
【００１５】
検索装置１は、記憶部１ａおよび演算部１ｂを有する。記憶部１ａは、ＲＡＭ（Random Access Memory）などの揮発性記憶装置でもよいし、ＨＤＤ（Hard Disk Drive）やフラッシュメモリなどの不揮発性記憶装置でもよい。演算部１ｂは、ＣＰＵ（Central Processing Unit）、ＤＳＰ（Digital Signal Processor）、ＡＳＩＣ（Application Specific Integrated Circuit）、ＦＰＧＡ（Field Programmable Gate Array）などを含み得る。演算部１ｂはプログラムを実行するプロセッサであってもよい。ここでいう「プロセッサ」には、複数のプロセッサの集合（マルチプロセッサ）も含まれ得る。
【００１６】
記憶部１ａは、木構造データ２を記憶する。記憶部１ａは、木構造データ２に含まれるノード間の接続関係を示す対応情報と、探索したノードに対して出力すべき文字列を示す識別情報と、を記憶する。
【００１７】
演算部１ｂは、木構造データ２のノード毎に、対応情報と識別情報とを設定する。具体的には次の通りである。ここでは、一例として、３つの文字列（例えば、プログラムのソースコードに含まれるメソッド名）を木構造データ２に登録することを考える。第１には、“ｇｅｔＡＢ”である。第２には、“ｇｅｔＡＢＣＤ”である。第３には、“ｇｅｔＸＹＺ”である。
【００１８】
この場合、木構造データ２は、ノード２ａ，２ｂ，２ｃ，２ｄ，２ｅを含む。ノード２ａは、最上位のノード（根（root）ノード）である。ノード２ｂは、ノード２ａの子ノード（ノード２ａの直下のノード）である。ノード２ｃ，２ｅそれぞれは、ノード２ｂの子ノードである。ノード２ｄは、ノード２ｃの子ノードである。
【００１９】
ここで、ノード２ａを示すポインタを“Ｂ１”とする。ノード２ｂを示すポインタを“Ｂ２”とする。ノード２ｃを示すポインタを“Ｂ３”とする。ノード２ｄを示すポインタを“Ｂ４”とする。ノード２ｅを示すポインタを“Ｂ５”とする。また、文字列“ｇｅｔＡＢ”を示すポインタを“Ｐ１”とする。文字列“ｇｅｔＡＢＣＤ”を示すポインタを“Ｐ２”とする。文字列“ｇｅｔＸＹＺ”を示すポインタを“Ｐ３”とする。ポインタ“Ｐ１”、“Ｐ２”および“Ｐ３”は、例えば、記憶部１ａに記憶された文字列情報３における、文字列“ｇｅｔＡＢ”、“ｇｅｔＡＢＣＤ”および“ｇｅｔＸＹＺ”それぞれの格納先アドレスを示している。なお、文字列には先頭および末尾を定めることができる。文字列“ｇｅｔＡＢ”の例でいえば、先頭は最も左側の文字“ｇ”であり、末尾は最も右側の文字“Ｂ”である。
【００２０】
木構造データ２において、ノード２ａは最上位のノードであり、最初に参照されるノードであるため、上記３つの文字列のうちの何れの文字列部分にも対応付けられていない。演算部１ｂは、ノード２ｂ，２ｃ，２ｄ，２ｅに対して、パトリシア木と同様の手法により、上記３つの文字列に含まれる何れかの文字列部分を対応付けている。
【００２１】
すなわち、文字列“ｇｅｔＡＢ”、“ｇｅｔＡＢＣＤ”および“ｇｅｔＸＹＺ”の文字列部分“ｇｅｔ”はノード２ｂに対応する。文字列“ｇｅｔＡＢ”および“ｇｅｔＡＢＣＤ”の文字列部分“ＡＢ”はノード２ｃに対応する。文字列“ｇｅｔＡＢＣＤ”の文字列部分“ＣＤ”はノード２ｄに対応する。文字列“ｇｅｔＸＹＺ”の文字列部分“ＸＹＺ”はノード２ｅに対応する。このようなパトリシア木のノード関係に加えて、演算部１ｂは、更に、上記対応情報と識別情報とをノード毎に設定する。
【００２２】
対応情報は、該当ノードの子ノードと子ノードに対応する文字列部分に含まれる接頭部との対応関係を示す。ここで、接頭部（プレフィックスまたはプレフィックス部）とは、ある文字列部分から最後尾の一字を順に除去して得られる文字列または文字である（ただし、該当の文字列部分自体も含む）。
【００２３】
例えば、ノード２ａの子ノードは、ノード２ｂである。ノード２ｂに対応する文字列部分は“ｇｅｔ”である。“ｇｅｔ”の接頭部は、“ｇｅｔ”、“ｇｅ”および“ｇ”である。このため、演算部１ｂは、ノード２ａに対し、接頭部“ｇｅｔ”、“ｇｅ”および“ｇ”それぞれに対応付けて、ノード２ｂのポインタ“Ｂ２”を設定する。
【００２４】
また、例えば、ノード２ｂの子ノードは、ノード２ｃ，２ｅである。ノード２ｃに対応する文字列部分は“ＡＢ”である。“ＡＢ”の接頭部は、“ＡＢ”および“Ａ”である。このため、演算部１ｂは、ノード２ｂに対し、接頭部“ＡＢ”および“Ａ”それぞれに対応付けて、ノード２ｃのポインタ“Ｂ３”を設定する。更に、ノード２ｅに対応する文字列部分は“ＸＹＺ”である。“ＸＹＺ”の接頭部は、“ＸＹＺ”、“ＸＹ”および“Ｘ”である。このため、演算部１ｂは、ノード２ｂに対し、接頭部“ＸＹＺ”、“ＸＹ”および“Ｘ”それぞれに対応付けて、ノード２ｅのポインタ“Ｂ５”を設定する。
【００２５】
また、例えば、ノード２ｃの子ノードは、ノード２ｄである。ノード２ｄに対応する文字列部分は“ＣＤ”である。“ＣＤ”の接頭部は、“ＣＤ”および“Ｃ”である。このため、演算部１ｂは、ノード２ｃに対し、接頭部“ＣＤ”および“Ｃ”それぞれに対応付けて、ノード２ｄのポインタ“Ｂ４”を設定する。なお、ノード２ｄ，２ｅには子ノードが存在しないので、ノード２ｄ，２ｅは、対応情報の設定なし（すなわち、空文字列）である。
【００２６】
識別情報は、木構造データ２を用いてノードを探索する際に、根ノードから自ノードまでに経由するノードと自ノードとに対応する各文字列部分を経由順に連結した連結文字列を接頭部に含む文字列を示す情報である。連結文字列は、ノードの経由順に各文字列部分を最後尾に繋げていって作成された文字列であるということもできる。識別情報は、各文字列（“ｇｅｔＡＢ”、“ｇｅｔＡＢＣＤ”および“ｇｅｔＸＹＺ”）に対応するポインタでもよい。
【００２７】
例えば、ノード２ａは根ノードであり、空の入力キーに対して全文字列を応答するため、演算部１ｂは、文字列“ｇｅｔＡＢ”、“ｇｅｔＡＢＣＤ”および“ｇｅｔＸＹＺ”それぞれのポインタ“Ｐ１”、“Ｐ２”、“Ｐ３”を識別情報としてノード２ａに設定する。
【００２８】
また、ノード２ｂまでに経由するノード２ａ，２ｂに対応する文字列部分（ノード２ａの空文字列“”とノード２ｂの文字列部分“ｇｅｔ”）を経由順に連結した連結文字列は“ｇｅｔ”である。文字列情報３に含まれる文字列のうち、“ｇｅｔ”を接頭部として含む文字列は、“ｇｅｔＡＢ”、“ｇｅｔＡＢＣＤ”および“ｇｅｔＸＹＺ”である。よって、演算部１ｂは、ポインタ“Ｐ１”、“Ｐ２”、“Ｐ３”を識別情報としてノード２ｂに設定する。
【００２９】
また、ノード２ｃまでに経由するノード２ａ，２ｂおよびノード２ｃに対応する文字列部分（“ｇｅｔ”および“ＡＢ”）を経由順に連結した連結文字列は“ｇｅｔＡＢ”である。文字列情報３に含まれる文字列のうち、“ｇｅｔＡＢ”を接頭部として含む文字列は、“ｇｅｔＡＢ”および“ｇｅｔＡＢＣＤ”である。よって、演算部１ｂは、ポインタ“Ｐ１”、“Ｐ２”を識別情報としてノード２ｃに設定する。
【００３０】
また、ノード２ｄまでに経由するノード２ａ，２ｂ，２ｃに対応する文字列部分（“ｇｅｔ”、“ＡＢ”および“ＣＤ”）を経由順に連結した連結文字列は“ｇｅｔＡＢＣＤ”である。文字列情報３に含まれる文字列のうち、“ｇｅｔＡＢＣＤ”を接頭部として含む文字列は、“ｇｅｔＡＢＣＤ”である。よって、演算部１ｂは、ポインタ“Ｐ２”を識別情報としてノード２ｄに設定する。
【００３１】
また、ノード２ｅまでに経由するノード２ａ，２ｂ，２ｃに対応する文字列部分（“ｇｅｔ”および“ＸＹＺ”）を経由順に連結した連結文字列は“ｇｅｔＸＹＺ”である。文字列情報３に含まれる文字列のうち、“ｇｅｔＸＹＺ”を接頭部として含む文字列は、“ｇｅｔＸＹＺ”である。よって、演算部１ｂは、ポインタ“Ｐ３”を識別情報としてノード２ｅに設定する。
【００３２】
演算部１ｂは、こうしてノード毎に設定した対応情報および識別情報を用いて、入力された第１の文字列に前方一致する第２の文字列を検索する。
演算部１ｂは、第１の文字列が入力されると、対応情報を用いて、第１の文字列に含まれる文字列部分に対応するノードを順番に辿り、第１の文字列のうち最後部の文字列部分に対するノードを検出する。すると、演算部１ｂは、検出したノードに対応する識別情報に基づいて第２の文字列を出力する。
【００３３】
例えば、第１の文字列として、“ｇｅｔＡ”が検索装置１に入力された場合を考える。演算部１ｂは、まず、ノード２ａを参照し、ノード２ａの対応情報から“ｇｅｔＡ”の文字列部分“ｇｅｔ”に対応するノード２ｂ（ポインタ“Ｂ２”）を特定する。次いで、演算部１ｂは、ノード２ｂを参照し、ノード２ｂの対応情報から“ｇｅｔＡ”の文字列部分“ｇｅｔ”を除いた文字列部分“Ａ”に対応するノード２ｃ（ポインタ“Ｂ３”）を特定する。この場合、文字列部分“Ａ”は、入力された文字列“ｇｅｔＡ”の最後部の文字列部分である。すなわち、演算部１ｂは、最後部の文字列部分“Ａ”に対するノード２ｃを検出する。この場合、演算部１ｂは、文字列情報３に含まれる文字列のうち、ノード２ｃに対応する識別情報“Ｐ１，Ｐ２”に基づいて文字列“ｇｅｔＡＢ”および“ｇｅｔＡＢＣＤ”を、“ｇｅｔＡ”に前方一致する第２の文字列として出力する。
【００３４】
このとき、演算部１ｂは、“ｇｅｔＡ”に対してノード２ｃまで辿りさえすれば、ノード２ｃに対して設定された識別情報“Ｐ１”、“Ｐ２”を用いて、“ｇｅｔＡ”に前方一致する“ｇｅｔＡＢ”および“ｇｅｔＡＢＣＤ”を取得できる。すなわち、ノード２ｃを検出した後、既存のパトリシア木のように、前方一致した文字列に対応付いたデータ群の収集のために、葉ノードまで探索せずに済むことになる。したがって、当該収集のための探索ステップを削減でき、前方一致検索を高速化できる。特に、検索対象の文字列群において類似する文字列が多く存在し、また検索対象の文字列の総数が多くなるほど、削減される探索ステップ数は多くなり、前方一致検索の高速化の効果は大きい。
【００３５】
なお、演算部１ｂは、対応情報において、各ノードを辿るためのキーを、文字列部分の接頭部そのものとする代わりに、接頭部毎のハッシュ値としてもよい。例えば、演算部１ｂは、ノード２ｂの対応情報において、文字列部分“Ａ”、“ＡＢ”それぞれのハッシュ値に対応付けて、ノード２ｃのポインタ“Ｂ３”を対応付ける。また、演算部１ｂは、ノード２ｂの対応情報において、文字列部分“Ｘ”、“ＸＹ”、“ＸＹＺ”それぞれのハッシュ値に対応付けて、ノード２ｅのポインタ“Ｂ５”を対応付ける。そして、演算部１ｂは、入力された文字列の文字列部分毎のハッシュ値によって、各ノードを辿る。すると、ノードの探索に要する時間を削減し、前方一致検索を更に高速化できる。なぜなら、ハッシュ値は、固定長の情報であり、次ノードの選択に要する時間を当該ハッシュ値の長さによって決まる所要時間よりも大きくならないように制限できるからである。検索対象の文字列長が長くなるほど、また、１ノード当たりの子ノードの数が多くなるほど、ハッシュ値を用いてノードを辿ることによる検索高速化の効果は大きい。
【００３６】
上記のように、検索装置１は、検索対象文字列間の編集距離が近い、すなわち、検索対象文字列同士の類似する度合が高く、検索対象文字列の総数が大きい場合に特に有用である。このような検索対象文字列を多く含むデータの一例として、プログラムのソースコードが挙げられる。例えば、ソフトウェアの開発において、ソースコードに含まれる文字列の解析結果全体の中から特定のメソッド名や関数名などを前方一致検索することが考えられる。そこで、以下では、ソースコードに含まれる文字列の解析結果全体に対する前方一致検索を行う場合を例示して、上記検索を更に具体的に説明する。
【００３７】
［第２の実施の形態］
図２は、第２の実施の形態の検索装置のハードウェア例を示す図である。検索装置１００は、プログラムのソースコードに含まれるメソッド名の全体集合の中から、ユーザにより入力された文字列に前方一致するメソッド名を検索し、出力する。これにより、ユーザによるメソッドの特定を支援する。
【００３８】
プログラムのソースコードには、互いに類似する名称のメソッドが大量に含まれ得る。例えば、あるオペレーティングシステム（ＯＳ：Operating System）のソースコードには、約１３０万ものメソッドが含まれており、“ｇｏ”、“ｇｅｔ”、“ｓｅｔ”などの定型の文字列を接頭部に含む類似するメソッド名が大量に存在し得る。検索装置１００は、このような大量のメソッド名の中から、入力された文字列に前方一致するメソッド名を高速に検索する機能を提供し、ユーザによるソフトウェアの開発を支援する。
【００３９】
検索装置１００は、プロセッサ１０１、ＲＡＭ１０２、ＨＤＤ１０３、画像信号処理部１０４、入力信号処理部１０５、媒体リーダ１０６および通信インタフェース１０７を有する。各ユニットは検索装置１００のバスに接続されている。
【００４０】
プロセッサ１０１は、検索装置１００の情報処理を制御する。プロセッサ１０１は、マルチプロセッサであってもよい。プロセッサ１０１は、例えばＣＰＵ、ＤＳＰ、ＡＳＩＣまたはＦＰＧＡなどである。プロセッサ１０１は、ＣＰＵ、ＤＳＰ、ＡＳＩＣ、ＦＰＧＡなどのうちの２以上の要素の組み合わせであってもよい。
【００４１】
ＲＡＭ１０２は、検索装置１００の主記憶装置である。ＲＡＭ１０２は、プロセッサ１０１に実行させるＯＳのプログラムやアプリケーションプログラムの少なくとも一部を一時的に記憶する。また、ＲＡＭ１０２は、プロセッサ１０１による処理に用いる各種データを記憶する。
【００４２】
ＨＤＤ１０３は、検索装置１００の補助記憶装置である。ＨＤＤ１０３は、内蔵した磁気ディスクに対して、磁気的にデータの書き込みおよび読み出しを行う。ＨＤＤ１０３は、ＯＳのプログラム、アプリケーションプログラム、および各種データを記憶する。検索装置１００は、フラッシュメモリやＳＳＤ（Solid State Drive）などの他の種類の補助記憶装置を備えてもよく、複数の補助記憶装置を備えてもよい。
【００４３】
画像信号処理部１０４は、プロセッサ１０１からの命令に従って、検索装置１００に接続されたディスプレイ１１に画像を出力する。ディスプレイ１１としては、ＣＲＴ（Cathode Ray Tube）ディスプレイや液晶ディスプレイなどを用いることができる。
【００４４】
入力信号処理部１０５は、検索装置１００に接続された入力デバイス１２から入力信号を取得し、プロセッサ１０１に出力する。入力デバイス１２としては、例えば、マウスやタッチパネルなどのポインティングデバイス、キーボードなどを用いることができる。
【００４５】
媒体リーダ１０６は、記録媒体１３に記録されたプログラムやデータを読み取る装置である。記録媒体１３として、例えば、フレキシブルディスク（ＦＤ：Flexible Disk）やＨＤＤなどの磁気ディスク、ＣＤ（Compact Disc）やＤＶＤ（Digital Versatile Disc）などの光ディスク、光磁気ディスク（ＭＯ：Magneto-Optical disk）を使用できる。また、記録媒体１３として、例えば、フラッシュメモリカードなどの不揮発性の半導体メモリを使用することもできる。媒体リーダ１０６は、例えば、プロセッサ１０１からの命令に従って、記録媒体１３から読み取ったプログラムやデータをＲＡＭ１０２またはＨＤＤ１０３に格納する。
【００４６】
通信インタフェース１０７は、ネットワーク１４を介して他の装置と通信を行う。通信インタフェース１０７は、有線通信インタフェースでもよいし、無線通信インタフェースでもよい。
【００４７】
図３は、検索装置の機能例を示す図である。検索装置１００は、記憶部１１０、格納受付部１２０、格納制御部１３０、ブロック更新部１４０、インデックス調整部１５０、検索受付部１６０および検索処理部１７０を有する。記憶部１１０は、ＲＡＭ１０２またはＨＤＤ１０３に確保された記憶領域として実現される。
【００４８】
格納受付部１２０、格納制御部１３０、ブロック更新部１４０、インデックス調整部１５０、検索受付部１６０および検索処理部１７０は、ＲＡＭ１０２に記憶されたプログラムをプロセッサ１０１が実行することで実現される。また、格納制御部１３０、ブロック更新部１４０およびインデックス調整部１５０の各機能は再帰的に呼び出される（例えば、格納受付部１２０に相当するプロセスは常駐してもよい）。検索処理部１７０は、検索受付部１６０によって呼び出される（例えば、検索処理部１７０に相当するプロセスは常駐してもよい）。例えば、呼び出しのたびに、各部に相当するプロセスが検索装置１００のＯＳにより生成され、処理完了後に該当プロセスは削除されると考えてもよい。
【００４９】
記憶部１１０は、検索対象となる文字列集合の情報を記憶する。各文字列は、記憶部１１０における格納アドレスを示すポインタによって表される。記憶部１１０は、文字列集合に含まれる各文字列を表す木構造データを記憶する。木構造データの詳細は後述される。
【００５０】
格納受付部１２０は、記憶部１１０に記憶された木構造データに新たに追加する文字列を受け付ける。例えば、ユーザは、入力デバイス１２を操作して、ソフトウェアの開発に伴って追加した新規メソッド名（すなわち、新規文字列）を検索装置１００に入力できる。あるいは、格納受付部１２０は、ソースコードの解析結果から、ソースコードに新規に追加されたメソッド名を取得してもよい。格納受付部１２０は、受け付けた新規文字列を格納制御部１３０に通知し、木構造データへの新規文字列の追加を指示する。格納受付部１２０は、格納制御部１３０から格納完了の通知（所定の返り値）を受け付けると、格納が完了した旨を、ディスプレイ１１を用いて表示させる。ユーザは、ディスプレイ１１の表示を閲覧することで、新規文字列の格納が完了したことを確認できる。
【００５１】
格納制御部１３０は、新規文字列の木構造データに対する格納を制御する。例えば、格納制御部１３０は、あるノードに対して子ノードの追加を制御する。あるいは、格納制御部１３０は、あるノードに対応する文字列部分を２つに分割し、分割後の２つの文字列部分に対して２つのノードの追加を制御することもある。ここで、第２の実施の形態の例では、木構造データにおける「ノード」を「ブロック」と称することとする。格納制御部１３０は、ブロックの追加や分割をブロック更新部１４０に指示する。
【００５２】
ブロック更新部１４０は、格納制御部１３０によるブロックの追加や分割の指示に応じて、ブロックの追加や分割を実行する。ブロック更新部１４０は、ブロック更新に伴う各ブロックのインデックス調整をインデックス調整部１５０に指示する。
【００５３】
インデックス調整部１５０は、ブロック更新部１４０によりブロック分割が行われる場合に、ブロック分割に伴うインデックス調整を行う。具体的には、インデックス調整部１５０は、ブロック分割により新たに作成された新規ブロックに対する子ブロックの参照先を示すポインタを設定したり、既存ブロックに対応する文字列部分の情報を変更したりする。
【００５４】
検索受付部１６０は、入力キーを受け付ける。入力キーは、文字でもよいし文字列でもよい。検索受付部１６０は、入力キーに前方一致する前方一致文字列の検索を検索処理部１７０に指示する。検索受付部１６０は、検索結果として、前方一致文字列を検索処理部１７０から受け付けると、検索された前方一致文字列を、ディスプレイ１１を用いて表示させる。ユーザは、ディスプレイ１１の表示を閲覧することで、入力キーに前方一致するメソッド名を特定できる。
【００５５】
検索処理部１７０は、検索受付部１６０から受け付けた入力キーに前方一致する文字列を、記憶部１１０に記憶された木構造データを用いて検索する。検索処理部１７０は、入力キーに含まれる文字列部分について、入力キーの先頭の文字列部分から木構造データの各ブロックを順番に辿ることで、入力キーに含まれる全ての文字列部分を辿れたかを判定する。全ての文字列部分に対応するノードを辿れた場合には、入力キーに前方一致するメソッド名が存在することになる。全ての文字列部分に対応するノードを辿れなかった（ある文字列部分に対応するノードを探索できなかった）場合は、入力キーに前方一致するメソッド名が存在しない（前方一致検索にマッチするメソッド名なし）ということになる。
【００５６】
検索処理部１７０は、入力キーに前方一致するメソッド名が存在する場合、入力キーについて辿ったノードのうち、最後に到達したノードに含まれるポインタ（文字列を示すポインタ）を取得する。そして、検索処理部１７０は、当該ポインタにより前方一致文字列を全て取得して、検索受付部１６０に応答する。一方、検索処理部１７０は、入力キーに前方一致するメソッド名が存在しない場合、マッチするメソッド名なしを検索受付部１６０に応答する。
【００５７】
図４は、木構造データの例を示す図である。木構造データ５０は、記憶部１１０に記憶されるデータ構造のイメージを図示したものである。木構造データ５０は、後述するように、例えば関係データベース（ＲＤＢ：Relational DataBase）におけるテーブルによって実装できる。木構造データ５０は、ブロックＮ１，Ｎ２，Ｎ３，Ｎ４，Ｎ５を有する。
【００５８】
ブロックＮ１，Ｎ２，Ｎ３，Ｎ４，Ｎ５それぞれは、ノードと呼ばれてもよい。ブロックＮ１，Ｎ２，Ｎ３，Ｎ４，Ｎ５それぞれは、ｄｉｃ（DICtionary）、ｄａｔａおよびｌｇｐ（LonGest Prefix）の情報を含む。
【００５９】
木構造データ５０は、一例として、３つのメソッド名を表している。第１のメソッド名は、“ｇｏｂａｃｋ”である。第２のメソッド名は、“ｇｏｂａｃｋｏｒｆ”である。第３のメソッド名は、“ｇｏｆｏｒｗ”である。
【００６０】
ｄｉｃは、後述の辞書テーブルに相当する。ｄｉｃは、あるブロックから当該ブロックの子ブロックを示すポインタ（あるいは、子ブロックへのエッジ）を表す情報である。当該ポインタは、ブロックを識別する情報なので、ブロックＩＤと呼ばれてもよい。当該ポインタは、子ブロックに対応する文字列部分の接頭部毎のハッシュ値に対応付けられる（図４では、ハッシュ関数を“ｈａｓｈ（）”と表している）。ハッシュ関数は、ある文字または文字列に対して固定長（例えば、１６バイトなど）の数値を計算するための関数である。ハッシュ関数により算出されたハッシュ値は、例えば、要約値やダイジェスト値などと呼ばれることもある。
【００６１】
ここで、ブロックＮ１のブロックＩＤは“ｂ１”である。ブロックＮ２のブロックＩＤは“ｂ２”である。ブロックＮ３のブロックＩＤは“ｂ３”である。ブロックＮ４のブロックＩＤは“ｂ４”である。ブロックＮ５のブロックＩＤは“ｂ５”である。
【００６２】
例えば、各ブロックのｄｉｃには次のような情報が登録されている。ブロックＮ１のｄｉｃでは、ハッシュ値ｈａｓｈ（“ｇ”）、ｈａｓｈ（“ｇｏ”）それぞれに対して、次に参照すべきブロックのブロックＩＤとして、ブロックＩＤ“ｂ４”が登録されている。
【００６３】
ブロックＮ２のｄｉｃでは、ハッシュ値ｈａｓｈ（“ｏ”）、ｈａｓｈ（“ｏｒ”）、ｈａｓｈ（“ｏｒｆ”）それぞれに対して、次に参照すべきブロックのブロックＩＤとして、ブロックＩＤ“ｂ３”が登録されている。
【００６４】
ブロックＮ３については、ブロックＮ３に子ノードが存在しないため、ブロックＮ３のｄｉｃは、設定なし（空文字列）である。
ブロックＮ４のｄｉｃでは、ハッシュ値ｈａｓｈ（“ｂ”）、ｈａｓｈ（“ｂａ”）、ｈａｓｈ（“ｂａｃ”）、ｈａｓｈ（“ｂａｃｋ”）それぞれに対して、次に参照すべきブロックのブロックＩＤとしてブロックＩＤ“ｂ２”が登録されている。また、ブロックＮ４のｄｉｃでは、ハッシュ値ｈａｓｈ（“ｆ”）、ｈａｓｈ（“ｆｏ”）、ｈａｓｈ（“ｆｏｒ”）、ｈａｓｈ（“ｆｏｒｗ”）それぞれに対して、次に参照すべきブロックのブロックＩＤとしてブロックＩＤ“ｂ５”が登録されている。
【００６５】
ブロックＮ５については、ブロックＮ５に子ノードが存在しないため、ブロックＮ５のｄｉｃは設定なし（空文字列）である。
ｄａｔａは、後述のデータテーブルに相当する。検索対象文字列（ｅｎｔｉｔｙと称することがある）へのポインタを格納した情報である。例えば、ポインタ“Ｍ１”は、メソッド名“ｇｏｂａｃｋ”を示す。ポインタ“Ｍ２”は、メソッド名“ｇｏｂａｃｋｏｒｆ”を示す。ポインタ“Ｍ３”は、メソッド名“ｇｏｆｏｒｗ”を示す。
【００６６】
例えば、ブロックＮ１のｄａｔａには、ポインタのリスト“Ｍ１，Ｍ２，Ｍ３”が登録されている。ブロックＮ２のｄａｔａには、ポインタのリスト“Ｍ１，Ｍ２”が登録されている。ブロックＮ３のｄａｔａには、ポインタのリスト“Ｍ２”が登録されている。ブロックＮ４のｄａｔａには、ポインタのリスト“Ｍ１，Ｍ２，Ｍ３”が登録されている。ブロックＮ５のｄａｔａには、ポインタのリスト“Ｍ３”が登録されている。
【００６７】
ｌｇｐは、後述の最長プレフィックステーブルに相当する。ただし、ブロックＮ１は、根ノードに相当するため、ブロックＮ１に対応する文字列部分は存在しない。このため、ブロックＮ１のｌｇｐは設定なし（空文字列）である。ブロックＮ４は、文字列部分“ｇｏ”に対応するため、ｌｇｐ＝“ｇｏ”である。ブロックＮ２は、文字列部分“ｂａｃｋ”に対応するため、ｌｇｐ＝“ｂａｃｋ”である。ブロックＮ３は、文字列部分“ｏｒｆ”に対応するため、ｌｇｐ＝“ｏｒｆ”である。ブロックＮ５は、文字列部分“ｆｏｒｗ”に対応するため、ｌｇｐ＝“ｆｏｒｗ”である。
【００６８】
ここで、ノードＮ１以外の各ノードに対して上位ノードを定めることができる。具体的には、ノードＮ１を出発点として、あるノードに達するまでに経由する各ノードが当該ノードの上位ノードである。図４の例において、ノードＮ４の上位ノードはＮ１である。ノードＮ２の上位ノードは、ノードＮ１，Ｎ４である。ノードＮ３の上位ノードは、ノードＮ１，Ｎ４，Ｎ２である。ノードＮ５の上位ノードは、ノードＮ１，Ｎ４である。
【００６９】
次に、木構造データ５０を実装するためのデータ構造を例示する。
図５は、辞書テーブルの例を示す図である。辞書テーブル１１１は、記憶部１１０に格納される。辞書テーブル１１１は、ブロックＩＤ（IDentifier）、ハッシュ値および次ブロックＩＤの項目を含む。
【００７０】
ブロックＩＤの項目には、ブロックＩＤが登録される。ブロックＩＤは、ブロックを示すポインタと考えることもできる。ハッシュ値の項目には、文字列部分の接頭部毎のハッシュ値が登録される。次ブロックＩＤの項目には、ハッシュ値に応じて次に辿るべきブロックＩＤ（子ノードのブロックＩＤ）が登録される。次ブロックＩＤは、次に辿るべきブロックＩＤを示すポインタと考えることもできる。
【００７１】
例えば、辞書テーブル１１１には、ブロックＩＤが“ｂ１”、ハッシュ値が“ｈａｓｈ（“ｇ”）”、次ブロックＩＤが“ｂ４”という情報が登録される。これは、ブロックＮ１（ブロックＩＤ“ｂ１”）においてハッシュ値ｈａｓｈ（“ｇ”）が、次ブロックであるブロックＮ４（次ブロックＩＤ“ｂ４”）に対応付けられていることを示す。辞書テーブル１１１には、他のブロックについても同様にして、各文字列部分のハッシュ値に対して次ブロックＩＤが登録される。ただし、子ブロックをもたないブロック（例えば、ブロックＮ３，Ｎ５）に関するレコードは辞書テーブル１１１に登録されなくてよい。
【００７２】
図６は、データテーブルの例を示す図である。データテーブル１１２は、記憶部１１０に格納される。データテーブル１１２は、ブロックＩＤおよびデータリストの項目を含む。
【００７３】
ブロックＩＤの項目には、ブロックＩＤが登録される。データリストの項目には、メソッド名に対応するポインタのリストが登録される。
例えば、データテーブル１１２には、ブロックＩＤが“ｂ１”、データリストが“Ｍ１，Ｍ２，Ｍ３”という情報が登録されている。これは、ブロックＮ１（ブロックＩＤ“ｂ１”）に対して、メソッド名を示すポインタ“Ｍ１，Ｍ２，Ｍ３”が対応付けられていることを示す。
【００７４】
また、例えば、データテーブル１１２には、ブロックＩＤが“ｂ２”、データリストが“Ｍ１，Ｍ２”という情報が登録されている。これは、ブロックＮ２（ブロックＩＤ“ｂ２”）に対して、メソッド名を示すポインタ“Ｍ１，Ｍ２”が対応付けられていることを示す。データテーブル１１２には、他のブロックについても同様にして、データリストが登録される。
【００７５】
図７は、最長プレフィックステーブルの例を示す図である。最長プレフィックステーブル１１３は、記憶部１１０に格納される。最長プレフィックステーブル１１３は、ブロックＩＤおよびｌｇｐの項目を含む。
【００７６】
ブロックＩＤの項目には、ブロックＩＤが登録される。ｌｇｐの項目には、当該ブロックＩＤのブロックで扱われる最長プレフィックスが登録される。最長プレフィックスは、該当のブロックに対応する文字列部分のうちの最長の接頭部であり、当該文字列部分そのものを示す。
【００７７】
例えば、最長プレフィックステーブル１１３には、ブロックＩＤが“ｂ１”、ｌｇｐが“”（空文字列）という情報が登録される。これは、ブロックＮ１のｌｇｐが空文字列であることを示す（ブロックＮ１は、ルートであるため）。
【００７８】
また、例えば、最長プレフィックステーブル１１３には、ブロックＩＤが“ｂ２”、ｌｇｐが“ｂａｃｋ”という情報が登録される。これは、ブロックＮ２のｌｇｐ（すなわち、ブロックＮ２に対応する文字列部分）が、“ｂａｃｋ”であることを示す。最長プレフィックステーブル１１３には、他のブロックについても同様にして、ｌｇｐが登録される。
【００７９】
図８は、ネームテーブルの例を示す図である。ネームテーブル１１４は、記憶部１１０に記憶される。ネームテーブル１１４は、ハッシュ値に対応するハッシュ関数への入力値を取得するためのテーブルである（図４ではネームテーブル１１４に相当する情報の図示を省略した）。ネームテーブル１１４は、ブロックＩＤ、ハッシュ値およびｎａｍ（NAMe）値の項目を含む。
【００８０】
ブロックＩＤの項目には、ブロックＩＤが登録される。ハッシュ値の項目には、ハッシュ値が登録される。ｎａｍ値の項目には、ｎａｍ値が登録される。ｎａｍ値は、該当のハッシュ値を得るためにハッシュ関数の入力となった文字または文字列の情報である。
【００８１】
例えば、ネームテーブル１１４には、ブロックＩＤが“ｂ１”、ハッシュ値が“ｈａｓｈ（“ｇ”）”、ｎａｍ値が“ｇ”という情報が登録されている。これは、ブロックＮ１に対応付けられたハッシュ値ｈａｓｈ（“ｇ”）を得るために、ハッシュ関数“ｈａｓｈ（）”に文字“ｇ”が入力されたことを示す。
【００８２】
また、例えば、ネームテーブル１１４には、ブロックＩＤが“ｂ２”、ハッシュ値が“ｈａｓｈ（“ｏｒ”）”、ｎａｍ値が“ｏｒ”という情報が登録されている。これは、ブロックＮ２に対応付けられたハッシュ値ｈａｓｈ（“ｏｒ”）を得るために、ハッシュ関数“ｈａｓｈ（）”に文字“ｏｒ”が入力されたことを示す。ネームテーブル１１４には、他のブロックについても同様にして、ハッシュ値とｎａｍ値との対応関係が登録される。ただし、子ブロックをもたないブロック（例えば、ブロックＮ３，Ｎ５）に関するレコードはネームテーブル１１４に登録されなくてよい。
【００８３】
次に、以上のような構成の検索装置１００による処理手順を説明する。まず、新規文字列格納時における、辞書テーブル１１１、データテーブル１１２、最長プレフィックステーブル１１３およびネームテーブル１１４の更新方法を例示する。
【００８４】
図９は、格納の例を示すフローチャートである。以下、図９に示す処理をステップ番号に沿って説明する。
（Ｓ１１）格納受付部１２０は、新たに格納するキー（文字列）の情報を受け付ける。例えば、ユーザは、入力デバイス１２を操作して、新たに格納するキーの情報を検索装置１００に入力できる。ここで、キーの情報は、格納対象の文字列（本例ではメソッド名に相当）、当該メソッド名の格納先を示すポインタを含む。また、木構造データ５０の各ブロックのうち、ステップＳ１１の時点で着目するブロック（着目ブロック（current block）と称する）は、ルートであるブロックＮ１（ブロックＩＤ“ｂ１”）である。
【００８５】
（Ｓ１２）格納受付部１２０は、格納制御部１３０を呼び出して、格納制御部１３０に受け付けたキーの情報を渡し、キーの格納を指示する。格納制御部１３０は、指示されたキーの格納処理を実行し、格納受付部１２０に所定の返り値を返す。格納受付部１２０は、格納制御部１３０から所定の返り値を受け付けることで、格納完了と判断し、ディスプレイ１１に格納完了を表示させる。
【００８６】
図１０は、キー追加の例を示すフローチャートである。以下、図１０に示す処理をステップ番号に沿って説明する。以下に示す処理は、ステップＳ１２における格納制御部１３０の処理に相当する。
【００８７】
（Ｓ２１）格納制御部１３０は、ネームテーブル１１４を参照して、呼出し元から受け付けたキーの各プレフィックスのうち、着目ブロックに対応するｎａｍ値に一致する最長のものをｃｏｍｍｏｎＫｅｙ（共通キー）とする。ただし、本ステップにおいて、受け付けたキーによっては、当該ｃｏｍｍｏｎＫｅｙが存在しないこともある。また、格納制御部１３０の呼出し元は、格納受付部１２０であることもあるし、ブロック更新部１４０であることもある。
【００８８】
（Ｓ２２）格納制御部１３０は、ｃｏｍｍｏｎＫｅｙがあるか否かを判定する。ｃｏｍｍｏｎＫｅｙがない場合、処理をステップＳ２３に進める。ｃｏｍｍｏｎＫｅｙがある場合、処理をステップＳ２４に進める。
【００８９】
（Ｓ２３）格納制御部１３０は、ブロック更新部１４０を呼び出して、兄弟ブロック追加処理の実行を、ブロック更新部１４０に指示する。兄弟ブロック追加処理の詳細は後述される。そして、処理をステップＳ３２に進める。
【００９０】
（Ｓ２４）格納制御部１３０は、着目ブロックのハッシュ値ｈａｓｈ（ｃｏｍｍｏｎＫｅｙ）に対応する参照先ブロック（辞書テーブル１１１における次ブロックＩＤに相当）を特定する。
【００９１】
（Ｓ２５）格納制御部１３０は、最長プレフィックステーブル１１３を参照して、参照先ブロックのｌｇｐがキーの真の部分文字列であるか否かを判定する。参照先ブロックのｌｇｐがキーの真の部分文字列である場合、処理をステップＳ２６に進める。参照先ブロックのｌｇｐがキーの真の部分文字列でない場合、処理をステップＳ２７に進める。ここで、「ｌｇｐがキーの真の部分文字列である」とは、ｌｇｐで示される文字列がキーで示される文字列と同一でなく、かつ、ｌｇｐで示される文字列がキーで示される文字列の一部分であることを意味する。すなわち、キーで示される文字列が、ｌｇｐで示される文字列（例えば、“ａｂ”）の末尾に１つ以上の文字（例えば、“ｃｄ”）が追加された文字列（例えば、“ａｂｃｄ”）である場合に、「ｌｇｐがキーの真の部分文字列である」ということになる。
【００９２】
（Ｓ２６）格納制御部１３０は、ブロック更新部１４０を呼び出して、子ブロック追加処理の実行を、ブロック更新部１４０に指示する。子ブロック追加処理の詳細は後述される。そして、処理をステップＳ３２に進める。
【００９３】
（Ｓ２７）格納制御部１３０は、参照先ブロックのｌｇｐの先頭からｃｏｍｍｏｎＫｅｙを除去した文字列をｏｌｄＴｒａｉｌｉｎｇＫｅｙとする。
（Ｓ２８）格納制御部１３０は、キーの先頭からｃｏｍｍｏｎＫｅｙを除去した文字列をｎｅｗＴｒａｉｌｉｎｇＫｅｙとする。
【００９４】
（Ｓ２９）格納制御部１３０は、ｏｌｄＴｒａｉｌｉｎｇＫｅｙとｎｅｗＴｒａｉｌｉｎｇＫｅｙとが共に空文字列であるか否かを判定する。共に空文字列でない場合、処理をステップＳ３０に進める。共に（両方とも）空文字列である場合、処理をステップＳ３１に進める。ステップＳ２１で受け付けたキーが既に格納済である場合に、ｏｌｄＴｒａｉｌｉｎｇＫｅｙとｎｅｗＴｒａｉｌｉｎｇＫｅｙとが両方とも空文字列になる。
【００９５】
（Ｓ３０）格納制御部１３０は、ブロック更新部１４０を呼び出して、ブロック分割処理の実行を、ブロック更新部１４０に指示する。ブロック分割処理の詳細は後述される。そして、処理をステップＳ３２に進める。
【００９６】
（Ｓ３１）格納制御部１３０は、着目ブロックのブロックＩＤを返り値として呼出し元（格納受付部１２０またはブロック更新部１４０）へ返す。そして、処理を終了する。
（Ｓ３２）格納制御部１３０は、ブロック更新部１４０による処理の実行結果に応じた返り値を、呼出し元（格納受付部１２０またはブロック更新部１４０）へ返す。そして、処理を終了する。
【００９７】
図１１は、兄弟ブロック追加の例を示すフローチャートである。以下、図１１に示す処理をステップ番号に沿って説明する。以下に示す処理は、図１０のステップＳ２３におけるブロック更新部１４０の処理に相当する。
【００９８】
（Ｓ４１）ブロック更新部１４０は、新規ブロックを作成し、新規ブロックのｌｇｐにキーを代入する。具体的には、ブロック更新部１４０は、最長プレフィックステーブル１１３に、新規ブロックのブロックＩＤを格納したレコードを追加する。ブロック更新部１４０は、最長プレフィックステーブル１１３の当該ブロックＩＤのレコードのｌｇｐに、キーを登録する。なお、兄弟ブロック追加の場合、ステップＳ４１で作成される新規ブロックに子ブロックは存在しないので、ブロック更新部１４０は、辞書テーブル１１１やネームテーブル１１４に新規ブロックに対応するレコードを追加しなくてもよい。ここで作成された新規ブロックは、着目ブロックの子ブロックに相当する。
【００９９】
（Ｓ４２）ブロック更新部１４０は、辞書テーブル１１１において、キーの各プレフィックス（接頭部）ｋのハッシュ値ｈａｓｈ（ｋ）と新規ブロックへのポインタとの対応を着目ブロック（新規ブロックの親ブロックに相当）に対して追加する。具体的には、まず、ブロック更新部１４０は、キーの各プレフィックスのハッシュ値を求める。例えば、キーが“ｇｏｂａｃｋ”である場合、当該キーの各プレフィックスは、“ｇｏｂａｃｋ”、“ｇｏｂａｃ”、“ｇｏｂａ”、“ｇｏｂ”、“ｇｏ”、“ｇ”である。このため、ブロック更新部１４０は、ハッシュ値として、ｈａｓｈ（“ｇｏｂａｃｋ”）、ｈａｓｈ（“ｇｏｂａｃ”）、ｈａｓｈ（“ｇｏｂａ”）、ｈａｓｈ（“ｇｏｂ”）、ｈａｓｈ（“ｇｏ”）、ｈａｓｈ（“ｇ”）を求める。そして、ブロック更新部１４０は、着目ブロックのブロックＩＤに対し、求めたハッシュ値それぞれを対応付けたレコードを辞書テーブル１１１に追加する。また、ブロック更新部１４０は、追加した各レコードの次ブロックＩＤの項目に、新規ブロックのブロックＩＤを登録する。
【０１００】
（Ｓ４３）ブロック更新部１４０は、ネームテーブル１１４において、キーの各プレフィックスｋのハッシュ値ｈａｓｈ（ｋ）と各プレフィックス（ｋ）（ｎａｍ値）との対応を着目ブロック（新規ブロックの親ブロックに相当）に対して追加する。具体的には、ブロック更新部１４０は、着目ブロックのブロックＩＤ、ステップＳ４２で求めたハッシュ値、およびハッシュ値の算出に使用したプレフィックス（ｎａｍ値）との対応関係を示すレコードをネームテーブル１１４に追加する。ステップＳ４２で複数のハッシュ値を算出している場合、ネームテーブル１１４には、複数のハッシュ値それぞれに関するレコードが追加される。
【０１０１】
（Ｓ４４）ブロック更新部１４０は、着目ブロックと新規ブロックとにｅｎｔｉｔｙへのポインタを追加する。具体的には、ブロック更新部１４０は、図９のステップＳ１１で受け付けたポインタを、データテーブル１１２に含まれる着目ブロックおよび新規ブロックそれぞれのブロックＩＤに対応するレコードに追加する。ここで、新規ブロックのブロックＩＤに対応するレコードがない場合、ブロック更新部１４０は、データテーブル１１２に、新規ブロックのブロックＩＤに対応するレコードを新たに追加する。
【０１０２】
（Ｓ４５）ブロック更新部１４０は、作成した新規ブロックのブロックＩＤを返り値として呼出し元へ返す。そして、処理を終了する。
図１２は、子ブロック追加の例を示すフローチャートである。以下、図１２に示す処理をステップ番号に沿って説明する。以下に示す処理は、図１０のステップＳ２６におけるブロック更新部１４０の処理に相当する。
【０１０３】
（Ｓ５１）ブロック更新部１４０は、参照先ブロックのｌｇｐが示す文字列をキーの先頭から除去した文字列をｔｒａｉｌｉｎｇＫｅｙとする。この時点における着目ブロックをブロックＸ、参照先ブロックをブロックＹとする。
【０１０４】
（Ｓ５２）ブロック更新部１４０は、格納制御部１３０を呼び出して、参照先ブロックを着目ブロックとしたキー追加処理の実行を、格納制御部１３０に指示する（追加するキーをｔｒａｉｌｉｎｇＫｅｙとする）。すなわち、格納制御部１３０は、着目ブロックをステップＳ５１におけるブロックＸからブロックＹに変更し、追加するキーをｔｒａｉｌｉｎｇＫｅｙで示される文字列として、図１０で説明したキー追加処理を実行する。こうして、格納制御部１３０およびブロック更新部１４０が再帰的に呼び出されて、ブロックＹの配下（ブロックＹの直下またはそれよりも下の階層）にブロックの追加が行われる（呼出しのたびに、各部に相当するプロセスが起動されると考えてよい）。
【０１０５】
（Ｓ５３）ブロック更新部１４０は、元の着目ブロック（ブロックＸ）にｅｎｔｉｔｙへのポインタを追加する。具体的には、ブロック更新部１４０は、図９のステップＳ１１で受け付けたポインタを、データテーブル１１２に含まれるブロックＸのブロックＩＤに対応するレコードに追加する。なお、ブロックＹやブロックＹの配下に新たに追加されたブロックに対しては、兄弟ブロック追加の処理などによるブロック追加処理の中で、同じポインタを追加済である。
【０１０６】
（Ｓ５４）ブロック更新部１４０は、参照先ブロック（ブロックＹ）のブロックＩＤを返り値として呼出し元へ返す。そして、処理を終了する。
図１３は、ブロック分割の例を示すフローチャートである。以下、図１３に示す処理をステップ番号に沿って説明する。以下に示す処理は、図１０のステップＳ３０におけるブロック更新部１４０の処理に相当する。
【０１０７】
（Ｓ６１）ブロック更新部１４０は、新規ブロックを作成し、新規ブロックのｌｇｐにｃｏｍｍｏｎＫｅｙを代入する。具体的には、ブロック更新部１４０は、最長プレフィックステーブル１１３に、新規ブロックのブロックＩＤを格納したレコードを追加する。ブロック更新部１４０は、最長プレフィックステーブル１１３の当該ブロックＩＤのレコードのｌｇｐに、ｃｏｍｍｏｎＫｅｙを登録する。
【０１０８】
（Ｓ６２）ブロック更新部１４０は、インデックス調整部１５０を呼び出して、既存ブロック（参照先ブロック）のインデックス調整を、インデックス調整部１５０に指示する。処理の詳細は後述される。ブロック更新部１４０は、インデックス調整部１５０によるインデックス調整の実行結果（返り値）として、調整対象ブロック（既存ブロック）のｌｇｐ（インデックス調整による変更前のｌｇｐ）を受け付ける。
【０１０９】
（Ｓ６３）ブロック更新部１４０は、ステップＳ６２におけるインデックス調整の実行で受け取った返り値を、ｏｌｄＬｇｐとする。
（Ｓ６４）ブロック更新部１４０は、ｎｅｗＴｒａｉｌｉｎｇＫｅｙが空文字列であるか否かを判定する。ｎｅｗＴｒａｉｌｉｎｇＫｅｙが空文字列である場合、処理をステップＳ６７に進める。ｎｅｗＴｒａｉｌｉｎｇＫｅｙが空文字列でない場合、処理をステップＳ６５に進める。
【０１１０】
（Ｓ６５）ブロック更新部１４０は、ｎｅｗＴｒａｉｌｉｎｇＫｅｙに対応する追加ブロックを作成し、追加ブロックのｌｇｐにｎｅｗＴｒａｉｌｉｎｇＫｅｙを代入する。具体的には、ブロック更新部１４０は、最長プレフィックステーブル１１３において、追加ブロックのブロックＩＤを格納したレコードを追加する。ブロック更新部１４０は、最長プレフィックステーブル１１３の当該ブロックＩＤのレコードのｌｇｐに、ｎｅｗＴｒａｉｌｉｎｇＫｅｙに代入された文字列を登録する。
【０１１１】
（Ｓ６６）ブロック更新部１４０は、追加ブロックに対してｅｎｔｉｔｙへのポインタを追加する。具体的には、ブロック更新部１４０は、追加ブロックのブロックＩＤに対応するレコードを、データテーブル１１２に新たに追加する。ブロック更新部１４０は、追加レコードのデータリストの項目に、図９のステップＳ１１で受け付けたポインタを追加する。そして、処理をステップＳ６７に進める。
【０１１２】
（Ｓ６７）ブロック更新部１４０は、辞書テーブル１１１において、着目ブロックの参照先ブロック（次ブロックＩＤ）を更新する。具体的には、ブロック更新部１４０は、着目ブロックに対し、ｃｏｍｍｏｎＫｅｙの各プレフィックスｋについて、ハッシュ値ｈａｓｈ（ｋ）およびステップＳ６１で作成した新規ブロックのブロックＩＤとの対応関係を辞書テーブル１１１に登録する。このとき、ハッシュ値ｈａｓｈ（ｋ）に対する既存のレコードが辞書テーブル１１１に登録されているので、ブロック更新部１４０は、次ブロックＩＤの項目の設定内容を新規ブロックのブロックＩＤに置き換えればよい。
【０１１３】
（Ｓ６８）ブロック更新部１４０は、ネームテーブル１１４において、着目ブロックに対するｎａｍ値を更新する。具体的には、ブロック更新部１４０は、着目ブロックに対し、ハッシュ値ｈａｓｈ（ｋ）およびｎａｍ値（ｋ）との対応関係をネームテーブル１１４に登録する。このとき、ネームテーブル１１４にはハッシュ値ｈａｓｈ（ｋ）に対する既存のレコードがネームテーブル１１４に登録されているので、ブロック更新部１４０は、既存のレコードを上書きする。
【０１１４】
（Ｓ６９）ブロック更新部１４０は、着目ブロックに関し、ｏｌｄＬｇｐの各プレフィックスのうち、ｃｏｍｍｏｎＫｅｙを真にプレフィックスとして含む文字列に関するレコードを、辞書テーブルおよびネームテーブルから削除する。ここで、「ｏｌｄＬｇｐのプレフィックスが、ｃｏｍｍｏｎＫｅｙを真にプレフィックスとして含む」とは、ｏｌｄＬｇｐのプレフィックスがｃｏｍｍｏｎＫｅｙと同一でなく、かつ、ｏｌｄＬｇｐのプレフィックスにｃｏｍｍｏｎＫｅｙが含まれることを意味する。
【０１１５】
（Ｓ７０）ブロック更新部１４０は、インデックス調整部１５０を呼び出して、ステップＳ６１で作成した新規ブロックのインデックス調整を、インデックス調整部１５０に指示する。
【０１１６】
（Ｓ７１）ブロック更新部１４０は、着目ブロックに対してｅｎｔｉｔｙへのポインタを追加する。具体的には、ブロック更新部１４０は、図９のステップＳ１１で受け付けたポインタを、データテーブル１１２に含まれる着目ブロックのブロックＩＤに対応するレコードに追加する。
【０１１７】
（Ｓ７２）ブロック更新部１４０は、ｎｅｗＴｒａｉｌｉｎｇＫｅｙが空文字列であるか否かを判定する。ｎｅｗＴｒａｉｌｉｎｇＫｅｙが空文字列である場合、処理をステップＳ７３に進める。ｎｅｗＴｒａｉｌｉｎｇＫｅｙが空文字列でない場合、処理をステップＳ７４に進める。
【０１１８】
（Ｓ７３）ブロック更新部１４０は、ステップＳ６１で作成した新規ブロックを示すポインタを、返り値として呼出し元へ返す。そして、処理を終了する。
（Ｓ７４）ブロック更新部１４０は、ステップＳ６５で作成した追加ブロックを示すポインタを、返り値として呼出し元へ返す。そして、処理を終了する。
【０１１９】
図１４は、既存ブロックインデックス調整のフローチャートを示す図である。以下、図１４に示す処理をステップ番号に沿って説明する。以下に示す処理は、図１３のステップＳ６２におけるインデックス調整部１５０の処理に相当する。
【０１２０】
（Ｓ８１）インデックス調整部１５０は、調整対象ブロック（参照先ブロック）のｌｇｐをｏｌｄＬｇｐにコピーする。具体的には、インデックス調整部１５０は、最長プレフィックステーブル１１３を参照して、参照先ブロックのブロックＩＤに対応するｌｇｐを取得し、インデックス調整部１５０が管理するローカル変数ｏｌｄＬｇｐに代入する。
【０１２１】
（Ｓ８２）インデックス調整部１５０は、調整対象ブロックのｌｇｐにｏｌｄＴｒａｉｌｉｎｇＫｅｙを代入する。具体的には、インデックス調整部１５０は、最長プレフィックステーブル１１３において、参照先ブロックのブロックＩＤに対応するｌｇｐを、ｏｌｄＴｒａｉｌｉｎｇＫｅｙに代入された文字列に置き換える。
【０１２２】
（Ｓ８３）インデックス調整部１５０は、ローカル変数ｏｌｄＬｇｐを呼出し元に返す。インデックス調整部１５０の呼出し元は、ブロック更新部１４０である。そして、処理を終了する。
【０１２３】
図１５は、新規ブロックインデックス調整のフローチャートを示す図である。以下、図１５に示す処理をステップ番号に沿って説明する。以下に示す処理は、図１３のステップＳ７０におけるインデックス調整部１５０の処理に相当する。
【０１２４】
（Ｓ９１）インデックス調整部１５０は、ｃｏｍｍｏｎＫｅｙに対応する新規ブロックについて、ｏｌｄＴｒａｉｌｉｎｇＫｅｙの各プレフィックスに対するハッシュ値と既存ブロックへのポインタとの対応を辞書テーブル１１１に追加する。ここで、既存ブロックとは、既存ブロックインデックス調整の処理において、ｏｌｄＴｒａｉｌｉｎｇＫｅｙをｌｇｐとして設定したブロックである。すなわち、インデックス調整部１５０は、新規ブロックのブロックＩＤに対応付けて、ｏｌｄＴｒａｉｌｉｎｇＫｅｙの各プレフィックスｋに対するハッシュ値ｈａｓｈ（ｋ）と既存ブロックへのポインタとを辞書テーブル１１１に追加する。
【０１２５】
（Ｓ９２）インデックス調整部１５０は、ｃｏｍｍｏｎＫｅｙに対応する新規ブロックについて、ｏｌｄＴｒａｉｌｉｎｇＫｅｙの各プレフィックスに対するハッシュ値と各プレフィックス（ｎａｍ値）との対応をネームテーブル１１４に追加する。すなわち、インデックス調整部１５０は、新規ブロックのブロックＩＤに対応付けて、ハッシュ値ｈａｓｈ（ｋ）とｏｌｄＴｒａｉｌｉｎｇＫｅｙのプレフィックスｋ（ｎａｍ値）とをネームテーブル１１４に追加する。
【０１２６】
（Ｓ９３）インデックス調整部１５０は、ｎｅｗＴｒａｉｌｉｎｇＫｅｙが空文字列であるか否かを判定する。ｎｅｗＴｒａｉｌｉｎｇＫｅｙが空文字列である場合、処理をステップＳ９６に進める。ｎｅｗＴｒａｉｌｉｎｇＫｅｙが空文字列でない場合、処理をステップＳ９４に進める。
【０１２７】
（Ｓ９４）インデックス調整部１５０は、ｃｏｍｍｏｎＫｅｙに対応する新規ブロックについて、ｎｅｗＴｒａｉｌｉｎｇＫｅｙの各プレフィックスに対するハッシュ値と追加ブロックへのポインタとの対応を辞書テーブル１１１に追加する。ここで、追加ブロックとは、ブロック分割の処理において、ｎｅｗＴｒａｉｌｉｎｇＫｅｙをｌｇｐとして設定したブロックである。すなわち、インデックス調整部１５０は、新規ブロックのブロックＩＤに対応付けて、ｎｅｗＴｒａｉｌｉｎｇＫｅｙの各プレフィックスｋに対するハッシュ値ｈａｓｈ（ｋ）と追加ブロックへのポインタとを辞書テーブル１１１に追加する。
【０１２８】
（Ｓ９５）インデックス調整部１５０は、ｃｏｍｍｏｎＫｅｙに対応する新規ブロックについて、ｎｅｗＴｒａｉｌｉｎｇＫｅｙの各プレフィックスに対するハッシュ値と各プレフィックス（ｎａｍ値）との対応をネームテーブル１１４に追加する。すなわち、インデックス調整部１５０は、追加ブロックのブロックＩＤに対応付けて、ハッシュ値ｈａｓｈ（ｋ）とｎｅｗＴｒａｉｌｉｎｇＫｅｙの各プレフィックスｋ（ｎａｍ値）とをネームテーブル１１４に追加する。
【０１２９】
（Ｓ９６）インデックス調整部１５０は、データテーブル１１２において、ｃｏｍｍｏｎＫｅｙに対応する新規ブロックのデータリストを、既存ブロックのデータリストをコピーした内容で置換する。
【０１３０】
（Ｓ９７）インデックス調整部１５０は、ｃｏｍｍｏｎＫｅｙに対応する新規ブロックにｅｎｔｉｔｙへのポインタを追加する。具体的には、インデックス調整部１５０は、図９のステップＳ１１で受け付けたポインタを、データテーブル１１２に含まれる新規ブロックのブロックＩＤに対応するレコードに追加する。そして、処理を終了する。
【０１３１】
次に上記のようにして作成される各テーブルを用いた前方一致検索の手順を例示する。
図１６は、検索の例を示すフローチャートである。以下、図１６に示す処理をステップ番号に沿って説明する。
【０１３２】
（Ｓ１０１）検索受付部１６０は、入力キーを受け付ける。以下では、入力キーに相当する文字列を“ｋｅｙ”と表記する。検索受付部１６０は、検索処理部１７０を呼び出して、ｋｅｙを通知し、前方一致検索を開始させる。ここで、ステップＳ１０１における着目ブロックｂをｒｏｏｔであるブロックＮ１（ブロックＩＤ“ｂ１”）とする（着目ブロックｂ＝ｒｏｏｔ）。
【０１３３】
（Ｓ１０２）検索処理部１７０は、ｋｅｙの長さが０よりも大きい（ｋｅｙの長さ＞０）であるか否かを判定する。ｋｅｙの長さが０よりも大きい場合、処理をステップＳ１０３に進める。ｋｅｙの長さが０よりも大きくない（すなわち、ｋｅｙの長さが０である）場合、処理をステップＳ１０９に進める。
【０１３４】
（Ｓ１０３）検索処理部１７０は、検索するプレフィックスｐにｋｅｙに相当する文字列を代入する（ｐ＝ｋｅｙ）。
（Ｓ１０４）検索処理部１７０は、ｐの長さが０よりも大きい（ｐの長さ＞０）であるか否かを判定する。ｐの長さが０よりも大きい場合、処理をステップＳ１０５に進める。ｐの長さが０よりも大きくない（すなわち、ｐの長さが０である）場合、処理をステップＳ１１０に進める。
【０１３５】
（Ｓ１０５）検索処理部１７０は、ハッシュ値ｈａｓｈ（ｐ）がｂ．ｄｉｃにあるか否かを判定する。ハッシュ値ｈａｓｈ（ｐ）がｂ．ｄｉｃにある場合、処理をステップＳ１０７に進める。ハッシュ値ｈａｓｈ（ｐ）がｂ．ｄｉｃにない場合、処理をステップＳ１０６に進める。ここで、ｂ．ｄｉｃは、辞書テーブル１１１のうち、ブロックＩＤの項目が着目ブロックｂのブロックＩＤであるレコードを示す。
【０１３６】
（Ｓ１０６）検索処理部１７０は、ｐから最後の１文字を除去した文字列を新たにｐとする。そして、処理をステップＳ１０４に進める。
（Ｓ１０７）検索処理部１７０は、ｂ．ｄｉｃ中のハッシュ値ｈａｓｈ（ｐ）に対応する次ブロックを新たに着目ブロックｂとする。
【０１３７】
（Ｓ１０８）検索処理部１７０は、ｋｅｙから先頭の文字列ｐを除去した文字列を新たにｋｅｙとする。検索処理部１７０は、ｐに代入された文字列をクリアする。そして、処理をステップＳ１０２に進める。
【０１３８】
（Ｓ１０９）検索処理部１７０は、ｂ．ｄａｔａを出力する。ここで、ｂ．ｄａｔａは、データテーブル１１２のうち、着目ブロックｂのブロックＩＤに対応するレコードのデータリストを示す。検索受付部１６０は、ｂ．ｄａｔａを取得し、当該データリストに含まれるポインタで示される文字列（メソッド名）を前方一致検索の結果としてディスプレイ１１に表示させる。そして、処理を終了する。
【０１３９】
（Ｓ１１０）検索処理部１７０は、何れの文字列ともマッチしなかった（入力キーに前方一致するメソッド名がなかった）旨を出力する。検索受付部１６０は、当該出力を取得し、入力キーに前方一致するメソッド名がない旨を、前方一致検索の結果としてディスプレイ１１に表示させる。そして、処理を終了する。
【０１４０】
次に、上記格納および検索の具体例を説明する。
図１７は、格納例（その１）を示す図である。図１７では、新規キー“ｇｏｂａｃｋ”を追加する例を示している。新規キー“ｇｏｂａｃｋ”に対応するｅｎｔｉｔｙを示すポインタは“Ｍ１”である。検索装置１００は、“ｇｏｂａｃｋ”および“Ｍ１”の入力を受け付ける（ステップＳ１１）。ここで、新規キー“ｇｏｂａｃｋ”を追加する前には、何の文字列も登録されていない。何の文字列も登録されていない場合、辞書テーブル１１１にブロックＮ１のレコード（ブロックＩＤ以外は設定なし）のみが存在する（他のテーブルのレコードはなし）。この状態では、ブロックＮ１のｎａｍ値は空文字列として扱われる。また、図１７では、この状態を、木構造データ５１（ｒｏｏｔであるブロックＮ１のみが存在する）として表している。なお、図１７以降の具体例の説明では、辞書テーブル１１１（ｄｉｃ）、データテーブル１１２（ｄａｔａ）および最長プレフィックステーブル１１３（ｌｇｐ）に相当する情報を図示するが、ネームテーブル１１４に相当する情報の図示を省略する。検索装置１００は、新規キー“ｇｏｂａｃｋ”について下記のようにキー追加処理を実行する（ステップＳ１２）。
【０１４１】
この時点で、ブロックＮ１について、新規キー“ｇｏｂａｃｋ”の各プレフィックスと一致するｎａｍ値は存在しない（ステップＳ２１，Ｓ２２）。したがって、キー追加処理におけるステップＳ２２の判定はＮｏとなり、検索装置１００は、ブロックＮ１（着目ブロック）に対する兄弟ブロックの追加を行う（ステップＳ２３）。
【０１４２】
木構造データ５２は、キー“ｇｏｂａｃｋ”を格納した後の状態を示す。検索装置１００は、ブロックＮ２（新規ブロック）を作成し、ブロックＮ２のｌｇｐにキー“ｇｏｂａｃｋ”を追加する（ステップＳ４１）。
【０１４３】
ここで、キー“ｇｏｂａｃｋ”のプレフィックスは、“ｇ”、“ｇｏ”、“ｇｏｂ”、“ｇｏｂａ”、“ｇｏｂａｃ”、“ｇｏｂａｃｋ”である。このため、検索装置１００は、ブロックＮ１（着目ブロック）について、ハッシュ値ｈａｓｈ（“ｇ”）、ｈａｓｈ（“ｇｏ”）、ｈａｓｈ（“ｇｏｂ”）、ｈａｓｈ（“ｇｏｂａ”）、ｈａｓｈ（“ｇｏｂａｃ”）、ｈａｓｈ（“ｇｏｂａｃｋ”）それぞれとブロックＮ２へのポインタ（ブロックＩＤ“ｂ２”）との対応関係を辞書テーブル１１１に登録する（ステップＳ４２）。
【０１４４】
また、検索装置１００は、ブロックＮ１について、ハッシュ値ｈａｓｈ（“ｇ”）、ｈａｓｈ（“ｇｏ”）、ｈａｓｈ（“ｇｏｂ”）、ｈａｓｈ（“ｇｏｂａ”）、ｈａｓｈ（“ｇｏｂａｃ”）、ｈａｓｈ（“ｇｏｂａｃｋ”）それぞれと、各プレフィックスとの対応関係をネームテーブル１１４に登録する（ステップＳ４３）。
【０１４５】
更に、検索装置１００は、データテーブル１１２において、ブロックＮ１（着目ブロック）およびブロックＮ２（新規ブロック）に対し、ｅｎｔｉｔｙへのポインタ“Ｍ１”を追加する（ステップＳ４４）。
【０１４６】
すなわち、文字列“ｇｏｂａｃｋ”の追加により、ノードＮ１の子ノードであるノードＮ２が木構造データ５１に追加されると、検索装置１００は、ノードＮ２に対応する文字列部分の接頭部とノードＮ２との対応情報をノードＮ１に対して追加する。また、検索装置１００は、ノードＮ１を含むノードＮ２の上位ノード（ここではノードＮ１）およびノードＮ２に対して文字列“ｇｏｂａｃｋ”を示す識別情報“Ｍ１”を追加する。こうして、木構造データ５２に相当するデータが作成される。
【０１４７】
図１８は、格納例（その２）を示す図である。図１８では、木構造データ５２に対して、更に、新規キー“ｇｏｂａｃｋｏｒｆ”を追加する例を示している。新規キー“ｇｏｂａｃｋｏｒｆ”に対応するｅｎｔｉｔｙを示すポインタは“Ｍ２”である。検索装置１００は、“ｇｏｂａｃｋｏｒｆ”および“Ｍ２”の入力を受け付ける（ステップＳ１１）。この場合、新規キー“ｇｏｂａｃｋｏｒｆ”のプレフィックス“ｇ”、“ｇｏ”、“ｇｏｂ”、“ｇｏｂａ”、“ｇｏｂａｃ”、“ｇｏｂａｃｋ”、“ｇｏｂａｃｋｏ”、“ｇｏｂａｃｋｏｒ”、“ｇｏｂａｃｋｏｒｆ”のうち、ブロックＮ１のｎａｍ値と一致する最長の文字列は“ｇｏｂａｃｋ”である。このため、検索装置１００は、“ｇｏｂａｃｋ”をｃｏｍｍｏｎＫｅｙとする（ステップＳ２１，Ｓ２２  Ｙｅｓ）。
【０１４８】
すると、検索装置１００は、ブロックＮ１（着目ブロック）のｈａｓｈ（“ｇｏｂａｃｋ”）に対応するブロックＮ２（参照先ブロック）を特定する（ステップＳ２４）。
ブロックＮ２のｌｇｐは、“ｇｏｂａｃｋ”である。文字列“ｇｏｂａｃｋ”は、キー“ｇｏｂａｃｋｏｒｆ”の真の部分文字列である（ステップＳ２５  Ｙｅｓ）。したがって、検索装置１００は、ブロックＮ２（参照先ブロック）に対する子ブロックの追加を行う（ステップＳ２６）。
【０１４９】
検索装置１００は、ブロックＮ２（参照先ブロック）のｌｇｐが示す文字列“ｇｏｂａｃｋ”を、キー“ｇｏｂａｃｋｏｒｆ”の先頭から除去した文字列“ｏｒｆ”をｔｒａｉｌｉｎｇＫｅｙとする（ステップＳ５１）。
【０１５０】
検索装置１００は、ブロックＮ２（参照先ブロック）を着目ブロックとして、キー“ｏｒｆ”の追加処理を行う（ステップＳ５２）。この場合、着目ブロックをブロックＮ２、キーを“ｏｒｆ”として、格納制御部１３０が呼び出され、キー追加処理が再帰的に実行される。ここでは、キー“ｏｒｆ”の各プレフィックス“ｏ”、“ｏｒ”、“ｏｒｆ”のうち、ブロックＮ２（着目ブロック）に対応するｎａｍ値は存在しない（ステップＳ２１，Ｓ２２）。したがって、ｃｏｍｍｏｎＫｅｙは存在しないことになり、検索装置１００は、ブロックＮ２（着目ブロック）に対する兄弟ブロックの追加を行う（ステップＳ２３）。
【０１５１】
木構造データ５３は、キー“ｇｏｂａｃｋｏｒｆ”を格納した後の状態を示す。兄弟ブロックの追加では、検索装置１００は、ブロックＮ３を作成し、ブロックＮ３のｌｇｐにキー“ｏｒｆ”を追加する（ステップＳ４１）。
【０１５２】
検索装置１００は、ブロックＮ２について、ハッシュ値ｈａｓｈ（“ｏ”）、ｈａｓｈ（“ｏｒ”）、ｈａｓｈ（“ｏｒｆ”）それぞれとブロックＮ３へのポインタ（ブロックＩＤ“ｂ３”）との対応関係を辞書テーブル１１１に登録する（ステップＳ４２）。
【０１５３】
また、検索装置１００は、ブロックＮ２について、ハッシュ値ｈａｓｈ（“ｏ”）、ｈａｓｈ（“ｏｒ”）、ｈａｓｈ（“ｏｒｆ”）それぞれと、各プレフィックスとの対応関係をネームテーブル１１４に登録する（ステップＳ４３）。
【０１５４】
更に、検索装置１００は、ブロックＮ２（着目ブロック）とブロックＮ３（新規ブロック）とについて、ｅｎｔｉｔｙへのポインタ“Ｍ２”を、データテーブル１１２に追加する（ステップＳ４４）。
【０１５５】
そして、検索装置１００は、ステップＳ４５，Ｓ３２を経て、ステップＳ５３を実行する。ステップＳ５３の実行により、検索装置１００は、ブロックＮ１（元の着目ブロック）について、ｅｎｔｉｔｙへのポインタ“Ｍ２”を、データテーブル１１２に追加する。
【０１５６】
すなわち、文字列“ｇｏｂａｃｋｏｒｆ”の追加により、ノードＮ２の子ノードであるノードＮ３が木構造データ５２に追加されると、検索装置１００は、ノードＮ３に対応する文字列部分の接頭部とノードＮ３との対応情報をノードＮ２に対して追加する。また、検索装置１００は、ノードＮ２を含むノードＮ３の上位ノード（ノードＮ１，Ｎ２）およびノードＮ３に対して文字列“ｇｏｂａｃｋｏｒｆ”を示す識別情報“Ｍ２”を追加する。こうして、木構造データ５３に相当するデータが作成される。
【０１５７】
図１９は、格納例（その３）を示す図である。図１９では、木構造データ５３に対して、更に、新規キー“ｇｏｆｏｒｗ”を追加する例を示している。新規キー“ｇｏｆｏｒｗ”に対応するｅｎｔｉｔｙを示すポインタは“Ｍ３”である。検索装置１００は、“ｇｏｆｏｒｗ”および“Ｍ３”の入力を受け付ける（ステップＳ１１）。この場合、新規キー“ｇｏｆｏｒｗ”の各プレフィックス“ｇ”、“ｇｏ”、“ｇｏｆ”、“ｇｏｆｏ”、“ｇｏｆｏｒ”、“ｇｏｆｏｒｗ”のうち、ブロックＮ１のｎａｍ値と一致する最長の文字列は“ｇｏ”である。このため、検索装置１００は、“ｇｏ”をｃｏｍｍｏｎＫｅｙとする（ステップＳ２１，Ｓ２２  Ｙｅｓ）。
【０１５８】
すると、検索装置１００は、ブロックＮ１（着目ブロック）のｈａｓｈ（“ｇｏ”）に対応するブロックＮ２（参照先ブロック）を特定する（ステップＳ２４）。
ブロックＮ２のｌｇｐは、“ｇｏｂａｃｋ”である。文字列“ｇｏｂａｃｋ”は、キー“ｇｏｆｏｒｗ”の真の部分文字列ではない（ステップＳ２５  Ｎｏ）。したがって、検索装置１００は、ブロックＮ２（参照先ブロック）のｌｇｐ“ｇｏｂａｃｋ”の先頭からｃｏｍｍｏｎＫｅｙ“ｇｏ”を除去した文字列“ｂａｃｋ”をｏｌｄＴｒａｉｌｉｎｇＫｅｙとする（ステップＳ２７）。また、検索装置１００は、キー“ｇｏｆｏｒｗ”の先頭からｃｏｍｍｏｎＫｅｙ“ｇｏ”を除去した文字列“ｆｏｒｗ”をｎｅｗＴｒａｉｌｉｎｇＫｅｙとする（ステップＳ２８）。
【０１５９】
この場合、ｏｌｄＴｒａｉｌｉｎｇＫｅｙおよびｎｅｗＴｒａｉｌｉｎｇＫｅｙの何れも空文字列ではないので（ステップＳ２９  Ｎｏ）、検索装置１００は、ブロックＮ２（参照先ブロック）の分割を行う（ステップＳ３０）。
【０１６０】
木構造データ５０は、キー“ｇｏｆｏｒｗ”を格納した後の状態を示す。ブロックＮ２の分割では、検索装置１００は、ブロックＮ４（新規ブロック）を作成し、ブロックＮ４のｌｇｐにｃｏｍｍｏｎＫｅｙ“ｇｏ”を設定する（ステップＳ６１）。
【０１６１】
検索装置１００は、ブロックＮ２（既存ブロック）のインデックス調整を行う（ステップＳ６２）。具体的には、検索装置１００は、ブロックＮ２のｌｇｐ“ｇｏｂａｃｋ”をｏｌｄＬｇｐにコピーすることで退避し、ブロックＮ２のｌｇｐにｏｌｄＴｒａｉｌｉｎｇＫｅｙ“ｂａｃｋ”を設定する（ステップＳ８１，Ｓ８２）。
【０１６２】
その後、ｎｅｗＴｒａｉｌｉｎｇＫｅｙは空文字列ではないので（ステップＳ６４  Ｎｏ）、検索装置１００は、ｎｅｗＴｒａｉｌｉｎｇＫｅｙに対応するブロックＮ５（追加ブロック）を作成する。そして、検索装置１００は、ブロックＮ５のｌｇｐに、ｎｅｗＴｒａｉｌｉｎｇＫｅｙ“ｆｏｒｗ”を設定する（ステップＳ６５）。また、検索装置１００は、ブロックＮ５に対して、ｅｎｔｉｔｙへのポインタ“Ｍ３”を追加する（ステップＳ６６）。
【０１６３】
検索装置１００は、ブロックＮ１（着目ブロック）に対応付けられた次ブロックを、新規に作成したブロックＮ４に変更する（ステップＳ６７）。ここで、ブロックＮ１に関し、ｏｌｄＬｇｐ“ｇｏｂａｃｋ”のプレフィックスは“ｇ”、“ｇｏ”、“ｇｏｂ”、“ｇｏｂａ”、“ｇｏｂａｃ”、“ｇｏｂａｃｋ”である。このうち、ｃｏｍｍｏｎＫｅｙ“ｇｏ”を真にプレフィックスとして含む文字列は、“ｇｏｂ”、“ｇｏｂａ”、“ｇｏｂａｃ”、“ｇｏｂａｃｋ”である。したがって、検索装置１００は、ブロックＮ１に関し、“ｇｏｂ”、“ｇｏｂａ”、“ｇｏｂａｃ”、“ｇｏｂａｃｋ”に対応するレコードを、辞書テーブル１１１およびネームテーブル１１４から削除する（ステップＳ６９）。なお、辞書テーブル１１１の削除対象レコードは、ネームテーブル１１４におけるｎａｍ値に対応するハッシュ値によって特定される。すると、辞書テーブル１１１およびネームテーブル１１４には、ブロックＮ１に対して、ハッシュ値ｈａｓｈ（“ｇ”）、ｈａｓｈ（“ｇｏ”）のレコードのみが残る。
【０１６４】
次に、検索装置１００は、ブロックＮ４（新規ブロック）のインデックス調整を行う（ステップＳ７０）。
具体的には、検索装置１００は、ｏｌｄＴｒａｉｌｉｎｇＫｅｙ“ｂａｃｋ”の各プレフィックス“ｂ”、“ｂａ”、“ｂａｃ”、“ｂａｃｋ”を得る。そして、検索装置１００は、ｃｏｍｍｏｎＫｅｙ“ｇｏ”に対応するブロックＮ４（新規ブロック）について、ハッシュ値ｈａｓｈ（“ｂ”）、ｈａｓｈ（“ｂａ”）、ｈａｓｈ（“ｂａｃ”）、ｈａｓｈ（“ｂａｃｋ”）とブロックＮ２（既存ブロック）へのポインタとの対応を辞書テーブル１１１に追加する（ステップＳ９１）。
【０１６５】
また、検索装置１００は、ブロックＮ４について、ハッシュ値ｈａｓｈ（“ｂ”）、ｈａｓｈ（“ｂａ”）、ｈａｓｈ（“ｂａｃ”）、ｈａｓｈ（“ｂａｃｋ”）と各プレフィックス“ｂ”、“ｂａ”、“ｂａｃ”、“ｂａｃｋ”（ｎａｍ値）との対応をネームテーブル１１４に追加する（ステップＳ９２）。
【０１６６】
更に、ｎｅｗＴｒａｉｌｉｎｇＫｅｙは空文字列ではないので（ステップＳ９３  Ｎｏ）、検索装置１００は、ブロックＮ４について、ｎｅｗＴｒａｉｌｉｎｇＫｅｙ“ｆｏｒｗ”に対応するブロックＮ５へのポインタも追加する。具体的には、検索装置１００は、ｎｅｗＴｒａｉｌｉｎｇＫｅｙ“ｆｏｒｗ”の各プレフィックス“ｆ”、“ｆｏ”、“ｆｏｒ”、“ｆｏｒｗ”を得る。そして、検索装置１００は、ブロックＮ４について、ハッシュ値ｈａｓｈ（“ｆ”）、ｈａｓｈ（“ｆｏ”）、ｈａｓｈ（“ｆｏｒ”）、ｈａｓｈ（“ｆｏｒｗ”）とブロックＮ５（追加ブロック）へのポインタとの対応を辞書テーブル１１１に追加する（ステップＳ９４）。
【０１６７】
また、検索装置１００は、ブロックＮ４について、ハッシュ値ｈａｓｈ（“ｆ”）、ｈａｓｈ（“ｆｏ”）、ｈａｓｈ（“ｆｏｒ”）、ｈａｓｈ（“ｆｏｒｗ”）と各プレフィックス“ｆ”、“ｆｏ”、“ｆｏｒ”、“ｆｏｒｗ”との対応をネームテーブル１１４に追加する（ステップＳ９５）。
【０１６８】
検索装置１００は、データテーブル１１２において、ブロックＮ４（新規ブロック）のデータリストを、ブロックＮ２（既存ブロック）のデータリスト“Ｍ１，Ｍ２”をコピーした内容で置換する（ステップＳ９６）。更に、検索装置１００は、ブロックＮ４（新規ブロック）に対し、ｅｎｔｉｔｙへのポインタ“Ｍ３”をデータテーブル１１２に追加する（ステップＳ９７）。こうして、ブロックＮ４（新規ブロック）に対するインデックス調整が完了する。その後、検索装置１００は、ブロックＮ１（着目ブロック）に対して、ｅｎｔｉｔｙへのポインタ“Ｍ３”をデータテーブル１１２に追加する（ステップＳ７１）。後は、ステップＳ７２，Ｓ７４，Ｓ３２を経て、キー“ｇｏｆｏｒｗ”を格納する処理が完了する。
【０１６９】
すなわち、文字列“ｇｏｆｏｒｗ”を追加することで、ノードＮ１の子ノードであるノードＮ４に対応付けられる文字列部分が変更されると（この場合、“ｇｏ”に変更されると）、検索装置１００は、ノードＮ１の対応情報のうちのノードＮ４に関する情報の一部（具体的には、ハッシュ値ｈａｓｈ（“ｇｏｂ”）、ｈａｓｈ（“ｇｏｂａ”）、ｈａｓｈ（“ｇｏｂａｃ”）、ｈａｓｈ（“ｇｏｂａｃｋ”）のレコード）を当該変更に応じて削除する。そして、検索装置１００は、ノードＮ１を含むノードＮ４の上位ノード（この場合、ノードＮ１）およびノードＮ４に対して文字列“ｇｏｆｏｒｗ”を示す識別情報“Ｍ３”を追加する。また、図１９の例では、検索装置１００は、ノードＮ４からノードＮ２へのエッジおよびノードＮ４からＮ５へのエッジも設定し、追加されたノードＮ５に対して文字列“ｇｏｆｏｒｗ”を示す識別情報“Ｍ３”の設定も行う。こうして、木構造データ５０に相当するデータが作成される。
【０１７０】
次に、このようにして作成された辞書テーブル１１１およびデータテーブル１１２を用いた検索装置１００による検索の具体例を説明する。
図２０は、検索例（その１）を示す図である。図２０では、入力キー“ｇｏｆ”を前方一致検索する場合の例を示している。図２０では、図面の上側から下側へ時系列に、図１６の各ステップが実行される様子を、変数ｂ，ｋｅｙ，ｐおよび出力値により示している。なお、値が存在していない箇所はハイフン“−”とし、各ステップで値が存在していない変数などについては言及しないこととする（以下、同様）。
【０１７１】
まず、検索装置１００が最初にステップＳ１０２を実行するとき、着目ブロックは、ブロックＮ１（ブロックＩＤ“ｂ１”）である（ｂ＝ｂ１）。この時点で、ｋｅｙ＝“ｇｏｆ”である。
【０１７２】
ｋｅｙ＝“ｇｏｆ”の長さ＞０で（ステップＳ１０２  Ｙｅｓ）、ｐ＝“ｇｏｆ”である（ステップＳ１０３）。したがって、検索装置１００が次にステップＳ１０４を実行するとき、ｂ＝ｂ１、ｋｅｙ＝“ｇｏｆ”、ｐ＝“ｇｏｆ”である。このとき、ｐ＝“ｇｏｆ”の長さ＞０である（ステップＳ１０４  Ｙｅｓ）。
【０１７３】
辞書テーブル１１１には、ブロックＮ１に対してハッシュ値ｈａｓｈ（ｐ）＝ｈａｓｈ（“ｇｏｆ”）は存在しない（ステップＳ１０５  Ｎｏ）。このため、検索装置１００は、ｐ＝“ｇｏｆ”から最後の１文字“ｆ”を除去した文字列“ｇｏ”を新たにｐに代入する（ステップＳ１０６）。したがって、検索装置１００が、次にステップＳ１０４を実行するとき、ｂ＝ｂ１、ｋｅｙ＝“ｇｏｆ”、ｐ＝“ｇｏ”である。このとき、ｐ＝“ｇｏ”の長さ＞０である（ステップＳ１０４  Ｙｅｓ）。
【０１７４】
辞書テーブル１１１には、ブロックＮ１に対してハッシュ値ｈａｓｈ（ｐ）＝ｈａｓｈ（“ｇｏ”）が存在する（ステップＳ１０５  Ｙｅｓ）。このため、検索装置１００は、辞書テーブル１１１に基づいて、ブロックＮ１のハッシュ値ｈａｓｈ（“ｇｏ”）に対する次ブロックであるブロックＮ４のブロックＩＤ“ｂ４”を新たにｂに代入する（ステップＳ１０７）。また、検索装置１００は、ｋｅｙ＝“ｇｏｆ”から、先頭の文字列ｐ＝“ｇｏ”を除去した文字列“ｆ”を新たにｋｅｙに代入する。また、検索装置１００は、ｐをクリアする。したがって、検索装置１００が、次にステップＳ１０２を実行するとき、ｂ＝ｂ４、ｋｅｙ＝“ｆ”である。
【０１７５】
ｋｅｙ＝“ｆ”の長さ＞０で（ステップＳ１０２  Ｙｅｓ）、ｐ＝“ｆ”である（ステップＳ１０３）。したがって、検索装置１００が次にステップＳ１０４を実行するとき、ｂ＝ｂ２、ｋｅｙ＝“ｆ”、ｐ＝“ｆ”である。このとき、ｐ＝“ｆ”の長さ＞０である（ステップＳ１０４  Ｙｅｓ）。
【０１７６】
辞書テーブル１１１には、ブロックＮ４に対してハッシュ値ｈａｓｈ（ｐ）＝ｈａｓｈ（“ｆ”）が存在する（ステップＳ１０５  Ｙｅｓ）。このため、検索装置１００は、辞書テーブル１１１に基づいて、ブロックＮ４のハッシュ値ｈａｓｈ（“ｆ”）に対する次ブロックであるブロックＮ５のブロックＩＤ“ｂ５”を新たにｂに代入する（ステップＳ１０７）。また、検索装置１００は、ｋｅｙ＝“ｆ”から、先頭の文字列ｐ＝“ｆ”を除去した文字列“”（空文字列である）を新たにｋｅｙに代入する。また、検索装置１００は、ｐをクリアする。したがって、検索装置１００が、次にステップＳ１０２を実行するとき、ｂ＝ｂ５、ｋｅｙ＝“”（空文字列）である。
【０１７７】
ｋｅｙの長さ＝０となったので（ステップＳ１０２  Ｎｏ）、検索装置１００は、ブロックＩＤ“ｂ５”に対応するポインタ“Ｍ３”をデータテーブル１１２から取得し、ポインタ“Ｍ３”で示される文字列“ｇｏｆｏｒｗ”を出力する（ステップＳ１０９）。例えば、検索装置１００は、入力キー“ｇｏｆ”に前方一致するメソッド名を表す文字列として“ｇｏｆｏｒｗ”を、ディスプレイ１１により表示する。
【０１７８】
図２１は、検索例（その２）を示す図である。図２１では、入力キー“ｄｏ”を前方一致検索する場合の例を示している。図２１でも、図面の上側から下側へ時系列に、図１６の各ステップが実行される様子を、変数ｂ，ｋｅｙ，ｐおよび出力値により示している。
【０１７９】
まず、検索装置１００が最初にステップＳ１０２を実行するとき、着目ブロックは、ブロックＮ１（ブロックＩＤ“ｂ１”）である（ｂ＝ｂ１）。この時点で、ｋｅｙ＝“ｄｏ”である。
【０１８０】
ｋｅｙ＝“ｄｏ”の長さ＞０で（ステップＳ１０２  Ｙｅｓ）、ｐ＝“ｄｏ”である（ステップＳ１０３）。したがって、検索装置１００が次にステップＳ１０４を実行するとき、ｂ＝ｂ１、ｋｅｙ＝“ｄｏ”、ｐ＝“ｄｏ”である。このとき、ｐ＝“ｄｏ”の長さ＞０である（ステップＳ１０４  Ｙｅｓ）。
【０１８１】
辞書テーブル１１１には、ブロックＮ１に対してハッシュ値ｈａｓｈ（ｐ）＝ｈａｓｈ（“ｄｏ”）は存在しない（ステップＳ１０５  Ｎｏ）。このため、検索装置１００は、ｐ＝“ｄｏ”から最後の１文字“ｏ”を除去した文字列“ｄ”を新たにｐに代入する（ステップＳ１０６）。したがって、検索装置１００が、次にステップＳ１０４を実行するとき、ｂ＝ｂ１、ｋｅｙ＝“ｄｏ”、ｐ＝“ｄ”である。このとき、ｐ＝“ｄ”の長さ＞０である（ステップＳ１０４  Ｙｅｓ）。
【０１８２】
辞書テーブル１１１には、ブロックＮ１に対してハッシュ値ｈａｓｈ（ｐ）＝ｈａｓｈ（“ｄ”）は存在しない（ステップＳ１０５  Ｎｏ）。このため、検索装置１００は、ｐ＝“ｄ”から最後の１文字“ｄ”を除去した文字列“”（空文字列）を新たにｐに代入する（ステップＳ１０６）。したがって、検索装置１００が、次にステップＳ１０４を実行するとき、ｂ＝ｂ１、ｋｅｙ＝“ｄｏ”、ｐ＝“”（空文字列）である。
【０１８３】
すると、ｐの長さ＝０となったので（ステップＳ１０４  Ｎｏ）、検索装置１００は、入力キー“ｄｏ”に前方一致する文字列がない旨を出力する（ステップＳ１１０）。例えば、検索装置１００は、入力キー“ｄｏ”に前方一致するメソッド名が存在しない旨を、ディスプレイ１１により表示する。
【０１８４】
次に、第２の実施の形態の方法と、他の手法との比較例を説明する。
図２２は、トライ木の例を示す図である。図２２は、メソッド名を示す文字列“ｇｏｂａｃｋ”、“ｇｏｂａｃｋｏｒｆ”、“ｇｏｆｏｒｗ”をトライ木により管理する例を示している。トライ木では、各文字列に含まれる１文字がエッジに対応付けられる。そして、エッジを辿って到達したノードに、当該ノードまでに辿った各文字を繋げたメソッド名のみを示すポインタが対応付けられる。例えば、“ｇｏｂａｃｋ”という文字列を検索する場合、“ｇ”、“ｏ”、“ｂ”、“ａ”、“ｃ”、“ｋ”と順番にエッジを辿る。そして、最後の“ｋ”で到達したノードに対応するポインタ“Ｍ１”が検出されれば、文字列“ｇｏｂａｃｋ”に一致するメソッド名が存在することになる。
【０１８５】
図２３は、パトリシア木の例を示す図である。図２３は、メソッド名を示す文字列“ｇｏｂａｃｋ”、“ｇｏｂａｃｋｏｒｆ”、“ｇｏｆｏｒｗ”をパトリシア木により管理する例を示している。パトリシア木は、トライ木において子ノードが１つのみであるノードを、当該子ノードと併合したものである。すなわち、図２２のトライ木の例でいえば、“ｇ”、“ｏ”が併合され、“ｇｏ”で１つのノードに対応付けられる。“ｂ”、“ａ”、“ｃ”、“ｋ”が併合され、“ｂａｃｋ”で１つのノードに対応付けられる。“ｏ”、“ｒ”、“ｆ”が併合され、“ｏｒｆ”で１つのノードに対応付けられる。“ｆ”、“ｏ”、“ｒ”、“ｗ”が併合され、“ｆｏｒｗ”で１つのノードに対応付けられる。
【０１８６】
パトリシア木でも、トライ木と同様に、エッジを辿って到達したノードに、当該ノードまでに辿った各文字を繋げたメソッド名のみを示すポインタが対応付けられる。例えば、“ｇｏｂａｃｋ”という文字列を検索する場合、“ｇｏ”、“ｂａｃｋ”と順番にエッジを辿る。そして、最後の“ｂａｃｋ”で到達したノードに対応するポインタ“Ｍ１”が検出されれば、文字列“ｇｏｂａｃｋ”に一致するメソッド名が存在することになる。
【０１８７】
ここで、トライ木（double arrayと呼ばれるデータ構造により実装される）やパトリシア木に検索対象文字列を格納して前方一致検索を行うことが考えられる。前方一致検索のためには、プレフィックス文字列を全て検索対象文字列として格納する必要がある。
【０１８８】
トライ木では、検索対象文字列の数が増えるとdouble array上の位置を指定するアドレスの長さが増大し、１ステップで処理対象となるデータ量が増えるため、検索の１ステップの所要時間が増大し得る。
【０１８９】
更に、同じプレフィックスをもつ多くの類似文字列を検索対象とする場合、トライ木のデータ構造の中間ノード（ｒｏｏｔおよび葉以外のノード）が冗長になり、検索のステップ数が最適値から乖離する。パトリシア木では中間ノードでの分岐が多くなり、辿るべき枝の選択が非効率となる。
【０１９０】
一方、検索装置１００は、あるブロックから子ブロックへのポインタを、子ブロックに対応する文字列部分の各接頭部（プレフィックス）に対応付けて保持する。また、検索装置１００は、ブロックを辿る際、次のブロックを特定するための情報として、メソッド名に含まれる文字列部分の各プレフィックスそのものに代えて、各プレフィックスのハッシュ値を用いる。これにより、入力キーに対してブロックを辿る時間を、トライ木やパトリシア木によりノードを辿る場合よりも短縮できる。具体的には次の通りである。
【０１９１】
トライ木において、格納済の全ての検索対象文字列の平均長をｆとする。トライ木構造の辺（エッジ）の数をＬとする。格納済の全ての検索対象文字列に関し、同一プレフィックス文字列をもつ後続文字列の平均個数をｄとする。また、トライ木構造の中で分岐なし部分の平均個数（double arrayを用いてトライ構造を格納したとき、終端文字のみで枝分かれするトライ部分構造を１個と数える場合の個数）をｐとする。ｐは、トライ木をパトリシア木で表したときに、各メソッド名を部分文字列に分割した分割数の平均であるということもできる。例えば、“ｇｏｂａｃｋｏｒｆ”は図２３のパトリシア木において“ｇｏ”、“ｂａｃｋ”、“ｏｒｆ”の３つに分割されており、各メソッド名のこのような分割数の平均がｐである。
【０１９２】
すると、トライ木において、入力キーに対応するノードを辿るために要する時間ｒｔ０は、式（１）で表される。
【０１９３】
【数１】
2017134554.tif 000003
【０１９４】
式（１）において、２ｌｏｇ2Ｌは、あるノードから次のノードの選択（辿るエッジの選択１回当たり）に要する時間である。あるノードの次のノードの選択に要する時間は、double arrayにおけるｉｎｄｅｘ計算およびｃｈｅｃｋ値計算の所要時間の和である。ｉｎｄｅｘ計算の所要時間は、ｌｏｇ2Ｌ（トライ構造の辺の数に相当する個数のＩＤを扱うだけのｉｎｄｅｘ長が必要なため）程度である。また、ｃｈｅｃｋ値計算の所要時間もｌｏｇ2Ｌ程度である。よって、これらの和がエッジ選択１回当たりの所要時間（ｌｏｇ2Ｌ＋ｌｏｇ2Ｌ）＝２ｌｏｇ2Ｌである。ｆは、辿るエッジ数である。
【０１９５】
また、パトリシア木において、入力キーに対応するノードを辿るために要する時間ｒｔ１は、式（２）で表される。
【０１９６】
【数２】
2017134554.tif 000004
【０１９７】
式（２）において、あるノードの次のノードの選択に要する時間が、ｄ（チェックする文字列数）×（ｆ／ｐ）（チェックする文字列長の平均）程度である。また、ｐは、辿るエッジ数である。
【０１９８】
一方、第２の実施の形態の検索方法では、入力キーに対応するノードを辿るために要する時間ｒｔ２は、式（３）で表される。ここで、ハッシュ値として、一般的な１６バイトハッシュ値を用いることを想定している。
【０１９９】
【数３】
2017134554.tif 000005
【０２００】
式（３）において、エッジ（次の１ブロック）の選択に要する時間がｌｏｇ2（１６×８）である。ｐは、辿るエッジ数である。
したがって、ｒｔ２のｒｔ０（既存のトライ木を用いる場合）に対する比は、式（４）で表される。
【０２０１】
【数４】
2017134554.tif 000006
【０２０２】
また、ｒｔ２のｒｔ１（既存のパトリシア木を用いる場合）に対する比は、式（５）で表される。
【０２０３】
【数５】
2017134554.tif 000007
【０２０４】
式（４）において、検索対象文字列の数が増えるとＬが大きくなる。また、式（４）、式（５）において、検索対象文字列のうち互いに類似する文字列が増える（共通のプレフィックスをもつ文字列が増える）とｐが小さくなる。また、検索対象文字列の数が増え、そのうち互いに類似する文字列が増えるとｄが大きくなるとも考えられる。したがって、このような傾向が見られる対象を検索する場合（例えば、あるＯＳのソースコードの解析結果など）、第２の実施の形態の検索方法の方が、既存のトライ木やパトリシア木を用いるよりも短時間で検索を行える。なぜなら、第２の実施の形態の検索方法では、ブロックを辿る際に用いるキーを固定長のハッシュ値とすることで、次ブロックの選択に要する時間を当該ハッシュ値の長さによって決まる所要時間よりも大きくならないように制限できる（次ブロックの選択に要する時間を頭打ちにできる）からである。
【０２０５】
例えば、あるＯＳのソースコードにおけるメソッド名の解析結果では、ｆ〜３０、Ｌ〜１０6、ｄ〜５、ｐ〜８程度となると見込まれる。その場合、ｒｔ０〜１１００、ｒｔ１〜１５０、ｒｔ２〜６０程度となり、第２の実施の形態の検索方法は、入力キーに対するブロックの探索において、既存の方法よりも２倍から１５倍程度高速化できる。なお、第２の実施の形態の例では、新規キーの格納時においてもハッシュ値によりブロックの探索を行うことで、格納時における処理の高速化も図れる。
【０２０６】
また、トライ木およびパトリシア木の何れも、入力キーに完全一致する文字列の検索を対象としており、木構造の葉（末端）ノードにのみ対応付けられたデータも存在する。そのため、前方一致した文字列に対応付いたデータ群を集める処理が非効率となるおそれがある。例えば、トライ木で前方一致検索を行う場合、入力キー“ｇｏｂａｃｋ”の最後の“ｋ”で到達したノードよりも更に下位のノード（末端のノード）まで探索して、データを収集することになる。また、例えば、パトリシア木で、前方一致検索を行う場合も、トライ木と同様に、入力キー“ｇｏｂａｃｋ”の最後の“ｂａｃｋ”で到達したノードよりも更に下位のノード（末端のノード）まで探索して、データを収集することになる。
【０２０７】
一方、検索装置１００は、到達先のブロックに達するまでに経由するブロックに対応する文字列部分と到達先のブロックに対応する文字列部分とを経由順に連結した連結文字列を接頭部として含む全ての文字列を示すポインタを、到達先のブロックに対応付けて保持する。このため、検索装置１００は、入力キーの各文字列部分に対応するブロックを探索しさえすれば、そのうち最後に到達したブロックの情報を参照することで、ヒットする前方一致文字列を全て特定し、出力できる。
【０２０８】
これによる検索効率をトライ木（double array）やパトリシア木と対比すると次のようになる。以下に示す比較では、前方一致検索時に、格納先の木構造の半分の深さまで検索して、到達したノードを根とする部分木の葉に格納されたデータを収集することを考える。ここで、トライ木におけるエッジの数をＬとする。また、検索対象の各文字列において、同一プレフィックス文字列をもつ後続文字列の平均個数をｄとする。すると、トライ木の最上位から末端までの深さは、ｌｏｇ2Ｌ程度である。このため、その半分の深さは、（１／２）×ｌｏｇ2Ｌである。また、１ノードに対する枝分かれの平均個数はｄ個程度である。
【０２０９】
すると、トライ木において、格納先の木構造の半分の深さまで検索し、到達したノードを根とする部分木の葉に格納された全データの収集に要する時間ｃｔ０は、式（６）で表される。
【０２１０】
【数６】
2017134554.tif 000008
【０２１１】
パトリシア木についても、枝分かれのしかただけを考えると、トライ木の場合と同じである。このため、パトリシア木において、格納先の木構造の半分の深さまで検索した後に、出力すべき全データの収集に要する時間ｃｔ１は、式（７）で表される。
【０２１２】
【数７】
2017134554.tif 000009
【０２１３】
一方、第２の実施の形態の方法では、木構造の半分の深さまで検索した後に、出力すべき全データの収集に要する時間ｃｔ２は、式（８）で表される。
【０２１４】
【数８】
2017134554.tif 000010
【０２１５】
これは、木構造の半分の深さにおいて到達したブロックに対応付けて、当該ブロックに到達したときに出力すべきデータ群を格納時点において収集済だからである。
したがって、既存のトライ木やパトリシア木を用いる場合との所要時間の比は、式（９）で表される。
【０２１６】
【数９】
2017134554.tif 000011
【０２１７】
式（９）において、検索対象文字列の数が増えるとＬが大きくなり、“式（９）の分子”＜＜“式（９）の分母”となるため、第２の実施の形態の検索方法の方が短時間で出力すべきデータ群を収集できる。また、検索対象文字列の数が増え、そのうち互いに類似する文字列が増えるとｄが大きくなるとも考えられる。したがって、検索対象文字列の数が増え、そのうち互いに類似する文字列が増えるほど、“式（９）の分母”が“式（９）の分子”よりも大きくなる度合いに拍車がかかる。このため、第２の実施の形態の検索方法は、検索対象文字列の数が多くなるほど、また、検索対象文字列において互いに類似する文字列が多くなるほど、検索を高速化できる。例えば、前述のように、あるＯＳのソースコードについて、Ｌ〜１０6、ｄ〜５程度となることが想定される。この場合、ｃｔ０＝ｃｔ１＞＞１＝ｃｔ２となり、このようなソースコードに含まれるメソッド名などを前方一致検索の対象とする場合、第２の実施の形態による検索処理は特に有用である。
【０２１８】
このように、検索装置１００は、入力キーに対するブロックを探索していく時間ｒｔ２および入力キーに対して最後に到達したブロックを基に前方一致文字列を収集する時間ｃｔ２それぞれにおいて、既存のトライ木やパトリシア木を用いる方法よりも短縮化できる。こうして、検索装置１００によれば、前方一致検索を高速化することができる。
【０２１９】
なお、第１の実施の形態の情報処理は、演算部１ｂにプログラムを実行させることで実現できる。また、第２の実施の形態の情報処理は、プロセッサ１０１にプログラムを実行させることで実現できる。プログラムは、コンピュータ読み取り可能な記録媒体１３に記録できる。
【０２２０】
例えば、プログラムを記録した記録媒体１３を配布することで、プログラムを流通させることができる。また、プログラムを他のコンピュータに格納しておき、ネットワーク経由でプログラムを配布してもよい。コンピュータは、例えば、記録媒体１３に記録されたプログラムまたは他のコンピュータから受信したプログラムを、ＲＡＭ１０２やＨＤＤ１０３などの記憶装置に格納し（インストールし）、当該記憶装置からプログラムを読み込んで実行してもよい。
【符号の説明】
【０２２１】
１  検索装置
１ａ  記憶部
１ｂ  演算部
２  木構造データ
２ａ，２ｂ，２ｃ，２ｄ，２ｅ  ノード
３  文字列情報
【図１】
2017134554.tif 000012
【図２】
2017134554.tif 000013
【図３】
2017134554.tif 000014
【図４】
2017134554.tif 000015
【図５】
2017134554.tif 000016
【図６】
2017134554.tif 000017
【図７】
2017134554.tif 000018
【図８】
2017134554.tif 000019
【図９】
2017134554.tif 000020
【図１０】
2017134554.tif 000021
【図１１】
2017134554.tif 000022
【図１２】
2017134554.tif 000023
【図１３】
2017134554.tif 000024
【図１４】
2017134554.tif 000025
【図１５】
2017134554.tif 000026
【図１６】
2017134554.tif 000027
【図１７】
2017134554.tif 000028
【図１８】
2017134554.tif 000029
【図１９】
2017134554.tif 000030
【図２０】
2017134554.tif 000031
【図２１】
2017134554.tif 000032
【図２２】
2017134554.tif 000033
【図２３】
2017134554.tif 000034