(57)【要約】【課題】使用メモリ量を削減すること。【解決手段】トライ木文字列登録装置１００は、制御部１３０が、計数部１２０が数え上げた経路の数が所定の個数以上だった場合、一致した文字列に対応する前方一致文字列タグを作成してルートノードに接続するとともに、数え上げた経路それぞれに対応する文字列および新規文字列のそれぞれから、一致した文字列を除いた文字列それぞれに基づき部分トライ木を作成し、当該部分トライ木を前記前方一致文字列タグに接続する。【選択図】図１
2010277544.tif 000002
【特許請求の範囲】
【請求項１】
文字列に対応するタグがノードにより階層的に接続されるトライ木を記憶部に格納したコンピュータに、前記トライ木に新規の文字列を登録させる機能を実現させるトライ木文字列登録プログラムであって、
コンピュータに、
前記新規の文字列の文字を先頭から順に読み出して前記トライ木の経路を順に辿るステップと、
前記新規の文字列と前記辿った経路に対応する文字列とで一致する文字列の長さが所定の長さ以上である経路の数を数え上げるステップと、
前記数え上げた経路の数が所定の個数以上だった場合、前記一致した文字列に対応する前方一致文字列タグを作成してルートノードに接続するとともに、前記数え上げた経路それぞれに対応する文字列および前記新規文字列のそれぞれから、前記一致した文字列を除いた文字列それぞれに基づき部分トライ木を作成し、当該部分トライ木を前記前方一致文字列タグに接続するステップと、
を実行させることを特徴とするトライ木文字列登録プログラム。
【請求項２】
前記一致した文字列に含まれる文字数と、ルートノードからノードに至る深さを基にして尾ノードを判定し、当該尾ノードの配下に接続されているノードをそのまま前記部分トライ木に接続するステップを更に実行させることを特徴とするトライ木文字列登録プログラム。
【請求項３】
文字列に対応するタグがノードにより階層的に接続されるトライ木を記憶する記憶部と、
登録対象となる新規の文字列を取得し、新規の文字列の文字を先頭から順に読み出して前記トライ木の経路を順に辿り、前記新規の文字列と前記辿った経路に対応する文字列とで一致する文字列の長さが所定の長さ以上である経路の数を数え上げる計数部と、
前記数え上げた経路の数が所定の個数以上だった場合、前記一致した文字列に対応する前方一致文字列タグを作成してルートノードに接続するとともに、前記数え上げた経路それぞれに対応する文字列および前記新規文字列のそれぞれから、前記一致した文字列を除いた文字列それぞれに基づき部分トライ木を作成し、当該部分トライ木を前記前方一致文字列タグに接続する制御部と、
を有することを特徴とするトライ木文字列登録装置。
【請求項４】
前記制御部は、前記一致した文字列に含まれる文字数と、ルートノードからノードに至る深さを基にして尾ノードを判定し、当該尾ノードの配下に接続されているノードをそのまま前記部分トライ木に接続する処理を更に実行することを特徴とするトライ木文字列登録装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、トライ木文字列登録プログラムおよびトライ木文字列登録装置に関する。
【背景技術】
【０００２】
文書検索システムにおいて、入力キーが指定された場合に、指定された入力キーに対応する文書や値等をデータベースから高速に検索するべく、トライ木が用いられている（例えば、特許文献１、２参照）。図６８は、従来のトライ木の一例を示す図である。このトライ木は、ルートノードを除くノードに対して、１文字あたり１ノードを割当てた木構造のデータである。図６８に示すトライ木は、一例として、キー「black、green、blue、grey、black、grey、greenyellow」にそれぞれ値「１、３、４、５、３、２、１」が割当てられたトライ木を示している。
【０００３】
従来の検索装置が、トライ木の探索処理を実行する場合には、入力キーを１文字ずつ取り出し、トライ木上の同じキーのノードを辿る。例えば、検索装置は、入力キー「blue」が指定された場合に、トライ木のノードをb、l、u、eの順に辿ることで、「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（子）、ノード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〜ノード/に登録されていたタグキーを子ノードに再接続する必要があるため、処理装置が実行すべき処理が多くなり、迅速にトライ木の再構築処理を実行することが出来ないという問題が存在する。
【００２６】
続いて、先行発明２について説明する。先行技術２は、入力キーの文字列を固定長で分割し、階層的なトライ木を構築する。図７１は、先行発明２のトライ木を示す図である。図７１の上段に示すように、このトライ木２０ａは、各階層にルートノードが存在し、ルートノードに接続されるノードには、所定の文字毎にタグキーを接続している。ルートノードａは、ノードh（１）、ノードtを順に接続し、ノードh（１）はタグキー「ttp:/」を有し、ノードtはタグキー「tps:」を有する。
【００２７】
タグキー「ttp:/」はルートノードｂに接続し、ルートノードbはノード/（１）に接続する。ノード/は、タグキー「aaa.a」を有する。タグキー「aaa.a」はルートノードｃに接続し、ルートノードｃはノード/（２）に接続する。ノード/（２）は、ノードe、ノードg、ノードh（２）、ノードk、ノードmに接続する。ノードeはタグキー「/」を有し、ノード/（３）に接続する。ノード/（３）は、タグキー「C/」を有する。また、ノードg、ノードh（２）、ノードk、ノードmは、それぞれタグキー「/」に接続する。タグキー「tps:」はノードｄに接続し、ノードｄはノード/（４）に接続する。ノード/（４）は、タグキー「b.b」を有する。
【００２８】
図７１の上段に示すように、入力キーの文字列を固定長で分割し、階層的なトライ木を構築すると、新規の入力キーを登録してトライ木を再構築する場合に、再接続するタグキーの数、更新するタグキーの数を大幅に削減することが出来る。
【００２９】
図７１の下段は、図７１の上段に示したトライ木に、キー「http://aaa.aaa/b/」を登録した場合のトライ木を示す。処理装置は、入力キー「http://aaa.aaa/b/」を１文字ずつ読み出し、トライ木を辿ると、ルートノードａ、ノードh（１）、タグキー「ttp:/」、ノードｂ、ノード/（１）、タグキー「aaa.a」、ルートノードｃ、ノード/（２）の順に遷移する。
【００３０】
処理装置は、ノード/（２）において、遷移先となるノード「b」が存在しないので、ノードbを新規に作成し、入力キーからトライ部分「http://aaa.aaa/b」を除いた残りのキー「/」をノードbに接続する。この際、タグキーの再接続、更新処理は、ルートノードｃの存在する階層のみで実行すればよく、ルートノードａ、ｂ、ｄの存在する階層において、タグキーの再接続、更新処理を実行する必要はない。
【００３１】
しかしながら、先行技術２には、下記に示す問題点が存在する。図７２は、先行技術２の問題点を説明するための図である。先行技術２では、文字列を固定長で分割する場合、かかる固定長を適切に設定しないと、使用メモリ量が増大してしまうという問題があった。図７２の上段に示すトライ木では一例として、分割する固定長を１０に設定した場合のトライ木を示す。
【００３２】
図７２の上段に示すように、固定長を１０に設定すると、各キーの先頭文字から固定長１０文字分だけ取り除いた残りの文字列に、各キーに共通する文字列「aaa/」が含まれている。各ノードは複数のタグキーを保持できないため、共通する文字列「aaa/」に対応するノードa（１）、ノードa（２）、ノードa（３）、ノード/が連なって接続される。
【００３３】
このように、共通する文字列が多く存在すると、直列状態で接続されるノードの数が増えてしまい、使用メモリ量が増大してしまう。また、図７２の上段に示すトライ木に、トライ木のキーと共通する部分を多く有する入力キーを登録すると、先行技術１の問題点で説明した場合と同様にして、再構築する場合の処理が多くなってしまうという問題も発生してしまう。
【００３４】
図７２の下段に示すように、入力キー「http://aaa.aaa/b/」をトライ木に登録すると、かかる入力キーに対応するタグキーが、ノードa（１）に接続され、ノードa（１）に接続されていたタグキーおよびノードa（１）の配下に接続された各ノードおよびタグキーを再構築する必要がある。
【００３５】
図７２に示した問題点を解消するためには、固定長を出来るだけ短く設定すればよいのだが、固定長を単に短くすると、一般的なトライ木と同様にノード数が多くなり、使用メモリ量を削減することが出来ないという問題がある。
【００３６】
次に、本実施例１にかかるトライ木文字列登録装置の構成について説明する。図１は、本実施例１にかかるトライ木文字列登録装置の構成を示す図である。図１に示すように、このトライ木文字列登録装置１００は、記憶部１１０、計数部１２０、制御部１３０を有する。
【００３７】
記憶部１１０は、文字列に対応するタグがノードにより階層的に接続されるトライ木１１０ａを記憶する記憶部である。
【００３８】
計数部１２０は、登録対象となる新規の文字列を取得し、新規の文字列の文字を先頭から順に読み出してトライ木１１０ａの経路を順に辿り、新規の文字列と辿った経路に対応する文字列とで一致する文字列の長さが所定の長さ以上である経路の数を数え上げる処理部である。
【００３９】
制御部１３０は、計数部１２０が数え上げた経路の数が所定の個数以上だった場合、一致した文字列に対応する前方一致文字列タグを作成してルートノードに接続するとともに、数え上げた経路それぞれに対応する文字列および新規文字列のそれぞれから、一致した文字列を除いた文字列それぞれに基づき部分トライ木を作成し、当該部分トライ木を前記前方一致文字列タグに接続する処理部である。
【００４０】
本実施例１にかかるトライ木文字列登録装置１００によれば、トライ木に登録された文字列と、新規の文字列に共通する文字列を集約した前方一致文字列タグをルートノードに接続するので、直列状態で接続されるノードの数を削減でき、使用メモリ量を削減することが出来る。
【実施例２】
【００４１】
まず、本実施例２にかかる検索装置の説明を行う前に、トライ木等の木構造に含まれるノードの用語について説明する。図２は、木構造に含まれるノードの用語を説明するための図である。図２に示すように、トライ木を構成する各ノードのうち、最上層に位置するノードをルートノードと定義する。また、基準ノードのひとつ上の層に存在し、基準ノードに接続されたノードを、基準ノードに対する親ノード（以下、単に親ノード）と定義する。また、基準ノードのひとつ下の層に存在し、基準ノードに接続されたノードを基準ノードに対する子供ノード（以下、単に子ノード）と定義する。
【００４２】
また、基準ノードと同じ層に存在し、基準ノードと同じ親ノードに接続され、基準ノードの上側に存在するノードを、基準ノードに対する兄ノード（以下、単に兄ノード）と定義する。また、基準ノードと同じ層に存在し、基準ノードと同じ親ノードに接続され、基準ノードの下側に存在するノードを、基準ノードに対する弟ノード（以下、単に弟ノード）と定義する。また、ルートノードから親ノードに至る各ノードをまとめて先祖ノードと定義する。また、基準ノードの配下に接続された各ノードをまとめて子孫ノードと定義する。
【００４３】
次に、本実施例２にかかる検索装置について説明する。図３は、本実施例２にかかる検索装置の構成を示す図である。図３に示すように、この検索装置２００は、入力部２１０、出力部２２０、入出力制御部２３０、記憶部２４０、制御部２５０を有する。
【００４４】
このうち、入力部２１０は、入力キー等の情報を入力する入力部であり、キーボードやマウス等に該当する。出力部２２０は、トライ木を用いた検索結果などの情報を出力する出力部であり、モニタ、若しくはディスプレイ、タッチパネル等に該当する。入出力制御部２３０は、入力部２１０、出力部２２０、記憶部２４０、制御部２５０によるデータの入出力を制御する処理部である。
【００４５】
記憶部２４０は、制御部２５０による各種処理に必要なデータおよびプログラムを記憶する記憶部である。この記憶部２４０は、登録データ管理テーブル２４０ａ、トライ木２４０ｂを有する。
【００４６】
ここで、登録データ管理テーブル２４０ａは、トライ木に登録するキーと値とを対応付けて記憶するテーブルである。図４は、登録データ管理テーブル２４０ａのデータ構造の一例を示す図である。図４に示すように、この登録データ管理テーブル２４０ａは、キーと値を対応付けて記憶している。
【００４７】
トライ木２４０ｂは、登録データ管理テーブル２４０ａを基にして生成されるトライ木である。図５は、トライ木のデータ構造の一例を示す図である。図５では一例として、図４に示した登録データ管理テーブル２４０ａに対応したトライ木を示す。図５に示すように、ルートノードａはノードdに接続し、ノードdは次の階層のルートノードbに接続する。そして、ルートノードｂは、ノードb、ノードcに接続する。また、ノードbは、タグキー「ark」を接続する。ノードbは、タグキー「lue」、値「２」を接続し、ノードcは、タグキー「yan」、値「１，３」を接続する。
【００４８】
ところで、検索装置２００は、トライ木のメモリ使用量を更に削減するべく、ノードにタグとして付加するタグキーを、トライ部分のキーを削除した形で保持するものとする。例えば、ノードdにタグキー「ark」が登録されているが、これは、ノードbにタグキー「dark」を登録していることと同じ意味である。ルートノードａからノードdに至るトライ部分とタグキーを合わせたキーが「d」であるため、「ark」と足しあわせると「dark」になる。
【００４９】
また、ノードbにタグキー「lue」が登録されているが、これは、ノードbにタグキー「darkblue」を登録していることと同じ意味である。ルートノードａからノードbに至るトライ部分とタグキーを合わせたキーが「darkb」であるため、「lue」と足し合わせると「darkblue」になる。
【００５０】
図５に示したトライ木を実データで表すと、図６に示すデータ構造となる。図６は、実データで表した場合のデータ構造の一例を示す図である。図６に示すように、このトライ木は、各ノードに対応するポインタ配列２０〜２４と、タグキーの文字列を記憶するテキスト表５０を有している。
【００５１】
ここで、ルートノードポインタに接続するポインタ配列２０は、図５のルートノードａに対応する。ポインタ配列２１は、図５のノードdに対応し、ポインタ配列２２は、ルートノードｂに対応する。ポインタ配列２３は、ノードbに対応し、ポインタ配列２４は、ノードcに対応する。
【００５２】
ポインタ配列２０〜２４は、各ポインタ配列へのポインタ領域「０×００〜０×ＦＦ」、「Next」領域、「TAG」領域、「Data」領域を有する。このうち、ポインタ領域は、次のポインタ配列の位置を格納する領域であり、所定の文字に対応付けて配置されている。例えば、ポインタ領域「０×６４」は、文字「d」に対応付けられており、ポインタ領域「０×６４」に接続されたポインタ配列２１は、ノードdとなる。
【００５３】
「Next」領域は、次の階層のルートノードに接続するポインタ（ルートノードに対応するポインタ配列の位置）を格納する。例えば、ポインタ配列２１のNext領域のポインタは、ポインタ配列２２に接続するので、ポインタ配列２２は、ルートノードポインタに接続されていなくても、次の階層のルートノードとなる。
【００５４】
「TAG」領域は、テキスト表５０の文字と対応付けることで、ノードに接続されたタグキーを表現する。例えば、ポインタ配列２３は、テキスト表５０の「l」に接続されているので、「l」から次の空白前までの文字列「lue」をタグキーとして指定している。なお、説明の便宜上、ポインタ配列２１は、文字列「ark」をテキスト表５０とは異なる領域の表に格納しているものとする。
【００５５】
入力キーを指定する場合にも、テキスト表５０を利用する。例えば、入力キー「green」を指定する場合には、入力キーポインタを、テキスト表５０の「g」に接続する。
【００５６】
「Data」領域は、値と対応付けることで、ノードに接続された値を表現する。例えば、ポインタ配列２３は、値「２」に接続されている。なお、入力キーに対応する値（入力値）は、入力キーポインタに対応付けられているものとする。
【００５７】
図３の説明に戻ると、制御部２５０は、各種の処理手順を規定したプログラムや制御データを格納するための内部メモリを有し、これらによって種々の処理を実行する制御部である。図３に示すように、この制御部２５０は、トライ木生成部２５０ａ、トライ木探索部２５０ｂを有する。
【００５８】
トライ木生成部２５０ａは、登録データ管理テーブル２４０ａに登録されたキーに基づいて、トライ木２４０ｂを生成する処理部である。トライ木生成部２５０ａは、新規の入力キーをトライ木２４０ｂに登録する場合に、入力キーの文字を先頭から順に読み出してトライ木２４０ｂを順に辿る。
【００５９】
トライ木生成部２５０ａは、入力キーと、辿った経路に含まれる各ノードのキーとを比較し、入力キーの文字列と一致する文字数が所定値（第１閾値）以上となるキーが所定の個数（第２閾値）以上存在する場合に、一致した文字列に対応する前方一致タグを作成してルートノードに接続する。そして、トライ木生成部２５０ａは、入力キーおよび各ノードのキーから、一致した文字列を取り除いた残りの文字列を、部分トライ木に接続し、ルートノードと部分トライ木を接続することで、トライ木２４０ｂを生成する。
【００６０】
図７は、トライ木生成部２５０ａの処理の概要を説明するための図である。図７の上段に示すように、データ追加前のトライ木２４０ｂは、ルートノードａ、ノード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、ノードt（１）、ノードt（２）、ノードp、ノード:、ノード/の順に辿る。
【００６２】
トライ木生成部２５０ａは、入力キーと、辿った経路に含まれる各ノードh〜ノード/のキーとを比較すると、入力キーの文字列と一致する文字数が第１閾値以上となるキーが所定の個数以上存在する。具体的には、入力キーの文字列と一致する文字数が１５となるキーが、６個存在する。
【００６３】
トライ木生成部２５０ａは、一致した文字列に対応する前方一致タグ「http://aaa.aaa/」を作成してルートノードに接続する。なお、図７では説明の便宜上、ルートノードａにノードhを接続し、ノードhに前方一致タグ「ttp://aaa.aaa/」を接続する。そして、トライ木生成部２５０ａは、入力キーおよび各ノードのキーから、一致した文字列「http://aaa.aaa/」を取り除いた残りの文字列を、部分トライ木として接続し、ルートノード（ルートノードａに接続されたノードh）と部分トライ木を接続することで、トライ木２４０ｂを生成する。図７の下段に示すトライ木２４０ｂ（データ追加後）を参照。
【００６４】
以下において、トライ木生成部２５０ａがトライ木２４０ａを生成する処理についてより詳細に説明する。図８〜図３２は、トライ木を生成する処理を説明するための図である。ここでは説明の便宜上、キー「http://aaa.aaa/e/」と値「１」、キー「http://aaa.aaa/e/c/」と値「２」、キー「http://aaa.aaa/e/b/」と値「３」、キー「http://aaa.aaa/e/a/」と値「４」、キー「http://aaa.aaa/e/d/」と値「５」、キー「http://aaa.aaa/f/」と値「６」の順で、トライ木を生成する場合について説明する。また、第１閾値を１、第２閾値を２とする。
【００６５】
図８に示すように、まず、ノードが存在していない状態で、入力キー「http://aaa.aaa/e/」、入力値「１」を追加する場合について説明する。トライ木生成部２５０ａは、ルートノードａを生成する（ステップＳ１０ａ）。実データ上において、トライ木生成部２５０ａは、ルートノードに対応するポインタ配列２０を生成し、ルートノードポインタとポインタ配列２０を接続する。また、ポインタ配列２０はルートノードに対応するので、「TAG」を空に接続する（ステップＳ１０ｂ）。
【００６６】
トライ木生成部２５０ａは、入力キー「http://aaa.aaa/e/」を用意する（ステップＳ１１ａ）。実データ上において、トライ木生成部２５０ａは、テキスト表５０に入力キー「http://aaa.aaa/e/」を格納し、入力キーのポインタを、テキスト表５０の１行目１列目の「h」に接続する（ステップＳ１１ｂ）。
【００６７】
トライ木生成部２５０ａは、入力キー「http://aaa.aaa/e/」の先頭文字「h」をキーとする子ノードが存在しないので、ルートノードを参照する。ここで、ルートノードにタグキーは存在しないので、ルートノードのタグキーの優先度よりも、入力キー「http://aaa.aaa/e/」の優先度が大きくなる。
【００６８】
トライ木生成部２５０ａは、ルートノードの配下に「h」をキーとするノードを作成し、入力キー「http://aaa.aaa/e/」から文字「h」を除いた残りのキーをタグキーとして、ノードhに接続する。また、入力キー「http://aaa.aaa/e/」の値「１」もノードhに接続する（ステップＳ１２ａ）。
【００６９】
実データ上において、トライ木生成部２５０ａは、ノードhに対応するポインタ配列２１を生成し、ポインタ配列２０のキー番号「０×６８」で、ポインタ配列２０とポインタ配列２１を接続する。また、トライ木生成部２５０ａは、ポインタ配列２１の「TAG」をテキスト表５０の１行２列目の「t」に接続し、ポインタ配列２１の「Data」と値「１」を接続する（ステップＳ１２ｂ）。
【００７０】
続いて、図９に移行する。ステップＳ１２ａ、１２ｂにおいて作成したトライ木に、キー「http://aaa.aaa/e/c/」、値「２」を追加する場合について説明する。トライ木生成部２５０ａは、入力キー「http://aaa.aaa/e/c/」の先頭文字「h」でルートノードからノードhに遷移する（現在のノードをノードhに遷移させる）。そして、トライ木生成部２５０ａは、入力キー「http://aaa.aaa/e/c/」のポインタを１つ進め、２文字目の「ｔ」に設定する（ステップＳ１３ａ）。
【００７１】
実データ上において、トライ木生成部２５０ａは、テキスト表５０に最後に登録されたキー「http://aaa.aaa/e/」との間を１つ空けて、キー「http://aaa.aaa/e/c/」を登録する。そして、トライ木生成部２５０ａは、テキスト表５０の２行目２列目の文字「t」に入力キーのポインタを接続し、現在のノードをポインタ配列２１に接続する（ステップＳ１３ｂ）。
【００７２】
トライ木生成部２５０ａは、ノードhにおいて、「t」をキーとする子ノードが存在しないので、ノードhのタグキー「ttp://aaa.aaa/e/」の優先度と、トライ部分の「h」を取り除いた入力キー「ttp://aaa.aaa/e/c/」の優先度を比較する。すると、入力キーの１７文字目がｃであり、タグキーの１７文字目が空であるため、入力キーの優先度が、タグキーの優先度よりも大きい（ステップＳ１４）。したがって、トライ木生成部２５０ａは、入力キー「ttp://aaa.aaa/e/c/」を、ノードh以降のノードに登録する。
【００７３】
続いて、図１０に移行する。トライ木生成部２５０ａは、入力キー「http://aaa.aaa/e/c/」の２文字目の「t」をキーとして新しいノードtを生成し、入力キーのポインタを３文字目の「t」に進める（ステップＳ１５ａ）。
【００７４】
実データ上において、トライ木生成部２５０ａは、ノードｔに対応するポインタ配列２２を生成し、ポインタ配列２１のキー番号「０×７４」で、ポインタ配列２１とポインタ配列２２を接続する。また、入力キーのポインタを１つ進め、テキスト表５０の２行目３列目の「t」に入力キーのポインタを接続する（ステップＳ１５ｂ）。
【００７５】
トライ木生成部２５０ａは、ステップＳ１５ａで作成したノードtに入力キー「http://aaa.aaa/e/c/」からトライ部分の「ht」を除いた残りのキー「tp://aaa.aaa/e/c/」をタグキーとして登録する（ステップＳ１６ａ）。
【００７６】
実データ上において、トライ木生成部２５０ａは、ポインタ配列２２の「TAG」をテキスト表５０の２行目３列目の「t」に接続し、ポインタ配列２２の「Data」と値「２」を接続する（ステップＳ１６ｂ）。
【００７７】
続いて、図１１に移行する。ステップＳ１６ａ、１６ｂにおいて作成したトライ木に、入力キー「http://aaa.aaa/e/b/」、値「３」を追加する場合について説明する。トライ木生成部２５０ａは、入力キー「http://aaa.aaa/e/b/」の先頭文字から１文字ずつ読み出して、トライ木上をノードh、tの順に遷移する。そして、トライ木生成部２５０ａは、遷移したノードの数に応じて、入力キー「http://aaa.aaa/e/b/」のポインタを２つ進め、３文字目の「t」に設定する。
【００７８】
そして、トライ木生成部２５０ａは、ノードtにおいて、「t」をキーとする子ノードが存在しないので、ノードtのタグキー「tp://aaa.aaa/e/c/」の優先度と、トライ部分の「ht」を取り除いた入力キー「tp://aaa.aaa/e/b/」の優先度を比較する。すると、タグキーの１６文字目が「c」であり、入力キーの１６文字目が「b」であるため、タグキーの優先度の方が、入力キーの優先度よりも大きくなる。
【００７９】
トライ木生成部２５０ａは、トライ部分「ht」およびタグキー「tp://aaa.aaa/e/c/」を合わせた文字列と、入力キー「http://aaa.aaa/e/b/」とを比較して、一致する文字列を判定する。トライ木生成部２５０ａは、一致する文字列「http://aaa.aaa/e/」の数１７を、最小一致長としてセットし、一致データ数を１にセットする（ステップＳ１７ａ）。
【００８０】
実データ上において、トライ木生成部２５０ａは、テキスト表５０に最後に登録されたキー「http://aaa.aaa/e/c/」との間を１つ空けて、キー「http://aaa.aaa/e/b/」を登録する。そして、トライ木生成部２５０ａは、テキスト表５０の３行目５列目の文字「t」に入力キーのポインタを接続する。また、ポインタ配列２２の「TAG」に接続された文字を先頭とする文字列と、入力キーのポインタに接続された文字を先頭とする文字列とを順次比較すると、タグキーの１６文字目が「c」であり、入力キーの１６文字目が「b」であるため、タグキーの優先度の方が、入力キーの優先度よりも大きくなる。
【００８１】
トライ木生成部２５０ａは、ポインタ配列２２の「TAG」に接続された全文字列「http://aaa.aaa/e/c」と、入力キー「http://aaa.aaa/e/b/」とを比較して、一致する文字列を判定する。トライ木生成部２５０ａは、一致する文字列「http://aaa.aaa/e/」の数１７を、最小一致長としてセットし、一致データ数を１にセットする（ステップＳ１７ｂ）。
【００８２】
トライ木生成部２５０ａは、入力キー「http://aaa.aaa/e/b/」のポインタを一つ戻して、２文字目の「t」に設定し、ノードtの親ノードとなるノードhに遷移する。そして、トライ木生成部２５０ａは、ノードhのタグキー「ttp://aaa.aaa/e/」の優先度と、トライ部分の「h」を取り除いた入力キー「ttp://aaa.aaa/e/b/」の優先度を比較する。すると、タグキーの１７文字目が空であり、入力キーの１７文字目が「b」であるため、入力キーの優先度の方が、タグキーの優先度よりも大きくなる（ステップＳ１８ａ）。
【００８３】
実データ上において、トライ木生成部２５０ａは、現在のノードのポインタをポインタ配列２１に接続し、テキスト表５０の３行目４列目の文字「t」に入力キーのポインタを接続する。また、ポインタ配列２１の「TAG」に接続された文字を先頭とする文字列と、入力キーのポインタに接続された文字を先頭とする文字列とを順次比較すると、タグキーの１７文字目が空であり、入力キーの１７文字目が「b」であるため、入力キーの優先度の方が、タグキーの優先度よりも大きくなる（ステップＳ１８ｂ）。
【００８４】
続いて、図１２に移行する。トライ木生成部２５０ａは、ノードhから、入力キー「http://aaa.aaa/e/b/」の２文字目のtでノードtに遷移し、入力キーのポインタを３文字目の「t」に設定する（ステップＳ１９ａ）。
【００８５】
実データ上において、トライ木生成部２５０ａは、現在のノードのポインタをポインタ配列２２に接続し、テキスト表５０の２行目３列目の文字「t」に入力キーのポインタを接続する（ステップＳ１９ｂ）。
【００８６】
トライ木生成部２５０ａは、ノードtのデータ（タグキー、値）と、入力データ（入力キー、値）を交換する。すなわち、トライ木生成部２５０ａは、入力キー「http://aaa.aaa/e/b/」からトライ部分「ht」を取り除いた残りのキー「tp://aaa.aaa/e/b/」をノードtのタグキーに登録する。また、入力キー「http://aaa.aaa/e/b/」に対応する値「３」もノード「t」に接続する。
【００８７】
トライ木生成部２５０ａは、ノードtに登録されていたタグキー「tp://aaa.aaa/e/c」の先頭にトライ部分「ht」を追加して、入力キーとして取り出す。また、トライ木生成部２５０ａは、タグキー「tp://aaa.aaa/e/c/」に対応付けられていた値「２」も取り出す（ステップＳ２０ａ）。
【００８８】
実データ上において、トライ木生成部２５０ａは、ノードtのデータ（タグキー）と、入力データ（入力キー、値）を交換する。すなわち、トライ木生成部２５０ａは、ノードtに対応するポインタ配列２２の「TAG」をテキスト表５０の３行目５列目の「t」に接続する。また、ポインタ配列２２の「Data」と値「３」を接続する。
【００８９】
そして、トライ木生成部２５０ａは、入力キーのポインタを、テキスト表５０の２行目３列目の「t」に接続する。また、ポインタ配列２２の「Data」に接続されていた値「２」を入力値に保持する（ステップＳ２０ｂ）。
【００９０】
続いて、図１３に移行する。トライ木生成部２５０ａは、入力キー「http://aaa.aaa/e/c/」の３文字目に対応するノードtが存在しないので、ノードtの配下に新たなノードtを生成する。ここで、各ノードtを区別するために以下の説明では、親側のノードtをノードｔ（１）と表記し、子側のノードｔをノードｔ（２）と表記する。また、トライ木生成部２５０ａは、入力キーのポインタを４文字目の「p」に設定する（ステップＳ２１ａ）。
【００９１】
実データ上において、トライ木生成部２５０ａは、ノードｔ（２）に対応するポインタ配列２３を生成し、ポインタ配列２２のキー番号「０×７４」で、ポインタ配列２２とポインタ配列２３を接続する。また、トライ木生成部２５０ａは、入力キーのポインタを、テキスト表５０の２行目４列目の「p」に接続する（ステップＳ２１ｂ）。
【００９２】
続いて、図１４に移行する。トライ木生成部２５０ａは、入力キー「http://aaa.aaa/e/c/」から、トライ部分「htt」を取り除いた残りのキー「p://aaa.aaa/e/c/」をノードt（２）に接続する。また、トライ木生成部２５０ａは、入力キー「http://aaa.aaa/e/c/」に対応する値「２」をノードt（２）に接続する（ステップＳ２２ａ）。
【００９３】
実データ上において、トライ木生成部２５０ａは、ポインタ配列２３の「TAG」をテキスト表５０の２行目４列目の「p」に接続し、入力キーのポインタを開放する。また、トライ木生成部２５０ａは、ポインタ配列２３の「Data」に値「２」を接続する（ステップＳ２２ｂ）。
【００９４】
続いて、図１５に移行する。ステップＳ２２ａ、２２ｂにおいて作成したトライ木に、キー「http://aaa.aaa/e/a/」、値「４」を追加する場合について説明する。トライ木生成部２５０ａは、入力キー「http://aaa.aaa/e/a/」の先頭から文字を順次読み出し、ノードh、ノードt（１）、ノードt（２）に遷移する。そして、トライ木生成部２５０ａは、入力キー「http://aaa.aaa/e/a/」のポインタを４文字目の「p」に設定する（ステップＳ２３ａ）。
【００９５】
実データ上において、トライ木生成部２５０ａは、テキスト表５０に最後に登録されたキー「http://aaa.aaa/e/b/」との間を１つ空けて、キー「http://aaa.aaa/e/a/」を登録する。そして、トライ木生成部２５０ａは、テキスト表５０の４行目８列目の「p」に入力キーのポインタを接続する。また、トライ木生成部２５０ａは、現在のノードをポインタ配列２３に接続する（ステップＳ２３ｂ）。
【００９６】
続いて、図１６に移行する。トライ木生成部２５０ａは、ノードt（２）のタグキー「p://aaa.aaa/e/c/」の優先度と、トライ部分「htt」を取り除いた入力キー「p://aaa.aaa/e/a/」の優先度を比較する。すると、入力キーの１５文字目が「a」であり、タグキーの１５文字目が「c」であるため、入力キーの優先度がタグキーの優先度よりも小さい。
【００９７】
トライ木生成部２５０ａは、トライ部分「htt」およびタグキー「p://aaa.aaa/e/c/」を合わせた文字列と、入力キー「http://aaa.aaa/e/a/」とを比較して、一致する文字列を判定する。トライ木生成部２５０ａは、一致する文字列「http://aaa.aaa/e/」の数１７を、最小一致長としてセットし、一致データ数を１にセットする。また、トライ木生成部２５０ａは、入力キーのポインタを１文字戻して、３文字目の「t」に設定し、ノードt（１）に遷移する（ステップＳ２４ａ）。
【００９８】
実データ上において、トライ木生成部２５０ａは、ポインタ配列２３の「TAG」に接続された文字を先頭とする文字列と、入力キーのポインタに接続された文字列とを順次比較すると、タグキーの１５文字目が「c」であり、入力キーの１５文字目が「a」であるため、入力キーの優先度がタグキーの優先度よりも小さい。
【００９９】
トライ木生成部２５０ａは、ポインタ配列２３の「TAG」に接続された文字列「http://aaa.aaa/e/c/」と、入力キー「http://aaa.aaa/e/a/」とを比較して、一致する文字列を判定する。トライ木生成部２５０ａは、一致する文字列「http://aaa.aaa/e/」の数１７を、最小一致長としてセットし、一致データ数を１にセットする（ステップＳ２４ｂ）。
【０１００】
続いて、図１７に移行する。トライ木生成部２５０ａは、ノードt（１）のタグキー「tp://aaa.aaa/e/b/」の優先度と、トライ部分「ht」を取り除いた入力キー「tp://aaa.aaa/e/a/」の優先度を比較する。すると、入力キーの１６文字目が「a」であり、タグキーの１６文字目が「b」であるため、入力キーの優先度がタグキーの優先度よりも小さい。トライ木生成部２５０ａは、一致データ数を「２」に設定する。一致データ数が第２閾値以上なので、トライ木生成部２５０ａは、新しい階層を作成する処理を開始する（ステップＳ２５ａ）。
【０１０１】
実データ上において、トライ木生成部２５０ａは、ポインタ配列２２の「TAG」に接続された文字を先頭とする文字列と、入力キーのポインタに接続された文字列とを順次比較すると、タグキーの１６文字目が「b」であり、入力キーの１６文字目が「a」であるため、入力キーの優先度がタグキーの優先度よりも小さい。トライ木生成部２５０ａは、一致データ数を「２」に設定する。一致データ数が第２閾値以上なので、トライ木生成部２５０ａは、新しい階層を作成する処理を開始する（ステップＳ２５ｂ）。
【０１０２】
続いて、図１８に移行する。トライ木生成部２５０ａは、親ノードとなるノードhがルートノードではないので、入力キーのポインタを１文字戻し、２文字目の「t」に設定する。そして、トライ木生成部２５０ａは、現在のノードをノードhに遷移する。トライ木生成部２５０ａは、トライ部分「h」とタグキー「ttp://aaa.aaa/e/」を合わせた文字列と、入力キーの文字列が１７文字一致するため、一致データ数をインクリメントし、一致データ数を３に設定する（ステップＳ２６ａ）。
【０１０３】
実データ上において、トライ木生成部２５０ａは、入力キーのポインタを、テキスト表５０の４行目６列目の「t」に設定する。また、トライ木生成部２５０ａは、ポインタ配列２１の「TAG」に接続された文字列と、入力キーのポインタに接続された文字列とを比較すると、１７文字一致し、最小一致長と同じ文字数となる。トライ木生成部２５０ａは、一致データ数をインクリメントし、一致データ数を３に設定する（ステップＳ２６ｂ）。
【０１０４】
続いて、図１９に移行する。トライ木生成部２５０ａは、ノードhの親ノードがルートノードなので、新しいルートノードｂを生成する。トライ木生成部２５０ａは、入力キー「http://aaa.aaa/e/a/」の先頭から最小一致長「１７」分の文字列を取り除いた文字列「a/」を特定する。
【０１０５】
トライ木生成部２５０ａは、文字列「a/」の先頭文字に対応するノードaを生成し、ルートノードｂとノードaを接続する。トライ木生成部２５０ａは、文字列「a/」からトライ部分を取り除いたキー「/」をノードaに接続する。そして、トライ木生成部２５０ａは、入力キー「http://aaa.aaa/e/a/」に対応する値「４」をノードaに接続する（ステップＳ２７ａ）。
【０１０６】
実データ上において、トライ木生成部２５０ａは、ルートノードbおよびノードaに対応するポインタ配列２４、２５をそれぞれ生成する。トライ木生成部２５０ａは、ポインタ配列２４のキー番号「０×６２」で、ポインタ配列２４とポインタ配列２５を接続する。トライ木生成部２５０ａは、ポインタ配列２５の「TAG」を、テキスト表５０の５行目５列目の「/」に接続する（ステップＳ２７ｂ）。
【０１０７】
続いて、図２０に移行する。入力キー「http://aaa.aaa/e/a/」からトライ部分「h」を取り除いた文字列「ttp://aaa.aaa/e/a/」と、タグキー「ttp://aaa.aaa/e/」は１６文字一致するため、ここでは一致数は「１６」となる。トライ木生成部２５０ａは、現在のノードhのタグキー「ttp://aaa.aaa/e/」のポインタを一致数「１６」文字だけ進めると空となる。トライ木生成部２５０ａは、ルートノードｂにタグキー「空」および値「１」を接続する（ステップＳ２８ａ）。
【０１０８】
実データ上において、トライ木生成部２５０ａは、ポインタ配列２１の「TAG」の接続先を１６文字進めると、接続先の文字は空となる。トライ木生成部２５０ａは、ルートノードｂに対応するポインタ配列２４の「TAG」に空を接続し、「Data」に「１」を接続する（ステップＳ２８ｂ）。
【０１０９】
続いて、図２１に移行する。トライ木生成部２５０ａは、ノードhとルートノードｂを接続し、一致データ数をデクリメントし、２に設定する。また、トライ木生成部２５０ａは、ノードhに接続された値「１」を削除する（ステップＳ２９ａ）。
【０１１０】
実データ上において、トライ木生成部２５０ａは、ポインタ配列２１の「Next」をポインタ配列２４に接続し、一致データ数をデクリメントし、２に設定する。また、トライ木生成部２５０ａは、ポインタ配列２１の「Data」をNULLに設定する（ステップＳ２９ｂ）。
【０１１１】
続いて、図２２に移行する。トライ木生成部２５０ａは、一致データ数が０より大きいため、ノードhの長男ノードとなるノードt（１）に遷移する。入力キー「http://aaa.aaa/e/a/」からトライ部分「ht」を取り除いた文字列「tp://aaa.aaa/e/a/」と、タグキー「tp://aaa.aaa/e/b/」は１５文字一致するため、ここでは一致数は「１５」となる。
【０１１２】
トライ木生成部２５０ａは、タグキー「tp://aaa.aaa/e/b/」から一致数「１５」分の文字列を取り除いた文字列「b/」を特定する。トライ木生成部２５０ａは、文字列「b/」の先頭文字に対応するノードbを生成し、ルートノードｂとノードbを接続する。トライ木生成部２５０ａは、文字列「b/」からトライ部分を取り除いたキー「/」をノードbに接続する。そして、トライ木生成部２５０ａは、ノードt（１）の値「３」をノードbに接続する（ステップＳ３０ａ）。
【０１１３】
実データ上において、トライ木生成部２５０ａは、ノードbに対応するポインタ配列２６を生成する。トライ木生成部２５０ａは、ポインタ配列２４のキー番号「０×６１」で、ポインタ配列２４とポインタ配列２６を接続する。トライ木生成部２５０ａは、ポインタ配列２６の「TAG」を、テキスト表５０の４行目３列目の「/」に接続し、「Data」と値「３」を接続する（ステップＳ３０ｂ）。
【０１１４】
続いて、図２３に移行する。トライ木生成部２５０ａは、ノードt（１）の長男ノードとなるノードt（２）のタグキー「tp://aaa.aaa/e/c/」と値「２」をノードt（１）に移し、ノードt（２）に移行する（ステップＳ３１ａ）。
【０１１５】
実データ上において、トライ木生成部２５０ａは、ポインタ配列２２の「TAG」をテキスト表５０の２行目３列目の「t」に接続する。また、トライ木生成部２５０ａは、ポインタ配列２２の「Data」に値「２」を接続し、削除親ノードをポインタ配列２１に接続する（ステップＳ３１ｂ）。
【０１１６】
続いて、図２４に移行する。トライ木生成部２５０ａは、ノードt（２）を削除し、ノードt（２）に接続されたタグキー「p://aaa.aaa/e/c/」を削除する。トライ木生成部２５０ａは、ノードt（２）と値「２」との接続を解除する。また、トライ木生成部２５０ａは、一致データ数をデクリメントして、一致データ数を「１」に設定し、現在のノードをノードhに設定する（ステップＳ３２ａ）。
【０１１７】
実データ上において、トライ木生成部２５０ａは、ポインタ配列２３を削除し、ポインタ配列２３とテキスト表５０、値「２」との接続を解除する。トライ木生成部２５０ａは、一致データ数をデクリメントして、一致データ数を「１」に設定し、現在のノードをポインタ配列２１に接続する（ステップＳ３２ｂ）。
【０１１８】
続いて、図２５に移行する。トライ木生成部２５０ａは、一致データ数が０より大きいので、ノードhの長男ノードとなるノードt（１）に遷移する。入力キー「http://aaa.aaa/e/a/」からトライ部分「ht」を取り除いた文字列「tp://aaa.aaa/e/a/」と、タグキー「tp://aaa.aaa/e/c/」は１５文字一致するため、ここでは一致数は「１５」となる。
【０１１９】
トライ木生成部２５０ａは、ノードtのタグキー「tp://aaa.aaa/e/c/」から一致数「１５」分の文字列を取り除いた文字列「c/」を特定する。トライ木生成部２５０ａは、文字列「c/」の先頭文字に対応するノードcを生成し、ルートノードｂとノードcを接続する。トライ木生成部２５０ａは、文字列「c/」からトライ部分を取り除いたキー「/」をノードcに接続する。そして、トライ木生成部２５０ａは、ノードt（１）の値「２」をノードcに接続する（ステップＳ３３ａ）。
【０１２０】
実データ上において、トライ木生成部２５０ａは、ノードcに対応するポインタ配列２７を生成する。トライ木生成部２５０ａは、ポインタ配列２４のキー番号「０×６３」で、ポインタ配列２４とポインタ配列２７を接続する。トライ木生成部２５０ａは、ポインタ配列２７の「TAG」を、テキスト表５０の３行目１列目の「/」に接続し、「Data」と値「２」を接続する（ステップＳ３３ｂ）。
【０１２１】
続いて、図２６に移行する。トライ木生成部２５０ａは、ノードt（１）を削除し、ノードt（１）に接続するタグキー「tp://aaa.aaa/e/c/」、値「２」を削除する（ステップＳ３４ａ）。
【０１２２】
実データ上において、トライ木生成部２５０ａは、現在のノードのポインタに接続されたポインタ配列２２を削除し、ポインタ配列２２とテキスト表５０、値「２」の接続を解除する（ステップＳ３４ｂ）。
【０１２３】
続いて、図２７に移行する。トライ木生成部２５０ａは、現在のノードをノードhに設定し、一致データ数をデクリメントし、一致データ数を０に設定する。一致データ数が０となったので、再構築処理を終了する（ステップＳ３５ａ）。
【０１２４】
実データ上において、トライ木生成部２５０ａは、現在のノードをポインタ配列２１に接続し、一致データ数をデクリメントし、一致データ数を０に設定する。一致データ数が０となったので、再構築処理を終了する（ステップＳ３５ｂ）。
【０１２５】
続いて、図２８に移行する。ステップＳ３５ａ、３５ｂにおいて作成したトライ木に、キー「http://aaa.aaa/e/d/」、値「５」を追加する場合について説明する。トライ木生成部２５０ａは、入力キー「http://aaa.aaa/e/d/」の先頭から文字を順次読み出し、ノードhに遷移する。また、トライ木生成部２５０ａは、入力キー「http://aaa.aaa/e/d/」のポインタを２文字目の「t」に設定する（ステップＳ３６ａ）。
【０１２６】
実データ上において、トライ木生成部２５０ａは、テキスト表５０に最後に登録されたキー「http://aaa.aaa/e/a/」との間を１つ空けて、キー「http://aaa.aaa/e/d/」を登録する。そして、トライ木生成部２５０ａは、テキスト表５０の５行目８列目に入力キーのポインタを接続する。また、トライ木生成部２５０ａは、現在のノードをポインタ配列２１に接続する（ステップＳ３６ｂ）。
【０１２７】
続いて、図２９に移行する。トライ木生成部２５０ａは、ノードhに接続されたタグキー「ttp://aaa.aaa/e/」と、入力キーのポインタ以降の文字列「http://aaa.aaa/e/d/」を比較すると、タグキーの文字列が、入力キーのポインタの前方に含まれる（前方一致する）ので、ルートノードｂに遷移する。トライ木生成部２５０ａは、入力キーのポインタを、タグキー「ttp://aaa.aaa/e/」分だけ進め、１８文字目の「d」に設定する（ステップＳ３７ａ）。
【０１２８】
実データ上において、トライ木生成部２５０ａは、ポインタ配列２１の「TAG」に接続された文字列「ttp://aaa.aaa/e/」と、入力キーのポインタに接続された文字列「ttp://aaa.aaa/e/d/」を比較すると、タグキーの文字列が、入力キーのポインタの前方に含まれる（前方一致する）ので、現在のノードをポインタ配列２４に接続する。トライ木生成部２５０ａは、入力キーのポインタを６行目６文字目の「d」に設定する（ステップＳ３７ｂ）。
【０１２９】
続いて、図３０に移行する。トライ木生成部２５０ａは、ルートノードbのタグキーは空なので、入力キーの優先度がタグキーの優先度よりも大きいと判定する。トライ木生成部２５０ａは、ノードdを生成し、ノードdとルートノードｂを接続すると共に、入力キーのポインタを１文字進めて、１９文字目の「/」に設定する。トライ木生成部２５０ａは、ノードdにタグキー「/」と値「５」を接続し、入力キーのポインタを１文字進める（ステップＳ３８ａ）。
【０１３０】
実データ上において、トライ木生成部２５０ａは、ポインタ配列２４の「TAG」が空に接続されているので、入力キーの優先度がタグキーの優先度よりも大きいと判定する。トライ木生成部２５０ａは、ノードdに対応するポインタ配列２８を生成し、ポインタ配列２４のキー番号「０×６４」で、ポインタ配列２４とポインタ配列２８を接続する。トライ木生成部２５０ａは、ポインタ配列２８の「TAG」を、テキスト表５０の６行目７列目の「/」に接続し、「Data」と値「５」を接続する（ステップＳ３８ｂ）。
【０１３１】
続いて、図３１に移行する。ステップＳ３８ａ、Ｓ３８ｂにおいて作成したトライ木に、キー「http://aaa.aaa/f/」、値「６」を追加する場合について説明する。トライ木生成部２５０ａは、入力キー「http://aaa.aaa/f/」の先頭から文字を順次読み出し、ノードhに遷移する。また、トライ木生成部２５０ａは、入力キー「http://aaa.aaa/f/」のポインタを２文字目の「t」に設定する（ステップＳ３９ａ）。
【０１３２】
実データ上において、トライ木生成部２５０ａは、テキスト表５０に最後に登録されたキー「http://aaa.aaa/e/d/」との間を１つ空けて、キー「http://aaa.aaa/f/」を登録する。そして、トライ木生成部２５０ａは、テキスト表５０の６行目１０列目に入力キーのポインタを接続する。また、トライ木生成部２５０ａは、現在のノードをポインタ配列２１に接続する（ステップＳ３９ｂ）。
【０１３３】
続いて、図３２に移行する。トライ木生成部２５０ａは、ノードhに接続されたタグキー「ttp://aaa.aaa/e/」と、入力キーのポインタ以降の文字列「ttp://aaa.aaa/f/」を比較すると、タグキーの文字列が、入力キーのポインタの前方に含まれないので（前方一致しない）ので、ルートノードｂに遷移しないと判定する。
【０１３４】
トライ木生成部２５０ａは、ノードhに接続されたタグキー「ttp://aaa.aaa/e/」の優先度と、トライ部分「h」を除いた入力キー「ttp://aaa.aaa/f/」の優先度を比較すると、タグキーの１５文字目が「e」であり、入力キーの１５文字目が「f」であるため、入力キーの優先度がタグキーの優先度よりも大きいと判定する。
【０１３５】
トライ木生成部２５０ａは、ノードhにおいて、「t」をキーとする子ノードが存在しないので、ノードtを生成し、タグキー「tp://aaa.aaa/f/」と値「６」をノードtに接続する。また、ノードhとノードtを接続する（ステップＳ４０ａ）。
【０１３６】
実データ上において、トライ木生成部２５０ａは、ポインタ配列２１に接続された文字列「ttp://aaa.aaa/e/」と、入力キーのポインタに接続された文字列「ttp://aaa.aaa/f/」を比較すると、タグキーの文字列が、入力キーのポインタの前方に含まれないので（前方一致しない）ので、「Next」の接続先となるポインタ配列に遷移しないと判定する。
【０１３７】
トライ木生成部２５０ａは、ポインタ配列２１に接続された文字列「ttp://aaa.aaa/e/」の優先度と、入力キーのポインタに接続された文字列「ttp://aaa.aaa/f/」の優先度を比較すると、タグキーの１５文字目が「e」であり、入力キーの１５文字目が「f」であるため、入力キーの優先度がタグキーの優先度よりも大きいと判定する。
【０１３８】
トライ木生成部２５０ａは、ノードtに対応するポインタ配列２９を生成し、ポインタ配列の「TAG」をテキスト表５０の６行目１１列目の「t」に接続し、「Data」を値「６」に接続する。また、トライ木生成部２５０ａは、ポインタ配列２１のキー番号「０×７４」で、ポインタ配列２１とポインタ配列２９を接続する（ステップＳ４０ｂ）。
【０１３９】
上述したように、トライ木生成部２５０ａが図８〜図３２に示した処理を実行することで、各キーの共通文字列「http://aaa.aaa/e/」が、ノードhおよびノードhのタグキーに集約されるので、直列状態で接続されるノードの数を削減し、使用メモリ量を節約することが可能となる。
【０１４０】
続いて、図３３〜図４３を用いて、トライ木を生成するその他の処理について説明する。図３３〜図４３は、トライ木を生成するその他の処理について説明するための図である。ここでは、説明の便宜上、図３３に示すトライ木が既に作成されており、かかるトライ木に入力キー「aba」を登録する場合について説明する。また、値の説明は省略する。
【０１４１】
図３３に示すように、このトライ木は、ルートノードａ、ノードa、ノードb、ノードf、ノードgを有する。また、ノードａはタグキー「bc」を有し、ノードbはタグキー「d」を有し、ノードfはタグキー「空」を有し、ノードgは、タグキー「e」を有する。トライ木生成部２５０ａは、入力キーのポインタを、入力キー「aba」の１文字目に設定する（ステップＳ５０ａ）。
【０１４２】
実データ上では、トライ木は、ルートノードａに対応するポインタ配列２０、ノードａに対応するポインタ配列２１、ノードbに対応するポインタ配列２２、ノードfに対応するポインタ配列２３、ノードgに対応するポインタ配列２４を有する。テキスト表５０は、「abc」、「abd」、「abf」、「abge」、「aba」を順に記憶する。テキスト表５０は、各文字列の間に１文字分の空欄を有する。
【０１４３】
ポインタ配列２０のキー番号「０×６１」で、ポインタ配列２０とポインタ配列２１は接続され、ポインタ配列２１のキー番号「０×６２」で、ポインタ配列２１とポインタ配列２２は接続される。また、ポインタ配列２２のキー番号「０×６６」で、ポインタ配列２２とポインタ配列２３は接続され、ポインタ配列２２のキー番号「０×６７」で、ポインタ配列２２とポインタ配列２４は接続される。
【０１４４】
ルートノードポインタは、ポインタ配列２０に接続される。トライ木生成部２５０ａは、現在のノードをポインタ配列２０に設定し、入力キーのポインタをテキスト表５０の１行目１８列目の「a」に接続する（ステップＳ５０ｂ）。
【０１４５】
続いて、図３４に移行する。トライ木生成部２５０ａは、入力キー「aba」の先頭文字から１文字ずつ読み出して、トライ木上をノードa、bの順に遷移する。そして、トライ木生成部２５０ａは、遷移したノードの数に応じて入力キー「aba」のポインタを２つ進め、３文字目の「a」に設定する（ステップＳ５１ａ）。
【０１４６】
実データ上において、トライ木生成部２５０ａは、現在のノードをポインタ配列２２に接続し、入力キーのポインタをテキスト表５０の１行目２０列目の「a」に接続する（ステップＳ５１ｂ）。
【０１４７】
続いて、図３５に移行する。トライ木生成部２５０ａは、ノードbにおいて、「a」をキーとする子ノードが存在しないので、ノードbのタグキー「b」の優先度と、トライ部分の「ab」を取り除いた入力キー「a」の優先度を比較する。すると、タグキーの１文字目が「ｂ」であり、入力キーの１文字目が「a」であるため、タグキーの優先度の方が、入力キーの優先度よりも大きくなる。
【０１４８】
トライ木生成部２５０ａは、トライ部分「ab」およびタグキー「b」を合わせた文字列と、入力キー「aba」とを比較して、一致する文字列を判定する。トライ木生成部２５０ａは、一致する文字列「ab」の数２を、最小一致長としてセットし、一致データ数を１にセットする。最小一致長は、第１閾値よりも大きい。
【０１４９】
なお、ルートノードａからノードbに至るまでの遷移回数（レベル）が２である。トライ木生成部２５０ａは、最小一致長と、レベルが同じ場合には、現在のノードを尾ノードとして登録する。図３５に示す例では、トライ木生成部２５０ａは、ノードｂを尾ノードとして登録する（ステップＳ５１ａ）。
【０１５０】
実データ上において、トライ木生成部２５０ａは、ポインタ配列２２に接続された文字列「d」と、入力キーのポインタに接続された文字列「a」とを比較すると、タグキーの１文字目が「d」であり、入力キーの１文字目が「a」であるため、タグキーの優先度の方が、入力キーの優先度よりも大きくなる。
【０１５１】
トライ木生成部２５０ａは、ポインタ配列２２の「TAG」に接続された全文字列「abd」と、入力キー「abc」とを比較して、一致する文字列を判定する。トライ木生成部２５０ａは、一致する文字列「ab」の数２を、最小一致長としてセットし、一致データ数を１にセットする。また、トライ木生成部２５０ａは、尾ノードのポインタをポインタ配列２２に接続する（ステップＳ５１ｂ）。ここで、尾ノードとは、次の階層をつくる一致文字列がすべてエッジで表現されているノードである。尾ノードには、一致する文字列の後部がタグキーに含まれていない特徴がある。また、尾ノードは、一致する文字列がすべてエッジで表現されており、次のノードへのエッジを表す文字は次の階層の先頭文字にあたるため、次の階層に直接接続してよい。
【０１５２】
続いて、図３６に移行する。トライ木生成部２５０ａは、一致データ数が第２閾値未満で、ノードbに兄ノードが存在せず、ノードbの親ノードaがルートノードでないため、ノードaに遷移する。トライ木生成部２５０ａは、入力キーのポインタを１文字戻し、２文字目の「b」に設定する（ステップＳ５２ａ）。
【０１５３】
実データ上において、トライ木生成部２５０ａは、現在のノードをポインタ配列２１に接続し、入力キーのポインタを１９文字目の「b」に設定する（ステップＳ５２ｂ）。
【０１５４】
続いて、図３７に移行する。トライ木生成部２５０ａは、ノードaのタグキー「bc」の優先度と、トライ部分「a」を取り除いた入力キー「ba」の優先度を比較する。すると、タグキーの２文字目が「c」であり、入力キーの２文字目が「a」であるため、タグキーの優先度が入力キーの優先度よりも大きくなる。
【０１５５】
トライ木生成部２５０ａは、トライ部分「a」およびタグキー「bc」を合わせた文字列と、入力キー「aba」とを比較すると、一致する文字数が最小一致長となるので、一致データ数をインクリメントし、一致データ数を２に設定する。トライ木生成部２５０ａは、一致データ数が、第２閾値以上となるので、新階層作成処理を開始する（ステップＳ５３ａ）。
【０１５６】
実データ上において、トライ木生成部２５０ａは、ポインタ配列２１に接続された文字列「bc」と、入力キーのポインタに接続された文字列「ba」とを比較すると、タグキーの２文字目が「c」であり、入力キーの２文字目が「a」であるため、タグキーの優先度の方が、入力キーの優先度よりも大きくなる。
【０１５７】
トライ木生成部２５０ａは、ポインタ配列２１の「TAG」に接続された全文字列「abc」と、入力キー「aba」とを比較して、一致する文字列を判定する。一致する文字数は、最小一致長と同じなので、トライ木生成部２５０ａは、一致データ数を２に設定する。トライ木生成部２５０ａは、一致データ数が、第２閾値以上となるので、新階層作成処理を開始する（ステップＳ５３ｂ）。
【０１５８】
続いて、図３８に移行する。トライ木生成部２５０ａは、ノードaの親ノードがルートノードであるため、ルートノードｂを新たに生成する。また、トライ木生成部２５０ａは、尾ノードに設定したノードbの子ノードf、ノードgをルートノードｂに接続し、ノードbとノードf、ノードgの接続を解除する（ステップＳ５４ａ）。
【０１５９】
実データ上において、トライ木生成部２５０ａは、ルートノードｂに対応するポインタ配列２５を作成し、ポインタ配列２５のキー番号「０×６６」で、ポインタ配列２５とポインタ配列２３を接続する。トライ木生成部２５０ａは、ポインタ配列２５のキー番号「０×６７」で、ポインタ配列２５とポインタ配列２４を接続する。また、トライ木生成部２５０ａは、ポインタ配列２２とポインタ配列２３の接続およびポインタ配列２２とポインタ配列２４の接続を解除する（ステップＳ５４ｂ）。
【０１６０】
続いて、図３９に移行する。トライ木生成部２５０ａは、入力キーのポインタを一致数分だけ進める。ノードａのタグキーは「bc」と、入力キーからトライ部分「a」を取り除いた文字列「ba」とを比較すると、一致数が１となるので、トライ木生成部２５０ａは、入力キーのポインタを１文字進め、３文字目の「a」に設定する。
【０１６１】
トライ木生成部２５０ａは、入力キーのポインタに設定された文字「a」に対応するノードaを生成し、ルートノードｂとノードaを接続する。また、トライ木生成部２５０ａは、ノードaにタグキー「空」を接続する（ステップＳ５５ａ）。
【０１６２】
実データ上において、トライ木生成部２５０ａは、ノードａの「TAG」に接続された文字列「bc」と、入力キーのポインタに接続された文字列「ba」とを比較すると、一致数が１となる。トライ木生成部２５０ａは、入力キーのポインタを、１行目２０列目の「a」に接続する。
【０１６３】
トライ木生成部２５０ａは、ノードaに対応するポインタ配列２６を生成し、ポインタ配列２６の「TAG」に「空」を接続する。トライ木生成部２５０ａは、ポインタ配列２５のキー番号「０×６１」で、ポインタ配列２５とポインタ配列２６を接続する（ステップＳ５５ｂ）。
【０１６４】
続いて、図４０に移行する。トライ木生成部２５０ａは、トライ部分「a」とノードaのタグキー「bc」を加算した文字列「abc」から、ルートノードaから尾ノードbに至るトライ部分「ab」を取り除いた文字列「c」を判定する。
【０１６５】
トライ木生成部２５０ａは、文字列「c」に対応するノードcを生成し、ルートノードｂとノードcを接続する。また、トライ木生成部２５０ａは、ノードcにタグキー「空」を接続する（ステップＳ５６ａ）。
【０１６６】
実データ上において、トライ木生成部２５０ａは、ポインタ配列２１の「TAG」に接続された全文字列「abc」から、ポインタ配列２０からポインタ配列２２に至るトライ部分「ab」を取り除いた文字列「c」を判定する。
【０１６７】
トライ木生成部２５０ａは、ノードcに対応するポインタ配列２７を生成し、ポインタ配列２５のキー番号「０×６３」で、ポインタ配列２５とポインタ配列２７を接続する。トライ木生成部２５０ａは、ポインタ配列２７の「TAG」を、テキスト表５０の１行目４列目の「空」に接続する（ステップＳ５６ｂ）。
【０１６８】
続いて、図４１に移行する。トライ木生成部２５０ａは、ノードaとルートノードｂを接続し、一致文字列「ab」をノードaに登録する。ここでは、一致文字数「ab」からトライ部分「a」を取り除いた「b」をノードaに接続する（ステップＳ５７ａ）。
【０１６９】
実データ上において、トライ木生成部２５０ａは、ポインタ配列２１の「Next」とポインタ配列２５を接続する。また、トライ木生成部２５０ａは、ポインタ配列２１の「TAG」をテキスト表の１行目２列目の「b」に接続する（ステップＳ５７ｂ）。
【０１７０】
続いて、図４２に移行する。トライ木生成部２５０ａは、一致データ数をデクリメントし、一致データ数を１に設定する。一致データ数が０より大きいので、トライ木生成部２５０ａは、ノードaの長男ノードとなるノードbに移行する（ステップＳ５８ａ）。
【０１７１】
実データ上において、トライ木生成部２５０ａは、一致データ数をデクリメントし、一致データ数を１に設定する。一致データ数が０より大きいので、トライ木生成部２５０ａは、ポインタ配列２１の長男ノードとなるポインタ配列２２に現在のノードを接続する（ステップＳ５８ｂ）。
【０１７２】
続いて、図４３に移行する。トライ木生成部２５０ａは、ノードbが尾ノードであるため、ノードbを削除する。トライ木生成部２５０ａは、一致データ数をデクリメントし、一致データ数を０に設定する。トライ木生成部２５０ａは、一致データ数が０となったため、新階層作成処理を終了する（ステップＳ５９ａ）。
【０１７３】
実データ上において、トライ木生成部２５０ａは、ノードbに対応するポインタ配列２２を削除し、ポインタ配列２２の「TAG」の接続を解除する。トライ木生成部２５０ａは、一致データ数をデクリメントし、一致データ数を０に設定する。トライ木生成部２５０ａは、一致データ数が０となったため、新階層作成処理を終了する（ステップＳ５９ｂ）。
【０１７４】
上述したように、トライ木生成部２５０ａが図３３〜図４３に示した処理を実行することで、各キーの共通文字列「ab」が、ノードaおよびノードaのタグキーに集約されるので、直列状態で接続されるノードの数を削減し、使用メモリ量を節約することが可能となる。
【０１７５】
図３の説明に戻ると、トライ木探索部２５０ｂは、トライ木２４０ｂに登録された値の集計値を抽出する処理、所定のキーに対応する値をトライ木２４０ｂから検出する処理を実行する処理部である。
【０１７６】
まず、トライ木探索部２５０ｂが、トライ木２４０ｂに登録された値の集計値を抽出する処理について説明する。トライ木探索部２５０ｂは、トライ木２４０ｂの各ノードを順に辿り、ノードに登録されたタグキーおよび値を対応付けて順次出力することで、集計値を抽出する。ノードに複数の値が登録されている場合には、トライ木探索部２５０ｂは、各値を合計しても良いし、別々に出力しても良い。本実施例にかかるトライ木探索部２５０ｂは、一例として、各値を合計して出力する。
【０１７７】
図４４〜図４８は、集計値を抽出する処理を説明するための図である。図４４に示すように、トライ木２４０ｂは、ルートノードａの配下に、ノードh、ノードtが順に接続されている。また、ノードhは、次の層のルートノードｂに接続されている。ルートノードｂは、ノードb、ノードcを接続する。
【０１７８】
ノードhはタグキー「ttp://aaa.aaa/e/」を登録し、ノードtは、タグキー「tp://aaa.aaa/f/」、値「６」を登録する。ルートノードｂはタグキー「空」、値「１」を登録し、ノードbはタグキー「/」、値「４」を登録し、ノードcはタグキー「/」、値「２」を登録する。
【０１７９】
実データ上では、ルートノードａ、ノードh、ノードt、ルートノードｂ、ノードb、ノードcに対応するポインタ配列２０〜２５が存在する。ポインタ配列２０の「TAG」は「空」に接続し、「Data」はNULLとなる。ポインタ配列２１の「TAG」はテキスト表５０の１行目２列目のtに接続し、「Data」はNULLとなる。
【０１８０】
ポインタ配列２２の「TAG」はテキスト表５０の６行目１１列目の「t」に接続し、「Data」は値「６」に接続する。ポインタ配列２３の「TAG」は「空」に接続し、「Data」は値「１」に接続する。ポインタ配列２４の「TAG」はテキスト表５０の５行目５列目の「/」に接続し、「Data」は値「４」に接続する。ポインタ配列２５の「TAG」はテキスト表５０の３行目１列目の「/」に接続し、「Data」は値「２」に接続する。
【０１８１】
トライ木探索部２５０ｂは、ルートノードａからノードhに遷移する。ノードhには値が存在しないので、集計値は出力されない（ステップＳ６０ａ）。実データ上において、トライ木探索部２５０ｂは、現在のノードをポインタ配列２１に接続する。ポインタ配列２１の「Data」はNULLのため、集計値は出力されない（ステップＳ６０ｂ）。
【０１８２】
続いて、図４５に移行する。トライ木探索部２５０ｂは、ノードhから次の階層のルートノードｂに移行する。ルートノードｂは、タグキー「空」と値「１」が登録されているので、トライ分部「h」とノードhのタグキー「ttp://aaa.aaa/e/」とをあわせた文字列と、値「１」を出力する（ステップＳ６１ａ）。
【０１８３】
実データ上において、トライ木探索部２５０ｂは、現在のノードをポインタ配列２３に接続する。ポインタ配列２３は、「Data」に値「１」が接続されているので、「TAG」に接続された文字列「http://aaa.aaa/e/」と、値「１」を出力する（ステップＳ６１ｂ）。
【０１８４】
続いて、図４６に移行する。トライ木探索部２５０ｂは、ルートノードｂから長男ノードのノードbに遷移する。ノードbは、タグキー「/」と値「４」が登録されている。トライ木探索部２５０ｂは、ノードhのトライ分部「h」と、ノードhのタグキー「ttp://aaa.aaa/e/」と、ノードbのトライ部分「b」と、ノードbのタグキー「/」を合わせた文字列「http://aaa.aaa/e/b/」と、値「４」を出力する（ステップＳ６２ａ）。
【０１８５】
実データ上において、トライ木探索部２５０ｂは、現在のノードをポインタ配列２４に接続する。ポインタ配列２３は、「Data」に値「４」が接続されているので、「TAG」に接続された文字列「http://aaa.aaa/e/b/」と、値「４」を出力する（ステップＳ６２ｂ）。
【０１８６】
続いて、図４７に移行する。トライ木探索部２５０ｂは、ノードbの弟ノードとなるノードcに遷移する。ノードcは、タグキー「/」と値「２」が登録されている。トライ木探索部２５０ｂは、ノードhのトライ分部「h」と、ノードhのタグキー「ttp://aaa.aaa/e/」と、ノードcのトライ部分「b」と、ノードcのタグキー「/」を合わせた文字列「http://aaa.aaa/e/c/」と、値「２」を出力する（ステップＳ６３ａ）。
【０１８７】
実データ上において、トライ木探索部２５０ｂは、現在のノードをポインタ配列２５に接続する。ポインタ配列２５は、「Data」に値「２」が接続されているので、「TAG」に接続された文字列「http://aaa.aaa/e/c/」と、値「２」を出力する（ステップＳ６３ｂ）。
【０１８８】
続いて、図４８に移行する。トライ木探索部２５０ｂは、ルートノードbの階層に未探索のノードが存在しないので、ノードhに戻り、ノードhの長男ノードとなるノードtに遷移する。ノードtは、タグキー「tp://aaa.aaa/f/」と値「６」が登録されている。トライ木探索部２５０ｂは、トライ部分「ht」とノードtのタグキー「tp://aaa.aaa/f/」を合わせた文字列「http://aaa.aaa/f/」と、値「６」を出力する（ステップＳ６４ａ）。
【０１８９】
実データ上において、トライ木探索部２５０ｂは、現在のノードをポインタ配列２２に接続する。ポインタ配列２２は、「Data」に値「６」が接続されているので、「TAG」に接続された文字列「http://aaa.aaa/f/」と、値「６」を出力する（ステップＳ６４ｂ）。
【０１９０】
次に、トライ木探索部２５０ｂが、指定された入力キーに対応する値をトライ木２４０ｂから検索する処理について説明する。トライ木探索部２５０ｂは、指定された入力キーの文字を先頭から１文字ずつ読み出して、トライ木の各ノードを辿り、入力キーに対応したタグキーを有するノードを判定し、判定したノードの値を検索結果として出力する。
【０１９１】
図４９〜図５３は、検索処理を説明するための図である。図４９に示すように、トライ木２４０ｂは、ルートノードａの配下に、ノードh、ノードtが順に接続されている。また、ノードhは、次の層のルートノードｂに接続されている。ルートノードｂは、ノードb、ノードcを接続する。
【０１９２】
ノードhはタグキー「ttp://aaa.aaa/e/」を登録し、ノードtは、タグキー「tp://aaa.aaa/f/」、値「６」を登録する。ルートノードｂはタグキー「空」、値「１」を登録し、ノードbはタグキー「/」、値「４」を登録し、ノードcはタグキー「/」、値「２」を登録する。
【０１９３】
実データ上では、ルートノードａ、ノードh、ノードt、ルートノードｂ、ノードb、ノードcに対応するポインタ配列２０〜２５が存在する。ポインタ配列２０の「TAG」は「空」に接続し、「Data」はNULLとなる。ポインタ配列２１の「TAG」はテキスト表５０の１行目２列目のtに接続し、「Data」はNULLとなる。
【０１９４】
ポインタ配列２２の「TAG」はテキスト表５０の６行目１１列目の「t」に接続し、「Data」は値「６」に接続する。ポインタ配列２３の「TAG」は「空」に接続し、「Data」は値「１」に接続する。ポインタ配列２４の「TAG」はテキスト表５０の５行目５列目の「/」に接続し、「Data」は値「４」に接続する。ポインタ配列２５の「TAG」はテキスト表の３行目１列目の「/」に接続し、「Data」は値「２」に接続する。
【０１９５】
図４９〜図５３における説明では、入力キー「http://aaa.aaa/e/c」が指定された場合の検索処理について説明する。図４９において、トライ木探索部２５０ｂは、入力キーのポインタを読み出して、ノードh、ノートtの順に遷移する。トライ木探索部２５０ｂは、入力キーのポインタを３文字目の「t」に設定する（ステップＳ７０ａ）。
【０１９６】
実データ上において、トライ木探索部２５０ｂは、現在のノードをポインタ配列２２に接続する（ステップＳ７０ｂ）。
【０１９７】
続いて、図５０に移行する。トライ木探索部２５０ｂは、ノードtのタグキーの優先度と入力キーの優先度とを比較すると、入力キーの優先度の方がタグキーの優先度よりも小さいので、ノードtの親ノードとなるノードhに移行する。また、トライ木探索部２５０ｂは、入力キーのポインタを２文字目の「t」に設定する（ステップＳ７１ａ）。
【０１９８】
実データ上において、トライ木探索部２５０ｂは、ポインタ配列２２の「TAG」に接続された文字列の優先度と、入力キーのポインタ（図示略）に接続された文字列の優先度を比較すると、入力キーの優先度の方がタグキーの優先度よりも小さいので、現在のノードをポインタ配列２１に接続する（ステップＳ７１ｂ）。
【０１９９】
続いて、図５１に移行する。トライ木探索部２５０ｂは、ノードhのタグキーと、入力キーのポインタ位置以降の文字列を比較すると前方一致する。また、ノードhが次の階層のルートノードbに接続されているので、トライ木探索部２５０ｂは、ルートノードｂに遷移する。トライ木探索部２５０ｂは、入力キーのポインタを前方一致した文字１６分進めて、１８文字目の「c」に設定する（ステップＳ７２ａ）。
【０２００】
実データ上において、トライ木探索部２５０ｂは、ポインタ配列２１の「TAG」に接続された文字列と、入力キーのポインタ（図示略）に接続された文字列とを比較すると、前方一致する。また、ポインタ配列２１の「Next」がポインタ配列２３に接続されているので、現在のノードのポインタをポインタ配列２３に接続する（ステップＳ７２ｂ）。
【０２０１】
続いて、図５２に移行する。トライ木探索部２５０ｂは、入力キーのポインタに接続された文字「c」をキーにして、ノードcに遷移する。トライ木探索部２５０ｂは、入力キーのポインタを１文字進め、ポインタを「/」に設定する（ステップＳ７３ａ）。
【０２０２】
実データ上において、トライ木探索部２５０ｂは、入力キーのポインタ（図示略）に接続された文字をキーにして、ノードcに対応するポインタ配列２５に移行する（ステップＳ７３ｂ）。
【０２０３】
続いて、図５３に移行する。トライ木探索部２５０ｂは、ノードcのタグキーの優先度と、入力キーの優先度を比較すると、タグキーの優先度と、入力キーの優先度が一致するため、検索対象にヒットしたと判定する。トライ木探索部２５０ｂは、ノードcに接続された値「２」を検索結果として出力する（ステップＳ７４ａ）。
【０２０４】
実データ上において、トライ木探索部２５０ｂは、ポインタ配列２５の「TAG」に接続された文字列の優先度と、入力キーのポインタ（図示略）に接続された文字列とを比較すると、各文字列の優先度が一致するため、検索対象にヒットしたと判定する。トライ木探索部２５０ｂは、ポインタ配列２５の「Data」に接続された値「２」を出力する（ステップＳ７４ｂ）。
【０２０５】
次に、本実施例２にかかる検索装置２００の処理手順について説明する。まず、トライ木生成部２５０ａが、登録データ管理テーブル２４０ａに基づいて、トライ木２４０ｂを生成するトライ木生成処理について説明する。図５４〜図６０は、トライ木生成処理の処理手順を示すフローチャートである。
【０２０６】
図５４に示すように、トライ木生成部２５０ａは、現在のノードをルートノードに設定し、レベルを０に設定し（ステップＳ１０１）、入力キーが存在するか否かを判定する（ステップＳ１０２）。
【０２０７】
トライ木生成部２５０ａは、入力キーが存在しない場合に（ステップＳ１０３，Ｎｏ）、図５５のステップＳ１０８に移行する。一方、トライ木生成部２５０ａは、入力キーが存在する場合に（ステップＳ１０３，Ｙｅｓ）、入力キーの先頭のキーで子ノードを参照し、キーの子ノードが存在するか否かを判定する（ステップＳ１０４）。
【０２０８】
トライ木生成部２５０ａは、キーの子ノードが存在しない場合に（ステップＳ１０５，Ｎｏ）、図５５のステップＳ１０８に移行する。一方、トライ木生成部２５０ａは、キーの子ノードが存在する場合に（ステップＳ１０５，Ｙｅｓ）、入力キーから一文字読み出し、入力キーのポインタを進め、ポインタのキーで子ノードに遷移する（ステップＳ１０６）。トライ木生成部２５０ａは、レベルに１を加算し（ステップＳ１０７）、ステップＳ１０２に移行する。
【０２０９】
続いて、図５５の説明に移行する。トライ木生成部２５０ａは、最小一致長を∞（あるいは、ＦＦ＜１６進数＞）に設定し（ステップＳ１０８）、ノードのタグキーを読み出す（ステップＳ１０９）。トライ木生成部２５０ａは、NextポインタがNULLであるか否かを判定する（ステップＳ１１０）。
【０２１０】
トライ木生成部２５０ａは、NextポインタがNULLではない場合に（ステップＳ１１１，Ｎｏ）、タグキーが入力キーに前方一致するか否かを判定する（ステップＳ１１２）。トライ木生成部２５０ａは、タグキーが入力キーに前方一致しない場合に（ステップＳ１１３，Ｎｏ）、ステップＳ１１９に移行する。
【０２１１】
一方、トライ木生成部２５０ａは、タグキーが入力キーに前方一致する場合に（ステップＳ１１３，Ｙｅｓ）、入力キーのポインタを前方一致部分だけ進める（ステップＳ１１４）。トライ木生成部２５０ａは、Nextポインタの指すノードをルートノードに設定し（ステップＳ１１５）、図５４のステップＳ１０１に移行する。
【０２１２】
ところで、トライ木生成部２５０ａは、NextポインタがNULLの場合に（ステップＳ１１１，Ｙｅｓ）、タグキーの優先度と入力キーの優先度が等しいか否かを判定する（ステップＳ１１６）。トライ木生成部２５０ａは、タグキーの優先度と入力キーの優先度が等しい場合に（ステップＳ１１７，Ｙｅｓ）、現在のノードに入力値を追加する（ステップＳ１１８）。
【０２１３】
一方、トライ木生成部２５０ａは、タグキーの優先度と入力キーの優先度が異なる場合に（ステップＳ１１７，Ｎｏ）、タグキーの優先度が入力キーの優先度よりも小さいか否かを判定する（ステップＳ１１９）。
【０２１４】
トライ木生成部２５０ａは、タグキーの優先度が入力キーの優先度よりも大きい場合に（ステップＳ１２０，Ｎｏ）、図５６のステップＳ１２１に移行する。一方、トライ木生成部２５０ａは、タグキーの優先度が入力キーの優先度よりも小さい場合に（ステップＳ１２０，Ｙｅｓ）、図５７のステップＳ１３６に移行する。
【０２１５】
続いて、図５６の説明に移行する。トライ木生成部２５０ａは、レベルと一致文字数の加算値が、第１閾値以上であるか否かを判定する（ステップＳ１２１）。トライ木生成部２５０ａは、加算値が第１閾値未満の場合に（ステップＳ１２２，Ｎｏ）、一致データ数を０に設定し、最小一致長を∞に設定する（ステップＳ１２３）。
【０２１６】
トライ木生成部２５０ａは、兄ノードが存在する、または、親ノードがルートノードであるか否かを判定する（ステップＳ１２４）。トライ木生成部２５０ａは、兄ノードが存在する、または、親ノードがルートノードの場合（条件を満たす場合）に（ステップＳ１２５，Ｙｅｓ）、図５７のステップＳ１３９に移行する。
【０２１７】
トライ木生成部２５０ａは、兄ノードが存在せず、かつ、親ノードがルートノードでない場合（条件を満たさない場合）に（ステップＳ１２５，Ｎｏ）、レベルから１を減算し、入力キーのポインタを１戻し、親ノードに遷移し（ステップＳ１２６）、図５５のステップＳ１０９に移行する。
【０２１８】
ところで、トライ木生成部２５０ａは、加算値が第１閾値以上の場合に（ステップＳ１２２，Ｙｅｓ）、レベルと一致文字数の加算値が最小一致長未満であるか否かを判定する（ステップＳ１２７）。
【０２１９】
トライ木生成部２５０ａは、加算値が最小一致長以上の場合に（ステップＳ１２８，Ｎｏ）、ステップＳ１３０に移行する。トライ木生成部２５０ａは、加算値が最小一致長未満の場合に（ステップＳ１２８，Ｙｅｓ）、最小一致長の値を、レベルと一致文字数の加算値に設定する（ステップＳ１２９）。
【０２２０】
トライ木生成部２５０ａは、一致データ数に１を加算し（ステップＳ１３０）、最小一致長とレベルが等しいか否かを判定する（ステップＳ１３１）。トライ木生成部２５０ａは、最小一致長とレベルが異なる場合に（ステップＳ１３２，Ｎｏ）、ステップＳ１３４に移行する。
【０２２１】
一方、トライ木生成部２５０ａは、最小一致長とレベルが等しい場合に（ステップＳ１３２，Ｙｅｓ）、尾ノードを現在のノードに設定する（ステップＳ１３３）。トライ木生成部２５０ａは、一致データ数が第２閾値以上であるか否かを判定する（ステップＳ１３４）。
【０２２２】
トライ木生成部２５０ａは、一致データ数が第２閾値未満の場合に（ステップＳ１３５，Ｎｏ）、ステップＳ１２４に移行する。トライ木生成部２５０ａは、一致データ数が第２閾値以上の場合に（ステップＳ１３５，Ｙｅｓ）、図５８のステップＳ１４４に移行する。
【０２２３】
続いて、図５７の説明に移行する。トライ木生成部２５０ａは、入力キーの先頭文字のキーで子ノードを参照し、子ノードが存在するか否かを判定する（ステップＳ１３６）。トライ木生成部２５０ａは、子ノードが存在する場合に（ステップＳ１３７，Ｙｅｓ）、入力キーの先頭一文字を読み取り、入力キーのポインタを１文字進め、読み出した文字をキーとして子ノードへ遷移する（ステップＳ１３８）。
【０２２４】
トライ木生成部２５０ａは、現在のノードのタグキー、値、入力キー、入力値をそれぞれ交換し（ステップＳ１３９）、ステップ１３６に移行する。
【０２２５】
一方、トライ木生成部２５０ａは、子ノードが存在しない場合に（ステップＳ１３７，Ｎｏ）、新しいノードを生成し（ステップＳ１４０）、入力キーの先頭１文字を読み取り、入力キーのポインタを１文字進め、読み出した文字をキーとして、現在のノードから新しいノードへ接続する（ステップＳ１４１）。
【０２２６】
トライ木生成部２５０ａは、入力キーをタグキーとして新しいノードに付加し（ステップＳ１４２）、入力値を新しいノードに付加する（ステップＳ１４３）。
【０２２７】
続いて、図５８の説明に移行する。トライ木生成部２５０ａは、兄ノードが存在する、または、親ノードがルートノードであるか否かを判定する（ステップＳ１４４）。トライ木生成部２５０ａは、兄ノードが存在しない、かつ、親ノードがルートノードでない場合（条件を満たさない場合）に（ステップＳ１４５，Ｎｏ）、レベルから１を減算し、入力キーのポインタを１戻し、親ノードへ遷移する（ステップＳ１４６）。
【０２２８】
トライ木生成部２５０ａは、入力キーとタグキーを比較し、前方一致文字数を算出し（ステップＳ１４７）、レベルと前方一致文字数の加算値が最小一致長未満であるか否かを判定する（ステップＳ１４８）。
【０２２９】
トライ木生成部２５０ａは、レベルと前方一致文字数の加算値が最小一致長未満の場合に（ステップＳ１４９，Ｙｅｓ）、ステップＳ１５１に移行する。一方、トライ木生成部２５０ａは、レベルと前方一致文字数の加算値が最小一致長以上の場合に（ステップＳ１４９，Ｎｏ）、一致データ数に１を加算し（ステップＳ１５０）、ステップＳ１４４に移行する。
【０２３０】
ところで、トライ木生成部２５０ａは、兄ノードが存在する、または、親ノードがルートノードである場合（条件を満たす場合）に（ステップＳ１４５，Ｙｅｓ）、新しいルートノードを生成する（ステップＳ１５１）。
【０２３１】
トライ木生成部２５０ａは、尾ノードがNULLであるか否かを判定し（ステップＳ１５２）、NULLの場合に（ステップＳ１５３，Ｙｅｓ）、ステップＳ１５５に移行する。一方、トライ木生成部２５０ａは、尾ノードがNULLでない場合に（ステップＳ１５３，Ｎｏ）、尾ノードの子を、キー（タグキー、値）をそのままに新しいルートノードの子として設定し、尾ノードの子ノードのエッジを全て削除する（ステップＳ１５４）。
【０２３２】
トライ木生成部２５０ａは、ルートノードを新しいルートノードに設定し、入力キーを入力キーの先頭から最小一致長分の文字列を取り除いた文字列としてデータを追加する（ステップＳ１５５）。ステップＳ１５５におけるデータの追加処理は、図５４〜図６０に示す処理手順に従うものとする。トライ木生成部２５０ａは、図５９のステップＳ１５６に移行する。
【０２３３】
続いて、図５９の説明に移行する。トライ木生成部２５０ａは、現在のノードのタグキーのポインタを（最小一致長−レベル）だけ進める（ステップＳ１５６）。トライ木生成部２５０ａは、新しいルートノードをルートノード、タグキーを入力キー、ノードの値を入力値としてデータを追加する（ステップＳ１５７）。ステップＳ１５７におけるデータの追加処理は、図５４〜図６０に示す処理手順に従うものとする。
【０２３４】
トライ木生成部２５０ａは、現在のノードのNextポインタを、追加したノードに付加し（ステップＳ１５８）、現在のノードのNextポインタを新しいルートノードに、タグキーを入力キーの先頭から最小一致長分に、値をNULLに設定する（ステップＳ１５９）。
【０２３５】
トライ木生成部２５０ａは、一致データ数から１を減算し（ステップＳ１６０）、一致データ数が０であるか否かを判定する（ステップＳ１６１）。トライ木生成部２５０ａは、一致データ数が０の場合に（ステップＳ１６２，Ｙｅｓ）、処理を終了する。
【０２３６】
一方、トライ木生成部２５０ａは、一致データ数が０でない場合に（ステップＳ１６２，Ｎｏ）、長男ノードに遷移し、レベルに１を加算する（ステップＳ１６３）。トライ木生成部２５０ａは、現在のノードのタグキーのポインタを（最小一致長−レベル）だけ進める（ステップＳ１６４）。
【０２３７】
トライ木生成部２５０ａは、新しいルートノードをルートノード、タグキーを入力キー、ノードの値を入力値としてデータを追加する（ステップＳ１６５）。ステップＳ１６５におけるデータの追加処理は、図５４〜図６０に示す処理手順に従うものとする。
【０２３８】
トライ木生成部２５０ａは、現在のノードのNextポインタを、追加したノードに付加し（ステップＳ１６６）、削除親ノードを親ノードに設定し（ステップＳ１６７）、図６０のステップＳ１６８に移行する。
【０２３９】
続いて、図６０に移行する。トライ木生成部２５０ａは、子ノードが存在するか否かを判定する（ステップＳ１６８）。トライ木生成部２５０ａは、子ノードが存在しない場合に（ステップＳ１６９，Ｎｏ）、親ノードの現在のノードへのエッジを削除し、現在のノードを削除する（ステップＳ１７０）。
【０２４０】
トライ木生成部２５０ａは、現在のノードを削除親ノードに設定し（ステップＳ１７１）、一致データ数から１を減算し（ステップＳ１７２）、図５９のステップＳ１６１に移行する。なお、子ノードが存在する場合に（ステップＳ１６９，Ｙｅｓ）、現在のノードのデータを長男ノードのデータに設定し（ステップＳ１７３）、現在のノードのタグキーを、長男ノードへのキーと長男ノードのタグキーを連結した文字列に設定し（ステップＳ１７４）、長男ノードへ遷移し（ステップＳ１７５）、ステップＳ１６８に移行する。
【０２４１】
次に、トライ木探索部２５０ｂがトライ木２４０ｂから入力キーに対応する値を検索する検索処理の処理手順について説明する。図６１、図６２は、検索処理の処理手順を示すフローチャートである。
【０２４２】
図６１に示すように、トライ木探索部２５０ｂは、現在のノードをルートノードに設定し、深さ（レベル）を０に設定し（ステップＳ２０１）、入力キーが存在するか否かを判定する（ステップＳ２０２）。
【０２４３】
トライ木探索部２５０ｂは、入力キーが存在しない場合に（ステップＳ２０３，Ｎｏ）、図６１のステップＳ２０８に移行する。一方、トライ木探索部２５０ｂは、入力キーが存在する場合に（ステップＳ２０３，Ｙｅｓ）、入力キーの先頭のキーで子ノードを参照し、キーの子ノードが存在するか否かを判定する（ステップＳ２０４）。
【０２４４】
トライ木探索部２５０ｂは、キーの子ノードが存在しない場合に（ステップＳ２０５，Ｎｏ）、図６１のステップＳ２０８に移行する。一方、トライ木探索部２５０ｂは、キーの子ノードが存在する場合に（ステップＳ２０５，Ｙｅｓ）、入力キーから一文字読み出し、入力キーのポインタを進め、ポインタのキーで子ノードに遷移する（ステップＳ２０６）。トライ木探索部２５０ｂは、深さに１を加算し（ステップＳ２０７）、ステップＳ２０２に移行する。
【０２４５】
続いて、図６２の説明に移行する。トライ木探索部２５０ｂは、ノードのタグキーを読み出し、NextポインタがNULLであるか否かを判定する（ステップＳ２０８）。トライ木探索部２５０ｂは、NextポインタがNULLではない場合に（ステップＳ２０９，Ｎｏ）、タグキーが入力キーに前方一致するか否かを判定する（ステップＳ２１０）。
【０２４６】
トライ木探索部２５０ｂは、前方一致しない場合に（ステップＳ２１１，Ｎｏ）、ステップＳ２１７に移行する。一方、トライ木探索部２５０ｂは、前方一致する場合に（ステップＳ２１１，Ｙｅｓ）、入力キーのポインタを前方一致分だけ進める（ステップＳ２１２）。トライ木探索部２５０ｂは、Nextポインタの示すノードをルートノードに設定し（ステップＳ２１３）、図６１のステップＳ２０１に移行する。
【０２４７】
ところで、トライ木探索部２５０ｂは、NextポインタがNULLの場合に（ステップＳ２０９，Ｙｅｓ）、タグキーの優先度と入力キーの優先度が等しいか否かを判定する（ステップＳ２１４）。トライ木探索部２５０ｂは、タグキーと入力キーが等しい場合に（ステップＳ２１５，Ｙｅｓ）、現在のノードのデータ（値）を出力する（ステップＳ２１６）。
【０２４８】
一方、トライ木探索部２５０ｂは、タグキーと入力キーが異なる場合に（ステップＳ２１５，Ｎｏ）、タグキーの優先度が入力キーの優先度未満であるか否かを判定する（ステップＳ２１７）。トライ木探索部２５０ｂは、タグキーの優先度が入力キーの優先度以上の場合に（ステップＳ２１８，Ｎｏ）、兄ノードが存在する、または、親ノードがルートノードであるか否かを判定する（ステップＳ２２０）。
【０２４９】
トライ木探索部２５０ｂは、兄ノードが存在せず、かつ、親ノードがルートノードではない場合に（ステップＳ２２１，Ｎｏ）、深さから１を減算し、入力キーのポインタを１戻し、親ノードへ遷移し（ステップＳ２２２）、ステップＳ２０８に移行する。
【０２５０】
次に、トライ木生成部２５０ａが、トライ木２４０ｂからデータを削除する削除処理について説明する。図６３〜図６５は、削除処理の処理手順を示すフローチャートである。図６３に示すように、トライ木生成部２５０ａは、現在のノードをルートノードに設定し、深さ（レベル）を０に設定し（ステップＳ３０１）、入力キーが存在するか否かを判定する（ステップＳ３０２）。
【０２５１】
トライ木生成部２５０ａは、入力キーが存在しない場合に（ステップＳ３０３，Ｎｏ）、図６４のステップＳ３０８に移行する。一方、トライ木生成部２５０ａは、入力キーが存在する場合に（ステップＳ３０３，Ｙｅｓ）、入力キーの先頭のキーで子ノードを参照し、キーの子ノードが存在するか否かを判定する（ステップＳ３０４）。
【０２５２】
トライ木生成部２５０ａは、キーの子ノードが存在しない場合に（ステップＳ３０５，Ｎｏ）、図６４のステップＳ３０８に移行する。一方、トライ木生成部２５０ａは、キーの子ノードが存在する場合に（ステップＳ３０５，Ｙｅｓ）、入力キーから一文字読み出し、入力キーのポインタを進め、ポインタのキーで子ノードに遷移する（ステップＳ３０６）。トライ木生成部２５０ａは、深さに１を加算し（ステップＳ３０７）、ステップＳ３０２に移行する。
【０２５３】
続いて、図６４の説明に移行する。トライ木生成部２５０ａは、ノードのタグキーを読み出し、NextポインタがNULLであるか否かを判定する（ステップＳ３０８）。トライ木生成部２５０ａは、NextポインタがNULLではない場合に（ステップＳ３０９，Ｎｏ）、タグキーが入力キーに前方一致するか否かを判定する（ステップＳ３１０）。
【０２５４】
トライ木生成部２５０ａは、前方一致しない場合に（ステップＳ３１１，Ｎｏ）、ステップＳ３１６に移行する。一方、トライ木生成部２５０ａは、前方一致する場合に（ステップＳ３１１，Ｙｅｓ）、入力キーのポインタを前方一致分だけ進める（ステップＳ３１２）。トライ木生成部２５０ａは、Nextポインタの指すノードをルートノードに設定し（ステップＳ３１３）、図６３のステップＳ３０１に移行する。
【０２５５】
ところで、トライ木生成部２５０ａは、NextポインタがNULLである場合に（ステップＳ３０９，Ｙｅｓ）、タグキーの優先度と入力キーの優先度が等しいか否かを判定する（ステップＳ３１４）。トライ木生成部２５０ａは、タグキーの優先度と入力キーの優先度が等しい場合に（ステップＳ３１５，Ｙｅｓ）、図６５のステップＳ３２２に移行する。
【０２５６】
一方、トライ木生成部２５０ａは、タグキーの優先度と入力キーの優先度が異なる場合に（ステップＳ３１５，Ｎｏ）、タグキーの優先度が入力キーの優先度未満であるか否かを判定する（ステップＳ３１６）。
【０２５７】
トライ木生成部２５０ａは、タグキーの優先度が入力キーの優先度未満の場合に（ステップＳ３１７，Ｙｅｓ）、一致データなしを出力する（ステップＳ３１８）。一方、トライ木生成部２５０ａは、タグキーの優先度が入力キーの優先度よりも大きい場合に（ステップＳ３１７，Ｎｏ）、兄ノードが存在する、または、親ノードがルートノードであるか否かを判定する（ステップＳ３１９）。
【０２５８】
トライ木生成部２５０ａは、兄ノードが存在する、または、親ノードがルートノードの場合（条件を満たす場合）に（ステップＳ３２０，Ｙｅｓ）、ステップＳ３１８に移行する。
【０２５９】
一方、トライ木生成部２５０ａは、兄ノードが存在しない、かつ、親ノードがルートノードではない場合（条件を満たさない場合）に（ステップＳ３２０，Ｎｏ）、深さから１を減算し、入力キーのポインタを１戻し、親ノードへ遷移し（ステップＳ３２１）、ステップＳ３０８に移行する。
【０２６０】
続いて、図６５の説明に移行する。トライ木生成部２５０ａは、削除対象データが存在するか否かを判定する（ステップＳ３２２）。トライ木生成部２５０ａは、削除データが存在しない場合に（ステップＳ３２３，Ｎｏ）、削除データなしを出力する（ステップＳ３２４）。
【０２６１】
トライ木生成部２５０ａは、削除対象データが存在する場合に（ステップＳ３２３，Ｙｅｓ）、対象データを削除し（ステップＳ３２５）、他のデータ（値）がノードに存在するか否かを判定する（ステップＳ３２６）。トライ木生成部２５０ａは、データが存在する場合に（ステップＳ３２７，Ｙｅｓ）、処理を終了する。
【０２６２】
一方、トライ木生成部２５０ａは、データが存在しない場合に（ステップＳ３２７，Ｎｏ）、子ノードが存在するか否かを判定する（ステップＳ３２８）。トライ木生成部２５０ａは、子ノードが存在しない場合に（ステップＳ３２９，Ｎｏ）、親ノードの現在のノードへのエッジを削除し、現在のノードを削除する（ステップＳ３３０）。
【０２６３】
一方、トライ木生成部２５０ａは、子ノードが存在する場合に（ステップＳ３２９，Ｙｅｓ）、現在のノードのデータを長男ノードのデータに設定する（ステップＳ３３１）。トライ木生成部２５０ａは、現在のノードのタグキーを、長男ノードへのキーと長男ノードのタグキーとを連結した文字列に設定し（ステップＳ３３２）、長男ノードへ遷移し（ステップＳ３３３）、ステップＳ３２８に移行する。
【０２６４】
次に、トライ木探索部２５０ｂが、トライ木の集計値を出力する集計処理について説明する。図６６は、集計処理の処理手順を示すフローチャートである。図６６に示すように、トライ木探索部２５０ｂは、現在のノードをルートノードに設定し（ステップＳ４０１）、NextポインタがNULLか否かを判定する（ステップＳ４０２）。
【０２６５】
トライ木探索部２５０ｂは、NextポインタがNULLではない場合に（ステップＳ４０３，Ｎｏ）、Nextポインタへ遷移し（ステップＳ４０４）、ノードにデータ（値）が存在するか否かを判定する（ステップＳ４０５）。
【０２６６】
トライ木探索部２５０ｂは、ノードにデータが存在しない場合に（ステップＳ４０６，Ｎｏ）、ステップＳ４０２に移行する。一方、トライ木探索部２５０ｂは、ノードにデータが存在する場合に（ステップＳ４０６）、現在のノードの各種データを加工（集計など）し出力し（ステップＳ４０７）、ステップＳ４０２に移行する。
【０２６７】
ところで、トライ木探索部２５０ｂは、NextポインタがNULLの場合に（ステップＳ４０３，Ｙｅｓ）、子ノードが存在するか否かを判定する（ステップＳ４０８）。トライ木探索部２５０ｂは、子ノードが存在する場合に（ステップＳ４０９，Ｙｅｓ）、長男ノードへ遷移し（ステップＳ４１０）、ステップＳ４０５に移行する。
【０２６８】
一方、トライ木探索部２５０ｂは、子ノードが存在しない場合に（ステップＳ４０９，Ｎｏ）、弟ノードが存在するか否かを判定する（ステップＳ４１１）。トライ木探索部２５０ｂは、弟ノードが存在する場合に（ステップＳ４１２，Ｙｅｓ）、弟ノードへ遷移し（ステップＳ４１３）、ステップＳ４０５に移行する。
【０２６９】
一方、トライ木探索部２５０ｂは、弟ノードが存在しない場合に（ステップＳ４１２，Ｎｏ）、親ノードへ遷移し（ステップＳ４１４）、現在のノードがルートノードであるか否かを判定する（ステップＳ４１５）。
【０２７０】
トライ木探索部２５０ｂは、現在のノードがルートノードではない場合に（ステップＳ４１６，Ｎｏ）、ステップＳ４１１に移行する。トライ木探索部２５０ｂは、現在のノードがルートノードの場合に（ステップＳ４１６，Ｙｅｓ）、一つ前の階層が存在するか否かを判定する（ステップＳ４１７）。
【０２７１】
トライ木探索部２５０ｂは、一つ前の階層が存在しない場合には（ステップＳ４１８，Ｎｏ）、処理を終了する。一方、トライ木探索部２５０ｂは、一つ前の階層が存在する場合には（ステップＳ４１８，Ｙｅｓ）、一つ前の階層に戻り（ステップＳ４１９）、ステップＳ４０８に移行する。
【０２７２】
上述してきたように、本実施例２にかかる検索装置２００は、トライ木生成部２５０ａがトライ木２４０ｂを生成する場合に、入力キーと、辿った経路に含まれる各ノードのキーとを比較し、入力キーの文字列と一致する文字数が第１閾値以上となるキーが所定の第２閾値以上存在する場合に、一致した文字列に対応する前方一致タグを作成してルートノードに接続する。そして、トライ木生成部２５０ａは、入力キーおよび各ノードのキーから、一致した文字列を取り除いた残りの文字列を、部分トライ木に接続し、ルートノードと部分トライ木を接続することで、トライ木２４０ｂを生成する。従って、各キーの共通文字列が、ルートノードに集約されるので、直列状態で接続されるノードの数を削減し、使用メモリ量を節約することが可能となる。
【０２７３】
ところで、本実施例において説明した各処理のうち、自動的におこなわれるものとして説明した処理の全部または一部を手動的におこなうこともでき、あるいは、手動的におこなわれるものとして説明した処理の全部または一部を公知の方法で自動的におこなうこともできる。この他、上記文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
【０２７４】
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。さらに、各装置にて行なわれる各処理機能は、その全部または任意の一部が、ＣＰＵおよび当該ＣＰＵにて解析実行されるプログラムにて実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。
【０２７５】
図６７は、実施例２に示した検索装置２００（あるいは、実施例１にかかるトライ木文字列登録装置１００）に対応するコンピュータのハードウェア構成を示す図である。図６７に示すように、このコンピュータ（検索装置）１０は、入力装置１１、モニタ１２、ＲＡＭ（Random  Access  Memory）１３、ＲＯＭ（Read  Only  Memory）１４、ネットワークを介して他の装置とデータ通信を実行する通信制御装置１５、媒体読取装置１６、ＣＰＵ（Central  Processing  Unit）１７、ＨＤＤ（Hard  Disk  Drive）１８をバス１９で接続している。
【０２７６】
そして、ＨＤＤ１８には、上述した検索装置２００の機能と同様の機能を発揮するトライ木生成プログラム１８ｂ、トライ木探索プログラム１８ｃが記憶されている。ＣＰＵ１７が、トライ木生成プログラム１８ｂ、トライ木探索プログラム１８ｃを読み出して実行することにより、トライ木生成プロセス１７ａ、トライ木探索プロセス１７ｂが起動される。
【０２７７】
ここで、トライ木生成プロセス１７ａは、図３に示したトライ木生成部２５０ａに対応する。また、トライ木探索プロセス１７ｂは、図３に示したトライ木探索部２５０ｂに対応する。
【０２７８】
なお、ＨＤＤ１８は、図３で示した記憶部２４０に記憶されたデータに対応する各種データ１８ａを記憶している。ＣＰＵ１７は、ＨＤＤ１８に記憶された各種データ１８ａをＲＡＭ１３に読み出し、各種データ１３ａを利用して、トライ木の構築等を実行する。
【符号の説明】
【０２７９】
１０    コンピュータ
１１    入力装置
１２    モニタ
１３    ＲＡＭ
１３ａ，１８ａ  各種データ
１４    ＲＯＭ
１５    通信制御装置
１６    媒体読取装置
１７    ＣＰＵ
１７ａ  トライ木生成プロセス
１７ｂ  トライ木探索プロセス
１８ｂ  トライ木生成プログラム
１８ｃ  トライ木探索プログラム
１８    ＨＤＤ
１９    バス
１００    トライ木文字列登録装置
１１０    記憶部
１１０ａ  トライ木
１２０    計数部
１３０    制御部
２００    検索装置
２１０    入力部
２２０    出力部
２３０    入出力制御部
２４０    記憶部
２４０ａ  登録データ管理テーブル
２４０ｂ  トライ木
２５０    制御部
２５０ａ  トライ木生成部
２５０ｂ  トライ木探索部
【図１】
2010277544.tif 000003
【図２】
2010277544.tif 000004
【図３】
2010277544.tif 000005
【図４】
2010277544.tif 000006
【図５】
2010277544.tif 000007
【図６】
2010277544.tif 000008
【図７】
2010277544.tif 000009
【図８】
2010277544.tif 000010
【図９】
2010277544.tif 000011
【図１０】
2010277544.tif 000012
【図１１】
2010277544.tif 000013
【図１２】
2010277544.tif 000014
【図１３】
2010277544.tif 000015
【図１４】
2010277544.tif 000016
【図１５】
2010277544.tif 000017
【図１６】
2010277544.tif 000018
【図１７】
2010277544.tif 000019
【図１８】
2010277544.tif 000020
【図１９】
2010277544.tif 000021
【図２０】
2010277544.tif 000022
【図２１】
2010277544.tif 000023
【図２２】
2010277544.tif 000024
【図２３】
2010277544.tif 000025
【図２４】
2010277544.tif 000026
【図２５】
2010277544.tif 000027
【図２６】
2010277544.tif 000028
【図２７】
2010277544.tif 000029
【図２８】
2010277544.tif 000030
【図２９】
2010277544.tif 000031
【図３０】
2010277544.tif 000032
【図３１】
2010277544.tif 000033
【図３２】
2010277544.tif 000034
【図３３】
2010277544.tif 000035
【図３４】
2010277544.tif 000036
【図３５】
2010277544.tif 000037
【図３６】
2010277544.tif 000038
【図３７】
2010277544.tif 000039
【図３８】
2010277544.tif 000040
【図３９】
2010277544.tif 000041
【図４０】
2010277544.tif 000042
【図４１】
2010277544.tif 000043
【図４２】
2010277544.tif 000044
【図４３】
2010277544.tif 000045
【図４４】
2010277544.tif 000046
【図４５】
2010277544.tif 000047
【図４６】
2010277544.tif 000048
【図４７】
2010277544.tif 000049
【図４８】
2010277544.tif 000050
【図４９】
2010277544.tif 000051
【図５０】
2010277544.tif 000052
【図５１】
2010277544.tif 000053
【図５２】
2010277544.tif 000054
【図５３】
2010277544.tif 000055
【図５４】
2010277544.tif 000056
【図５５】
2010277544.tif 000057
【図５６】
2010277544.tif 000058
【図５７】
2010277544.tif 000059
【図５８】
2010277544.tif 000060
【図５９】
2010277544.tif 000061
【図６０】
2010277544.tif 000062
【図６１】
2010277544.tif 000063
【図６２】
2010277544.tif 000064
【図６３】
2010277544.tif 000065
【図６４】
2010277544.tif 000066
【図６５】
2010277544.tif 000067
【図６６】
2010277544.tif 000068
【図６７】
2010277544.tif 000069
【図６８】
2010277544.tif 000070
【図６９】
2010277544.tif 000071
【図７０】
2010277544.tif 000072
【図７１】
2010277544.tif 000073
【図７２】
2010277544.tif 000074