(57)【要約】【課題】メモリ使用量の問題等を解消すること。【解決手段】接続部１２０は、トライ木１１０ａに接続されたエッジノードを順に辿り、エッジノードに対応する前方一致文字列において、新規データと先頭部分が一致するものがあるかを検索する。接続部１２０は、検索されたエッジノードに対応する前方一致文字列と新規データとのそれぞれから一致した先頭部分を除いた文字列を辞書順で比較する。接続部１２０は、辞書順で比較した結果、新規データから一致した先頭部分を除いた文字列の方が大きかった場合に、エッジノードを先頭部分の文字列とそれ以外の文字列とをそれぞれ格納した２個のエッジノードを作成し、新たにノードを作成して２個のエッジノードの間に接続し、新規データから一致した先頭部分を除いた文字列を格納するエッジノードを作成して新たに作成したノードに接続させる。【選択図】図１
2010277556.tif 000002
【特許請求の範囲】
【請求項１】
データ間で前方一致する前方一致文字列をエッジノードに格納して接続するトライ木を記憶部に格納したコンピュータに、前記トライ木に新規データを登録させるトライ木文字登録プログラムであって、
コンピュータに、
前記トライ木に接続されたエッジノードを順に辿り、エッジノードに対応する前方一致文字列において、前記新規データと先頭部分が一致するものがあるかを検索するステップと、
検索されたエッジノードに対応する前方一致文字列と前記新規データとのそれぞれから前記一致した先頭部分を除いた文字列を辞書順で比較するステップと、
前記辞書順で比較した結果、前記新規データから前記一致した先頭部分を除いた文字列の方が大きかった場合に、前記エッジノードを前記先頭部分の文字列とそれ以外の文字列とをそれぞれ格納した２個のエッジノードを作成し、新たにノードを作成して前記２個のエッジノードの間に接続し、前記新規データから前記一致した先頭部分を除いた文字列を格納するエッジノードを作成して前記新たに作成したノードに接続させるステップと
を実行させることを特徴とするトライ木文字列登録プログラム。
【請求項２】
前記辞書順で比較した結果、前記新規データから前記一致した先頭部分を除いた文字列の方が小さかった場合に、前記エッジノードを前記先頭部分の文字列とそれ以外の文字列とをそれぞれ格納した２個とエッジノードを作成し、新たにノードを作成して前記２個のエッジノードの間に接続し、前記新規データから前記一致した先頭部分を除いた文字列を前記新たに作成したノードに接続するステップを更にコンピュータに実行させることを特徴とする請求項１に記載のトライ木文字列登録プログラム。
【請求項３】
前記トライ木に接続されたエッジノードを辿り、エッジノードに接続されたノードに文字列が接続されていない場合に、前記新規のデータから前記前方一致文字列を取り除いた残りの文字列を前記ノードに接続するステップを更にコンピュータに実行させることを特徴とする請求項１または２に記載のトライ木文字列登録プログラム。
【請求項４】
データ間で前方一致する前方一致文字列をエッジノードに格納して接続するトライ木を記憶する記憶部と、
前記トライ木に接続されたエッジノードを順に辿り、エッジノードに対応する前方一致文字列において、前記新規データと先頭部分が一致するものがあるかを検索し、
検索されたエッジノードに対応する前方一致文字列と前記新規データとのそれぞれから前記一致した先頭部分を除いた文字列を辞書順で比較し、
前記辞書順で比較した結果、前記新規データから前記一致した先頭部分を除いた文字列の方が大きかった場合に、前記エッジノードを前記先頭部分の文字列とそれ以外の文字列とをそれぞれ格納した２個のエッジノードを作成し、新たにノードを作成して前記２個のエッジノードの間に接続し、前記新規データから前記一致した先頭部分を除いた文字列を格納するエッジノードを作成して前記新たに作成したノードに接続させる接続部と
を有することを特徴とするトライ木文字列登録装置。
【請求項５】
前記接続部は、前記辞書順で比較した結果、前記新規データから前記一致した先頭部分を除いた文字列の方が小さかった場合に、前記エッジノードを前記先頭部分の文字列とそれ以外の文字列とをそれぞれ格納した２個とエッジノードを作成し、新たにノードを作成して前記２個のエッジノードの間に接続し、前記新規データから前記一致した先頭部分を除いた文字列を前記新たに作成したノードに接続することを特徴とする請求項４に記載のトライ木文字列登録装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、トライ木文字列登録プログラムおよびトライ木文字列登録装置に関する。
【背景技術】
【０００２】
文書検索システムにおいて、入力キーが指定された場合に、指定された入力キーに対応する文書や値等をデータベースから高速に検索するべく、トライ木が用いられている（例えば、特許文献１、２参照）。図５０は、従来のトライ木の一例を示す図である。このトライ木は、ルートノードを除くノードに対して、１文字あたり１ノードを割当てた木構造のデータである。図５０に示すトライ木は、一例として、キー「black、green、blue、grey、black、grey、greenyellow」にそれぞれ値「１、３、４、５、３、２、１」が割当てられたトライ木を示している。
【０００３】
従来の検索装置が、トライ木の探索処理を実行する場合には、入力キーを１文字ずつ取り出し、トライ木上の同じキーのノードを辿る。例えば、検索装置は、入力キー「blue」が指定された場合に、トライ木のノードをb、l、u、eの順に辿ることで、「blue」に割当てられた値「４」を検出する。
【０００４】
ところで、図５０に示したトライ木では、トライ木を構築するキーが長い場合に、ノード数が増えてしまい、使用メモリ量が増大してしまうという問題があった。また、キーが長い場合に、検索処理時に比較するノード数が増えてしまい、検索処理等が完了するまでの時間が長くなってしまうという問題が発生する。
【０００５】
そこで、かかるトライ木の問題点を解消するべく、パトリシア木（Patricia  Tree）と呼ばれるトライ木が考案されている。図５１は、パトリシア木の一例を示す図である。このパトリシア木は、ノードから他のノードへ遷移するエッジ部（エッジノード）を、文字ではなく文字列で表現することで、使用メモリ量を削減している。
【０００６】
例えば、図５０に示したトライ木では、文字「b」をキーにして、ルートノードからノードbに遷移する。一方、図５１に示すパトリシア木では、文字列「bl」をキーにして、ルートノードaからルートノードbに遷移する。なお、図５１に示すパトリシア木は、キー「black、green、blue、grey、black、grey、greenyellow」にそれぞれ値「１、３、４、５、３、２、１」が割当てられたパトリシア木を示している。
【０００７】
従来の検索装置が、トライ木の検索処理を実行する場合には、入力キーとエッジ部の文字列とを順次比較し、パトリシア木を辿る。例えば、検索装置は、入力木「blue」が指定された場合には、パトリシア木のエッジノード（エッジ部）をbl、ueの順に辿ることで、「blue」に割当てられた「４」を検出する。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開昭５９−４７６６９号公報
【特許文献２】特開平１１−７４５１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
上述したパトリシア木は、通常のトライ木と比較してメモリ使用量の問題等を解消することが出来る。しかし、パトリシア木は、所定の文字列毎にノードを作成しているため、登録対象となる文字列の文字数が多い場合には、多くのノード、エッジノードを生成する必要があり、メモリ使用量が増大してしまうという問題があった。
【００１０】
開示の技術は、上記に鑑みてなされたものであって、メモリ使用量を削減することが出来るトライ木文字列登録プログラムおよびトライ木文字列登録装置を提供することを目的とする。
【課題を解決するための手段】
【００１１】
本願の開示するトライ木文字列登録プログラムは、データ間で前方一致する前方一致文字列をエッジノードに格納して接続するトライ木を記憶部に格納したコンピュータに、前記トライ木に新規データを登録させるトライ木文字登録プログラムであって、コンピュータに、前記トライ木に接続されたエッジノードを順に辿り、エッジノードに対応する前方一致文字列において、前記新規データと先頭部分が一致するものがあるかを検索するステップと、検索されたエッジノードに対応する前方一致文字列と前記新規データとのそれぞれから前記一致した先頭部分を除いた文字列を辞書順で比較するステップと、前記辞書順で比較した結果、前記新規データから前記一致した先頭部分を除いた文字列の方が大きかった場合に、前記エッジノードを前記先頭部分の文字列とそれ以外の文字列とをそれぞれ格納した２個のエッジノードを作成し、新たにノードを作成して前記２個のエッジノードの間に接続し、前記新規データから前記一致した先頭部分を除いた文字列を格納するエッジノードを作成して前記新たに作成したノードに接続させるステップとを実行させることを要件とする。
【発明の効果】
【００１２】
本願の開示するトライ木文字列登録プログラムは、メモリ使用量の問題等を解消することが出来る。
【図面の簡単な説明】
【００１３】
【図１】図１は、本実施例１にかかるトライ木文字列登録装置の構成を示す図である。
【図２】図２は、木構造に含まれるノードの用語を説明するための図である。
【図３】図３は、本実施例２にかかる検索装置の構成を示す図である。
【図４】図４は、登録データ管理テーブルのデータ構造の一例を示す図である。
【図５】図５は、トライ木のデータ構造の一例を示す図である。
【図６】図６は、実データで表した場合のデータ構造の一例を示す図である。
【図７】図７は、トライ木生成部の処理の概要を説明するための図である。
【図８】図８は、トライ木生成部のその他の処理を説明するための図である。
【図９】図９は、トライ木を生成する処理を説明するための図（１）である。
【図１０】図１０は、トライ木を生成する処理を説明するための図（２）である。
【図１１】図１１は、トライ木を生成する処理を説明するための図（３）である。
【図１２】図１２は、トライ木を生成する処理を説明するための図（４）である。
【図１３】図１３は、トライ木を生成する処理を説明するための図（５）である。
【図１４】図１４は、トライ木を生成する処理を説明するための図（６）である。
【図１５】図１５は、トライ木を生成する処理を説明するための図（７）である。
【図１６】図１６は、トライ木を生成する処理を説明するための図（８）である。
【図１７】図１７は、トライ木を生成する処理を説明するための図（９）である。
【図１８】図１８は、トライ木を生成する処理を説明するための図（１０）である。
【図１９】図１９は、トライ木を生成する処理を説明するための図（１１）である。
【図２０】図２０は、トライ木を生成する処理を説明するための図（１２）である。
【図２１】図２１は、トライ木を生成する処理を説明するための図（１３）である。
【図２２】図２２は、トライ木を生成する処理を説明するための図（１４）である。
【図２３】図２３は、トライ木を生成する処理を説明するための図（１５）である。
【図２４】図２４は、トライ木を生成する処理を説明するための図（１６）である。
【図２５】図２５は、トライ木を生成する処理を説明するための図（１７）である。
【図２６】図２６は、トライ木を生成する処理を説明するための図（１８）である。
【図２７】図２７は、トライ木を生成する処理を説明するための図（１９）である。
【図２８】図２８は、集計値を抽出する処理を説明するための図（１）である。
【図２９】図２９は、集計値を抽出する処理を説明するための図（２）である。
【図３０】図３０は、集計値を抽出する処理を説明するための図（３）である。
【図３１】図３１は、集計値を抽出する処理を説明するための図（４）である。
【図３２】図３２は、集計値を抽出する処理を説明するための図（５）である。
【図３３】図３３は、検索処理を説明するための図（１）である。
【図３４】図３４は、検索処理を説明するための図（２）である。
【図３５】図３５は、検索処理を説明するための図（３）である。
【図３６】図３６は、トライ木生成処理の処理手順を示すフローチャート（１）である。
【図３７】図３７は、トライ木生成処理の処理手順を示すフローチャート（２）である。
【図３８】図３８は、トライ木生成処理の処理手順を示すフローチャート（３）である。
【図３９】図３９は、トライ木生成処理の処理手順を示すフローチャート（４）である。
【図４０】図４０は、トライ木生成処理の処理手順を示すフローチャート（５）である。
【図４１】図４１は、集計処理の処理手順を示すフローチャートである。
【図４２】図４２は、検索処理の処理手順を示すフローチャート（１）である。
【図４３】図４３は、検索処理の処理手順を示すフローチャート（２）である。
【図４４】図４４は、削除処理の処理手順を示すフローチャート（１）である。
【図４５】図４５は、削除処理の処理手順を示すフローチャート（２）である。
【図４６】図４６は、削除処理の処理手順を示すフローチャート（３）である。
【図４７】図４７は、削除処理の処理手順を示すフローチャート（４）である。
【図４８】図４８は、トライ木のその他のデータ構造の一例を示す図である。
【図４９】図４９は、実施例２に示した検索装置に対応するコンピュータのハードウェア構成を示す図である。
【図５０】図５０は、従来のトライ木の一例を示す図である。
【図５１】図５１は、パトリシア木の一例を示す図である。
【図５２】図５２は、先行発明のトライ木を示す図である。
【図５３】図５３は、先行技術の問題点を説明するための図（１）である。
【図５４】図５４は、先行技術の問題点を説明するための図（２）である。
【図５５】図５５は、パトリシア木と従来技術を組合せた技術を示す図である。
【図５６】図５６は、パトリシア木と先行技術を組合せた場合の問題点を説明するための図である。
【発明を実施するための形態】
【００１４】
以下に、本願の開示するトライ木文字列登録プログラムおよびトライ木文字列登録装置の実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。
【実施例１】
【００１５】
まず、本実施例１の説明を行う前に、発明者が考案した先行発明について説明する。以下に示す先行発明１は従来技術に該当するものではない。
【００１６】
先行発明は、１データあたり１ノードを割当てることでトライ木を構築する。図５２は、先行発明のトライ木を示す図である。図５２に示したトライ木１０は、図５０に示したトライ木と同じように、タグキー「black、green、blue、grey、black、grey」にそれぞれ値「１、３、４、５、３、２」を割当てている。
【００１７】
なお、トライ木１０において、トライを省略したことにより表現できないキーは、ノードにタグキーを付加して保持する。例えば、ノードｂにタグキー「lack」を付加することで、blackを表現する。このように、トライ木１０は、１ノードにタグキーを一つ対応付けているため、データを保持していないノードが存在せず、メモリ効率を高めることができる。
【００１８】
ただし、先行発明のトライ木は、１つのノードに１つのタグキーを割当てた代償として、実際にノードに登録されたタグキーを参照しなければ、入力キーがタグキーにヒットしたか否かを判定できない。
【００１９】
例えば、入力キー「blue」を検索する場合について説明する。図５２に示したトライ木１０では、入力キー「blue」の１文字目「b」により、ノードを遷移すると、まず、ルートノードからノードbに移行する。ノードbに移行した時点では、入力キーにヒットしたか否かを判定できない。実際に、ノードbのタグキー「black」と比較して初めて、ヒットしていないと判定できる。
【００２０】
そして、２文字目「l」によりノードlに遷移し、ノードlのタグキー「blue」と入力キー「blue」とを比較すると、入力キーとタグキーが一致したと判定できるので、ノードlに付加された値「４」が検出結果として検出される。したがって、ただ闇雲に、各ノードにタグキーを割当ててしまうと、各入力キーにより遷移する各ノードのタグキーと順次比較処理を行うこととなり、処理効率の向上が図れない。
【００２１】
かかる課題を解消するため、先行発明では、深さ優先探索順でタグキーが並ぶようにトライ木を構築する。このように、深さ優先探索順でタグキーを並べると、データの検索時に入力キーと比較対象となるタグキーを有するノードを絞り込むことができ、処理の効率化を図ることができる。先行発明では、深さ優先探索順でキーが並ぶようにトライ木を構築する際に、各キーの優先度を判定し、優先度が小さいキーほどルートノードに近いノードに割当てる。
【００２２】
先行発明では、各文字列の優先度の大小を判定する場合に、異なる文字が検出されるまで各キーの文字を先頭から順に抽出する。そして、抽出した文字において、アルファベット順で、ａに近い文字ほど優先度を小さくし、ｚに近い文字ほど優先度を大きくする。すなわち、優先度は、「a＜b＜c＜d＜e＜f＜g＜h＜i＜j＜k＜l＜m＜n＜o＜p＜q＜r＜s＜t＜u＜v＜w＜x＜y＜z」となる。なお、優先度が同じ文字列は、等しい文字列であるといえる。
【００２３】
例えば、タグキー「black」と「blue」を比較すると、３文字目で異なる文字が抽出される。具体的には、「black」から「a」が抽出され、「blue」から「u」が抽出される。そして、「a」と「u」とを比較すると、「u」の方が「a」よりも優先度が大きくなる。したがって、優先度の小さい「black」を「blue」よりもルートノード側のノードに割り当てる。
【００２４】
しかしながら、先行技術には下記に示す問題点が存在する。図５３および図５４は、先行技術の問題点を説明するための図である。図５３に示すトライ木は、ルートノードに、ノードh、ノードt（親）、ノードt（子）が順に接続されている。ノードhはタグキー「ttp://aaa.aaa/e/」を有し、ノードt（親）はタグキー「tp://aaa.aaa/e/c/」を有し、ノードt（子）はタグキー「p://aaa.aaa/g/」を有する。
【００２５】
例えば、図５３に示すトライ木に文字列「http://aaa.aaa/h/」を登録する場合について説明する。かかる新規の文字列（以下、入力キー）は、トライ木に登録されている文字列と先頭部分の文字列が一致している。従って、各文字列の一致していない文字同士を比較するまで、優先度の大小を判定できないため、比較すべき文字数が増えてしまう。
【００２６】
具体的に、入力キー「http://aaa.aaa/h/」を登録する場合には、入力キーを先頭から読み出してトライ木を遷移し、遷移するたびに、入力キーとノードに対応する文字列を１文字ずつ比較することになる。まず、処理装置は、ノードhに遷移し、ノードhに対応する文字列「http://aaa.aaa/e/」と、入力キー「http://aaa.aaa/h/」を比較すると、ノードhに登録された文字列の１６文字目の「e」と、入力キーの１６文字目の「h」とを比較して初めて、入力キーの優先度がノードhの文字列よりも大きいと判定できる。
【００２７】
実際は、ノードhのタグキー「ttp://aaa.aaa/e/」と、入力キーからトライ部分hを取り除いた「ttp://aaa.aaa/h/」を比較して、優先度の大小を比較する。図５３の説明では、ノードt（親）、ノードt（子）と比較する場合も同様。
【００２８】
続いて、処理装置は、ノードt（親）に対応する文字列「http://aaa.aaa/e/c/」と、入力キー「http://aaa.aaa/h/」を比較すると、ノードhに登録された文字列の１６文字目の「e」と、入力キーの１６文字目の「h」とを比較して初めて、入力キーの優先度がノードt（親）の文字列よりも大きいと判定できる。
【００２９】
また、処理装置は、ノードt（子）に対応する文字列「http://aaa.aaa/g/」と、入力キー「http://aaa.aaa/h/」を比較すると、ノードhに登録された文字列の１６文字目の「g」と、入力キーの１６文字目の「h」とを比較して初めて、入力キーの優先度がノードt（子）の文字列よりも大きいと判定できる。ここで、入力キーの優先度は、ノードt（子）の文字列の優先度よりも大きいと判定できたため、処理装置は、新たなノードを生成して、ノードtに接続し、新たなノードに入力キーを登録することになる。
【００３０】
上述したように、トライ木に登録された文字列と入力キーの先頭部分が多く一致していると、実質、トライ木に登録された全ての文字列と入力キーを比較するはめになり、入力キーを登録する場合の処理時間に多くの時間を要し、迅速にトライ木の再構成処理を実行できない。
【００３１】
続いて、図５４の説明に移行する。図５４の上段に示すトライ木は、ルートノードに、ノードh、ノードt（親）、ノードt（子）、ノードp、ノード:、ノード/が順に接続されている。
【００３２】
また、図５４の上段に示すトライ木は、優先度の小さいタグキーから順に、各ノードに登録されている。ノードhはタグキー「ttp://aaa.aaa/e/」を有し、ノードt（親）はタグキー「tp://aaa.aaa/e/c/」を有し、ノードt（子）はタグキー「p://aaa.aaa/g/」を有する。ノードpはタグキー「://aaa.aaa/h/」を有し、ノード:はタグキー「//aaa.aaa/k/」を有し、ノード/はタグキー「/aaa.aaa/m/」を有する。
【００３３】
図５４に示すように、先頭文字列が一致しているキーが多いと、トライ木が深くなってしまい、トライ木に新しいキーを登録してトライ木を再構築する場合の処理が多くなってしまうという問題がある。
【００３４】
図５４の下段は、図５４の上段に示したトライ木に、キー「http://aaa.aaa/b/」を登録した場合のトライ木を示す。ここで、入力キー「http://aaa.aaa/b/」からトライ部分「h」を削除したキー「ttp://aaa.aaa/b/」の優先度は、ノードhのタグキー「ttp://aaa.aaa/e/」の優先度よりも小さい。
【００３５】
したがって、処理装置は、ノードhにキー「ttp://aaa.aaa/b/」をタグキーとして登録し、ノードhに登録されていたキー「（ht）tp://aaa.aaa/e/」を子ノードのノードt（親）のタグキーとして登録する。同様に、ノードt（親）〜ノード/に登録されていたタグキーも、子ノードに順次登録する。
【００３６】
この場合、ノードhに新たなキーを登録したので、ノードh〜ノード/に登録されていたタグキーを更新すると共に、ノードh〜ノード/に登録されていたタグキーを子ノードに再接続する必要があるため、処理装置が実行すべき処理が多くなり、迅速にトライ木の再構築処理を実行することが出来ないという問題が存在する。
【００３７】
ところで、背景技術に示したパトリシア木と先行技術とを組合せることで、図５３、図５４で示した再構築処理に時間がかかってしまうという問題点を解消することが出来る。以下において、パトリシア木と先行技術を組合せた技術について説明する。図５５は、パトリシア木と従来技術を組合せた技術を示す図である。
【００３８】
かかる技術では、各文字列を参照して、前方一致する文字列を１つのエッジノードに縮退し、残りの文字列をタグに格納してノードに接続することで、トライ木を構築する。例えば、図５５に示すように、文字列「http://aaa.aaa/e/」、「http://aaa.aaa/e/c/」、「http://aaa.aaa/g/」は、前方一致する文字列が、「http://aaa.aaa」となるため、かかる文字列「http://aaa.aaa」をエッジノードに縮退して、ルートノードａに接続する。
【００３９】
文字列「http://aaa.aaa/e/」から前方一致する文字列「http://aaa.aaa」を取り除くと、文字列「e/」となるので、ノードｂにタグキー「e/」を接続する。文字列「http://aaa.aaa/e/c/」から前方一致する文字列「http://aaa.aaa」を取り除くと、文字列「e/c/」となるので、ノードｂにエッジノード「e/c/」を接続する。また、ここでは説明の便宜上、エッジノード「e/c/」の配下にノードcを接続し、タグキー「空」を接続する。
【００４０】
文字列「http://aaa.aaa/e/g/」から前方一致する文字列「http://aaa.aaa」を取り除くと、文字列「g/」となるので、ノードｂにエッジノード「g/」を接続する。また、ここでは説明の便宜上、エッジノード「g/」の配下にノードdを接続し、タグキー「空」を接続する。
【００４１】
図５５のようにトライ木を構築することで、トライ木に登録されている文字列と先頭部分の文字列が一致している入力キーを新たに登録する場合でも、再構築処理にかかる時間を図５４に示した場合と比較して大幅に削減することが出来る。
【００４２】
ここでは一例として、入力キー「http://aaa.aaa/h」を登録する場合について説明する。処理装置が、入力キーとルートノードａのエッジキー（エッジノードに登録された文字列）とを比較すると、入力キーの先頭文字「h」からエッジノードの文字数に対応する文字「/」までの文字列「http://aaa.aaa/」が、エッジノードの文字列と一致する（以下、前方一致する）ので、ノードｂに遷移する。
【００４３】
処理装置は、ノードｂにおいて、入力キーからエッジノードの文字列を取り除いた文字列「h/」を特定し、文字「h」をキーとする遷移先が存在しないので、ノードｂのタグキー「e/」の優先度と文字列「h/」の優先度を比較する。
【００４４】
処理装置は、文字列「h/」の優先度がタグキー「e/」の優先度よりも大きいので、ノードｂにエッジノード「h/」を登録することで、入力キー「http://aaa.aaa/h」の登録処理が完了する。
【００４５】
このように、前方一致する文字列を１つのエッジノードに縮退しているので、トライ木に登録されている文字列と先頭部分の文字列が一致している入力キーを新たに登録する場合でも、比較回数を削減することができ、再構築処理にかかる時間を削減することが出来る。
【００４６】
しかしながら、パトリシア木と先行技術を組合せた場合でも、入力キーの登録時において、前方一致文字列に対応するエッジノードに接続されている部分木を全面的に再構築しなければならない場合があり、そのような場合の処理に時間がかかるという問題点があった。
【００４７】
図５６は、パトリシア木と先行技術を組合せた場合の問題点を説明するための図である。図５６の上段に示すトライ木は、文字列「http://bbb.bbb/e/」、「http://bbb.bbb/e/c/」、「http://bbb.bbb/e/g/」、「http://bbb.bbb/k」を有するトライ木である。
【００４８】
このトライ木において、ルートノードａは、エッジノード「http://bbb.bbb/e/」に接続されている。かかるエッジノードの文字列「http://bbb.bbb/e/」は、文字列「http://bbb.bbb/e/」、「http://bbb.bbb/e/c/」、「http://bbb.bbb/e/g/」、「http://bbb.bbb/k」に共通する文字列である。
【００４９】
エッジノード「http://bbb.bbb/」は、ノードｂに接続する。ノードｂは、タグキー「e/」、エッジノード「e/」、エッジノード「k/」に接続する。エッジノード「e/」は、ノードｃに接続する。ノードｃは、タグキー「c/」、エッジノード「g/」に接続する。エッジノード「g/」は、ノードｄに接続する。ノードｄは、タグキー「空」に接続する。エッジノード「k/」は、ノードｅに接続し、ノードｅは、タグキー「空」に接続する。
【００５０】
ここで、図５６の上段に示すトライ木に、入力キー「http://bbb.ccc/h/」を登録する場合について説明する。入力キー「http://bbb.ccc/h/」と、エッジノードの文字列「http://bbb.bbb/e/」を比較すると、エッジノードの文字列の一部「http://bbb.」が、入力キーと一致する。
【００５１】
パトリシア木と先行技術を組合せたトライ木は、登録する全ての文字列に共通する部分の文字列をエッジノードに集約するという条件の下、生成されているので、ルートノードａに接続されるエッジキーの文字列が「http://bbb.bbb/e/」から「http://bbb.」に変更される。
【００５２】
このように、エッジノードの文字列が「http://bbb.bbb/e/」から「http://bbb.」に変更されると、トライ木全体の整合性を保つべく、処理装置は、エッジノード「http://bbb.bbb」の配下に接続されたノード、タグキー、エッジノードを全て再構成する必要がある。
【００５３】
図５６の下段に示すように、処理装置は、ルートノードａにエッジノード「http://bbb」を接続し、エッジノード「http://bbb」と、ノードｂを接続する。処理装置は、ノードｂとタグキー「bbb/e/」、エッジノード「bbb/」、エッジノード「ccc/h/」を接続する。
【００５４】
処理装置は、エッジノード「bbb/」とノードｃを接続し、ノードｃと、タグキー「e/c/」、エッジノード「e/g/」、エッジノード「k/」を接続する。処理装置は、エッジノード「e/g/」とノードｄを接続し、ノードｄと、タグキー「空」を接続する。処理装置は、エッジノード「k/」とノードｅを接続し、ノードｅと、タグキー「空」を接続する。処理装置は、エッジノード「ccc/h/」とノードｆを接続し、ノードｆと、タグキー「空」を接続する。
【００５５】
このように、パトリシア木と先行技術を組合せたトライ木は、最適な文字列でエッジノードの縮退を実行しておかないと、入力キーとエッジノードの文字列の相性が悪い場合に、図５６に示すようなトライ木の再構築処理を実行することとなるので、トライ木の再構築処理に時間がかかってしまうという問題があった。
【００５６】
次に、本実施例１にかかるトライ木文字列登録装置の構成について説明する。図１は、本実施例１にかかるトライ木文字列登録装置の構成を示す図である。図１に示すように、このトライ木文字列登録装置１００は、記憶部１１０と、接続部１２０を有する。
【００５７】
記憶部１１０は、データ間で前方一致する前方一致文字列をエッジノードに格納して接続するトライ木１１０ａを記憶する記憶部である。
【００５８】
接続部１２０は、新規データをトライ木１１０ａに接続する処理部である。具体的に、接続部１２０は、トライ木１１０ａに接続されたエッジノードを順に辿り、エッジノードに対応する前方一致文字列において、新規データと先頭部分が一致するものがあるかを検索する。
【００５９】
そして、接続部１２０は、検索されたエッジノードに対応する前方一致文字列と新規データとのそれぞれから一致した先頭部分を除いた文字列を辞書順で比較する。接続部１２０は、辞書順で比較した結果、新規データから一致した先頭部分を除いた文字列の方が大きかった場合に、エッジノードを先頭部分の文字列とそれ以外の文字列とをそれぞれ格納した２個のエッジノードを作成し、新たにノードを作成して２個のエッジノードの間に接続し、新規データから一致した先頭部分を除いた文字列を格納するエッジノードを作成して新たに作成したノードに接続させる。
【００６０】
このように、本実施例１にかかるトライ木文字列登録装置１００は、接続部１２０が、新規データとエッジノードの文字列とを基にして、配下に接続されたデータの整合性を保ちつつ、新規ノードをトライ木に接続するので、トライ木の再構成処理の処理時間を削減することが出来る。
【実施例２】
【００６１】
まず、本実施例２にかかる検索装置の説明を行う前に、トライ木等の木構造に含まれるノードの用語について説明する。図２は、木構造に含まれるノードの用語を説明するための図である。図２に示すように、トライ木を構成する各ノードのうち、最上層に位置するノードをルートノードと定義する。また、基準ノードのひとつ上の層に存在し、基準ノードに接続されたノードを、基準ノードに対する親ノード（以下、単に親ノード）と定義する。また、基準ノードのひとつ下の層に存在し、基準ノードに接続されたノードを基準ノードに対する子供ノード（以下、単に子供ノード）と定義する。
【００６２】
また、基準ノードと同じ層に存在し、基準ノードと同じ親ノードに接続され、基準ノードの上側に存在するノードを、基準ノードに対する兄ノード（以下、単に兄ノード）と定義する。また、基準ノードと同じ層に存在し、基準ノードと同じ親ノードに接続され、基準ノードの下側に存在するノードを、基準ノードに対する弟ノード（以下、単に弟ノード）と定義する。また、根ノード（ルートノード）から親ノードに至る各ノードをまとめて先祖ノードと定義する。また、基準ノードの配下に接続された各ノードをまとめて子孫ノードと定義する。なお、各ノードを接続する文字列をエッジノードとする。
【００６３】
次に、本実施例２にかかる検索装置について説明する。図３は、本実施例２にかかる検索装置の構成を示す図である。図３に示すように、この検索装置２００は、入力部２１０、出力部２２０、入出力制御部２３０、記憶部２４０、制御部２５０を有する。
【００６４】
このうち、入力部２１０は、入力キー等の情報を入力する入力部であり、キーボードやマウス等に該当する。出力部２２０は、トライ木を用いた検索結果などの情報を出力する出力部であり、モニタ、若しくはディスプレイ、タッチパネル等に該当する。入出力制御部２３０は、入力部２１０、出力部２２０、記憶部２４０、制御部２５０によるデータの入出力を制御する処理部である。
【００６５】
記憶部２４０は、制御部２５０による各種処理に必要なデータおよびプログラムを記憶する記憶部である。この記憶部２４０は、登録データ管理テーブル２４０ａ、トライ木２４０ｂを有する。
【００６６】
ここで、登録データ管理テーブル２４０ａは、トライ木に登録するキーと値とを対応付けて記憶するテーブルである。図４は、登録データ管理テーブル２４０ａのデータ構造の一例を示す図である。図４に示すように、この登録データ管理テーブル２４０ａは、キーと値を対応付けて記憶している。
【００６７】
トライ木２４０ｂは、登録データ管理テーブル２４０ａを基にして生成されるトライ木である。図５は、トライ木のデータ構造の一例を示す図である。図５では一例として、図４に示した登録データ管理テーブル２４０ａに対応したトライ木を示す。
【００６８】
図５に示すように、このトライ木２４０ｂは、ルートノードａがエッジノード「b」を介してノードｂに接続し、エッジノード「green」を介してノードｄに接続する。ノードｂは、タグキー「eige」、値「２」を接続する。また、ノードｂは、エッジノード「lack」を介してノードｃに接続する。ノードｃは、タグキー「空」、値「１，３」を接続する。ノードｄは、タグキー「空」、値「４」に接続する。
【００６９】
図５に示したトライ木を実データで表すと、図６に示すデータ構造となる。図６は、実データで表した場合のデータ構造の一例を示す図である。図６に示すように、このトライ木は、各ノードに対応するポインタ配列２０〜２３と、タグキーの文字列を記憶するテキスト表５０を有している。
【００７０】
ここで、ルートノードポインタに接続するポインタ配列２０は、図５のルートノードａに対応する。ポインタ配列２１は、図５のノードｂに対応し、ポインタ配列２２は、ノードｃに対応し、ポインタ配列２３は、ノードｄに対応する。
【００７１】
ポインタ配列２０〜２３は、各ポインタ配列へのポインタ領域「０×００〜０×ＦＦ」、「Edge」領域、「TAG」領域、「Data」領域を有する。このうち、ポインタ領域は、次のポインタ配列の位置を格納する領域であり、所定の文字に対応付けて配置されている。例えば、ポインタ領域「０×６２」は、文字「ｂ」に対応付けられており、エッジノードの文字列の先頭文字に対応する。エッジノードの残りの文字は、遷移先のポインタ配列の「Edge」領域に格納されている。
【００７２】
例えば、ポインタ配列２１の「Edge」領域は「空」に接続されているので、文字「ｂ」と「空」を合わせた「ｂ」が、ポインタ配列２０からポインタ配列２１に遷移する場合のエッジノードとなる。
【００７３】
また、ポインタ配列２１において、ポインタ領域「０×６ｃ」は、文字「l」に対応付けられており、エッジノードの文字列の先頭文字に対応する。エッジノードの残りの文字は、遷移先のポインタ配列の「Edge」領域に格納されている。例えば、ポインタ配列２２の「Edge」領域は「ack」に接続されているので、文字「l」と「ack」を合わせた「lack」が、ポインタ配列２１からポインタ配列２２に遷移する場合のエッジノードの文字列となる。
【００７４】
「TAG」領域は、テキスト表５０の文字と対応付けることで、ノードに接続されたタグキーを表現する。例えば、ポインタ配列２１は、テキスト表５０の「e」に接続されているので、「e」から次の空白前までの文字列「eige」をタグキーとして指定している。
【００７５】
入力キーを指定する場合にも、テキスト表５０を利用する。例えば、入力キー「green」を指定する場合には、入力キーポインタを、テキスト表５０の「g」に接続する。
【００７６】
「Data」領域は、値と対応付けることで、ノードに接続された値を表現する。例えば、ポインタ配列２１は、値「２」に接続されている。なお、入力キーに対応する値（入力値）は、入力キーポインタに対応付けられているものとする。
【００７７】
図３の説明に戻ると、制御部２５０は、各種の処理手順を規定したプログラムや制御データを格納するための内部メモリを有し、これらによって種々の処理を実行する制御部である。図３に示すように、この制御部２５０は、トライ木生成部２５０ａ、トライ木探索部２５０ｂを有する。
【００７８】
トライ木生成部２５０ａは、登録データ管理テーブル２４０ａに登録されたキー（文字列）に基づいて、トライ木２４０ｂを生成する処理部である。トライ木生成部２４０ｂは、入力キーを追加する場所に応じて、登録処理の内容を切り替えることで、トライ木２４０ｂ内で再構築する部分を最小限に抑え、再構築処理にかかる時間を削減する。
【００７９】
トライ木生成部２５０ａは、新規の入力キーをトライ木２４０ｂに登録する場合に、入力キーの文字列を読み出してエッジノードを辿り、入力キーと先頭部分が一致する文字列を有するエッジノードを探索する。以下の説明において、先頭部分が一致した文字列を前方一致文字列と表記する。
【００８０】
そして、トライ木生成部２５０ａは、探索したエッジノードの文字列から前方一致文字列を除いた文字列の優先度と、入力キーから前方一致文字列を除いた文字列の優先度を比較する。トライ木生成部２５０ａは、入力キーから前方一致文字列を除いた文字列の優先度がエッジノードから前方一致文字列を除いた文字列の優先度よりも小さい場合は、第１の登録処理を実行する。一方、入力キーから前方一致文字列を除いた文字列の優先度がエッジノードから前方一致文字列を除いた文字列の優先度よりも大きい場合は、第２の登録処理を実行する。
【００８１】
第１の登録処理において、トライ木生成部２５０ａは、前方一致文字列を含む第１のエッジノードと、エッジキーから前方一致文字列を除いた文字列を含む第２のエッジノードを作成する。トライ木生成部２５０ａは、新しいノードを生成し、第１のエッジノードと第２のエッジノードの間に新規のノードを接続する。そして、トライ木生成部２５０ａは、入力キーから前方一致文字列を取り除いた残りの文字列を新規のタグキーに登録することで、第１の登録処理を完了する。
【００８２】
第２の登録処理において、トライ木生成部２５０ａは、前方一致文字列を含む第１のエッジノードと、エッジキーから前方一致文字列を除いた文字列を含む第２のエッジノードを作成する。トライ木生成部２５０ａは、新しいノードを生成し、第１のエッジノードと第２のエッジノードの間に新規のノードを接続する。そして、トライ木生成部２５０ａは、入力キーから前方一致文字列を取り除いた残りの文字列を新規のエッジノードに登録し、かかる新規のエッジノードを、新規のノードに接続することで、第２の登録処理を完了する。
【００８３】
図７は、トライ木生成部２５０ａの処理の概要を説明するための図である。図７では説明の便宜上、ノードに接続される値を省く。図７の上段に示すトライ木２４０ｂは、文字列「http://bbb.bbb/e/」、「http://bbb.bbb/e/c/」、「http://bbb.bbb/g/」を有するトライ木である。トライ木２４０ｂは、ルートノードａがエッジノード「http://bbb.bbb/」を介してノードｂに接続する。
【００８４】
ノードｂは、タグキー「e/」を接続する。ノードｂは、エッジノード「e/c/」を介してノードｃに接続し、エッジノード「g/」を介してノードｄに接続する。ノードｃ、ノードｂは、タグキー「空」に接続する。
【００８５】
まず、図７の上段に示すトライ木２４０ｂに、入力キー「http://bbb.aaa/h/」を登録する場合について説明する。トライ木生成部２５０ａは、新規の入力キー「http://bbb.aaa/h/」をトライ木２４０ｂに登録する場合に、入力キーの文字列を読み出してエッジノードを辿り、入力キーと先頭部分が一致する文字列を有するエッジノードを探索する。
【００８６】
ここでは、エッジノード「http://bbb.bbb/」が、入力キーと先頭部分が一致する文字列「http://bbb.」を有するエッジノードとなる。かかる文字列「http://bbb.」は、上述した前方一致文字列に対応する。
【００８７】
そして、トライ木生成部２５０ａは、探索したエッジノード「http://bbb.bbb/」から前方一致文字列を除いた文字列「bbb/」の優先度と、入力キーから前方一致文字列を除いた文字列「aaa/h/」の優先度を比較する。すると、入力キーの優先度がエッジノードの優先度よりも小さいので、トライ木生成部２５０ａは、第１の登録処理を実行する。
【００８８】
トライ木生成部２５０ａは、前方一致文字列を含む第１のエッジノード「http://bbb.」と、エッジノードから前方一致文字列を除いた文字列を含む第２のエッジノード「bbb/」を作成する。トライ木生成部２５０ａは、新しいノードeを生成し、第１のエッジノードと第２のエッジノードの間に新規のノードeを接続する。そして、トライ木生成部２５０ａは、入力キーから前方一致文字列を取り除いた残りの文字列「aaa/h/」をノードeのタグキーに登録することで、第１の登録処理を完了する。
【００８９】
このように、トライ木生成部２５０ａが、入力キー「http://bbb.aaa/h/」にあわせて、第１の登録処理を実行することで、エッジノードの文字列が「http://bbb.bbb/」から「http://bbb.」に変更されても、ノードbの配下に接続されたタグキーやノードはそのままの状態で整合がとれているので、第１の登録処理以外にトライ木生成部２５０ａは再構築処理を実行する必要がない。図７の中段のトライ木参照。
【００９０】
続いて、入力キー「http://bbb.ccc/h/」を登録する場合について説明する。トライ木生成部２５０ａは、新規の入力キー「http://bbb.ccc/h/」をトライ木２４０ｂに登録する場合に、入力キーの文字列を読み出してエッジノードを辿り、入力キーと先頭部分が一致する文字列を有するエッジノードを探索する。
【００９１】
ここでは、エッジノード「http://bbb.bbb/」が、入力キーと先頭部分が一致する文字列「http://bbb.」を有するエッジノードとなる。かかる文字列「http://bbb.」は、上述した前方一致文字列に対応する。
【００９２】
そして、トライ木生成部２５０ａは、探索したエッジノード「http://bbb.bbb/」から前方一致文字列を除いた文字列「bbb/」の優先度と、入力キーから前方一致文字列を除いた文字列「ccc/h/」の優先度を比較する。すると、入力キーの優先度がエッジノードの優先度よりも大きいので、トライ木生成部２５０ａは、第２の登録処理を実行する。
【００９３】
トライ木生成部２５０ａは、前方一致文字列を含む第１のエッジノード「http://bbb.」と、エッジノードから前方一致文字列を除いた文字列を含む第２のエッジノード「bbb/」を作成する。トライ木生成部２５０ａは、新しいノードeを生成し、第１のエッジノードと第２のエッジノードの間に新規のノードeを接続する。そして、トライ木生成部２５０ａは、入力キーから前方一致文字列を取り除いた残りの文字列「ccc/h/」を特定する。
【００９４】
トライ木生成部２５０ａは、エッジノード「bbb/」の文字数にあわせて、エッジノード「ccc/」を生成し、ノードeに接続する。また、トライ木生成部２５０ａは、エッジノード「ccc/」の配下にノードfを生成し、入力キーの残りの文字列「h/」に対応するタグキー「h/」をノードfに接続する。
【００９５】
このように、トライ木生成部２５０ａが、入力キー「http://bbb.ccc/h/」にあわせて、第２の登録処理を実行することで、エッジノードの文字列が「http://bbb.bbb/」から「http://bbb.」に変更されても、ノードbの配下に接続されたタグキーやノードはそのままの状態で整合がとれているので、第２の登録処理以外にトライ木生成部２５０ａは再構築処理を実行する必要がない。図７の下段のトライ木参照。
【００９６】
ところで、トライ木生成部２５０ａは、エッジノードの配下に接続されたノードにタグキーが登録されていない（タグキーが空）状態で入力キーを登録する場合に、新規にノードを生成することなく、タグキーが登録されていないノードに、入力キーに対応する文字列を接続する。図８は、トライ木生成部２５０ａのその他の処理を説明するための図である。
【００９７】
図８の上段に示すトライ木は、図７の下段に示したトライ木に対応する。図８の上段に示すように、ノードeにはタグキーが接続されていない。ここで、トライ木生成部２５０ａが、入力キー「http://bbb.aaa/d/」を登録する場合について説明する。
【００９８】
トライ木生成部２５０ａは、新規の入力キー「http://bbb.aaa/h/」をトライ木２４０ｂに登録する場合に、入力キーの文字列を読み出してエッジノードを辿り、入力キーと先頭部分が一致する文字列を有するエッジノードを探索する。
【００９９】
ここでは、エッジノード「http://bbb.」が、入力キーと先頭部分が一致する文字列「http://bbb.」を有するエッジノードとなる。かかる文字列「http://bbb.」は、上述した前方一致文字列に対応する。
【０１００】
そして、トライ木生成部２５０ａは、ノードeに移行すると、ノードeにタグキーが接続されていないので、入力キーから前方一致文字列を取り除いた残りの文字列「aaa/d/」を、ノードeに接続し、登録処理を完了する。
【０１０１】
このように、トライ木生成部２５０ａは、エッジノードの配下に接続されたノードにタグキーが登録されていない（タグキーが空）状態で入力キーを登録する場合に、新規にノードを生成することなく、タグキーが登録されていないノードに、入力キーに対応する文字列を接続するので、再構築処理を簡略化することが出来る。
【０１０２】
続いて、トライ木生成部２５０ａの処理をより詳細に説明する。図９〜図２７は、トライ木を生成する処理を説明するための図である。ここでは説明の便宜上、キー「http://aaa.aaa/e/」と値「１」、キー「http://aaa.aaa/e/c/」と値「２」、キー「http://aaa.aaa/d/」と値「３」、キー「http://aaa.aaa/e/」と値「４」、キー「http://aaa.ccc/ff/」と値「５」、キー「http://aaa.aaa/」と値「６」の順で、トライ木を生成する場合について説明する。
【０１０３】
図９に示すように、まず、ノードが存在していない状態で、入力キー「http://aaa.aaa/e/」、入力値「１」を追加する場合について説明する。トライ木生成部２５０ａは、ルートノードを生成する（ステップＳ１０ａ）。実データ上において、トライ木生成部２５０ａは、ルートノードに対応するポインタ配列２０を生成し、ルートノードポインタとポインタ配列２０を接続する（ステップＳ１０ｂ）。
【０１０４】
トライ木生成部２５０ａは、入力キー「http://aaa.aaa/e/」を用意する（ステップＳ１１ａ）。実データ上において、トライ木生成部２５０ａは、テキスト表５０に入力キー「http://aaa.aaa/e/」を格納し、入力キーのポインタを、テキスト表５０の１行目１列目の「h」に接続する（ステップＳ１１ｂ）。
【０１０５】
トライ木生成部２５０ａは、入力キー「http://aaa.aaa/e/」の先頭文字「h」をキーとする子ノードが存在しないので、ルートノードを参照する。ここで、ルートノードにタグキーは存在しないので、トライ木生成部２５０ａは、ルートノードのタグキーとして、入力キー「http://aaa.aaa/e/」、値「１」を登録する（ステップＳ１２ａ）。
【０１０６】
実データ上において、トライ木生成部２５０ａは、ポインタ配列２０の「TAG」をテキスト表５０の１行目１列目の「h」に接続する。また、トライ木生成部２５０ａは、ポインタ配列２０の「Data」と値「１」を接続する（ステップＳ１２ｂ）。
【０１０７】
続いて、図１０に移行する。ステップＳ１２ａ、１２ｂにおいて作成したトライ木に、キー「http://aaa.aaa/e/c/」、値「２」を追加する場合について説明する。トライ木生成部２５０ａは、入力キー「http://aaa.aaa/e/c/」を用意する（ステップＳ１３ａ）。
【０１０８】
実データ上において、トライ木生成部２５０ａは、テキスト表５０に最後に登録されたキー「http://aaa.aaa/e/」との間を１つ空けて、キー「http://aaa.aaa/e/c/」を登録する。そして、トライ木生成部２５０ａは、テキスト表５０の２行目２列目の文字「h」に入力キーのポインタを接続する（ステップＳ１３ｂ）。
【０１０９】
トライ木生成部２５０ａは、入力キー「http://aaa.aaa/e/c/」の先頭文字「h」をキーとする子ノードが存在しないので、ルートノードを参照する。トライ木生成部２５０ａは、タグキー「http://aaa.aaa/e/」の優先度と、入力キー「http://aaa.aaa/e/c/」の優先度を比較する。すると、タグキーの１８文字目が空であり、入力キーの１８文字目がcであるため、トライ木生成部２５０ａは、入力キーの優先度が、タグキーの優先度よりも大きいと判定する。
【０１１０】
トライ木生成部２５０ａは、入力キーに対応するエッジノード「http://aaa.aaa/e/c/」を生成する。トライ木生成部２５０ａは、ノードｂを生成し、エッジノード「http://aaa.aaa/e/c/」を介して、ルートノードとノードｂを接続する。また、トライ木生成部２５０ａは、ノードｂにタグキー「空」と値「２」を登録する（ステップＳ１４ａ）。
【０１１１】
実データ上において、トライ木生成部２５０ａは、ノードｂに対応するポインタ配列２１を生成し、文字hに対応付けられたキー番号「０×６８」で、ポインタ配列２０とポインタ配列２１を接続する。トライ木生成部２５０ａは、ポインタ配列２１の「Edge」に文字列「ttp://aaa.aaa/e/c/」を接続し、「TAG」をテキスト表５０の３行目２列目の空に接続し、「Data」と値「２」を接続する（ステップＳ１４ｂ）。
【０１１２】
続いて、図１１に移行する。ステップＳ１４ａ、１４ｂにおいて作成したトライ木に、キー「http://aaa.aaa/d/」、値「３」を追加する場合について説明する。トライ木生成部２５０ａは、入力キーの先頭文字「h」をキーとする子ノードｂが存在するので、ノードｂに遷移する（ステップＳ１５ａ）。
【０１１３】
実データ上において、トライ木生成部２５０ａは、入力キーの先頭文字「h」に対応付けられたキー番号「０×６８」で、ポインタ配列２１に遷移し、現在のノードをポインタ配列２１に接続する（ステップＳ１５ｂ）。
【０１１４】
続いて、図１２に移行する。トライ木生成部２５０ａは、入力キー「http://aaa.aaa/d/」とエッジノード「http://aaa.aaa/e/c/」とを比較すると、前方一致しない。具体的には、文字列「http://aaa.aaa/e/c/」が、入力キーの先頭部分に含まれていない。トライ木生成部２５０ａは、入力キーのポインタは１文字目の「h」に設定し、親ノードに遷移する（ステップＳ１６ａ）。
【０１１５】
実データ上において、トライ木生成部２５０ａは、文字ｈと、「Edge」の文字列「ttp://aaa.aaa/e/c/」を合わせたエッジノードの文字列を特定する。そして、トライ木生成部２５０ａは、入力キー「http://aaa.aaa/d/」とエッジノード「http://aaa.aaa/e/c/」とを比較すると、前方一致しない。トライ木生成部２５０ａは、入力キーのポインタをテキスト表５０の３行目３列目の「h」に接続し、現在のノードをポインタ配列２０に接続する（ステップＳ１６ｂ）。
【０１１６】
続いて、図１３に移行する。トライ木生成部２５０ａは、ルートノードに接続されたタグキー「http://aaa.aaa/e/」の優先度と、入力キー「http://aaa.aaa/d/」の優先度を比較する。すると、タグキーの１６文字目がeであり、入力キーの１６文字目がdであるため、トライ木生成部２５０ａは、入力キーの優先度がタグキーの優先度よりも大きいと判定する。
【０１１７】
また、トライ木生成部２５０ａは、現在のノードがルートノードであるため、ルートノードのタグキー「http://aaa.aaa/e/」、値「１」と入力キー「http://aaa.aaa/d/」、入力値「３」を交換する（ステップＳ１７ａ）。
【０１１８】
実データ上において、トライ木生成部２５０ａは、ポインタ配列２０の「TAG」を、テキスト表５０の３行目３列目の「h」に接続し、「Data」に値「３」を接続する。トライ木生成部２５０ａは、入力キーのポインタを１行目１列目に接続する（ステップＳ１７ｂ）。
【０１１９】
続いて、図１４に移行する。トライ木生成部２５０ａは、入力キー「http://aaa.aaa/e/」の先頭文字「h」をキーにして、ノードｂに遷移する。トライ木生成部２５０ａは、入力キーのポインタを２文字目の「t」に設定する（ステップＳ１８ａ）。
【０１２０】
実データ上において、トライ木生成部２５０ａは、入力キーの先頭文字「h」に対応するキー番号「０×６８」でポインタ配列２１に遷移し、現在のポインタをポインタ配列２１に接続する。トライ木生成部２５０ａは、入力キーのポインタを１行目２列目の「t」に接続する（ステップＳ１８ｂ）。
【０１２１】
続いて、図１５に移行する。トライ木生成部２５０ａは、入力キー「http://aaa.aaa/e/」とエッジノード「http://aaa.aaa/e/c/」とを比較すると、前方一致しない。具体的に、文字列「http://aaa.aaa/e/c/」が、入力キーの先頭部分に含まれていない。
【０１２２】
トライ木生成部２５０ａは、入力キー「http://aaa.aaa/e/」とエッジノード「http://aaa.aaa/e/c/」とを比較し、各文字列の不一致部分「c/」を判定する。トライ木生成部２５０ａは、エッジノード「c/」を生成し、新しいノードｃを生成する。トライ木生成部２５０ａは、エッジノード「http://aaa.aaa/e/c/」とノードｃを接続し、ノードｃとエッジノード「c/」を接続し、エッジノード「c/」とノードｂを接続する（ステップＳ１９ａ）。
【０１２３】
実データ上において、トライ木生成部２５０ａは、ノードｃに対応するポインタ配列２２を生成し、文字「h」に対応するキー番号「０×６８」で、ポインタ配列２０とポインタ配列２２を接続する。トライ木生成部２５０ａは、ポインタ配列２２の「Edge」に文字列「ttp://aaa.aaa/e/」を接続する。
【０１２４】
トライ木生成部２５０ａは、文字「c」に対応するキー番号「０×６３」で、ポインタ配列２２とポインタ配列２１を接続する。トライ木生成部２５０ａは、ポインタ配列２２の「Edge」に文字列「/」を接続する（ステップＳ１９ｂ）。
【０１２５】
続いて、図１６に移行する。トライ木生成部２５０ａは、入力キーのポインタを１８文字目の「空」に設定する。トライ木生成部２５０ａは、入力キーの優先度がエッジノードの文字列の優先度よりも小さくなるので、入力キーの不一致部分「空」をタグキーとして、ノードｃに接続する。また、トライ木生成部２５０ａは、値「１」をノードｃに接続する（ステップＳ２０ａ）。
【０１２６】
実データ上において、トライ木生成部２５０ａは、入力キーのポインタを１行目１８列目の「空」に接続する。トライ木生成部２５０ａは、ポインタ配列２２の「TAG」をテキスト表５０の１行目１８列目の「空」に接続し、「Data」に値「１」を接続する（ステップＳ２０ｂ）。
【０１２７】
続いて、図１７に移行する。ステップＳ２０ａ、２０ｂにおいて作成したトライ木に、キー「http://aaa.aaa/e/」、値「４」を追加する場合について説明する。トライ木生成部２５０ａは、入力キーの先頭文字「h」をキーとする子ノードｃが存在するので、ノードｃに遷移する。
【０１２８】
トライ木生成部２５０ａは、入力キー「http://aaa.aaa/e/」とエッジノード「http://aaa.aaa/e/」とを比較すると、前方一致する。具体的には、文字列「http://aaa.aaa/e/」が、入力キーの先頭部分に含まれている。トライ木生成部２５０ａは、入力キーのポインタを、エッジノード「http://aaa.aaa/e/」の文字列分進め、１８文字目の「空」に設定する（ステップＳ２１ａ）。
【０１２９】
実データ上において、トライ木生成部２５０ａは、テキスト表５０に最後に登録されたキー「http://aaa.aaa/d/」との間を１つ空けて、キー「http://aaa.aaa/e/」を登録する。そして、トライ木生成部２５０ａは、テキスト表５０の４行目３列目の文字「h」に入力キーのポインタを接続する。
【０１３０】
トライ木生成部２５０ａは、文字hと、ポインタ配列２２の「Edge」の文字列「ttp://aaa.aaa/e/」を合わせたエッジノードの文字列を特定する。そして、トライ木生成部２５０ａは、入力キー「http://aaa.aaa/e/」とエッジノード「http://aaa.aaa/e/」とを比較すると、前方一致する。トライ木生成部２５０ａは、入力キーのポインタをテキスト表５０の５行目１列目の「空」に接続し、現在のノードをポインタ配列２２に接続する（ステップＳ２１ｂ）。
【０１３１】
続いて、図１８に移行する。トライ木生成部２５０ａは、ノードｃのタグキーと、入力キーのポインタ以降の文字を比較してタグキーと入力キーの優先度を判定すると、双方のキーは空であるため、優先度が等しくなる。トライ木生成部２５０ａは、入力キーに対応する入力値「４」をノードｃに登録する（ステップＳ２２ａ）。
【０１３２】
実データ上において、トライ木生成部２５０ａは、入力キーとタグキーの優先度が等しくなるので、ポインタ配列２２の「Data」に値「４」を登録する（ステップＳ２２ｂ）。
【０１３３】
続いて、図１９に移行する。ステップＳ２２ａ、２２ｂにおいて作成したトライ木に、キー「http://aaa.cc/ff/」、値「５」を追加する場合について説明する。トライ木生成部２５０ａは、入力キーの先頭文字「h」をキーとする子ノードｃが存在するので、ノードｃに遷移し、エッジノードの文字列「http://aaa.aaa/e/」と入力キーが前方一致するか否かを判定する。
【０１３４】
トライ木生成部２５０ａは、エッジノードの文字列「http://aaa.aaa/e/」と入力キーが前方一致しないので、ルートノードに遷移する（ステップＳ２３ａ）。
【０１３５】
実データ上において、トライ木生成部２５０ａは、テキスト表５０に最後に登録されたキー「http://aaa.aaa/e/」との間を１つ空けて、キー「http://aaa.cc/ff/」を登録する。そして、トライ木生成部２５０ａは、テキスト表５０の５行目２列目の文字「h」に入力キーのポインタを接続する。
【０１３６】
トライ木生成部２５０ａは、文字hと、ポインタ配列２２の「Edge」の文字列「ttp://aaa.aaa/e/」を合わせたエッジノードの文字列を特定する。そして、トライ木生成部２５０ａは、入力キー「http://aaa.cc/ff/」とエッジノード「http://aaa.aaa/e/」とを比較すると、前方一致しない。トライ木生成部２５０ａは、現在のノードをポインタ配列２０に接続する（ステップＳ２３ｂ）。
【０１３７】
続いて、図２０に移行する。トライ木生成部２５０ａは、ルートノードのタグキーの優先度と、入力キーの優先度を比較する。すると、タグキーの１２文字目が「a」であり、入力キーの１２文字目が「c」であるため、トライ木生成部２５０ａは、入力キーの優先度がタグキーの優先度よりも大きいと判定する。
【０１３８】
トライ木生成部２５０ａは、入力キー「http://aaa.cc/ff/」の先頭文字「h」の子ノードｃが存在するので、ノードｃに遷移する。また、入力キーのポインタを１文字進め、２文字目の「t」に接続する（ステップＳ２４ａ）。
【０１３９】
実データ上において、トライ木生成部２５０ａは、入力キーの優先度がタグキーの優先度よりも大きいと判定し、現在のノードをポインタ配列２２に接続する。また、トライ木生成部２５０ａは、入力キーのポインタをテキスト表の５行目３列目の「t」に接続する（ステップＳ２４ｂ）。
【０１４０】
続いて、図２１に移行する。トライ木生成部２５０ａは、入力キー「http://aaa.cc/ff/」とエッジノード「http://aaa.aaa/e/」が前方一致しないので、新しいノードｄを生成する。また、トライ木生成部２５０ａは、入力キー「http://aaa.cc/ff/」とエッジノード「http://aaa.aaa/e/」とを比較し、一致する文字列「http://aaa.」を有するエッジノードと、エッジノード「http://aaa.aaa/e/」から「http://aaa.」を除いた文字列「aaa/e/」を有するエッジノードを生成する。
【０１４１】
トライ木生成部２５０ａは、ルートノードとノードｄを、エッジノード「http://aaa.」を介して接続する。また、トライ木生成部２５０ａは、ノードｄとノードｃを、エッジノード「aaa/e/」を介して接続する（ステップＳ２５ａ）。
【０１４２】
実データ上において、トライ木生成部２５０ａは、ノードｄに対応するポインタ配列２３を生成する。トライ木生成部２５０ａは、文字hに対応するキー番号「０×６８」でポインタ配列２０とポインタ配列２３を接続する。トライ木生成部２５０ａは、文字aに対応するキー番号「０×６１」で、ポインタ配列２３とポインタ配列２２を接続する。
【０１４３】
また、トライ木生成部２５０ａは、ポインタ配列２３の「Edge」に文字列「ttp://aaa.」を接続し、ポインタ配列２２の「Edge」に文字列「aa/e/」を接続する（ステップＳ２５ｂ）。
【０１４４】
続いて、図２２に移行する。トライ木生成部２５０ａは、ノードｃのエッジキー「aaa/e/」の優先度と、入力キーから前方一致文字列「http://aaa.」を除いた文字列の優先度を比較すると、入力キーの優先度の方が大きくなる。
【０１４５】
トライ木生成部２５０ａは、第２の登録処理を実行すると判定し、入力キー「http://aaa.cc/ff/」から文字列「http://aaa.」を除いた文字列「cc/ff/」を有するエッジノードを生成する。トライ木生成部２５０ａは、ノードeを生成し、ノードｄとノードｅを、エッジノード「cc/ff/」を介して接続する。トライ木生成部２５０ａは、ノードeにタグキー「空」と値「５」を登録する（ステップＳ２６ａ）。
【０１４６】
実データ上において、トライ木生成部２５０ａは、ノードｅに対応するポインタ配列２４を生成する。トライ木生成部２５０ａは、文字ｃに対応するキー番号「０×６３」でポインタ配列２３とポインタ配列２４を接続し、ポインタ配列２４の「Edge」に文字列「c/ff/」を接続する。また、トライ木生成部２５０ａは、ポインタ配列２４の「TAG」をテキスト表５０の５行目１９列目の「空」に接続し、「Data」を値「５」に接続する（ステップＳ２６ｂ）。
【０１４７】
続いて、図２３に移行する。トライ木生成部２５０ａは、現在のノードを一つ目の新しいノードｄに設定する。ノードｄは、兄ノードが存在せず、ルートノードでもなく、親ノード（ルートルートノード）のタグキーが、エッジノード「http://aaa.」と前方一致する。この場合、トライ木生成部２５０ａは、親ノード（ルートノード）のタグキーから、エッジノードの文字列「http://aaa.」を取り除いた文字列「aaa/d/」を、ノードｄのタグキーとして登録し、親ノードの値「３」もノードｄの値として登録する（ステップＳ２７ａ）。
【０１４８】
実データ上において、トライ木生成部２５０ａは、ノードｄに対応するポインタ配列２３の「TAG」を、テキスト表５０の３行目１４列目の「a」に接続する。また、トライ木生成部２５０ａは、ポインタ配列２３の「Data」を値「３」に接続する（ステップＳ２７ｂ）。
【０１４９】
続いて、図２４に移行する。トライ木生成部２５０ａは、ノードｄの親ノードに遷移する。ノードｄの親ノードはルートノードであるため、トライ木生成部２５０ａは、ルートノードに接続されたタグキーを削除する（ステップＳ２８ａ）。
【０１５０】
実データ上において、トライ木生成部２５０ａは、現在のポインタをルートノードに対応するポインタ配列２０に接続する。トライ木生成部２５０ａは、ポインタ配列２０の「TAG」を「NULL」に設定する（ステップＳ２８ｂ）。
【０１５１】
続いて、図２５に移行する。ステップＳ２８ａ、２８ｂにおいて作成したトライ木に、キー「http://aaa.aaa/」、値「６」を追加する場合について説明する。トライ木生成部２５０ａは、入力キーの先頭文字「h」をキーとする子ノードｄが存在するので、ノードｄに遷移する。トライ木生成部２５０ａは、入力キーがエッジノードの文字列「http://aaa.」と前方一致するので、入力キーのポインタをエッジノードの文字列分進め、１２文字目の「a」に設定する。
【０１５２】
トライ木生成部２５０ａは、入力キーのポインタをキーにして、ノードｃに遷移するが、入力キーとエッジノードの文字列「aaa/e/」と前方一致しないので、ノードｄに戻る（ステップＳ２９ａ）。
【０１５３】
実データ上において、トライ木生成部２５０ａは、テキスト表５０に最後に登録されたキー「http://aaa.cc/ff/」との間を１つ空けて、キー「http://aaa.aaa/」を登録する。そして、トライ木生成部２５０ａは、テキスト表５０の６行目１列目の文字「h」に入力キーのポインタを接続する。
【０１５４】
トライ木生成部２５０ａは、現在のノードをノードｄに対応するポインタ配列２３に接続する。そして、トライ木生成部２５０ａは、入力キーのポインタを、テキスト表５０の６行目１２列目の「a」に接続する（ステップＳ２９ｂ）。
【０１５５】
続いて、図２６に移行する。トライ木生成部２５０ａは、ノードｄのタグキー「aaa/d/」と入力キーのポインタ以降の文字列「aaa/」とを比較すると、タグキーの優先度が入力キーの優先度よりも大きくなるので、ルートノードに遷移する。また、トライ木生成部２５０ａは、入力キーのポインタを１文字目の「h」に設定する（ステップＳ３０ａ）。
【０１５６】
実データ上において、トライ木生成部２５０ａは、ポインタ配列２３のタグキーの優先度が入力キーの優先度よりも大きいので、現在のポインタをポインタ配列２０に接続する。トライ木生成部２５０ａは、入力キーのポインタを６行目１列目の「h」に接続する（ステップＳ３０ｂ）。
【０１５７】
続いて、図２７に移行する。トライ木生成部２５０ａは、ルートノードにタグキーが存在しないので、入力キー「http://aaa.aaa/」をルートノードのタグキーとして登録する。トライ木生成部２５０ａは、ルートノードに値「６」を登録する（ステップＳ３１ａ）。
【０１５８】
実データ上において、トライ木生成部２５０ａは、ポインタ配列２０の「TAG」をテキスト表５０の６行目１列目の「h」に接続する。トライ木生成部２５０ａは、「Data」と値「６」を接続する（ステップＳ３１ｂ）。
【０１５９】
上述したように、トライ木生成部２５０ａが図９〜図２７に示したように、入力キーを追加する場所に応じて、登録処理を切り替えることで、トライ木２４０ｂ内で再構築する部分を最小限に抑え、再構築処理にかかる時間を削減する。
【０１６０】
図３の説明に戻ると、トライ木探索部２５０ｂは、トライ木２４０ｂに登録された値の集計値を抽出する処理、所定のキーに対応する値をトライ木２４０ｂから検出する処理を実行する処理部である。
【０１６１】
まず、トライ木探索部２５０ｂが、トライ木２４０ｂに登録された値の集計値を抽出する処理について説明する。トライ木探索部２５０ｂは、トライ木２４０ｂの各ノードを順に辿り、ノードに登録されたタグキーおよび値を対応付けて順次出力することで、集計値を抽出する。ノードに複数の値が登録されている場合には、トライ木探索部２５０ｂは、各値を合計しても良いし、別々に出力しても良い。本実施例にかかるトライ木探索部２５０ｂは、一例として、各値を合計して出力する。
【０１６２】
図２８〜図３２は、集計値を抽出する処理を説明するための図である。図２８に示すトライ木は、図２７に示したトライ木に対応する。トライ木探索部２５０ｂは、初期状態をルートノードに設定する。ルートノードは、値「６」を接続するので、トライ木探索部２５０ｂは、ルートノードに接続されたタグキー「http://aaa.aaa/」と値「６」を出力する（ステップＳ４０ａ）。
【０１６３】
実データ上において、トライ木探索部２５０ｂは、現在のノードをポインタ配列２０に接続する。ポインタ配列２０の「Data」に値「６」が接続されているので、トライ木探索部２５０ｂは、「TAG」に接続された文字列「http://aaa.aaa/」と、値「６」を出力する（ステップＳ４０ｂ）。
【０１６４】
続いて、図２９に移行する。トライ木探索部２５０ｂは、エッジノード「http://aaa.」を介して、ルートノードからノードｄに遷移する。ノードｄは、値「３」を接続するので、トライ木探索部２５０ｂは、エッジキー「http://aaa.」とノードｄに接続されたタグキー「aaa/d/」を合わせた文字列「http://aaa.aaa/d/」と値「３」を出力する（ステップＳ４１ａ）。
【０１６５】
実データ上において、トライ木探索部２５０ｂは、現在のノードをポインタ配列２３に接続する。ポインタ配列２３の「Data」に値「３」が接続されているので、トライ木探索部２５０ｂは、「TAG」に接続された文字列「http://aaa.aaa/d/」と値「３」を出力する（ステップＳ４１ｂ）。
【０１６６】
続いて、図３０に移行する。トライ木探索部２５０ｂは、ノードｄの長男ノードとなるノードｃに遷移する。ノードｃは、値「１，４」を接続するので、トライ木探索部２５０ｂは、エッジキー「http://aaa.」、「aaa/e/」、ノードｃのタグキー「空」を合わせた文字列「http://aaa.aaa/e/」、値「１，４」の合計値「５」を出力する（ステップＳ４２ａ）。
【０１６７】
実データ上において、トライ木探索部２５０ｂは、現在のノードをポインタ配列２２に接続する。ポインタ配列２２の「Data」に値「１，４」が接続されているので、トライ木探索部２５０ｂは、「TAG」に接続された文字列「http://aaa.aaa/e/」、値「１，４」の合計値「５」を出力する（ステップＳ４２ｂ）。
【０１６８】
続いて、図３１に移行する。トライ木探索部２５０ｂは、ノードｂに遷移する。ノードｂは、値「２」を接続するので、トライ木探索部２５０ｂは、エッジキー「http://aaa.」、「aaa/e/」、「c/」、ノードｂのタグキー「空」を合わせた文字列「http://aaa.aaa/e/c/」、値「２」を出力する（ステップＳ４３ａ）。
【０１６９】
実データ上において、トライ木探索部２５０ｂは、現在のノードをポインタ配列２１に接続する。ポインタ配列２１の「Data」に値「２」が接続されているので、トライ木探索部２５０ｂは、「TAG」に接続された文字列「http://aaa.aaa/e/c/」、値「２」を出力する（ステップＳ４３ｂ）。
【０１７０】
続いて、図３２に移行する。トライ木探索部２５０ｂは、ノードｅに遷移する。ノードｅは、値「５」を接続するので、トライ木探索部２５０ｂは、エッジキー「http://aaa.」、「cc/ff/」、ノードｅのタグキー「空」を合わせた文字列「http://aaa.cc/ff/」、値「５」を出力する（ステップＳ４４ａ）。
【０１７１】
実データ上において、トライ木探索部２５０ｂは、現在のノードをポインタ配列２４に接続する。ポインタ配列２４の「Data」に値「５」が接続されているので、トライ木探索部２５０ｂは、「TAG」に接続された文字列「http://aaa.cc/ff/」、値「５」を出力する（ステップＳ４４ｂ）。
【０１７２】
次に、トライ木探索部２５０ｂが、指定された入力キーに対応する値をトライ木２４０ｂから検索する処理について説明する。トライ木探索部２５０ｂは、指定された入力キーの文字を先頭から読み出して、トライ木の各ノードを辿り、入力キーに対応したノードを判定し、判定したノードの値を検索結果として出力する。
【０１７３】
図３３〜図３５は、検索処理を説明するための図である。図３３〜図３５に示すトライ木は、図２７に示したトライ木に対応する。また、図３３〜図３５における説明では、入力キー「http://aaa.aaa/d/」が指定された場合の検索処理について説明する。
【０１７４】
図３３において、トライ木探索部２５０ｂは、入力キーの先頭文字「h」でノードｄに遷移し、エッジキー「http://aaa.」の文字数に合わせて、入力キーのポインタを１２文字目の「a」に設定する（ステップＳ５０ａ）。
【０１７５】
実データ上において、トライ木探索部２５０ｂは、現在のノードをポインタ配列２３に接続する。また、トライ木探索部２５０ｂは、入力キーのポインタを「a」に設定する（ステップＳ５０ｂ）。
【０１７６】
続いて、図３４に移行する。トライ木探索部２５０ｂは、入力キーがエッジキー「http://aaa.」に前方一致するので、現在のポインタの文字「a」で、ノードｃに遷移する。しかし、入力キーがエッジキー「aaa/e/」と前方一致しないので、ノードｄに戻る（ステップＳ５１ａ）。
【０１７７】
実データ上において、トライ木探索部２５０ｂは、ポインタ配列２２に現在のノードを接続する。ポインタ配列の「Edge」に接続された「aa/e/」と、入力キーの「aaa/d/」が前方一致しないので、トライ木探索部２５０ｂは、現在のノードをポインタ配列２３に接続する（ステップＳ５１ｂ）。
【０１７８】
トライ木探索部２５０ｂは、ノードｄに接続されたタグキーと、入力キーのポインタ以降の文字列を比較すると各キーが一致するので、入力キー「http://aaa.aaa/d/」とノードｄの値「３」を出力する（ステップＳ５２ａ）。
【０１７９】
実データ上において、トライ木探索部２５０ｂは、ポインタ配列２３のタグキーと入力キーを比較すると各キーが一致するので、入力キー「http://aaa.aaa/d/」とポインタ配列２３の「Data」に接続された値「３」を出力する（ステップＳ５２ｂ）。
【０１８０】
次に、本実施例２にかかる検索装置２００の処理手順について説明する。まず、トライ木生成部２５０ａが、登録データ管理テーブル２４０ａに基づいて、トライ木２４０ｂを生成するトライ木生成処理について説明する。図３６〜図４０は、トライ木生成処理の処理手順を示すフローチャートである。
【０１８１】
図３６に示すように、トライ木生成部２５０ａは、現在のノードをルートノードに設定し（ステップＳ１０１）、入力キーが空であるか否かを判定する（ステップＳ１０２）。トライ木生成部２５０ａは、入力キーが空の場合に（ステップＳ１０３，Ｙｅｓ）、図３７のステップＳ１１１に移行する。
【０１８２】
一方、トライ木生成部２５０ａは、入力キーが空でない場合に（ステップＳ１０３，Ｎｏ）、入力キーの先頭文字のキーで子ノードを参照し、子ノードが存在するか否かを判定する（ステップＳ１０４）。
【０１８３】
トライ木生成部２５０ａは、子ノードが存在しない場合に（ステップＳ１０５，Ｎｏ）、図３７のステップＳ１１１に移行する。
【０１８４】
一方、トライ木生成部２５０ａは、子ノードが存在する場合に（ステップＳ１０５，Ｙｅｓ）、入力キーの先頭一文字を読み取り、入力キーのポインタを一文字進め、読み出した文字をキーとして子ノードへ遷移する（ステップＳ１０６）。
【０１８５】
トライ木生成部２５０ａは、入力キーがエッジキー（エッジノードの文字列）に前方一致するか否かを判定する（ステップＳ１０７）。トライ木生成部２５０ａは、入力キーがエッジキーに前方一致する場合に（ステップＳ１０８，Ｙｅｓ）、入力キーのポインタをエッジキー長分進め（ステップＳ１０９）、ステップＳ１０２に移行する。
【０１８６】
一方、トライ木生成部２５０ａは、入力キーがエッジキーに前方一致しない場合に（ステップＳ１０８，Ｎｏ）、入力キーのポインタを一文字戻し、親ノードへ遷移し（ステップＳ１１０）、図３７のステップＳ１１１に移行する。
【０１８７】
図３７に移行する。トライ木生成部２５０ａは、ノードの情報を参照し（ステップＳ１１１）、タグキーが存在するか否かを判定する（ステップＳ１１２）。タグキーが存在しない場合には（ステップＳ１１３，Ｎｏ）、タグキーに入力キーを登録し（ステップＳ１１４）、現在のノードに入力値を追加する（ステップＳ１１５）。
【０１８８】
一方、トライ木生成部２５０ａは、タグキーが存在する場合に（ステップＳ１１３，Ｙｅｓ）、タグキーの優先度と入力キーの優先度が等しいか否かを判定する（ステップＳ１１６）。トライ木生成部２５０ａは、タグキーの優先度と入力キーの優先度が等しい場合に（ステップＳ１１７，Ｙｅｓ）、ステップＳ１１５に移行する。
【０１８９】
一方、トライ木生成部２５０ａは、タグキーの優先度と入力キーの優先度が異なる場合に（ステップＳ１１７，Ｎｏ）、タグキーの優先度が入力キーの優先度よりも大きいか否かを判定する（ステップＳ１１８）。
【０１９０】
トライ木生成部２５０ａは、タグキーの優先度が入力キーの優先度よりも小さい場合に（ステップＳ１１９，Ｎｏ）、図３８のステップＳ１２３に移行する。一方、トライ木生成部２５０ａは、タグキーの優先度が入力キーの優先度よりも大きい場合に（ステップＳ１１９，Ｙｅｓ）、兄ノードが存在する、または、現在のノードがルートノードであるか否かを判定する（ステップＳ１２０）。
【０１９１】
トライ木生成部２５０ａは、兄ノードが存在する、または、現在のノードがルートノードである場合（条件を満たす場合）に（ステップＳ１２１，Ｙｅｓ）、図３８のステップＳ１３３に移行する。
【０１９２】
一方、トライ木生成部２５０ａは、兄ノードが存在せず、かつ、現在のノードがルートノードでない場合（条件を満たさない場合）に（ステップＳ１２１，Ｎｏ）、入力キーのポインタをエッジキー長+１文字分戻し、親ノードへ遷移し（ステップＳ１２２）、ステップＳ１１１に遷移する。
【０１９３】
続いて、図３８に移行する。トライ木生成部２５０ａは、入力キーの先頭文字のキーで子ノードを参照し、子ノードが存在するか否かを判定する（ステップＳ１２３）。トライ木生成部２５０ａは、子ノードが存在しない場合に（ステップＳ１２４，Ｎｏ）、新しいノードを生成する（ステップＳ１２５）。
【０１９４】
トライ木生成部２５０ａは、入力キーの先頭一文字を読み取り、入力キーのポインタを一文字進め、読み出した文字をキーとして、現在のノードから新しいノードへ接続し（ステップＳ１２６）、入力キーをエッジキーとして、空をタグキーとして、新しいノードに登録する（ステップＳ１２７）。トライ木生成部２５０ａは、入力値を新しいノードに登録する（ステップＳ１２８）。
【０１９５】
ところで、トライ木生成部２５０ａは、子ノードが存在する場合に（ステップＳ１２４，Ｙｅｓ）、入力キーの先頭一文字を読み取り、入力キーのポインタを一文字進め、読み出した文字をキーとして、子ノードへ遷移する（ステップＳ１２９）。
【０１９６】
トライ木生成部２５０ａは、入力キーがエッジキーに前方一致するか否かを判定する（ステップＳ１３０）。トライ木生成部２５０ａは、入力キーがエッジキーに前方一致しない場合に（ステップＳ１３１，Ｎｏ）、図３９のステップＳ１３４に移行する。
【０１９７】
一方、トライ木生成部２５０ａは、入力キーがエッジキーに前方一致する場合に（ステップＳ１３１，Ｙｅｓ）、入力キーのポインタをエッジキー長分進める（ステップＳ１３２）。トライ木生成部２５０ａは、現在のノードのタグキー、値と入力キー、入力値をそれぞれ交換し（ステップＳ１３３）、ステップＳ１２３に移行する。
【０１９８】
続いて、図３９に移行する。トライ木生成部２５０ａは、新しいノードを生成し（ステップＳ１３４）、エッジキーの不一致文字部分の先頭一文字をキーとして新しいノードから現在のノードに接続する（ステップＳ１３５）。
【０１９９】
トライ木生成部２５０ａは、現在のノードのエッジキーをエッジキーの不一致部分の先頭一文字を除いた部分に変更し（ステップＳ１３６）、入力キーのポインタの一文字前の文字をキーとして、親ノードから新しいノードへ接続する（ステップＳ１３７）。
【０２００】
トライ木生成部２５０ａは、入力キーとエッジキーの前方一致文字列をエッジキーとして新しいノードに登録し（ステップＳ１３８）、入力キーの優先度がエッジキーの優先度未満であるか否かを判定する（ステップＳ１３９）。
【０２０１】
トライ木生成部２５０ａは、入力キーの優先度がエッジキーの優先度未満の場合に（ステップＳ１４０，Ｙｅｓ）、入力キーの不一致文字部分をタグキーとして、新しいノードに登録し（ステップＳ１４１）、入力値を新しいノードに登録する（ステップＳ１４２）。
【０２０２】
一方、トライ木生成部２５０ａは、入力キーの優先度がエッジキーの優先度未満でない場合に（ステップＳ１４０，Ｎｏ）、二つ目の新しいノードを生成する（ステップＳ１４３）。トライ木生成部２５０ａは、入力キーの不一致文字部分の先頭一文字をキーとして、一つ目の新しいノードから二つ目の新しいノードへ接続する（ステップＳ１４４）。
【０２０３】
トライ木生成部２５０ａは、入力キーの不一致部分の先頭一文字を除いた部分をエッジキーとして二つ目の新しいノードに登録する（ステップＳ１４５）。トライ木生成部２５０ａは、空をタグキーとして、二つ目の新しいノードに登録し（ステップＳ１４６）、入力値を二つ目の新しいノードに登録し（ステップＳ１４７）、図４０のステップＳ１４８に移行する。
【０２０４】
図４０に移行する。トライ木生成部２５０ａは、現在のノードを一つ目の新しいノードに設定し（ステップＳ１４８）、兄ノードが存在する、または、現在のノードがルートであるか否かを判定する（ステップＳ１４９）。
【０２０５】
トライ木生成部２５０ａは、兄ノードが存在する、または、現在のノードがルートノードの場合（条件を満たす場合）に（ステップＳ１５０，Ｙｅｓ）、現在のノードのタグキーを削除する（ステップＳ１５１）。
【０２０６】
一方、トライ木生成部２５０ａは、兄ノードが存在しない、かつ、現在のノードがルートノードでない場合（条件を満たさない場合）に（ステップＳ１５０，Ｎｏ）、親ノードのタグキーがエッジキーの前方に一致するか否かを判定する（ステップＳ１５２）。
【０２０７】
トライ木生成部２５０ａは、親ノードのタグキーがエッジキーに前方一致しない場合に（ステップＳ１５３，Ｎｏ）、ステップＳ１５１に移行する。一方、トライ木生成部２５０ａは、親ノードのタグキーがエッジキーに前方一致する場合に（ステップＳ１５３，Ｙｅｓ）、親ノードのタグキーの不一致文字部分を現在のノードのタグキーとして登録する（ステップＳ１５４）。
【０２０８】
トライ木生成部２５０ａは、親ノードの値を現在のノードの値として登録し、親ノードへ遷移し（ステップＳ１５５）、ステップＳ１４９に移行する。
【０２０９】
次に、トライ木探索部２５０ｂが実行する集計処理について説明する。図４１は、集計処理の処理手順を示すフローチャートである。トライ木探索部２５０ｂは、現在のノードをルートノードに設定し（ステップＳ２０１）、子ノードが存在するか否かを判定する（ステップＳ２０２）。
【０２１０】
トライ木探索部２５０ｂは、子ノードが存在する場合に（ステップＳ２０３，Ｙｅｓ）、長男ノードへ遷移し（ステップＳ２０４）、タグキーが存在するか以下かを判定する（ステップＳ２０５）。
【０２１１】
トライ木探索部２５０ｂは、タグキーが存在しない場合に（ステップＳ２０６，Ｎｏ）、ステップＳ２０２に移行する。トライ木探索部２５０ｂは、タグキーが存在する場合に（ステップＳ２０６，Ｙｅｓ）、現在のノードの各種データを加工（集計等）し出力し（ステップＳ２０７）、ステップＳ２０２に移行する。
【０２１２】
ところで、トライ木探索部２５０ｂは、子ノードが存在しない場合に（ステップＳ２０３，Ｎｏ）、弟ノードが存在するか否かを判定する（ステップＳ２０８）。トライ木探索部２５０ｂは、弟ノードが存在する場合に（ステップＳ２１０，Ｙｅｓ）、次の弟ノードへ遷移し（ステップＳ２０９）、ステップＳ２０５に遷移する。
【０２１３】
一方、トライ木探索部２５０ｂは、弟ノードが存在しない場合に（ステップＳ２１０，Ｎｏ）、親ノードへ遷移し（ステップＳ２１１）、現在のノードがルートノードであるか否かを判定する（ステップＳ２１２）。
【０２１４】
トライ木探索部２５０ｂは、現在のノードがルートノードではない場合に（ステップＳ２１３，Ｎｏ）、ステップＳ２０８に移行する。一方、トライ木探索部２５０ｂは、現在のノードがルートノードの場合に（ステップＳ２１３，Ｙｅｓ）、処理を終了する。
【０２１５】
次に、トライ木探索部２５０ｂが実行する検索処理について説明する。図４２、図４３は、検索処理の処理手順を示すフローチャートである。図４２に示すように、トライ木探索部２５０ｂは、現在のノードをルートノードに設定し（ステップＳ３０１）、入力キーが空であるか否かを判定する（ステップＳ３０２）。トライ木探索部２５０ｂは、入力キーが空の場合に（ステップＳ３０３，Ｙｅｓ）、図４３のステップＳ３１１に移行する。
【０２１６】
一方、トライ木探索部２５０ｂは、入力キーが空でない場合に（ステップＳ３０３，Ｎｏ）、入力キーの先頭文字のキーで子ノードを参照し、子ノードが存在するか否かを判定する（ステップＳ３０４）。
【０２１７】
トライ木探索部２５０ｂは、子ノードが存在しない場合に（ステップＳ３０５，Ｎｏ）、図４３のステップＳ３１１に移行する。
【０２１８】
一方、トライ木探索部２５０ｂは、子ノードが存在する場合に（ステップＳ３０５，Ｙｅｓ）、入力キーの先頭一文字を読み取り、入力キーのポインタを一文字進め、読み出した文字をキーとして子ノードへ遷移する（ステップＳ３０６）。
【０２１９】
トライ木探索部２５０ｂは、入力キーがエッジキー（エッジノードの文字列）に前方一致するか否かを判定する（ステップＳ３０７）。トライ木探索部２５０ｂは、入力キーがエッジキーに前方一致する場合に（ステップＳ３０８，Ｙｅｓ）、入力キーのポインタをエッジキー長分進め（ステップＳ３０９）、ステップＳ３０２に移行する。
【０２２０】
一方、トライ木探索部２５０ｂは、入力キーがエッジキーに前方一致しない場合に（ステップＳ３０８，Ｎｏ）、入力キーのポインタを一文字戻し、親ノードへ遷移し（ステップＳ３１０）、図４３のステップＳ３１１に移行する。
【０２２１】
続いて、図４３に移行する。トライ木探索部２５０ｂは、ノードの情報を参照し（ステップＳ３１１）、タグキーが存在するか否かを判定する（ステップＳ３１２）。タグキーが存在しない場合には（ステップＳ３１３，Ｎｏ）、一致データなしを出力する（ステップＳ３１４）。
【０２２２】
一方、トライ木探索部２５０ｂは、タグキーが存在する場合に（ステップＳ３１３，Ｙｅｓ）、タグキーの優先度と入力キーの優先度が等しいか否かを判定する（ステップＳ３１５）。トライ木探索部２５０ｂは、タグキーの優先度と入力キーの優先度が等しい場合に（ステップＳ３１６，Ｙｅｓ）、現在のノードのデータを出力する（ステップＳ３１７）。
【０２２３】
一方、トライ木探索部２５０ｂは、タグキーの優先度と入力キーの優先度が異なる場合に（ステップＳ３１６，Ｎｏ）、タグキーの優先度が入力キーの優先度よりも大きいか否かを判定する（ステップＳ３１８）。
【０２２４】
トライ木探索部２５０ｂは、タグキーの優先度が入力キーの優先度よりも小さい場合に（ステップＳ３１９，Ｎｏ）、ステップＳ３１４に移行する。一方、トライ木探索部２５０ｂは、タグキーの優先度が入力キーの優先度よりも大きい場合に（ステップＳ３１９，Ｙｅｓ）、兄ノードが存在する、または、現在のノードがルートノードであるか否かを判定する（ステップＳ３２０）。
【０２２５】
トライ木探索部２５０ｂは、兄ノードが存在する、または、現在のノードがルートノードである場合（条件を満たす場合）に（ステップＳ３２１，Ｙｅｓ）、ステップＳ３１４に移行する。
【０２２６】
一方、トライ木探索部２５０ｂは、兄ノードが存在せず、かつ、現在のノードがルートノードでない場合（条件を満たさない場合）に（ステップＳ３２１，Ｎｏ）、入力キーのポインタをエッジキー長+１文字分戻し、親ノードへ遷移し（ステップＳ３２２）、ステップＳ３１１に遷移する。
【０２２７】
次に、トライ木探索部２５０ａが実行する削除処理について説明する。図４４〜図４７は、削除処理の処理手順を示すフローチャートである。図４４に示すように、トライ木探索部２５０ｂは、現在のノードをルートノードに設定し（ステップＳ４０１）、入力キーが空であるか否かを判定する（ステップＳ４０２）。トライ木探索部２５０ｂは、入力キーが空の場合に（ステップＳ４０３，Ｙｅｓ）、図４５のステップＳ４１１に移行する。
【０２２８】
一方、トライ木探索部２５０ｂは、入力キーが空でない場合に（ステップＳ４０３，Ｎｏ）、入力キーの先頭文字のキーで子ノードを参照し、子ノードが存在するか否かを判定する（ステップＳ４０４）。
【０２２９】
トライ木探索部２５０ｂは、子ノードが存在しない場合に（ステップＳ４０５，Ｎｏ）、図４５のステップＳ４１１に移行する。
【０２３０】
ところで、トライ木探索部２５０ｂは、子ノードが存在する場合に（ステップＳ４０５，Ｙｅｓ）、入力キーの先頭一文字を読み取り、入力キーのポインタを１文字進め、読み出した文字をキーとして子ノードに遷移する（ステップＳ４０６）。
【０２３１】
トライ木探索部２５０ｂは、入力キーが前方一致するか否かを判定する（ステップＳ４０７）。トライ木探索部２５０ｂは、前方一致しない場合に（ステップＳ４０８，Ｎｏ）、入力キーのポインタを一文字戻し、親ノードへ遷移し、図４５のステップＳ４１１に移行する。
【０２３２】
トライ木探索部２５０ｂは、前方一致する場合に（ステップＳ４０８，Ｙｅｓ）、入力キーのポインタをエッジキー長分進め（ステップＳ４０９）、ステップＳ４０２に移行する。
【０２３３】
トライ木探索部２５０ｂは、ノードの情報を参照し（ステップＳ４１１）、タグキーが存在するか否かを判定する（ステップＳ４１２）。タグキーが存在しない場合には（ステップＳ４１３，Ｎｏ）、一致データなしを出力する（ステップＳ４１４）。
【０２３４】
一方、トライ木探索部２５０ｂは、タグキーが存在する場合に（ステップＳ４１３，Ｙｅｓ）、タグキーの優先度と入力キーの優先度が等しいか否かを判定する（ステップＳ４１５）。トライ木探索部２５０ｂは、タグキーの優先度と入力キーの優先度が等しい場合に（ステップＳ４１６，Ｙｅｓ）、図４６のステップＳ４２２に移行する。
【０２３５】
トライ木探索部２５０ｂは、タグキーの優先度と入力キーの優先度が異なる場合に（ステップＳ４１６，Ｎｏ）、タグキーの優先度が入力キーの優先度よりも大きいか否かを判定する（ステップＳ４１７）。
【０２３６】
トライ木探索部２５０ｂは、タグキーの優先度が入力キーの優先度よりも小さい場合に（ステップＳ４１８，Ｎｏ）、ステップＳ４１４に移行する。一方、トライ木探索部２５０ｂは、タグキーの優先度が入力キーの優先度よりも大きい場合に（ステップＳ４１８，Ｙｅｓ）、兄ノードが存在する、または、現在のノードがルートノードであるか否かを判定する（ステップＳ４１９）。
【０２３７】
トライ木探索部２５０ｂは、兄ノードが存在する、または、現在のノードがルートノードである場合（条件を満たす場合）に（ステップＳ４２０，Ｙｅｓ）、ステップＳ４１４に移行する。
【０２３８】
一方、トライ木探索部２５０ｂは、兄ノードが存在せず、かつ、現在のノードがルートノードでない場合（条件を満たさない場合）に（ステップＳ４２０，Ｎｏ）、入力キーのポインタをエッジキー長+１文字分戻し、親ノードへ遷移し（ステップＳ４２１）、ステップＳ４１１に遷移する。
【０２３９】
続いて、図４６に移行する。トライ木探索部２５０ｂは、削除対象データが存在するか否かを判定し（ステップＳ４２２）、削除対象データが存在しない場合には（ステップＳ４２３，Ｎｏ）、削除対象データなしを出力する（ステップＳ４２４）。
【０２４０】
一方、トライ木探索部２５０ｂは、削除対象データが存在する場合に（ステップＳ４２３，Ｙｅｓ）、削除対象データを削除し（ステップＳ４２５）、他のデータが存在するか否かを判定する（ステップＳ４２６）。
【０２４１】
トライ木探索部２５０ｂは、他のデータが存在する場合に（ステップＳ４２７，Ｙｅｓ）、処理を終了する。一方、トライ木探索部２５０ｂは、他のデータが存在しない場合に（ステップＳ４２７，Ｎｏ）、図４７のステップＳ４２８に移行する。
【０２４２】
続いて、図４７に移行する。トライ木探索部２５０ｂは、子ノードが存在するか否かを判定する（ステップＳ４２８）。トライ木探索部２５０ｂは、子ノードが存在しない場合に（ステップＳ４２９，Ｎｏ）、親ノードの現在のノードへのエッジを削除し、現在のノードを削除する（ステップＳ４３０）。
【０２４３】
トライ木探索部２５０ｂは、子ノードが存在する場合に（ステップＳ４２９，Ｙｅｓ）、子ノードが一つであるか否かを判定する（ステップＳ４３１）。トライ木探索部２５０ｂは、子ノードが一つの場合に（ステップＳ４３２，Ｙｅｓ）、現在のノードのエッジキーを子ノードのエッジキーの前に挿入する（ステップＳ４３６）。トライ木探索部２５０ｂは、親ノードの現在のノードへのエッジを子ノードに変更し、現在のノードを削除する（ステップＳ４３７）。
【０２４４】
一方、トライ木探索部２５０ｂは、子ノードが一つでない場合に（ステップＳ４３２，Ｎｏ）、現在のノードのデータを長男ノードのデータに設定する（ステップＳ４３３）。トライ木探索部２５０ｂは、現在のノードのデータを長男ノードへの接続キーと長男ノードのエッジキーと長男ノードのタグキーを連結した文字列とし（ステップＳ４３４）、長男ノードへ遷移し（ステップＳ４３５）、ステップＳ４２８に遷移する。
【０２４５】
上述してきたように、本実施例２にかかる検索装置２００は、トライ木生成部２５０ａが、トライ木２４０ｂに新規の入力キーを追加する場合に、入力キーを追加する場所に応じて、登録処理の内容を切り替えるので、トライ木２４０ｂ内で再構築する部分を最小限に抑え、再構築処理にかかる時間を削減することが出来る。
【０２４６】
また、本実施例２にかかるトライ木生成部２５０ａは、トライ木２４０ｂを構築する場合に、各キーの共通部分をエッジノードに集約するので、先頭文字列が一致しているキーが多い場合であっても、トライ木が深くなることを防止し、メモリ使用量を削減することが出来る。
【０２４７】
ところで、図６に示したトライ木２４０ｂの実データのデータ構造は、１ノードあたりASCIIコードの１文字にあたる８ビットの場合を示しているが、これに限定されるものではない。例えば、ASCIIコード１文字を4ビット単位の２つに分割して、１ノードあたり４ビットとしてもよい。その場合、ポインタ配列のもつキー番号は８ビットの場合に「０ｘ００〜０ｘＦＦ」の２５６個であったのに対し、４ビットの場合には「０ｘ０〜０ｘＦ」の１６個に減らすことができ、メモリ使用量を削減することが可能である。図４８は、トライ木２４０ｂのその他のデータ構造の一例を示す図である。
【０２４８】
例えば、「beige」の場合、１ノードあたり８ビットの場合には先頭キー番号「０ｘ６２」で、ポインタ配列に接続するが、１ノードあたり４ビットの場合には先頭キー番号として「０ｘ６２」の前半部分の「０ｘ６」で、図４８のポインタ配列XXに接続される。また、「beige」に加え「black」を続けて追加する場合、１ノードあたり８ビットの場合には２番目のキー番号「０ｘ６ｃ」でポインタ配列に接続するが、１ノードあたり４ビットの場合には２番目のキー番号として「０ｘ６２」の後半部分の「０ｘ２」で、図４８のポインタ配列YYに接続される。なお、ポインタ配列YYはポインタ配列XXへの接続のキー番号「０ｘ６」とポインタ配列YYへの接続のキー番号「０ｘ２」とをあわせた「０ｘ６２」、すなわち「b」を表すノードである。またさらに「blue」を続けて追加する場合、１ノードあたり８ビットの場合には３番目の文字「u]のキー番号「０ｘ７５」で次のポインタ配列に接続するが、１ノードあたり４ビットの場合には３番目のキー番号として２文字目「l」のキー番号「０ｘ６ｃ」の前半部分の「０ｘ６」で次のポインタ配列に接続する。
【０２４９】
また、日本語コードのようにマルチバイト文字に関しても、複数バイトを１文字として扱い、１ノードあたり１６ビットとするのではなく、１文字を複数に分割して、１ノードあたり８ビットとしたり、４ビットとしてもよい。
【０２５０】
なお、現在のコンピュータにおいては直接ビット位置を指定してビット列を取り出すことはできないが、ビット位置から所望のビット列を含むバイト位置を特定し、１バイトを取り出した後、ビット処理演算を用いて所望のビット列を取り出すことで処理できる。タグキーを表す文字列を取り出すときも同様に行うことができる。
【０２５１】
また別に、リーフノードに該当するポインタ配列はすべてのキー番号領域がNULLであるので、ポインタ配列の一部（キー番号領域）を省くなどして簡略化しても良い。なお、この場合には、各ポインタ配列に、自身のポインタ配列がリーフノードであるか否かを示すフラグを設定する。
【０２５２】
ところで、本実施例において説明した各処理のうち、自動的におこなわれるものとして説明した処理の全部または一部を手動的におこなうこともでき、あるいは、手動的におこなわれるものとして説明した処理の全部または一部を公知の方法で自動的におこなうこともできる。この他、上記文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
【０２５３】
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。さらに、各装置にて行なわれる各処理機能は、その全部または任意の一部が、ＣＰＵおよび当該ＣＰＵにて解析実行されるプログラムにて実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。
【０２５４】
図４９は、実施例２に示した検索装置２００（あるいは、実施例１にかかるトライ木文字列登録装置１００）に対応するコンピュータのハードウェア構成を示す図である。図４９に示すように、このコンピュータ（検索装置）１０は、入力装置１１、モニタ１２、ＲＡＭ（Random  Access  Memory）１３、ＲＯＭ（Read  Only  Memory）１４、ネットワークを介して他の装置とデータ通信を実行する通信制御装置１５、媒体読取装置１６、ＣＰＵ（Central  Processing  Unit）１７、ＨＤＤ（Hard  Disk  Drive）１８をバス１９で接続している。
【０２５５】
そして、ＨＤＤ１８には、上述した検索装置２００の機能と同様の機能を発揮するトライ木生成プログラム１８ｂ、トライ木探索プログラム１８ｃが記憶されている。ＣＰＵ１７が、トライ木生成プログラム１８ｂ、トライ木探索プログラム１８ｃを読み出して実行することにより、トライ木生成プロセス１７ａ、トライ木探索プロセス１７ｂが起動される。
【０２５６】
ここで、トライ木生成プロセス１７ａは、図３に示したトライ木生成部２５０ａに対応する。また、トライ木探索プロセス１７ｂは、図３に示したトライ木探索部２５０ｂに対応する。
【０２５７】
なお、ＨＤＤ１８は、図３で示した記憶部２４０に記憶されたデータに対応する各種データ１８ａを記憶している。ＣＰＵ１７は、ＨＤＤ１８に記憶された各種データ１８ａをＲＡＭ１３に読み出し、各種データ１３ａを利用して、トライ木の構築等を実行する。
【０２５８】
以上の各実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０２５９】
（付記１）データ間で前方一致する前方一致文字列をエッジノードに格納して接続するトライ木を記憶部に格納したコンピュータに、前記トライ木に新規データを登録させるトライ木文字登録プログラムであって、
コンピュータに、
前記トライ木に接続されたエッジノードを順に辿り、エッジノードに対応する前方一致文字列において、前記新規データと先頭部分が一致するものがあるかを検索するステップと、
検索されたエッジノードに対応する前方一致文字列と前記新規データとのそれぞれから前記一致した先頭部分を除いた文字列を辞書順で比較するステップと、
前記辞書順で比較した結果、前記新規データから前記一致した先頭部分を除いた文字列の方が大きかった場合に、前記エッジノードを前記先頭部分の文字列とそれ以外の文字列とをそれぞれ格納した２個のエッジノードを作成し、新たにノードを作成して前記２個のエッジノードの間に接続し、前記新規データから前記一致した先頭部分を除いた文字列を格納するエッジノードを作成して前記新たに作成したノードに接続させるステップと
を実行させることを特徴とするトライ木文字列登録プログラム。
【０２６０】
（付記２）前記辞書順で比較した結果、前記新規データから前記一致した先頭部分を除いた文字列の方が小さかった場合に、前記エッジノードを前記先頭部分の文字列とそれ以外の文字列とをそれぞれ格納した２個とエッジノードを作成し、新たにノードを作成して前記２個のエッジノードの間に接続し、前記新規データから前記一致した先頭部分を除いた文字列を前記新たに作成したノードに接続するステップを更にコンピュータに実行させることを特徴とする付記１に記載のトライ木文字列登録プログラム。
【０２６１】
（付記３）前記トライ木に接続されたエッジノードを辿り、エッジノードに接続されたノードに文字列が接続されていない場合に、前記新規のデータから前記前方一致文字列を取り除いた残りの文字列を前記ノードに接続するステップを更にコンピュータに実行させることを特徴とする付記１または２に記載のトライ木文字列登録プログラム。
【０２６２】
（付記４）データ間で前方一致する前方一致文字列をエッジノードに格納して接続するトライ木を記憶する記憶部と、
前記トライ木に接続されたエッジノードを順に辿り、エッジノードに対応する前方一致文字列において、前記新規データと先頭部分が一致するものがあるかを検索し、
検索されたエッジノードに対応する前方一致文字列と前記新規データとのそれぞれから前記一致した先頭部分を除いた文字列を辞書順で比較し、
前記辞書順で比較した結果、前記新規データから前記一致した先頭部分を除いた文字列の方が大きかった場合に、前記エッジノードを前記先頭部分の文字列とそれ以外の文字列とをそれぞれ格納した２個のエッジノードを作成し、新たにノードを作成して前記２個のエッジノードの間に接続し、前記新規データから前記一致した先頭部分を除いた文字列を格納するエッジノードを作成して前記新たに作成したノードに接続させる接続部と
を有することを特徴とするトライ木文字列登録装置。
【０２６３】
（付記５）前記接続部は、前記辞書順で比較した結果、前記新規データから前記一致した先頭部分を除いた文字列の方が小さかった場合に、前記エッジノードを前記先頭部分の文字列とそれ以外の文字列とをそれぞれ格納した２個とエッジノードを作成し、新たにノードを作成して前記２個のエッジノードの間に接続し、前記新規データから前記一致した先頭部分を除いた文字列を前記新たに作成したノードに接続することを特徴とする付記４に記載のトライ木文字列登録装置。
【０２６４】
（付記６）前記接続部は、前記トライ木に接続されたエッジノードを辿り、エッジノードに接続されたノードに文字列が接続されていない場合に、前記新規のデータから前記前方一致文字列を取り除いた残りの文字列を前記ノードに接続することを特徴とする付記４または５に記載のトライ木文字列登録装置。
【符号の説明】
【０２６５】
１０    コンピュータ
１１    入力装置
１２    モニタ
１３    ＲＡＭ
１３ａ、１８ａ  各種データ
１４    ＲＯＭ
１５    通信制御装置
１６    媒体読取装置
１７    ＣＰＵ
１７ａ  トライ木生成プロセス
１７ｂ  トライ木検索プロセス
１８    ＨＤＤ
１８ｂ  トライ木生成プログラム
１８ｃ  トライ木検索プログラム
１９    バス
１００    トライ木文字列登録装置
１１０，２４０    記憶部
１１０ａ，２４０ｂ  トライ木
１２０    接続部
２００    検索装置
２１０    入力部
２２０    出力部
２３０    入出力制御部
２４０ａ  登録データ管理テーブル
２５０    制御部
２５０ａ  トライ木生成部
２５０ｂ  トライ木探索部
【図１】
2010277556.tif 000003
【図２】
2010277556.tif 000004
【図３】
2010277556.tif 000005
【図４】
2010277556.tif 000006
【図５】
2010277556.tif 000007
【図６】
2010277556.tif 000008
【図７】
2010277556.tif 000009
【図８】
2010277556.tif 000010
【図９】
2010277556.tif 000011
【図１０】
2010277556.tif 000012
【図１１】
2010277556.tif 000013
【図１２】
2010277556.tif 000014
【図１３】
2010277556.tif 000015
【図１４】
2010277556.tif 000016
【図１５】
2010277556.tif 000017
【図１６】
2010277556.tif 000018
【図１７】
2010277556.tif 000019
【図１８】
2010277556.tif 000020
【図１９】
2010277556.tif 000021
【図２０】
2010277556.tif 000022
【図２１】
2010277556.tif 000023
【図２２】
2010277556.tif 000024
【図２３】
2010277556.tif 000025
【図２４】
2010277556.tif 000026
【図２５】
2010277556.tif 000027
【図２６】
2010277556.tif 000028
【図２７】
2010277556.tif 000029
【図２８】
2010277556.tif 000030
【図２９】
2010277556.tif 000031
【図３０】
2010277556.tif 000032
【図３１】
2010277556.tif 000033
【図３２】
2010277556.tif 000034
【図３３】
2010277556.tif 000035
【図３４】
2010277556.tif 000036
【図３５】
2010277556.tif 000037
【図３６】
2010277556.tif 000038
【図３７】
2010277556.tif 000039
【図３８】
2010277556.tif 000040
【図３９】
2010277556.tif 000041
【図４０】
2010277556.tif 000042
【図４１】
2010277556.tif 000043
【図４２】
2010277556.tif 000044
【図４３】
2010277556.tif 000045
【図４４】
2010277556.tif 000046
【図４５】
2010277556.tif 000047
【図４６】
2010277556.tif 000048
【図４７】
2010277556.tif 000049
【図４８】
2010277556.tif 000050
【図４９】
2010277556.tif 000051
【図５０】
2010277556.tif 000052
【図５１】
2010277556.tif 000053
【図５２】
2010277556.tif 000054
【図５３】
2010277556.tif 000055
【図５４】
2010277556.tif 000056
【図５５】
2010277556.tif 000057
【図５６】
2010277556.tif 000058