(57)【要約】【課題】メモリ使用量を削減すること。【解決手段】検索装置２００がトライ木２４０ｂを生成する場合には、子ノードのタグキーと親ノードのタグキーとを比較する。そして、検索装置２００は、親ノードにタグキーを登録する場合に、全てのタグキーを登録するのではなく、子ノードと一致しない部分の文字列のみを親ノードに登録する。また、検索装置２００は、子ノードのタグキーと親ノードのタグキーと一致する部分の文字数もあわせて親ノードに登録する。【選択図】図５６
2010231643.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータに、
所定の文字に対応するノードが木構造にて接続されるトライ木を記憶装置に記憶し、当該トライ木に新規の文字列を登録する場合に、当該新規の文字列の文字を先頭から順に読み出して前記トライ木に含まれるノードを当該ノードに対応する文字に応じて辿り、単一のノードに対して単一の文字列が登録されるように、辿ったノードの何れかに新規の文字列を登録する場合に、登録対象のノードの子ノードに登録された文字列と新規の文字列とを比較して一致する文字を判定し、新規の文字列から一致する文字を除いた残りの文字列と一致文字数を、登録対象のノードに登録する文字列登録機能
を実現させるためのプログラムを格納した記憶媒体。
【請求項２】
前記文字列登録機能は、各ノードに登録される各文字列に対して所定の文字順序に基づく優先度を設定し、当該優先度に基づいて各ノードに各文字列を登録することを特徴とする請求項１に記載の記憶媒体。
【請求項３】
前記文字列登録機能は、ノードに登録された文字列の優先度と、新規の文字列の優先度とを比較して、登録されたノードの文字列の優先度よりも新規の文字列の優先度の方が小さい場合に、登録された文字列と新規の文字列で一致する文字数を判定する判定機能と、前記ノードの親ノードに遷移し、前記判定機能で判定した一致する文字数と、前記親ノードに登録された一致文字数とを基にして、新規のノードを前記親ノードに登録するか否かを判定する登録機能を更に実現させるためのプログラムを格納した請求項１または２に記載の記憶媒体。
【請求項４】
検索文字列を検索する場合に、ノードに登録された文字列と、該検索文字列とを比較して、各文字列が一致しない場合に、登録された文字列と該検索文字列で一致する文字数を判定する検索判定機能と、前記ノードの親ノードに遷移し、前記検索判定機能で判定した一致する文字数に応じて、該検索文字列と前記親ノードの文字列の一部を除いた後に、各文字列が一致するか否かを判定する一致判定機能を更に実現させるためのプログラムを格納した記憶媒体。
【請求項５】
検索装置が、
所定の文字に対応するノードが木構造にて接続されるトライ木を記憶装置に記憶するステップと、
前記記憶装置に記憶されたトライ木に新規の文字列を登録する場合に、当該新規の文字列の文字を先頭から順に読み出して前記トライ木に含まれるノードを当該ノードに対応する文字に応じて辿り、単一のノードに対して単一の文字列が登録されるように、辿ったノードの何れかに新規の文字列を登録する場合に、登録対象のノードの子ノードに登録された文字列と新規の文字列とを比較して一致する文字を判定し、新規の文字列から一致する文字を除いた残りの文字列と一致文字数を、登録対象のノードに登録するステップと
を含んだことを特徴とするトライ木生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、トライ木を用いて各種の処理を行うトライ木生成装置等に関する。
【背景技術】
【０００２】
文書検索システムにおいて、キーから所望の文書、値等を高速に検索するべく、トライ木が用いられている（例えば、特許文献１、２参照）。図９０は、従来のトライ木の一例を示す図である。このトライ木は、ルートノードを除くノードに対して、１文字あたり１ノードを割当てることにより、木構造を構築している。また、図９０に示すトライ木は、キー「black、green、blue、grey、black、grey、greenyellow」にそれぞれ値「１、３、４、５、３、２、１」が割当てられたトライ木を示している。
【０００３】
従来の検索装置が、トライ木の検索処理を実行する場合には、入力キーを１文字ずつ取り出し、トライ木上の同じキーのノードを辿る。例えば、検索装置は、入力キー「blue」が指定された場合には、トライ木のノードをノードb、l、u、eの順に辿ることで、「blue」に割当てられた「４」を検出する。
【０００４】
ところで、図９０に示したトライ木では、トライ木を構築するキーが長い場合に、ノード数が増えてしまい、使用メモリ量が増大してしまうという問題があった。また、キーが長い場合に、検索処理時に比較するノード数が増えてしまい、検索処理等が完了するまでの時間が長くなってしまうという問題が発生する。
【０００５】
そこで、かかるトライ木の問題点を解消するべく、パトリシア木（Patricia  Tree）と呼ばれるトライ木が考案されている（例えば、非特許文献１参照）。図９１は、パトリシア木の一例を示す図である。このパトリシア木は、ノードから他のノードへ遷移するエッジ部を、文字ではなく文字列で表現することで、使用メモリ量を削減している。なお、図９１に示すパトリシア木は、キー「black、green、blue、grey、black、grey、greenyellow」にそれぞれ値「１、３、４、５、３、２、１」が割当てられたパトリシア木を示している。
【０００６】
従来の検索装置が、トライ木の検索処理を実行する場合には、入力キーとエッジ部の文字列とを順次比較し、パトリシア木を辿る。例えば、検索装置は、入力キー「blue」が指定された場合には、パトリシア木のエッジ部をbl、ueの順に辿ることで、「blue」に割当てられた「４」を検出する。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開昭５９−４７６６９号公報
【特許文献２】特開平１１−７４５１号公報
【非特許文献】
【０００８】
【非特許文献１】“基数木”、［online］、［平成２１年２月２５日検索］、インターネット＜http://ja.wikipedia.org/wiki/%E5%9F%BA%E6%95%B0%E6%9C%A8＞
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、上述したパトリシア木は、通常のトライ木と比較してメモリ使用量の問題等を解消することができるものの、所定の文字列毎にノードを作成する必要があるため、キーの文字数が多い場合には、メモリ使用量が増大してしまうという問題があった。
【００１０】
そこで、この発明は、上述した従来技術の課題を解決するためになされたものであり、メモリ使用量を削減することができる記憶媒体およびトライ木生成方法を提供することを目的とする。
【課題を解決するための手段】
【００１１】
上述した課題を解決し、目的を達成するため、この記憶媒体は、コンピュータに、所定の文字に対応するノードが木構造にて接続されるトライ木を記憶装置に記憶し、当該トライ木に新規の文字列を登録する場合に、当該新規の文字列の文字を先頭から順に読み出して前記トライ木に含まれるノードを当該ノードに対応する文字に応じて辿り、単一のノードに対して単一の文字列が登録されるように、辿ったノードの何れかに新規の文字列を登録する場合に、登録対象のノードの子ノードに登録された文字列と新規の文字列とを比較して一致する文字を判定し、新規の文字列から一致する文字を除いた残りの文字列と一致文字数を、登録対象のノードに登録する文字列登録機能を実現させるためのプログラムを格納することを要件とする。
【発明の効果】
【００１２】
この記憶媒体が記憶するプログラムを実行することで、コンピュータは、１ノードにタグキーを１つ対応付け、タグキーを有さないノードを無くすので、メモリ使用効率を向上させることが出来る。
【図面の簡単な説明】
【００１３】
【図１】図１は、木構造に含まれるノードの用語を説明するための図である。
【図２】図２は、本実施例にかかる検索装置の概要を説明するための図（１）である。
【図３】図３は、本実施例にかかる検索装置の概要を説明するための図（２）である。
【図４】図４は、比較対象ノードを説明するための図である。
【図５】図５は、新規のキーをトライ木に登録する処理を説明するための図である。
【図６】図６は、タグキーをトライ部分のキーを削除した形で保持するトライ木の一例を示す図である。
【図７】図７は、従来のパトリシア木のデータ構造による使用メモリ量と、本願発明にかかるトライ木の使用メモリ量とを示す図（１）である。
【図８】図８は、リーフノードからポインタ配列を削除した場合のトライ木を示す図である。
【図９】図９は、図８および図６に示した手法を用いてメモリ量を削減した場合の、従来のパトリシア木のデータ構造による使用メモリ量と、本実施例にかかるトライ木の使用メモリ量とを示す図である。
【図１０】図１０は、本実施例１にかかる検索装置の構成を示す図である。
【図１１】図１１は、本実施例１にかかる登録データ管理テーブルのデータ構造の一例を示す図である。
【図１２】図１２は、本実施例２にかかるトライ木のデータ構造の一例を示す図である。
【図１３−１】図１３−１は、図１２に示したトライ木を実データで表した場合のデータ構造の一例を示す図である。
【図１３−２】図１３−２は、トライ木のその他のデータ構造の一例を示す図である。
【図１４】図１４は、トライ木生成部がトライ木を生成する処理の概要を説明するための図である。
【図１５】図１５は、トライ木を生成する処理を説明するための図（１）である。
【図１６】図１６は、トライ木を生成する処理を説明するための図（２）である。
【図１７】図１７は、トライ木を生成する処理を説明するための図（３）である。
【図１８】図１８は、トライ木を生成する処理を説明するための図（４）である。
【図１９】図１９は、トライ木を生成する処理を説明するための図（５）である。
【図２０】図２０は、トライ木を生成する処理を説明するための図（６）である。
【図２１】図２１は、トライ木を生成する処理を説明するための図（７）である。
【図２２】図２２は、トライ木を生成する処理を説明するための図（８）である。
【図２３】図２３は、トライ木を生成する処理を説明するための図（９）である。
【図２４】図２４は、トライ木を生成する処理を説明するための図（１０）である。
【図２５】図２５は、集計値を抽出する処理を説明するための図（１）である。
【図２６】図２６は、集計値を抽出する処理を説明するための図（２）である。
【図２７】図２７は、集計値を抽出する処理を説明するための図（３）である。
【図２８】図２８は、二分探索法を用いた場合の検索処理を説明するための図（１）である。
【図２９】図２９は、二分探索法を用いた場合の検索処理を説明するための図（２）である。
【図３０】図３０は、二分探索法を用いた場合の検索処理を説明するための図（３）である。
【図３１】図３１は、二分探索法を用いた場合の検索処理を説明するための図（４）である。
【図３２】図３２は、二分探索法を用いた場合の検索処理を説明するための図（５）である。
【図３３】図３３は、二分探索法を用いた場合の検索処理を説明するための図（６）である。
【図３４】図３４は、二分探索法を用いた場合の検索処理を説明するための図（７）である。
【図３５】図３５は、二分探索法を用いた場合の検索処理を説明するための図（８）である。
【図３６】図３６は、二分探索法を用いない場合の探索処理を説明するための図（１）である。
【図３７】図３７は、二分探索法を用いない場合の探索処理を説明するための図（２）である。
【図３８】図３８は、二分探索法を用いない場合の探索処理を説明するための図（３）である。
【図３９】図３９は、二分探索法を用いない場合の探索処理を説明するための図（４）である。
【図４０】図４０は、二分探索法を用いない場合の探索処理を説明するための図（５）である。
【図４１】図４１は、削除処理を説明するための図である。
【図４２】図４２は、本実施例１にかかるトライ木生成処理の処理手順を示すフローチャートである。
【図４３】図４３は、二分探索法を用いないデータ追加処理の処理手順を示すフローチャート（１）である。
【図４４】図４４は、二分探索法を用いないデータ追加処理の処理手順を示すフローチャート（２）である。
【図４５】図４５は、二分探索法を用いるデータ追加処理の処理手順を示すフローチャート（１）である。
【図４６】図４６は、二分探索法を用いるデータ追加処理の処理手順を示すフローチャート（２）である。
【図４７】図４７は、二分探索法を用いるデータ追加処理の処理手順を示すフローチャート（３）である。
【図４８】図４８は、二分探索法を用いない検索処理の処理手順を示すフローチャートである。
【図４９】図４９は、二分探索法を用いる検索処理の処理手順を示すフローチャート（１）である。
【図５０】図５０は、二分探索法を用いる検索処理の処理手順を示すフローチャート（２）である。
【図５１】図５１は、集計値の抽出処理の処理手順を示すフローチャートである。
【図５２】図５２は、削除処理の処理手順を示すフローチャート（１）である。
【図５３】図５３は、削除処理の処理手順を示すフローチャート（２）である。
【図５４】図５４は、実施例１にかかる検索装置の課題を説明するための図である。
【図５５】図５５は、本実施例２にかかる検索装置の概要を説明するための図である。
【図５６】図５６は、本実施例２にかかる検索装置の構成を示す図である。
【図５７】図５７は、本実施例２にかかる登録データ管理テーブルのデータ構造の一例を示す図である。
【図５８】図５８は、本実施例２にかかるトライ木のデータ構造の一例を示す図である。
【図５９】図５９は、図５８に示したトライ木を実データで表した場合のデータ構造の一例を示す図である。
【図６０】図６０は、本実施例２にかかるトライ木を生成する処理を説明するための図（１）である。
【図６１】図６１は、本実施例２にかかるトライ木を生成する処理を説明するための図（２）である。
【図６２】図６２は、本実施例２にかかるトライ木を生成する処理を説明するための図（３）である。
【図６３】図６３は、本実施例２にかかるトライ木を生成する処理を説明するための図（４）である。
【図６４】図６４は、本実施例２にかかるトライ木を生成する処理を説明するための図（５）である。
【図６５】図６５は、本実施例２にかかるトライ木を生成する処理を説明するための図（６）である。
【図６６】図６６は、本実施例２にかかるトライ木を生成する処理を説明するための図（７）である。
【図６７】図６７は、本実施例２にかかるトライ木を生成する処理を説明するための図（８）である。
【図６８】図６８は、本実施例２にかかるトライ木を生成する処理を説明するための図（９）である。
【図６９】図６９は、本実施例２にかかるトライ木を生成する処理を説明するための図（１０）である。
【図７０】図７０は、本実施例２における集計値を抽出する処理を説明するための図（１）である。
【図７１】図７１は、本実施例２における集計値を抽出する処理を説明するための図（２）である。
【図７２】図７２は、本実施例２における集計値を抽出する処理を説明するための図（３）である。
【図７３】図７３は、本実施例２にかかる探索処理を説明するための図（１）である。
【図７４】図７４は、本実施例２にかかる探索処理を説明するための図（２）である。
【図７５】図７５は、本実施例２にかかる探索処理を説明するための図（３）である。
【図７６】図７６は、本実施例２にかかる探索処理を説明するための図（４）である。
【図７７】図７７は、本実施例２にかかる探索処理を説明するための図（５）である。
【図７８】図７８は、本実施例２にかかるトライ木生成処理の処理手順を示すフローチャートである。
【図７９】図７９は、本実施例２にかかるデータ追加処理の処理手順を示すフローチャート（１）である。
【図８０】図８０は、本実施例２にかかるデータ追加処理の処理手順を示すフローチャート（２）である。
【図８１】図８１は、本実施例２にかかるデータ追加処理の処理手順を示すフローチャート（３）である。
【図８２】図８２は、本実施例２にかかる検索処理の処理手順を示すフローチャート（１）である。
【図８３】図８３は、本実施例２にかかる検索処理の処理手順を示すフローチャート（２）である。
【図８４】図８４は、本実施例２にかかる集計値の抽出処理の処理手順を示すフローチャートである。
【図８５】図８５は、本実施例２にかかる削除処理の処理手順を示すフローチャート（１）である。
【図８６】図８６は、本実施例２にかかる削除処理の処理手順を示すフローチャート（２）である。
【図８７】図８７は、本実施例２にかかる削除処理の処理手順を示すフローチャート（３）である。
【図８８】図８８は、本実施例２にかかる削除処理の処理手順を示すフローチャート（４）である。
【図８９】図８９は、実施例２に示した検索装置に対応するコンピュータのハードウェア構成を示す図である。
【図９０】図９０は、従来のトライ木の一例を示す図である。
【図９１】図９１は、パトリシア木の一例を示す図である。
【発明を実施するための形態】
【００１４】
以下に、本願の開示する記憶媒体およびトライ木生成方法の実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。
【実施例１】
【００１５】
まず、本実施例にかかる検索装置の説明を行う前に、木構造に含まれるノードの用語について説明する。図１は、木構造に含まれるノードの用語を説明するための図である。図１に示すように、トライ木を構成する各ノードのうち、最上層に位置するノードをルートノードと定義する。また、基準ノードのひとつ上の層に存在し、基準ノードに接続されたノードを、基準ノードに対する親ノード（以下、単に親ノード）と定義する。また、基準ノードのひとつ下の層に存在し、基準ノードに接続されたノードを基準ノードに対する子供ノード（以下、単に子供ノード）と定義する。
【００１６】
また、基準ノードと同じ層に存在し、基準ノードと同じ親ノードに接続され、基準ノードの上側に存在するノードを、基準ノードに対する兄ノード（以下、単に兄ノード）と定義する。また、基準ノードと同じ層に存在し、基準ノードと同じ親ノードに接続され、基準ノードの下側に存在するノードを、基準ノードに対する弟ノード（以下、単に弟ノード）と定義する。また、根ノードから親ノードに至る各ノードをまとめて先祖ノードと定義する。また、基準ノードの配下に接続された各ノードをまとめて子孫ノードと定義する。
【００１７】
次に、本実施例にかかる検索装置の概要について説明する。図２、図３は、本実施例にかかる検索装置の概要を説明するための図である。まず、図２に示すように、本実施例にかかる検索装置は、指定されたキーに基づいてトライ木を生成する場合に、１つのノードに１つのキーを割当てる。以下の説明において、ノードに割当てられたキーをタグキーと表記する。図２において、ノードb、l、g、r、eには、それぞれタグキー「black、blue、green、grey、greenyellow」が１つずつ割当てられている。また、ノードb、l、g、r、eには、値「１、３」、「４」、「３」、「５、２」、「１」がそれぞれ割当てられている。
【００１８】
図２に示したトライ木は、図９０に示したトライ木あるいは図９１に示したパトリシア木と同じように、タグキー「black、green、blue、grey、black、grey、greenyellow」にそれぞれ値「１、３、４、５、３、２、１」を割当てている。しかし、本実施例にかかるトライ木は、図９０、９１に示したトライ木、パトリシア木と異なり、１ノードにタグキーを一つ対応付けているため、データを持っていないノードが存在せず、メモリ利用効率を高めることができる。また、本実施例にかかるトライ木は、ノードに含まれる文字数が多い場合であっても、トライ木のノード数を増加させる必要がないため、メモリ使用量を抑えることが出来る。
【００１９】
ただし、本実施例にかかるトライ木は、１つのノードに１つのタグキーを割当てた代償として、実際にノードに登録されたタグキーを参照しなければ、入力キーがタグキーにヒットしたか否かを判定できない。例えば、図２に示したトライ木では、入力キー「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」よりもルートノード側のノードに割り当てる。
【００２４】
また、「green」と「greenyellow」を比較すると、６文字目で異なる文字が抽出される。具体的には、「green」には６文字目が存在しないので「空」が抽出され、「greenyellow」から「y」が抽出される。このような場合には、検索装置は、空白が抽出されなかったキー「greenyellow」の方が「green」よりも優先度が大きいと判定する。したがって、優先度の小さい「green」を「greenyellow」よりもルートノード側のノードに割り当てる。
【００２５】
なお、本実施例では、同一の親ノードに直接接続された子（子供）ノードが複数存在する場合には、優先度の小さいキーを兄ノード側に配置し、優先度の大きいキーを弟ノード側に配置する。例えば、「black」と「green」とを比較すると、１文字目で異なる文字が抽出される。具体的には、「black」から「b」が抽出され、「green」から「g」が抽出される。そして、「b」と「g」を比較すると、「g」の方が「b」よりも優先度が大きくなる。したがって、優先度の小さい「black」を「green」よりも兄側のノードに配置する。なお、図２のように、各タグキーを割当てると、複数の子ノードを有する親ノードのタグキーと兄弟ノードのタグキーとの優先度の大小関係は、親ノードのキー＜長男ノードのキー＜次男ノードのキー＜三男ノード＜・・・となる。また、配下に接続されるノードほど優先度が大きくなる。例えば、図３において、ノードeのキーの優先度は、ノードr、gの優先度よりも大きい。
【００２６】
図３に示すように、各ノードにタグキーが配置されると、入力キーの優先度と、タグキーの優先度の関係から、検索対象となる入力キーの位置を絞り込むことが出来る。これは、入力キーと優先度が等しいタグキーを捜せばよいので、入力キーの文字により遷移する各ノードの内、入力キーよりも優先度が大きいノード以降のノード（子孫ノード）のタグキーと比較する必要は無く、入力キーよりも優先度が小さいノード以前のノード（先祖ノード）のタグキーと比較する必要が無くなるためである。
【００２７】
ここで、入力キーの文字を先頭から１文字ずつ読み出して、トライ木の各ノードを遷移し、最後に到達するノードを到達ノードと定義する。また、ルートノードから到達ノードに至る各ノードに含まれ、かつ、兄ノードを有するノードの内、優先度が最も大きいキーを有するノードを特定ノードと定義する。なお、兄ノードを有するノードが存在しない場合には、ルートノードの子ノードを特定ノードと定義する。
【００２８】
本実施例にかかる検索装置は、入力キーに一致するタグキーを検索する場合に、到達ノードから特定ノードに至る各ノードの内、いずれかを検索対象とすればよい。検索対象となるノードの中に、入力キーと一致するタグキーが存在しない場合には、その他のタグキーを参照しなくても、入力キーと一致するタグキーは存在しないと判定可能である。
【００２９】
なぜなら、特定ノードの親ノードのキーの優先度は、兄ノードのキーの優先度よりも小さく、兄ノードのキーの優先度は、弟ノード（特定ノード）のキー文字列に属する登録対象の入力キーの優先度よりも小さいからであり、入力キーが弟ノードを辿っている時点で、兄ノード側のタグキーの優先度よりも、入力キーの優先度の方が大きいことが確定するからである。
【００３０】
以下の説明において、到達ノードから特定ノードに至る各ノードを、比較対象ノードと表記する。検索装置は、入力キーと一致するキーを検索する場合には、かかる比較対象ノードのタグキーを対象として比較処理を実行すればよい。
【００３１】
図４は、比較対象ノードを説明するための図である。入力キーを先頭から１文字ずつ読みだし、最後にノード６に到達した場合には、比較対象ノードＡに含まれるノード５，６のタグキーと入力キーとを比較すればよい。
【００３２】
続いて、本実施例にかかる検索装置が、新規のキーをトライ木に登録する場合について説明する。図５は、新規のキーをトライ木に登録する処理を説明するための図である。新規のキーをトライ木に構築する場合にも、比較対象ノードのタグキーと比較処理を行い、優先度に応じて、新規のキーをトライ木に登録すればよい。
【００３３】
図５を用いて具体的に説明する。図５の左側に示すトライ木は、ノードb、i、l、uに、それぞれキー「beige、bisque、black、blueviolet」が１つずつ割当てられている。また、ノードb、i、l、uには、値「２」、「４」、「１、３」、「３」がそれぞれ割当てられている。
【００３４】
検索装置は、図５の左側に示すトライ木に、キー「blue」、値「４」を追加する場合、到達ノードは「ノードu」、特定ノードは「ノードl」となる。したがって、比較対象ノードは、ノードl、ノードu、（ノードuの配下に接続されるノード）となる。
【００３５】
登録対象ノードに接続されたキー「blueviolet」、「black」をそれぞれ「blue」と比較すると、キー「blue」の優先度は、「blueviolet」よりも小さく、「black」よりも大きいので、「blueviolet」を有するノードと、「black」を有するノードの間に「blue」を登録すればよい。この場合には、図５の右側に示すように、ノードuにキー「blue」、値「４」を割り当て、ノードuの配下にノードeを作成して、かかるノードuに「blueviolet」、値「３」を割当てる。
【００３６】
ところで、本実施例にかかる検索装置は、トライ木のメモリ使用量を更に削減するべく、ノードにタグとして付加するタグキーを、トライ部分のキーを削除した形で保持するものとする。図６は、トライ部分のキーを削除した形でタグキーを保持するトライ木の一例を示す図である。
【００３７】
例えば、ノードlにタグキー「ack」が登録されているが、これは、ノードlにタグキー「black」を登録していることと同じ意味である。ルートノードからノードｌに至るトライ部分のキーが「b、l」であるため、トライ部とタグキーとをあわせると「black」となる。
【００３８】
図６のようなデータ構造を取ることで、タグキーの文字列が減るので、入力キーと比較するタグキーの数を減らすことが出来る。また、図６のように、トライ木上にはタグキーのデータを持たずに、各ノードはタグキーへのポインタのみを保持しても良い。また、タグキーのデータを全て保持しておき、比較を開始する文字位置を変えても良い。
【００３９】
図７は、従来のパトリシア木のデータ構造による使用メモリ量と、本願発明にかかるトライ木の使用メモリ量とを示す図である。パトリシア木およびトライ木は、共に、キー「aaaaa、aacab、ababc、abacb、abcab」にそれぞれ「１、２、３、４、５」が割当てられている。
【００４０】
ここで、ノードメモリを１KB、タグキーメモリを１Byte、値メモリを４Byteとすると、パトリシア木は、ノードを１０個、タグキーを１７文字、値を５個有しているので、合計で約１０KBとなる。一方、本発明にかかるトライ木は、ノードを６ノード、タグキーを１６文字、値を４個有しているので、合計で約６KBとなる。したがって、本発明にかかるトライ木は、従来のパトリシア木と比較して、使用メモリ量を削減できる。
【００４１】
また、本実施例にかかる検索装置は、トライ木の末端ノードに対応するリーフノードからポインタ配列を削除しても構わない。ここで、ポインタ配列は、接続先のノードを示すポインタの配列である。図８は、リーフノードからポインタ配列を削除した場合のトライ木を示す図である。このように、リーフノードからポインタ配列を削除することにより、リーフノードの使用メモリ量を削減することができる。
【００４２】
図９は、図８および図６に示した手法を用いてメモリ量を削減した場合の、従来のパトリシア木のデータ構造による使用メモリ量と、本実施例にかかるトライ木の使用メモリ量とを示す図である。
【００４３】
ここで、内部ノードメモリを１KB、リーフノードメモリを１２Byte、キー１文字当たりのメモリを１Byte、値メモリを４Byteとすると、パトリシア木は、内部ノードを５個、リーフノードを５個、キーを１７文字、値を５個有しているので、合計で約５KBとなる。一方、本実施例のトライ木は、内部メモリを３個、リーフノードを３個、キーを１９文字、値を５個有しているので、合計で約３KBとなる。このように、図８および図９の手法を用いて使用メモリ使用量を削減した場合であっても、本実施例にかかるトライ木の方がパトリシア木と比較して、メモリ使用量をより多く削減することが出来る。
【００４４】
次に、本実施例にかかる検索装置の構成について説明する。図１０は、本実施例１にかかる検索装置の構成を示す図である。図１０に示すように、この検索装置１００は、入力部１１０と、出力部１２０と、入出力制御部１３０と、記憶部１４０と、制御部１５０を有する。
【００４５】
このうち、入力部１１０は、入力キー等の情報を入力する入力部であり、キーボードやマウス等に該当する。出力部１２０は、トライ木を用いた検索結果などの情報を出力する出力部であり、モニタ、若しくはディスプレイ、タッチパネル等に該当する。入出力制御部１３０は、入力部１１０、出力部１２０、記憶部１４０、制御部１５０によるデータの入出力を制御する処理部である。
【００４６】
記憶部１４０は、制御部１５０による各種処理に必要なデータおよびプログラムを記憶する記憶部である。この記憶部１４０は、登録データ管理テーブル１４０ａとトライ木１４０ｂを有する。
【００４７】
ここで、登録データ管理テーブル１４０ａは、トライ木に登録するキーと値とを対応付けて記憶するテーブルである。図１１は、本実施例１にかかる登録データ管理テーブル１４０ａのデータ構造の一例を示す図である。図１１に示すように、この登録データ管理テーブル１４０ａは、キーと値を対応付けて記憶している。
【００４８】
トライ木１４０ｂは、登録データ管理テーブル１４０ａを基にして生成されるトライ木である。図１２は、本実施例１にかかるトライ木のデータ構造の一例を示す図である。図１２では一例として、図１１に示した登録データ管理テーブル１４０ａに対応したトライ木を示す。図１２に示すように、ルートノードにノードb、ノードgが接続されており、ノードbにノードlが接続されている。
【００４９】
また、ノードbは、タグキー「eige」と値「２」が接続されている。ノードlは、タグキー「ack」と値「１、３」が接続されている。ノードgは、タグキー「reen」と値「４」が接続されている。
【００５０】
図１２に示したトライ木を実データで表すと図１３−１に示すデータ構造となる。図１３−１は、図１２に示したトライ木を実データで表した場合のデータ構造の一例を示す図である。図１３−１に示すように、このトライ木１４０ｂは、ポインタ配列１０〜１３、テキスト表１４を有している。
【００５１】
ここで、ルートノードポインタに接続されたポインタ配列１０は、図１２のルートノードに対応し、ポインタ配列１１は、図１２のノードbに対応し、ポインタ配列１２は、図１２のノードlに対応する。また、ポインタ配列１３は、図１２のノードgに対応する。
【００５２】
ポインタ配列１０〜１３は、「TAG」領域と「Data」領域を有しており、「TAG」は、テキスト表１４の文字と対応付けることで、ノードに接続されたタグキーを表現する。例えば、ポインタ配列１１は、テキスト表１４の「e」に接続されているので、「e」から次の空白前までの文字列「eige」をタグキーとして指定している。また、「Data」は、値と対応付けることで、ノードに接続された値を表現する。例えば、ポインタ配列１１は、値「２」に接続されている。
【００５３】
また、各ポインタ配列１０〜１３は、配下に接続されたポインタ配列を判定するためのキー番号（ポインタ）「０×００〜０×ＦＦ」を有している。例えば、ポインタ配列１０のキー番号「０×６２」が、ポインタ配列１１に接続され、ポインタ配列１０のキー番号「０×６７」が、ポインタ配列１３に接続されている。
【００５４】
なお、図１３−１等に示したトライ木１４０ｂの実データのデータ構造は、１ノードあたりASCIIコードの１文字にあたる８ビットの場合を示しているが、これに限定されるものではない。例えば、ASCIIコード１文字を4ビット単位の２つに分割して、１ノードあたり４ビットとしてもよい。その場合、ポインタ配列のもつキー番号は８ビットの場合に「０ｘ００〜０ｘＦＦ」の２５６個であったのに対し、４ビットの場合には「０ｘ０〜０ｘＦ」の１６個に減らすことができ、メモリ使用量を削減することが可能である。図１３−２は、トライ木１４０ｂのその他のデータ構造の一例を示す図である。
【００５５】
例えば、「beige」の場合、１ノードあたり８ビットの場合には先頭キー番号「０ｘ６２」で、ポインタ配列１１に接続されているが、１ノードあたり４ビットの場合には先頭キー番号として「０ｘ６２」の前半部分の「０ｘ６」で、図１３−２のポインタ配列XXに接続される。また、「beige」に加え「black」を続けて追加する場合、１ノードあたり８ビットの場合には２番目のキー番号「０ｘ６ｃ」でポインタ配列１２に接続されているが、１ノードあたり４ビットの場合には２番目のキー番号として「０ｘ６２」の後半部分の「０ｘ２」で、図１３−２のポインタ配列YYに接続される。なお、ポインタ配列YYはポインタ配列XXへの接続のキー番号「０ｘ６」とポインタ配列YYへの接続のキー番号「０ｘ２」とをあわせた「０ｘ６２」、すなわち「b」を表すノードである。またさらに「blue」を続けて追加する場合、１ノードあたり８ビットの場合には３番目の文字「u]のキー番号「０ｘ７５」で次のポインタ配列に接続するが、１ノードあたり４ビットの場合には３番目のキー番号として２文字目「l」のキー番号「０ｘ６ｃ」の前半部分の「０ｘ６」で次のポインタ配列に接続する。
【００５６】
また、日本語コードのようにマルチバイト文字に関しても、複数バイトを１文字として扱い、１ノードあたり１６ビットとするのではなく、１文字を複数に分割して、１ノードあたり８ビットとしたり、４ビットとしてもよい。
【００５７】
なお、現在のコンピュータにおいては直接ビット位置を指定してビット列を取り出すことはできないが、ビット位置から所望のビット列を含むバイト位置を特定し、１バイトを取り出した後、ビット処理演算を用いて所望のビット列を取り出すことで処理できる。タグキーを表す文字列を取り出すときも同様に行うことができる。
【００５８】
また別に、リーフノードに該当するポインタ配列はすべてのキー番号領域がNULLであるので、ポインタ配列の一部（キー番号領域）を省くなどして簡略化しても良い。なお、この場合には、各ポインタ配列に、自身のポインタ配列がリーフノードであるか否かを示すフラグを設定する。
【００５９】
図１０の説明に戻ると、制御部１５０は、各種の処理手順を規定したプログラムや制御データを格納するための内部メモリを有し、これらによって種々の処理を実行する制御部である。図１０に示すように、この制御部１５０は、トライ木生成部１５０ａと、トライ木探索部１５０ｂを有する。
【００６０】
トライ木生成部１５０ａは、登録データ管理テーブル１４０ａに登録されたキーに基づいて、トライ木１４０ｂを生成する処理である。なお、トライ木生成部１５０ａは、図２、図３等で説明したように、１つのノードに１つのキーを割当てることでトライ木１４０を構築する。また、トライ木生成部１５０ａは、ノードにタグキーを登録する場合に、深さ優先探索順でタグキーが並ぶようにトライ木を生成する。
【００６１】
図１４は、トライ木生成部１５０ａが、トライ木１４０ｂを生成する処理の概要を説明するための図である。なお、ここでは説明の便宜上、図１４の左側に示すトライ木に入力キー「blue」、値「４」を登録する場合について説明する。また、図１４の左側に示すトライ木は、図６において説明したトライ木と同様にして、トライ部分のキーを削除した状態で、各ノードにタグキーを割当てている。
【００６２】
まず、トライ木生成部１５０ａは、入力キーから文字を１文字ずつ取り出し、トライ木上のノードを辿る。辿る途中において、トライ木生成部１５０ａは、入力キーとタグキーとの比較を実行しない。入力キーが「blue」の場合には、「blue」の先頭から１文字ずつ文字を取り出し、トライ木上のノードを辿ると、ルートノード、ノードb、l、uの順に遷移する。
【００６３】
次に、トライ木生成部１５０ａは、辿る先にノードが存在しない場合や、入力キーを全て辿った後に、兄ノードを持つノード、あるいは、ルートノードの子ノードまでノードを戻りながら、入力キーよりも小さいキーを検索する。つまり、比較対象ノード内で、入力キーよりも優先度の小さいタグキーを検索する。なお、入力キーとタグキーの優先度を比較する場合には、入力キーからトライ部のキーを除いた残りのキーとタグキーとを比較する。
【００６４】
入力キーが「blue」の場合には、比較対象ノードがノードu、ノードlとなるので、ノードu、ノードlの順に比較を行う。入力キー「blue」は、ノードlのタグキー「violet」よりも優先度が小さく、「ack」よりも優先度が大きい。なお、入力キー「blue」とタグキー「violet」との優先度を比較する場合には、ルートノードからノードuに至るトライ部のキー「blue」を入力キー「blue」から取り除いた後に比較する。また、入力キー「blue」とタグキー「ack」との優先度を比較する場合には、ルートノードからノードlに至るトライ部のキー「bl」を入力キー「blue」から取り除いた後に比較する。
【００６５】
トライ木生成部１５０ａは、入力キーよりも優先度の大きいタグキーの中で、優先度が最小となるタグキーを有するノードに、入力キーおよび入力キーに対応する値を登録し、既に登録されてあったタグキーをシフトさせる。
【００６６】
入力キーが「blue」の場合には、トライ木生成部１５０ａは、ノードuに入力キー「blue」、値「４」を登録する。ルートノードからノードuに至るトライ部分のキーが「blu」であるため、実際には、タグキー「e」をノードuに登録する。また、トライ木生成部１５０ａは、ノードｕに登録してあったタグキー「blueviolet」をシフトさせるべく、新規のノードeをノードuの配下に作成し、タグキー「blueviolet」を登録する。ノードｅに至るトライ部分のキーが「blue」であるため、実際には、タグキー「violet」をノードeに登録する。上記のような登録処理を実行することで、図１４の右側に示すトライ木が生成される。なお、トライ木生成部１５０ａは、兄ノードを有するノードを識別するために、識別情報を登録しておいても良い。例えば、図１４の右側では、ノードlが兄ノードｉを有しているので、ノードlに識別情報を登録する。
【００６７】
以下において、トライ木生成部１５０ａがトライ木を生成する処理について具体的に説明する。図１５〜図２４は、トライ木を生成する処理を説明するための図である。ここでは説明の便宜上、キー「http://aaa.aaa/e/」、値「１」と、キー「http://aaa.aaa/e/c/」、値「２」と、キー「http://aaa.aaa/e/c/」、値「３」と、キー「http://aaa.aaa/e/」、値「４」の順で、トライ木を生成する場合について説明する。
【００６８】
図１５に示すように、まず、ノードが存在しない状態で、キー「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に遷移する。そして、トライ木生成部１５０ａは、入力キー「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/d/」、値「３」を追加する場合について説明する。トライ木生成部１５０ａは、入力キー「http://aaa.aaa/d/」の先頭文字から１文字ずつ取り出して、トライ木上をノードh、tの順に遷移する。そして、トライ木生成部１５０ａは、遷移したノードの数に応じて、入力キー「http://aaa.aaa/d/」のポインタを２つ進め、３文字目の「t」に設定する。
【００８１】
そして、トライ木生成部１５０ａは、ノードtにおいて、「t」をキーとする子ノードが存在しないので、ノードtのタグキー「tp://aaa.aaa/e/c/」の優先度と、トライ部分の「ht」を取り除いた入力キー「tp://aaa.aaa/d/」の優先度を比較する。すると、タグキーの１４文字目が「e」であり、入力キーの１４文字目が「d」であるため、タグキーの優先度の方が、入力キーの優先度よりも大きくなる（ステップＳ１７ａ）。
【００８２】
実データ上において、トライ木生成部１５０ａは、テキスト表１４に最後に登録されたキー「http://aaa.aaa/e/c/」との間を１つ空けて、キー「http://aaa.aaa/d/」を登録する。そして、トライ木生成部１５０ａは、テキスト表１４の３行目５文字目の文字「t」に入力キーのポインタを接続する。また、ポインタ配列２２の「TAG」に接続された文字を先頭とする文字列と、入力キーのポインタに接続された文字を先頭とする文字列とを順次比較すると、タグキーの１４文字目が「e」であり、入力キーの１４文字目が「d」であるため、タグキーの優先度の方が、入力キーの優先度よりも大きくなる（ステップＳ１７ｂ）。
【００８３】
トライ木生成部１５０ａは、入力キー「http://aaa.aaa/d/」のポインタを一つ戻して、２文字目の「t」に設定し、ノードtの親ノードとなるノードhに遷移する。そして、トライ木生成部１５０ａは、ノードhのタグキー「ttp://aaa.aaa/e/c」の優先度と、トライ部分の「h」を取り除いた入力キー「ttp://aaa.aaa/d/」の優先度を比較する。すると、タグキーの１５文字目が「e」であり、入力キーの１４文字目が「d」であるため、タグキーの優先度の方が、入力キーの優先度よりも大きくなる（ステップＳ１８ａ）。
【００８４】
実データ上において、トライ木生成部１５０ａは、現在のノードのポインタをポインタ配列２１に接続し、テキスト表１４の３行目４文字目の文字「t」に入力キーのポインタを接続する。また、ポインタ配列２２の「TAG」に接続された文字を先頭とする文字列と、入力キーのポインタに接続された文字を先頭とする文字列とを順次比較すると、タグキーの１５文字目が「e」であり、入力キーの１５文字目が「d」であるため、タグキーの優先度の方が、入力キーの優先度よりも大きくなる（ステップＳ１８ｂ）。
【００８５】
続いて、図１９に移行する。トライ木生成部１５０ａは、ノードhの親ノードがルートノードであるため、ノードhのデータ（タグキー、値）と、入力データ（入力キー、値）を交換する。すなわち、トライ木生成部１５０ａは、入力キー「http://aaa.aaa/d/」からトライ部分「h」を取り除いた残りのキー「ttp://aaa.aaa/d/」をノードhのタグキーに登録する。また、入力キー「http://aaa.aaa/d/」に対応する値「３」もノードhに登録する。また、トライ木生成部１５０ａは、ノードhに登録されていたタグキー「ttp://aaa.aaa/e/」の先頭にトライ部分「h」を追加して、入力キーとして取り出す。また、タグキー「ttp://aaa.aaa/e/」に対応付けられていた値「１」も取り出す（ステップＳ１９ａ）。
【００８６】
実データ上において、トライ木生成部１５０ａは、ノードhのデータ（タグキー、値）と、入力データ（入力キー、値）を交換する。すなわち、トライ木生成部１５０ａは、ノードhに対応するポインタ配列２１の「TAG」をテキスト表１４の３行目４列目の文字「t」に接続する。また、ポインタ配列２１の「Data」と値「３」を接続する。そして、トライ木生成部１５０ａは、入力キーのポインタを、テキスト表１４の１行目２列目の「t」に接続する。また、ポインタ配列２１の「Data」に接続されていた値「１」を入力値に保持する（ステップＳ１９ｂ）。
【００８７】
トライ木生成部１５０ａは、ノードhから、入力キー「http://aaa.aaa/e/」の２文字目のtでノードtに遷移し、ノードtのデータ（タグキー、値）と入力データ（入力キー、値）を交換する。すなわち、トライ木生成部１５０ａは、入力キー「http://aaa.aaa/e/」からトライ部分「ht」を取り除いた残りのキー「tp://aaa.aaa/e/」をノードtのタグキーに登録する。また、入力キー「http://aaa.aaa/e/」に対応する値「１」もノードtに登録する。また、トライ木生成部１５０ａは、ノードtに登録されていたタグキー「tp://aaa.aaa/e/c/」の先頭にトライ部分「h」を追加して、入力キーとして取り出す。また、タグキー「ttp://aaa.aaa/e/c/」に対応付けられていた値「２」も取り出す（ステップＳ２０ａ）。
【００８８】
実データ上において、トライ木生成部１５０ａは、ノードtのデータ（タグキー、値）と、入力データ（入力キー、値）を交換する。すなわち、トライ木生成部１５０ａは、ノードtに対応するポインタ配列２２の「TAG」をテキスト表１４の１列目３列目の文字「t」に接続する。また、ポインタ配列２２の「Data」と値「１」を接続する。そして、トライ木生成部１５０ａは、入力キーのポインタを、テキスト表１４の２行目３列目の「t」に接続する。また、ポインタ配列２１の「Data」に接続されていた値「２」を入力値に保持する（ステップＳ２０ｂ）。
【００８９】
続いて、図２０に移行する。トライ木生成部１５０ａは、入力キー「http://aaa.aaa/e/c/」の３文字目に対応するノードｔが、ノード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/」、値「４」を追加する場合について説明する。トライ木生成部１５０ａは、入力キー「http://aaa.aaa/e/」の先頭から文字を順次読み出し、ノードh、t（親）、t（子）に遷移する。そして、トライ木生成部１５０ａは、入力キー「http://aaa.aaa/e/」のポインタを４文字目の「p」に設定する（ステップＳ２３ａ）。
【００９４】
実データ上において、トライ木生成部１５０ａは、テキスト表１４に最後に登録されたキー「http://aaa.aaa/e/d/」との間を１つ空けて、キー「http://aaa.aaa/e/」を登録する。そして、トライ木生成部１５０ａは、テキスト表１４の４行目６列目の文字「p」に入力キーのポインタを接続する（ステップＳ２３ｂ）。
【００９５】
続いて、図２３に移行する。トライ木生成部１５０ａは、ノードt（子）において、「p」をキーとする子ノードが存在しないので、ノードt（子）のタグキー「p://aaa.aaa/e/c/」の優先度と、トライ部分の「htt」を取り除いた入力キー「p://aaa.aaa/e/」の優先度を比較する。すると、入力キーの１５文字目が「空」であり、タグキーの１５文字目が「c」であるため、タグキーの優先度が入力キーよりも大きい。
【００９６】
したがって、トライ木生成部１５０ａは、ノードt（子）のデータと、入力データとの交換を行わずに、ノードt（子）からノードt（親）に戻り、入力キー「http://aaa.aaa/e/」のポインタを３文字目の「t」に設定する（ステップＳ２４ａ）。
【００９７】
実データ上において、トライ木生成部１５０ａは、テキスト表１４の４行目６列目の文字「p」に入力キーのポインタを接続する。また、トライ木生成部１５０ａは、ポインタ配列２３の「TAG」に接続された文字を先頭とする文字列と、入力キーのポインタに接続された文字を先頭とする文字列とを順次比較すると、入力キーの１５文字目が「空」であり、タグキーの１５文字目が「c」であるため、タグキーの優先度が入力キーよりも大きいと判定する。そして、トライ木生成部１５０ａは、入力キーのポインタを、４行目５列目の「t」に設定する（ステップＳ２４ｂ）。
【００９８】
続いて、図２４に移行する。トライ木生成部１５０ａは、ノードt（親）のタグキー「tp://aaa.aaa/e/」の優先度と、トライ部分の「ht」を取り除いた入力キー「tp://aaa.aaa/e/」の優先度とを比較する。すると、入力キーとタグキーの優先度が等しい（入力キーとタグキーが同じ）である。この場合、トライ木生成部１５０ａは、入力キー「http://aaa.aaa/e/」に対応する値「４」を、ノードtに追加する（ステップＳ２５ａ）。
【００９９】
実データ上において、トライ木生成部１５０ａは、テキスト表１４の４行目５列目の文字「t」に入力キーのポインタを接続する。また、トライ木生成部１５０ａは、ポインタ配列２２の「TAG」に接続された文字を先頭とする文字列と、入力キーのポインタに接続された文字を先頭とする文字列とを順次比較すると、空に至るまでの各文字列が等しいため、タグキーの優先度と入力キーの優先度は等しい（タグキーと入力キーは同じ）と判定する。そして、トライ木生成部１５０ａは、ポインタ配列２２に「Data」に値「４」を追加する（ステップＳ２５ｂ）。
【０１００】
図１５〜図２４に示したように、トライ木生成部１５０ａは、トライ木１４０ｂを生成する場合に、１つのノードに１つのキーを割当てるので、トライ木１４０ｂのメモリ使用量を削減することが出来る。また、トライ木生成部１５０ａは、新規の入力キーをトライ木１４０ｂに割当てる場合に、全てのタグキーと入力キーを比較することはせず、比較対象ノードのタグキーのみと比較して、タグキーを新規に登録するので、処理負荷を軽減させつつ、深さ優先探索順でタグキーが並ぶようにトライ木１４０ｂを生成することが出来る。
【０１０１】
なお、図１５〜図２４に示した実データに対応する各種データ（ポインタ配列、テキスト表等）は、記憶部１４０に記憶されているものとする。
【０１０２】
図１０の説明に戻ると、トライ木探索部１５０ｂは、トライ木１４０ｂに登録された値の集計値を抽出する処理、所定のキーに対応する値をトライ木１４０ｂから検索する処理を実行する処理部である。
【０１０３】
まず、トライ木探索部１５０ｂが、トライ木１４０ｂに登録された値の集計値を抽出する処理について説明する。トライ木探索部１５０ｂは、指定された入力キーの文字を先頭から１文字ずつ読み出して、各ノードを辿り、ノードに登録されたタグキーおよび値を対応付けて順次出力することで、集計値を抽出する。ノードに複数の値が登録されている場合には、トライ木探索部１５０ｂは、各値を合計しても良いし、別々に出力しても良い。本実施例にかかるトライ木探索部１５０ｂは、一例として、各値を合計して出力する。
【０１０４】
図２５〜図２７は、集計値を抽出する処理を説明するための図である。図２５に示すように、トライ木１４０ｂは、ルートノードの配下に、ノードh、ノードt（親）、ノードt（子）が順に接続されている。ノードhは、タグキー「ttp://aaa.aaa/d/」、値「３」を登録し、ノードt（親）は、タグキー「tp://aaa.aaa/e/」、値「１、４」を登録し、ノードt（子）は、タグキー「p://aaa.aaa/e/c/」、値「２」を登録しているものとする。
【０１０５】
また、図２５〜図２７における説明では、入力キー「http://aaa.aaa/e/」が指定された場合の集計値の抽出処理について説明する。図２５において、トライ木探索部１５０ｂは、入力キー「http://aaa.aaa/e/」の１文字目をポインタに設定し、ポインタの文字にしたがって、ノードhに移行する。
【０１０６】
ノードhは、タグキー「ttp://aaa.aaa/d/」、値「３」が登録されているので、トライ木探索部１５０ｂは、トライ部分「h」をタグキー「ttp://aaa.aaa/d/」の先頭に追加したキー「http://aaa.aaa/d/」と、値（合計値）「３」を出力する（ステップＳ３０ａ）。
【０１０７】
実データ上において、トライ木探索部１５０ｂは、テキスト表１４の４行目３列目に入力キー「http://aaa.aaa/d/」を登録し、入力キーのポインタを４行目３列目に接続する。また、トライ木探索部１５０ｂは、現在のノードのポインタをポインタ配列２１に接続する。また、トライ木探索部１５０ｂは、ノードhに対応するポインタ配列２１の「TAG」に接続された文字の前後空までの文字列「http://aaa.aaa/d/」と、「Data」に接続された値「３」を出力する（ステップＳ３０ｂ）。
【０１０８】
図２６の説明に移行する。トライ木探索部１５０ｂは、入力キー「http://aaa.aaa/e/」の２文字目をポインタに設定し、ポインタの文字にしたがって、ノードhからノードt（親）に移行する。ノードt（親）は、タグキー「tp://aaa.aaa/e/」、値「１、４」が登録されているので、トライ木探索部１５０ｂは、トライ部分「ht」をタグキー「tp://aaa.aaa/e/」の先頭に追加したキーと、値「１、４」を合計した値「５」を出力する（ステップＳ３１ａ）。
【０１０９】
実データ上において、トライ木探索部１５０ｂは、入力キーのポインタ接続先を１文字ずらし、テキスト表１４の４行目４列目の文字「t」に接続する。また、トライ木探索部１５０ｂは、現在のノードのポインタをポインタ配列２２に接続する。また、トライ木探索部１５０ｂは、ノードt（親）に対応するポインタ配列２２の「TAG」に接続された文字の前後空までの文字列「http://aaa.aaa/e/」と、「Data」に接続された値「１、４」の合計値「５」を出力する（ステップＳ３１ｂ）。
【０１１０】
図２７の説明に移行する。トライ木探索部１５０ｂは、入力キー「http://aaa.aaa/e/」の３文字目をポインタに設定し、ポインタの文字にしたがって、ノードt（親）からノードt（子）に移行する。ノードt（子）は、タグキー「p://aaa.aaa/e/c/」、値「２」が登録されているので、トライ木探索部１５０ｂは、トライ部分「htt」をタグキー「p://aaa.aaa/e/c/」の先頭に追加したキーと、値（合計値）「２」を出力する（ステップＳ３２ａ）。
【０１１１】
実データ上において、トライ木探索部１５０ｂは、入力キーのポインタ接続先を１文字ずらし、テキスト表１４の４行目５列目の文字「t」に接続する。また、トライ木探索部１５０ｂは、現在のノードのポインタをポインタ配列２３に接続する。また、トライ木探索部１５０ｂは、ノードt（子）に対応するポインタ配列２３の「TAG」に接続された文字の前後空までの文字列「http://aaa.aaa/e/c/」と、「Data」に接続された値（合計値）「２」を出力する（ステップＳ３２ｂ）。
【０１１２】
図２５〜図２７に示したように、入力キーを順次読み出し、トライ木１４０ｂを辿ることで、入力キーに対応する集計値を出力することが出来る。
【０１１３】
次に、トライ木探索部１５０ｂが、指定された入力キーに対応する値をトライ木１４０ｂから検索する処理について説明する。トライ木探索部１５０ｂは、トライ木１４０ｂが、深さ優先探索順でタグキーが並ぶように生成されているので、比較対象ノードに登録されたタグキーと入力キーを比較すればよい。また、比較対象ノードに含まれる各ノードと入力キーを比較する場合に、二分探索法を用いることで、更に処理負荷を軽減させることが出来る。
【０１１４】
以下において、二分探索法を用いた場合の検索処理について説明する。図２８〜図３１は、二分探索法を用いた場合の検索処理を説明するための図である。図２８に示すように、トライ木１４０ｂは、ルートノードの配下に、ノードh、ノードt（親）、ノードt（子）が順に接続されている。ノードhは、タグキー「ttp://aaa.aaa/d/」、値「３」を登録し、ノードt（親）は、タグキー「tp://aaa.aaa/e」、値「１、４」を登録し、ノードt（子）は、タグキー「p://aaa.aaa/e/c」、値「２」を登録しているものとする。
【０１１５】
また、図２８〜図３１における説明では、入力キー「http://aaa.aaa/d」が指定された場合の検索処理について説明する。図２８において、トライ木探索部１５０ｂは、入力キー「http://aaa.aaa/d」の先頭文字から順に文字を読み出し、ルートノードからノードh、ノードt（親）、ノードt（子）の順に遷移する。そして、トライ木探索部１５０ｂは、入力キー「http://aaa.aaa/d」のポインタを初期位置の「h」から３文字ずらした「p」に設定する。また、遷移した各ノードにスタックを追加する（ステップＳ４０ａ）。
【０１１６】
実データ上では、トライ木探索部１５０ｂは、ノードh、ノードt（親）、ノードt（子）に対応するポインタ配列２１、２２、２３にそれぞれスタックを追加する。また、トライ木探索部１５０ｂは、現在のノードのポインタをポインタ配列２３に接続する（ステップＳ４０ｂ）。なお、ここでは、説明の便宜上、入力キー「http://aaa.aaa/d」の記載を省略するが、テキスト表１４に入力キー「http://aaa.aaa/d」の情報が格納されているものとする。
【０１１７】
続いて、図２９の説明に移行する。トライ木探索部１５０ｂは、スタックの真ん中のノードt（親）に遷移し、入力キーのポインタを戻った分だけ戻す。ここでは、ノードt（子）からノードt（親）に戻っているので、入力キー「http://aaa.aaa/d」のポインタを「p」から１つ戻した「t（３文字目のt）」に設定する。
【０１１８】
そして、トライ木探索部１５０ｂは、ノードtのタグキー「tp://aaa.aaa/e」の優先度と、トライ部分「ht」を取り除いた入力キー「tp://aaa.aaa/d」の優先度とを比較する。すると、入力キーの１４文字目が「d」であり、タグキーの１４文字目が「e」であるため、トライ木探索部１５０ｂは、タグキーの優先度が入力キーの優先度よりも大きいと判定する（ステップＳ４１ａ）。ノードt（親）タグキーの優先度が入力キーの優先度よりも大きい場合には、ノードt（親）以降のノードには、検索対象となるタグキーが存在しない。
【０１１９】
実データ上において、トライ木探索部１５０ｂは、スタックの真ん中に接続されたポインタ配列２２に現在のノードのポインタを移動させる。そして、トライ木探索部１５０ｂは、ポインタ配列２２の「TAG」に接続された文字以降の文字列「tp://aaa.aaa/e」と、トライ部分「ht」を除いた残りの入力キー「tp://aaa.aaa/d」とを比較する。すると、入力キーの１４文字目が「d」であり、タグキーの１４文字目が「e」であるため、トライ木探索部１５０ｂは、タグキーの優先度が入力キーの優先度よりも大きいと判定する（ステップＳ４１ｂ）。
【０１２０】
続いて、図３０の説明に移行する。図２９で説明したように、ノードt（親）タグキーの優先度が入力キーの優先度よりも大きい場合には、ノードt（親）以降のノードには、検索対象となるタグキーが存在しない。したがって、トライ木探索部１５０ｂは、スタックの後半となる、ノードt（親）、ノードt（子）に追加されたスタックを削除する。
【０１２１】
また、トライ木探索部１５０ｂは、スタックの真ん中のノードhに遷移し、入力キーのポインタを戻った分だけ戻す。ここでは、ノードt（親）からノードhに戻っているので、入力キー「http://aaa.aaa/d/」のポインタを「t（３文字目）」から１つ戻した「t（２文字目）」に設定する（ステップＳ４２ａ）。
【０１２２】
実データ上において、トライ木生成部１５０ａは、スタックの真ん中に接続されたポインタ配列２１に現在のノードのポインタを移動させる（ステップＳ４１ｂ）。
【０１２３】
図３１の説明に移行する。トライ木探索部１５０ｂは、ノードhのタグキー「ttp://aaa.aaa/d/」の優先度と、トライ部分「h」を取り除いた入力キー「ttp://aaa.aaa/d/」の優先度を比較する。すると、タグキーと入力キーの優先度が等しい（タグキーと入力キーが同じ）ため、トライ木探索部１５０ｂは、ノードhに接続されたタグキー「ttp://aaa.aaa/d/」の先頭にトライ部分「h」を追加したキー「http://aaa.aaa/d/」と、値「３」を検索結果として出力する（ステップＳ４３ａ）。
【０１２４】
実データ上において、トライ木探索部１５０ｂは、ポインタ配列２１の「TAG」に接続された文字以降の文字列「ttp://aaa.aaa/d/」の優先度と、トライ部分「h」を取り除いた残りの入力キー「tp://aaa.aaa/d/」の優先度を比較する。すると、タグキーと入力キーの優先度が等しい（タグキーと入力キーが同じ）ため、トライ木探索部１５０ｂは、ポインタ配列２１の「TAG」に接続された文字の前後空までの文字列「http://aaa.aaa/d/」と、「Data」に接続された値「３」を出力する（ステップＳ４３ｂ）。
【０１２５】
次に、図３２〜図３５において、その他の例を用いて、二分探索法を用いた場合の検索処理について説明する。図３２に示すように、トライ木１４０ｂは、ルートノードの配下に、ノードa、ノードb、ノードcを接続している。ノードaは、タグキー「aa」、値「３」を登録し、ノードbは、タグキー「c」、値「１」を登録し、ノードcは、タグキー「b」、値「２」を登録しているものとする。なお、ノードbとノードcの関係は、ノードbが兄ノードであり、ノードcが弟ノードである。
【０１２６】
また、図３２〜図３５における説明では、入力キー「ac」が指定された場合の検索処理について説明する。図３２において、トライ木探索部１５０ｂは、入力キー「ac」から「a」を読み出し、入力キーのポインタを「a」から「c」にずらす。また、トライ木探索部１５０ｂは、ノードaにスタックを追加する（ステップＳ５０ａ）。
【０１２７】
実データ上では、トライ木探索部１５０ｂは、ノードaに対応するポインタ配列２１にスタックを追加する。また、トライ木探索部１５０ｂは、現在のノードのポインタをポインタ配列２１に接続する。トライ木探索部１５０ｂは、入力キーのポインタを、テキスト表１４の１行目１４列目の文字「c」に設定する（ステップＳ５０ｂ）。
【０１２８】
続いて、図３３の説明に移行する。トライ木探索部１５０ｂは、入力キー「ac」からポインタが指定する「c」を読み出し、ノードcに遷移する。ノードcに遷移した時点で、ノードaの先祖ノードに登録されたタグキーの優先度は、入力キー「ac」の優先度よりもすべて小さいものとなるため、検索対象から外す必要がある。したがって、トライ木探索部１５０ｂは、一旦スタックを空にし、スタックに新しくノードcを追加する。また、入力キーのポインタを「c」から１文字ずらし、ポインタを「空」に設定する（ステップＳ５１ａ）。
【０１２９】
実データ上では、トライ木探索部１５０ｂは、現在のノードをポインタ配列２３に指定する。トライ木探索部１５０ｂは、ポインタ配列２１に接続されたスタックを削除し、ポインタ配列２３にスタックを追加する。また、トライ木探索部１５０ｂは、入力キーのポインタをテキスト表１４の１行目１５文字目の「空」に設定する（ステップＳ５１ｂ）。
【０１３０】
続いて、図３４の説明に移行する。トライ木探索部１５０ｂは、ポインタが指定する文字が「空」なので、スタックの真ん中のノードcを現在のノードに設定し、ノードcのタグキー「b」の優先度と、トライ部分「ac」を除いた「空」の優先度を比較する。トライ木探索部１５０ｂは、比較した結果、タグキーの優先度の方が入力キーの優先度よりも大きいと判定する（ステップＳ５２ａ）。
【０１３１】
実データ上では、トライ木探索部１５０ｂは、スタックの真ん中に対応するポインタ配列２３に現在のノードを設定し、ポインタ配列２３の「TAG」に接続された文字を先頭とする文字列と、入力キーのポインタに接続された「空」とを比較する。トライ木探索部１５０ｂは、比較した結果、タグキーの優先度の方が入力キーの優先度よりも大きいと判定する（ステップＳ５２ｂ）。
【０１３２】
続いて、図３５の説明に移行する。トライ木探索部１５０ｂは、タグキーの優先度の方が入力キーの優先度よりも大きいので、タグキーを登録するノードcのスタックを削除する。全てのスタックが無くなり、入力キー「ac」と一致するタグキーが存在しないので、トライ木探索部１５０ｂは、一致データが存在しない旨を出力する（ステップＳ５３ａ）。
【０１３３】
実データ上では、トライ木探索部１５０ｂは、タグキーの優先度の方が入力キーの優先度よりも大きいので、ノードcに対応するポインタ配列２８に接続されたスタックを削除する。全てのスタックが無くなり、入力キー「ac」と一致するタグキーが存在しないので、トライ木探索部１５０ｂは、一致データが存在しない旨を出力する（ステップＳ５３ｂ）。
【０１３４】
上述した図２８〜図３５では、トライ木探索部１５０ｂが、二分探索法を用いて検索処理を実行する場合について説明したが、トライ木探索部１５０ｂは、必ずしも二分探索法を用いなくてもよい。図３６〜図４０は、二分探索法を用いない場合の探索処理を説明するための図である。図３６に示すように、トライ木１４０ｂは、ルートノードの配下にノードb、ノードa、ノードb、ノードcが接続されている。ここで、各ノードbを区別するために、ルートノードの子ノードに対応するノードbをノードb（１）と表記し、もう一方のノードbをノードb（２）と表記する。
【０１３５】
ノードb（１）は、タグキー「a」、値「１」を登録し、ノードaは、タグキー「aa」、値「３」を登録し、ノードb（２）は、タグキー「c」、値「１」を登録し、ノードcは、タグキー「b」、値「２」を登録しているものとする。
【０１３６】
また、図３６〜図４０における説明では、入力キー「baca」が指定された場合の検索処理について説明する。図３６において、トライ木探索部１５０ｂは、入力キーのポインタを先頭文字「b」に設定し、ポインタの指定する「b」により、ルートノードからノードb（１）に遷移する。そして、トライ木探索部１５０ｂは、入力キーのポインタを「b」から１文字ずらした「a」に設定する（ステップＳ６０ａ）。
【０１３７】
実データ上では、トライ木探索部１５０ｂは、テキスト表１４に入力キー「baca」を登録し、入力キーのポインタをテキスト表１４の２行目１列目の「b」に接続する。トライ木探索部１５０ｂは、入力キーのポインタに接続された「b」により、ポインタ配列２０からポインタ配列２１に現在のノードのポインタを遷移させ、入力キーのポインタを１文字ずらした「a」に設定する（ステップＳ６０ｂ）。
【０１３８】
続いて、図３７の説明に移行する。トライ木探索部１５０ｂは、ポインタの指定する「a」により、ノードb（１）からノードaに遷移し、入力キーのポインタを「a」から１文字ずらした「c」に設定する（ステップＳ６１ａ）。
【０１３９】
実データ上では、トライ木探索部１５０ｂは、入力キーのポインタに接続された「a」により、ポインタ配列２１からポインタ配列２２に現在のノードのポインタを遷移させ、入力キーのポインタを１文字ずらした「c」に設定する（ステップＳ６１ｂ）。
【０１４０】
続いて、図３８の説明に移行する。トライ木探索部１５０ｂは、ポインタの指定する「c」により、ノードaからノードcに遷移し、入力キーのポインタを「c」から１文字ずらした「a」に設定する（ステップＳ６２ａ）。
【０１４１】
実データ上では、トライ木探索部１５０ｂは、入力キーのポインタに接続された「c」により、ポインタ配列２２からポインタ配列２４に現在のノードのポインタを遷移させ、入力キーのポインタを１文字ずらした「a」に設定する（ステップＳ６２ｂ）。
【０１４２】
図３９の説明に移行する。トライ木探索部１５０ｂは、ポインタの指定する「a」に対応した子ノードが、ノードcに存在しないので、ノードcに登録されたタグキー「ｂ」の優先度と、トライ部分「bac」を取り除いた入力キー「a」の優先度とを比較する。トライ木探索部１５０ｂは、比較した結果、入力キーの優先度よりもタグキーの優先度の方が大きいと判定する（ステップＳ６３ａ）。
【０１４３】
実データ上では、トライ木探索部１５０ｂは、ポインタ配列２４の「TAG」に接続された文字「b」の優先度と、入力キーのポインタに接続された文字「a」の優先度を比較する。トライ木探索部１５０ｂは、比較した結果、入力キーの優先度よりもタグキーの優先度の方が大きいと判定する（ステップＳ６３ｂ）。
【０１４４】
図４０の説明に移行する。トライ木探索部１５０ｂは、ノードcが兄ノード（ノードb（２））を有するので、ノードcより前のノード（ノードa、ノードb（１））に、入力キーと一致するタグキーを有するノードは存在しないと判定する。トライ木探索部１５０ｂは、該当データが無い旨を出力する（ステップＳ６４）。
【０１４５】
ところで、トライ木探索部１５０ｂは、トライ木１４０ｂに対して削除するキーを指定された場合に、指定された入力キーをトライ木１４０ｂから削除する。図４１は、削除処理を説明するための図である。ここでは、図４１の左側に示すトライ木からタグキー「black」、値「１」を削除する場合について説明する。
【０１４６】
まず、トライ木探索部１５０ｂは、上述した探索処理と同様にして、入力キー「black」と同じタグキーを有するノードlを探索し、ノードlに登録されたタグキー「ack」と値「１」を削除する。
【０１４７】
そして、トライ木探索部１５０ｂは、ノードlの長男ノードとなるノードuのタグキー「e（blue）」、値「４」をノードlに登録する。また、トライ木探索部１５０ｂは、ノードuの長男ノードとなるノードeのタグキー「blueviolet」、値「３」をノードuに登録し、ノードeをトライ木から削除する。トライ木探索部１５０ｂが、図４１の左側に示すトライ木からキー「black」、値「１」を削除することで、図４１の右側に示すトライ木が生成される。
【０１４８】
次に、本実施例１にかかる検索装置１００の各種の処理手順について説明する。まず、本実施例１にかかる検索装置１００がトライ木１４０ｂを生成する処理について説明する。図４２は、本実施例２にかかるトライ木生成処理の処理手順を示すフローチャートである。
【０１４９】
図４２に示すように、トライ木生成部１５０ａは、ルートノードを生成し（ステップＳ１０１）、次の入力データ（キー、値）が登録データ管理テーブル１４０ａに存在するか否かを判定する（ステップＳ１０２）。
【０１５０】
トライ木生成部１５０ａは、次の入力データが登録データ管理テーブル１４０ａに存在しないと判定した場合には（ステップＳ１０３、Ｎｏ）、処理を終了する。一方、トライ木生成部１５０ａは、次の入力データが登録データ管理テーブル１４０ａに登録されている場合には（ステップＳ１０３，Ｙｅｓ）、未読の入力データを読み出し（ステップＳ１０４）、データ追加処理を実行し（ステップＳ１０５）、ステップＳ１０２に移行する。
【０１５１】
次に、図４２のステップＳ１０５に示したデータ追加処理の処理手順について説明する。ここでは、二分探索法を用いないでデータ追加処理を実行する場合と、二分探索法を用いてデータ追加処理を実行する場合に分けて説明する。
【０１５２】
図４３および図４４は、二分探索法を用いないデータ追加処理の処理手順を示すフローチャートである。図４３に示すように、トライ木生成部１５０ａは、現在のノードをルートノードに設定し（ステップＳ１５０）、入力キーが空であるか否かを判定する（ステップＳ１５１）。
【０１５３】
トライ木生成部１５０ａは、入力キーが空ではない場合には（ステップＳ１５２，Ｎｏ）、入力キーの先頭文字のキーで子ノードを参照し、子ノードが存在するか否かを判定する（ステップＳ１５３）。トライ木生成部１５０ａは、子ノードが存在する場合には（ステップＳ１５４，Ｙｅｓ）、入力キーの先頭の１文字を読取り、入力キーのポインタを１文字進め、読み出した文字をキーとして子ノードに遷移し（ステップＳ１５５）、ステップＳ１５１に移行する。
【０１５４】
一方、トライ木生成部１５０ａは、子ノードが存在しない場合には（ステップＳ１５４，Ｎｏ）、ステップＳ１５６に移行する。
【０１５５】
ところで、ステップＳ１５２において、入力キーが空の場合には（ステップＳ１５２，Ｙｅｓ）、ノードの情報を参照し（ステップＳ１５６）、タグキーの優先度が入力キーの優先度と等しい（タグキーが入力キーと等しい）か否かを判定する（ステップＳ１５７）。タグキーの優先度と入力キーの優先度が等しい場合には（ステップＳ１５８，Ｙｅｓ）、トライ木生成部１５０ａは、現在のノードに入力値（入力キーに対応する値）を追加し（ステップＳ１５９）、データ追加処理を終了する。
【０１５６】
一方、タグキーの優先度と入力キーの優先度が異なる場合には（ステップＳ１５８，Ｎｏ）、トライ木生成部１５０ａは、タグキーの優先度が入力キーの優先度よりも大きいか否かを判定する（ステップＳ１６０）。タグキーの優先度が入力キーの優先度よりも小さい場合には（ステップＳ１６１，Ｎｏ）、ステップＳ１６４に移行する。
【０１５７】
タグキーの優先度が入力キーの優先度よりも大きい場合には（ステップＳ１６１，Ｙｅｓ）、兄ノードが存在する、または、親ノードがルートノードであるか否かを判定する（ステップＳ１６２）。兄ノードが存在せず、かつ、親ノードがルートノードではない場合には（条件を満たさない場合には）（ステップＳ１６３，Ｎｏ）、入力キーのポインタを１文字戻し、親ノードへ遷移し（ステップＳ１６４）、ステップＳ１６０に遷移する。
【０１５８】
一方、兄ノードが存在する、または、親ノードがルートノードの場合（条件を満たす場合）には（ステップＳ１６３，Ｙｅｓ）、現在のノードのタグキー、値と入力キー、入力値をそれぞれ交換し（ステップＳ１６８）、ステップＳ１６５に移行する。
【０１５９】
ところで、トライ木生成部１５０ａは、ステップＳ１６１において、タグキーの優先度が入力キーの優先度よりも小さい場合には（ステップＳ１６１，Ｎｏ）、入力キーの先頭文字のキーで子ノードを参照し、子ノードが存在するか否かを判定する（ステップＳ１６５）。
【０１６０】
子ノードが存在する場合には（ステップＳ１６６，Ｙｅｓ）、トライ木生成部１５０ａは、入力キーの先頭１文字を読み取り、入力キーのポインタを１文字進め、読み出した文字をキーとして子ノードへ遷移し（ステップＳ１６７）、ステップＳ１６８に移行する。
【０１６１】
一方、子ノードが存在しない場合には（ステップＳ１６６，Ｎｏ）、トライ木生成部１５０ａは、新しいノードを生成し（ステップＳ１６９）、入力キーの先頭１文字を読み取り、入力キーのポインタを１文字進め、読み出した文字をキーとして、現在のノードから新しいノードへ接続する（ステップＳ１７０）。
【０１６２】
トライ木生成部１５０ａは、入力キーをタグキーとして新しいノードに付加し（ステップＳ１７１）、入力値を新しいノードに付加し（ステップＳ１７２）、データ追加処理を終了する。
【０１６３】
図４５〜図４７は、二分探索法を用いるデータ追加処理の処理手順を示すフローチャートである。トライ木生成部１５０ａは、現在のノードをルートノードに設定し（ステップＳ１８０）、入力キーが空であるか否かを判定する（ステップＳ１８１）。
【０１６４】
入力キーが空の場合には（ステップＳ１８２，Ｙｅｓ）、トライ木生成部１５０ａは、ステップＳ１９０に移行する。一方、入力キーが空ではない場合には（ステップＳ１８２，Ｎｏ）、トライ木生成部１５０ａは、入力キーの先頭文字のキーで子ノードを参照し、子ノードが存在するか否かを判定する（ステップＳ１８３）。
【０１６５】
子ノードが存在する場合には（ステップＳ１８４，Ｙｅｓ）、トライ木生成部１５０ａは、子ノードが長男であるか否かを判定し（ステップＳ１８５）、子ノードが長男の場合には（ステップＳ１８６，Ｙｅｓ）、ステップＳ１８８に移行する。
【０１６６】
一方、子ノードが長男ではない場合には（ステップＳ１８６，Ｎｏ）、トライ木生成部１５０ａは、スタックを空に設定し（ステップＳ１８７）、入力キーの先頭１文字を読み取り、入力キーのポインタを１文字進め、読み出した文字をキーとして子ノードへ遷移する（ステップＳ１８８）。トライ木生成部１５０ａは、遷移したノードをスタックに追加し（ステップＳ１８９）、ステップＳ１８１に移行する。
【０１６７】
ところで、トライ木生成部１５０ａは、ステップＳ１８４において、子ノードが存在しない場合には（ステップＳ１８４，Ｎｏ）、スタックが空であるか否かを判定し（ステップＳ１９１）、スタックが空ではない場合には（ステップＳ１９１，Ｎｏ）、スタックの真ん中のデータを現在のノードとし、入力キーのポインタを移動した分だけ、ずらす（ステップＳ１９２）。
【０１６８】
図４６に移行する。トライ木生成部１５０ａは、タグキーの優先度と入力キーの優先度が等しいか否かを判定し（ステップＳ１９３）、タグキーの優先度と入力キーの優先度が等しい場合には（ステップＳ１９４，Ｙｅｓ）、現在のノードに入力値を追加する（ステップＳ１９５）。
【０１６９】
一方、トライ木生成部１５０ａは、タグキーの優先度と入力キーの優先度が異なる場合には（ステップＳ１９４，Ｎｏ）、タグキーの優先度が入力キーの優先度よりも大きいか否かを判定する（ステップＳ１９６）。
【０１７０】
トライ木生成部１５０ａは、タグキーの優先度が入力キーの優先度よりも大きい場合には（ステップＳ１９７，Ｙｅｓ）、真ん中のスタックを含む、スタックの後半を削除し（ステップＳ１９９）、図４５のステップＳ１９０に移行する。
【０１７１】
一方、トライ木生成部１５０ａは、タグキーの優先度が入力キーの優先度よりも小さい場合には（ステップＳ１９７，Ｎｏ）、真ん中のスタックを含む、スタックの前半を削除し（ステップＳ１９８）、図４５のステップＳ１９０に移行する。
【０１７２】
ところで、図４５のステップＳ１９１において、スタックが空の場合には（ステップＳ１９１，Ｙｅｓ）、図４７に移行し、トライ木生成部１５０ａは、入力キーの先頭文字のキーで子ノードを参照し、子ノードが存在するか否かを判定する（ステップＳ２００）。
【０１７３】
トライ木生成部１５０ａは、子ノードが存在する場合には（ステップＳ２０１，Ｙｅｓ）、入力キーの先頭１文字を読み取り、残り入力キーのポインタを１文字進め、読み出した文字をキーとして、子ノードに遷移する（ステップＳ２０２）。そして、トライ木生成部１５０ａは、現在のノードのタグキー、値と入力キー、入力値をそれぞれ交換し（ステップＳ２０３）、ステップＳ２００に移行する。
【０１７４】
一方、トライ木生成部１５０ａは、子ノードが存在しない場合には（ステップＳ２０１，Ｎｏ）、新しいノードを生成し（ステップＳ２０４）、入力キーの先頭１文字を読み取り、残り入力キーのポインタを１文字進め、読み出した文字をキーとして、現在のノードから新しいノードへ接続する（ステップＳ２０５）。トライ木生成部１５０ａは、入力キーをタグキーとして新しいノードに付加し（ステップＳ２０６）、入力値を新しいノードに付加する（ステップＳ２０７）。
【０１７５】
次に、本実施例にかかる検索装置１００がトライ木１４０ｂを用いて検索を行う処理について説明する。ここでは、二分探索法を用いないで検索処理を実行する場合と、二分探索法を用いて検索処理を実行する場合について説明する。
【０１７６】
まず、二分探索法を用いない検索処理の処理手順について説明する。図４８は、二分探索法を用いない検索処理の処理手順を示すフローチャートである。図４８に示すように、トライ木探索部１５０ｂは、現在のノードをルートノードに設定し（ステップＳ３００）、入力キーが空であるか否かを判定する（ステップＳ３０１）。
【０１７７】
トライ木探索部１５０ｂは、入力キーが空ではない場合には（ステップＳ３０２，Ｎｏ）、入力キーの先頭文字のキーで子ノードを参照し、子ノードが存在するか否かを判定する（ステップＳ３０３）。トライ木探索部１５０ｂは、子ノードが存在しない場合には（ステップＳ３０４，Ｎｏ）、ステップＳ３０６に移行する。
【０１７８】
一方、トライ木探索部１５０ｂは、子ノードが存在する場合には（ステップＳ３０４，Ｙｅｓ）、入力キーの先頭１文字を読み取り、入力キーのポインタを１文字進め、読み出した文字をキーとして子ノードに遷移し（ステップＳ３０５）、ステップＳ３０１に移行する。
【０１７９】
ところで、ステップＳ３０２において、入力キーが空の場合には（ステップＳ３０２，Ｙｅｓ）、トライ木探索部１５０ｂは、ノードの情報を参照し、タグキーの優先度と入力キーの優先度が等しいか否かを判定する（ステップＳ３０６）。トライ木探索部１５０ｂは、タグキーの優先度と入力キーの優先度が等しい場合には（ステップＳ３０７，Ｙｅｓ）、現在のノードのデータ（値）を出力する（ステップＳ３０８）。
【０１８０】
一方、タグキーの優先度と入力キーの優先度が異なる場合には（ステップＳ３０７，Ｎｏ）、トライ木探索部１５０ｂは、タグキーの優先度が入力キーの優先度よりも大きいか否かを判定する（ステップＳ３１０）。トライ木探索部１５０ｂは、タグキーの優先度が入力キーの優先度よりも小さい場合には（ステップＳ３１０，Ｎｏ）、ステップＳ３１４に移行する。
【０１８１】
一方、タグキーの優先度が入力キーの優先度よりも大きい場合には（ステップＳ３１０，Ｙｅｓ）、トライ木探索部１５０ｂは、兄ノードが存在するか、または、親ノードがルートノードであるか否かを判定する（ステップＳ３１１）。
【０１８２】
トライ木探索部１５０ｂは、兄ノードが存在しないで、かつ、親ノードがルートノードではない場合（条件を満たさない場合）に（ステップＳ３１２，Ｎｏ）、入力キーのポインタを１文字戻し、親ノードへ遷移する（ステップＳ３１３）。
【０１８３】
一方、トライ木探索部１５０ｂは、兄ノードが存在するか、または、親ノードがルートノードの場合（条件を満たす場合）に（ステップＳ３１２，Ｙｅｓ）、一致するデータが存在しない旨を出力する（ステップＳ３１４）。
【０１８４】
続いて、二分探索法を用いる検索処理の処理手順について説明する。図４９および図５０は、二分探索法を用いる検索処理の処理手順を示すフローチャートである。図４９に示すように、トライ木探索部１５０ｂは、現在のノードをルートノードに設定し（ステップＳ３５０）、入力キーが空であるか否かを判定する（ステップＳ３５１）。
【０１８５】
トライ木探索部１５０ｂは、入力キーが空の場合には（ステップＳ３５２，Ｙｅｓ）、図５０のステップＳ３６０に移行する。一方、トライ木探索部１５０ｂは、入力キーが空ではない場合に（ステップＳ３５２，Ｎｏ）、入力キーの先頭文字のキーで、子ノードが存在するか否かを判定する（ステップＳ３５３）。
【０１８６】
トライ木探索部１５０ｂは、子ノードが存在しない場合には（ステップＳ３５４，Ｎｏ）、図５０のステップＳ３６０に移行する。一方、トライ木探索部１５０ｂは、子ノードが存在する場合に（ステップＳ３５４，Ｙｅｓ）、子ノードが長男であるか否かを判定する（ステップＳ３５５）。
【０１８７】
トライ木探索部１５０ｂは、子ノードが長男である場合には（ステップＳ３５６，Ｙｅｓ）、ステップＳ３５８に移行する。一方、トライ木探索部１５０ｂは、子ノードが長男ではない場合に（ステップＳ３５６，Ｎｏ）、スタックを空に設定する（ステップＳ３５７）。
【０１８８】
トライ木探索部１５０ｂは、入力キーの先頭１文字を読み取り、入力キーのポインタを１文字進め、読み出した文字をキーとして子ノードに遷移する（ステップＳ３５８）。そして、トライ木探索部１５０ｂは、遷移したノードをスタックに追加し（ステップＳ３５９）、ステップＳ３５１に移行する。
【０１８９】
ところで、トライ木探索部１５０ｂは、ステップＳ３５２において、入力キーが空の場合（ステップＳ３５２，Ｙｅｓ）、または、ステップＳ３５４において、子ノードが存在しない場合（ステップＳ３５４，Ｎｏ）には、図５０のステップＳ３６０に移行する。
【０１９０】
図５０において、トライ木探索部１５０ｂは、スタックが空であるか否かを判定し（ステップＳ３６０）、スタックが空の場合には（ステップＳ３６１，Ｙｅｓ）、一致データが無い旨の情報を出力する（ステップＳ３６２）。
【０１９１】
一方、トライ木探索部１５０ｂは、スタックが空ではない場合に（ステップＳ３６１，Ｎｏ）、スタックの真ん中のノードを現在のノードとし、入力キーのポインタを移動した分だけ、ずらす（ステップＳ３６３）。
【０１９２】
トライ木探索部１５０ｂは、タグキーの優先度と入力キーの優先度が等しいか否かを判定し（ステップＳ３６４）、タグキーの優先度と入力キーの優先度が等しい場合には（ステップＳ３６５，Ｙｅｓ）、現在のノードのデータ（値）を出力する（ステップＳ３６６）。
【０１９３】
一方、トライ木探索部１５０ｂは、タグキーの優先度と入力キーの優先度が異なる場合には（ステップＳ３６５，Ｎｏ）、タグキーの優先度が入力キーの優先度よりも大きいか否かを判定する（ステップＳ３６７）。
【０１９４】
トライ木探索部１５０ｂは、タグキーの優先度が入力キーの優先度よりも小さい場合には（ステップＳ３６８，Ｎｏ）、真ん中のスタックを含むスタックの前半を削除し（ステップＳ３６９）、ステップＳ３６０に移行する。
【０１９５】
一方、トライ木探索部１５０ｂは、タグキーの優先度が入力キーの優先度よりも大きい場合には（ステップＳ３６８，Ｙｅｓ）、真ん中のスタックを含むスタックの後半を削除し（ステップＳ３７０）、ステップＳ３６０に移行する。
【０１９６】
次に、検索装置１００が、集計値を抽出する処理について説明する。図５１は、集計値の抽出処理の処理手順を示すフローチャートである。図５１に示すように、このトライ木探索部１５０ｂは、現在のノードをルートノードに設定し（ステップＳ４００）、子ノードが存在するか否かを判定する（ステップＳ４０１）。
【０１９７】
トライ木探索部１５０ｂは、子ノードが存在する場合には（ステップＳ４０２，Ｙｅｓ）、各子ノードのうち、長男ノードへ遷移し（ステップＳ４０３）、現在のノードの各種データを加工し出力し（ステップＳ４０４）、ステップＳ４０１に移行する。ステップＳ４０４において、トライ木探索部１５０ｂは、例えば、長男ノードに複数の値が登録されている場合には、各値を加算する処理をおこない、加算した値を出力する。
【０１９８】
一方、子ノードが存在しない場合には（ステップＳ４０２，Ｎｏ）、トライ木探索部１５０ｂは、弟ノードが存在するか否かを判定し（ステップＳ４０５）、弟ノードが存在する場合には（ステップＳ４０６，Ｙｅｓ）、次の弟ノードへ遷移し（ステップＳ４０７）、ステップＳ４０４に移行する。
【０１９９】
一方、トライ木探索部１５０ｂは、弟ノードが存在しない場合には（ステップＳ４０６，Ｎｏ）、親ノードへ遷移し（ステップＳ４０８）、現在のノードがルートノードであるか否かを判定する（ステップＳ４０９）。
【０２００】
トライ木探索部１５０ｂは、現在のノードがルートノードでない場合には（ステップＳ４１０，Ｎｏ）、ステップＳ４０５に移行する。一方、トライ木探索部１５０ｂは、現在のノードがルートノードの場合に（ステップＳ４１０，Ｙｅｓ）、処理を終了する。
【０２０１】
次に、検索装置１００が、トライ木１４０ｂのデータを削除する削除処理について説明する。図５２および図５３は、削除処理の処理手順を示すフローチャートである。図５２に示すように、トライ木探索部１５０ｂは、現在のノードをルートノードに設定し（ステップＳ４５０）、入力キーが空か否かを判定する（ステップＳ４５１）。
【０２０２】
トライ木探索部１５０ｂは、入力キーが空ではない場合に（ステップＳ４５２，Ｎｏ）、入力キーの先頭文字のキーで子ノードを参照し、子ノードが存在するか否かを判定する（ステップＳ４５３）。トライ木探索部１５０ｂは、子ノードが存在しない場合には（ステップＳ４５４，Ｎｏ）、ステップＳ４５６に移行する。
【０２０３】
一方、トライ木探索部１５０ｂは、子ノードが存在する場合に（ステップＳ４５４，Ｙｅｓ）、入力キーの先頭１文字を読み取り、入力キーのポインタを１文字進め、読み出した文字をキーとして子ノードに遷移し（ステップＳ４５５）、ステップＳ４５１に移行する。
【０２０４】
ところで、ステップＳ４５２において、トライ木探索部１５０ｂは、入力キーが空の場合に（ステップＳ４５２，Ｙｅｓ）、ノードの情報を参照し、タグキーの優先度が入力キーの優先度と等しいか否かを判定する（ステップＳ４５６）。
【０２０５】
トライ木探索部１５０ｂは、タグキーの優先度と入力キーの優先度が等しくない場合に（ステップＳ４５７，Ｎｏ）、タグキーの優先度が入力キーの優先度よりも大きいか否かを判定する（ステップＳ４５８）。トライ木探索部１５０ｂは、タグキーの優先度が入力キーの優先度よりも小さい場合に（ステップＳ４５９，Ｎｏ）、ステップＳ４６３に移行する。
【０２０６】
トライ木探索部１５０ｂは、タグキーの優先度が入力キーの優先度よりも大きい場合には（ステップＳ４５９，Ｙｅｓ）、兄ノードが存在、あるいは、親ノードがルートノードであるか否かを判定する（ステップＳ４６０）。
【０２０７】
トライ木探索部１５０ｂは、兄ノードが存在せず、かつ、親ノードがルートノードではない場合（条件を満たさない場合）に（ステップＳ４６１，Ｎｏ）、入力キーのポインタを１文字戻し、親ノードへ遷移し（ステップＳ４６２）、ステップＳ４５６に移行する。
【０２０８】
一方、トライ木探索部１５０ｂは、兄ノードが存在する、または、親ノードがルートノードの場合に（ステップＳ４６１，Ｙｅｓ）、削除データが存在しない旨を出力する（ステップＳ４６３）。
【０２０９】
ところで、ステップＳ４５７において、トライ木探索部１５０ｂは、タグキーの優先度が入力キーの優先度と等しい場合に（ステップＳ４５７，Ｙｅｓ）、図５３のステップＳ４６４に移行する。
【０２１０】
トライ木探索部１５０ｂは、削除対象のデータ（値）が存在するか否かを判定し（ステップＳ４６４）、削除対象のデータが存在しない場合には（ステップＳ４６５，Ｎｏ）、削除データが存在しない旨を出力する（ステップＳ４６６）。
【０２１１】
一方、トライ木探索部１５０ｂは、削除対象のデータが存在する場合に（ステップＳ４６５，Ｙｅｓ）、他のデータ（値）が存在するか否かを判定する（ステップＳ４６７）。トライ木探索部１５０ｂは、他のデータが存在する場合に（ステップＳ４６８，Ｙｅｓ）、処理を終了する。
【０２１２】
一方、トライ木探索部１５０ｂは、他のデータが存在しない場合に（ステップＳ４６８，Ｎｏ）、子ノードが存在するか否かを判定する（ステップＳ４６９）。トライ木探索部１５０ｂは、子ノードが存在しない場合に（ステップＳ４７０，Ｎｏ）、親ノードの現在のノードへのエッジを削除（接続を解除）し、現在のノードを削除する（ステップＳ４７１）。
【０２１３】
一方、トライ木探索部１５０ｂは、子ノードが存在する場合に（ステップＳ４７０，Ｙｅｓ）、現在のノードのデータを長男ノードのデータとし（ステップＳ４７２）、長男ノードへ遷移し（ステップＳ４７３）、ステップＳ４６９に移行する。
【０２１４】
上述してきたように、本実施例にかかる検索装置１００は、トライ木生成部１５０ａがトライ木１４０ｂを作成する場合に、１ノードにタグキーを１つ対応付け、タグキーを有さないノードを無くすので、メモリ使用効率を向上させることが出来る。
【０２１５】
また、本実施例にかかる検索装置１００は、トライ木生成部１５０ａがトライ木１４０ｂの各ノードにタグキーを登録する場合に、優先度の低いタグキーをルートノード側のタグキーに登録するので、トライ木探索部１５０ｂが検索処理などを実行する場合に、比較対象となるノードの領域を絞り込むことができ、検索処理にかかる処理効率を向上させることが出来る。
【実施例２】
【０２１６】
まず、上述した実施例１にかかる検索装置１００の課題を説明する。図５４は、実施例１にかかる検索装置１００の課題を説明するための図である。図５４に示すトライ木は、ルートノードにノードh、ノードt（親）、ノードt（子）が順に接続されており、ノードhはタグキー「ttp://aaa.aaa/e/」を有し、ノードt（親）はタグキー「tp://aaa.aaa/e/c/」を有し、ノードt（子）はタグキー「p://aaa.aaa/g/」を有している。ここでは説明の便宜上、値の記載は省略するが、各ノードは値を有しているものとする。
【０２１７】
例えば、検索装置１００が新規にキーを登録する場合には、登録対象となる入力キーの先頭文字から順に文字を読み出し、読み出した文字をキーにしてトライ木の各ノードを遷移する。そして、検索装置１００は、遷移先のノードから順に、ノードに登録されたタグキーの各文字と、入力キーの各文字を順に比較して、優先度の大小を判定することで、入力キーを登録していた。
【０２１８】
具体的に、登録対象となる入力キーを「http://aaa.aaa/b/」として説明を行う。検索装置１００は、入力キーの文字を先頭文字から順に読み出し、読み出した文字をキーにしてトライ木の各ノードを遷移する。ここでは、文字「h、t、t」が順に読み出されるので、ルートノードから、ノードh、ノードt（親）、ノードt（子）に遷移し、現在のノードをノードt（子）に設定する。
【０２１９】
そして、検索装置１００は、入力キーからトライ部分「htt」を除いたキー「p://aaa.aaa/d/」と、ノードｔ（子）のタグキー「p://aaa.aaa/g/」を先頭から１文字ずつ比較すると、タグキーの優先度が入力キーの優先度よりも大きいので、検索装置１００は、現在のノードをノードt（親）に遷移する。
【０２２０】
検索装置１００は、入力キーからトライ部分「ht」を除いた「tp://aaa.aaa/b/」と、ノードt（親）のタグキー「tp://aaa.aaa/e/c/」を先頭から１文字ずつ比較すると、タグキーの優先度が入力キーの優先度よりも大きいので、検索装置１００は、現在のノードをノードhに移行する。
【０２２１】
検索装置１００は、入力キーからトライ部分「h」を除いた「ttp://aaa.aaa/b/」と、ノードhのタグキー「ttp://aaa.aaa/e/」を先頭から１文字ずつ比較すると、タグキーの優先度が入力キーの優先度よりも大きい。ここで、ノードhの親ノードはルートノードなので、検索装置１００は、入力キーからトライ部分「h」を除いた「ttp://aaa.aaa/b/」をノードhに登録すると判定する。
【０２２２】
このように、実施例１にかかる検索装置１００は、各ノードのタグキーの各文字と入力キーの各文字を順次比較することで、入力キーを登録するノードを判定していた。しかしながら、図５４に示すトライ木の各タグキーを参照すると、トライ部分を含むタグキーの「http://aaa.aaa/」が共通している。このように、各タグキーの一部が共通している場合であっても、実施例１の検索装置１００は、先頭文字から順に比較を行っているので、処理効率が悪かった。
【０２２３】
例えば、ノードt（子）のタグキーの「p://aaa.aaa/g/」と、入力キーを比較した後に、ノードt（親）のタグキー「tp://aaa.aaa/e/c/」と入力キーとを比較する場合には、タグキーの「tp://aaa.aaa/」は既に比較済みであるため、入力キーとタグキー「tp://aaa.aaa/e/c/」を初めから１文字ずつ比較することは無駄である。
【０２２４】
本実施例２にかかる検索装置は、上述した実施例１にかかる検索装置の無駄を省くことで、処理の高速化を図る。図５５は、本実施例２にかかる検索装置の概要を説明するための図である。同図に示すように、本実施例２にかかる検索装置がトライ木を生成する場合には、子ノードのタグキーと親ノードのタグキーとを比較する。そして、検索装置は、親ノードにタグキーを登録する場合に、全てのタグキーを登録するのではなく、子ノードと一致しない部分の文字列のみを親ノードに登録する。また、検索装置は、子ノードのタグキーと親ノードのタグキーと一致する部分の文字数もあわせて親ノードに登録する。
【０２２５】
例えば、図５５に示すように、親ノードのタグキーが「tp://aaa.aaa/e/c/」、子ノードのタグキーが「p://aaa.aaa/g/」の場合には、一致する文字が「（t）p://aaa.aaa/」となるため、親ノードに一致する文字数「１３」と、残りの文字列「e/c/」を登録する。以下の説明において、一致する文字数を一致数と表記する。
【０２２６】
また、親ノードのタグキーが「ttp://aaa.aaa/e/」、子ノードのタグキーが「tp://aaa.aaa/e/c/」の場合には、一致する文字が「（t）tp://aaa.aaa/e/」となるため、親ノードに一致数「１６」を親ノードに登録する。なお、この場合は、一致する文字列がそのまま、親ノードのタグキーとなるので、親ノードには、文字列が登録されない。
【０２２７】
図５５のように、トライ木を生成することで、実施例１の検索装置１００のように、１度比較した文字列を重複して比較するという無駄を省くことが出来る。具体的に、登録対象となる入力キーを「http://aaa.aaa/b/」として説明を行う。
【０２２８】
本実施例２にかかる検索装置は、入力キーの文字を先頭から順に読み出し、読み出した文字をキーにしてトライ木の各ノードを遷移する。ここでは、文字「h、t、t」が順に読み出されるので、ルートノードから、ノードh、ノードt（親）、ノードt（子）に遷移し、現在のノードをノードt（子）に設定する。
【０２２９】
本実施例２にかかる検索装置は、入力キーからトライ部分「htt」を除いたキー「p://aaa.aaa/b/」と、ノードt（子）のタグキー「p://aaa.aaa/g/」を先頭から１文字ずつ比較すると、タグキーの優先度が入力キーの優先度よりも大きいので、検索装置は、現在のノードをノードt（親）に遷移する。
【０２３０】
本実施例２にかかる検索装置は、入力キーからトライ部分「ht」を除いた「tp://aaa.aaa/b/」と、ノードt（親）のタグキーとを比較する。ここで、親ノードt（親）に一致数「１３」が登録されているので、検索装置は、キー「tp://aaa.aaa/b/」のうち、先頭から１３文字目までの比較処理をスキップし、１４文字目から、ノードt（親）のタグキー「e/c/」と比較を行う。すると、タグキーの優先度が入力キーの優先度よりも大きいので、検索装置は、現在のノードをノードhに移行する。
【０２３１】
本実施例２にかかる検索装置は、入力キーからトライ部分「h」を除いた「ttp://aaa.aaa/b/」と、ノードhのタグキーを比較する。ここで、ノードhに一致数「１６」が登録されているので、検索装置は、キー「ttp://aaa.aaa/b/」のうち、先頭から１６文字目までの比較処理をスキップする。すると、比較対象となるキーが空になる。この場合には、タグキーが入力キーよりも大きいと判定する。ここで、ノードhの親ノードはルートノードなので、検索装置は、入力キーからトライ部「h」を除いた「ttp://aaa.aaa/b/」をノードhに登録すると判定する。
【０２３２】
このように、本実施例２にかかる検索装置は、各ノードのタグキーと入力キーとを比較する場合に、先頭文字から順に各キーの文字を比較するのではなく、一致数だけ比較する文字をスキップするので、入力キーをトライ木に登録する処理を高速化することが出来る。
【０２３３】
ところで、図５５に示す例では、新規に入力キーを登録する場合の処理について説明したが、トライ木から入力キーと一致するタグキーを検索する場合にも、一致数を用いて同様に、検索処理の処理効率を向上させることが出来る。
【０２３４】
次に、本実施例２にかかる検索装置２００の構成について説明する。図５６は、本実施例２にかかる検索装置２００の構成を示す図である。図５６に示すように、この検索装置２００は、入力部２１０、出力部２２０、入出力制御部２３０、記憶部２４０、制御部２５０を有する。
【０２３５】
このうち、入力部２１０は、入力キー等の情報を入力する入力部であり、キーボードやマウス等に該当する。出力部２２０は、トライ木を用いた検索結果などの情報を出力する出力部であり、モニタ、若しくはディスプレイ、タッチパネル等に該当する。入出力制御部２３０は、入力部２１０、出力部２２０、記憶部２４０、制御部２５０によるデータの入出力を制御する処理部である。
【０２３６】
記憶部２４０は、制御部２５０による各種処理に必要なデータおよびプログラムを記憶する記憶部である。図５６に示すように、この記憶部２４０は、登録データ管理テーブル２４０ａとトライ木２４０ｂを有する。
【０２３７】
ここで、登録データ管理テーブル２４０ａは、トライ木に登録するキーと値とを対応付けて記憶するテーブルである。図５７は、本実施例２にかかる登録データ管理テーブル２４０ａのデータ構造の一例を示す図である。図５７に示すように、この登録データ管理テーブル２４０ａは、キーと値を対応付けて記憶している。
【０２３８】
トライ木２４０ｂは、登録データ管理テーブル２４０ａを基にして生成されるトライ木である。図５８は、本実施例２にかかるトライ木のデータ構造の一例を示す図である。図５８では一例として、図５７に示した登録データ管理テーブル２４０ａに対応したトライ木を示す。図５８に示すように、ルートノードにノードb、ノードgが接続されており、ノードbにノードlが接続されている。
【０２３９】
ノードbは、一致数「１」、タグキー「ack」、値「２」を有し、ノードlは、一致数「０」、タグキー「ue」、値「１、３」を有し、ノードgは、一致数「０」、タグキー「reen」、値「４」を有している。
【０２４０】
図５８に示したトライ木２４０ｂを実データで表すと、図５９に示すデータ構造となる。図５９は、図５８に示したトライ木を実データで表した場合のデータ構造の一例を示す図である。図５９に示すように、このトライ木２４０ｂは、ポインタ配列３０〜３３、テキスト表３４を有している。
【０２４１】
ここで、ルートノードポインタに接続されたポインタ配列３０は、図５８のルートノードに対応し、ポインタ配列３１は、図５８のノードbに対応する。また、ポインタ配列３２は、図５８のノードlに対応し、ポインタ配列３３は、図５８のノードgに対応する。
【０２４２】
ポインタ配列３０〜３３は、「一致」領域、「TAG」領域、「Data」領域を有している。「一致」は、数値と対応付けることで、ノードの一致数を表現する。「TAG」は、テキスト表３４の文字と対応付けることで、ノードに接続されたタグキーを表現する。例えば、ポインタ配列３１は、テキスト表３４の「a」に接続されているので、「a」から次の空白前までの文字列「ack」をタグキーとして指定している。また、「Data」は、値と対応付けることで、ノードに接続された値を表現する。例えば、ポインタ配列３１は、値「２」に接続されている。
【０２４３】
また、各ポインタ配列３０〜３３は、配下に接続されたポインタ配列を判定するためのキー番号（ポインタ）「０×００〜０×ＦＦ」を有している。例えば、ポインタ配列３０のキー番号「０×６２」が、ポインタ配列３１に接続され、キー番号「０×６７」が、ポインタ配列３３に接続されている。
【０２４４】
図５６の説明に戻ると、制御部２５０は、各種の処理手順を規定したプログラムや制御データを格納するための内部メモリを有し、これらによって種々の処理を実行する制御部である。図５６に示すように、この制御部２５０は、トライ木生成部２５０ａと、トライ木探索部２５０ｂを有する。
【０２４５】
トライ木生成部２５０ａは、登録データ管理テーブル２４０ａに登録されたキーに基づいて、トライ木２４０ｂを生成する処理である。なお、トライ木生成部２５０ａは、実施例１と同様にして、深さ優先探索順でタグキーが並ぶようにトライ木を生成する。更に、トライ木生成部２５０ａは、図５５で説明したように、親ノードのタグキーと子ノードのタグキーを比較して、一致する文字数を一致数としてノードに登録する。また、トライ木生成部２５０ａは、親ノードのタグキーと子ノードのタグキーの一致する文字列を削除し、残りの文字列のみをタグキーとしてノードに登録する。
【０２４６】
以下において、トライ木生成部２５０ａがトライ木を生成する処理について具体的に説明する。図６０〜図６９は、本実施例２にかかるトライ木を生成する処理を説明するための図である。ここでは説明の便宜上、キー「http://aaa.aaa/e/」、値「１」と、キー「http://aaa.aaa/e/c/」、値「２」と、キー「http://aaa.aaa/d/」、値「３」と、キー「http://aaa.aaa/e/」、値「４」の順でトライ木を生成する場合について説明する。
【０２４７】
図６０に示すように、まず、ノードが存在しない状態で、キー「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」を取り除いた残りのキー「ttp://aaa.aaa/e/」をタグキーとして、ノードhに接続する。また、トライ木生成部２５０ａは、一致数「０」、値「１」をノードhに接続する（ステップＳ７２ａ）。
【０２５１】
実データ上において、トライ木生成部２５０ａは、ノードhに対応するポインタ配列３１を生成し、ポインタ配列３０のキー番号「０×６８」で、ポインタ配列３０とポインタ配列３１を接続する。また、トライ木生成部２５０ａは、ポインタ配列３１の「TAG」をテキスト表３４の１行目２列目の「t」に接続し、ポインタ配列３１の「Data」に１を接続する。また、トライ木生成部２５０ａは、ポインタ配列３１の一致（一致数）を「０」に設定する（ステップＳ７２ｂ）。
【０２５２】
続いて、図６１に移行し、ステップＳ７２ａ、７２ｂにおいて作成したトライ木に、キー「http://aaa.aaa/e/c/」、値「２」を追加する場合について説明する。トライ木生成部２５０ａは、入力キー「http://aaa.aaa/e/c/」の先頭文字hでルートノードからノードhに遷移する。そして、トライ木生成部２５０ａは、入力キー「http://aaa.aaa/e/c/」のポインタを１つ進め、２文字目の「t」に設定する（ステップＳ７３ａ）。
【０２５３】
実データ上において、トライ木生成部２５０ａは、テキスト表３４に最後に登録されたキー「http://aaa.aaa/e/」との間を１つ空けて、キー「http://aaa.aaa/e/c」を登録する。そして、トライ木生成部２５０ａは、テキスト表３４の２行目２列目の文字「t」に入力キーのポインタを接続する（ステップＳ７３ｂ）。
【０２５４】
トライ木生成部２５０ａは、ノードhにおいて、「t」をキーとする子ノードが存在しないので、ノードhのタグキー「ttp://aaa.aaa/e/」の優先度と、トライ部分の「h」を取り除いた入力キー「ttp://aaa.aaa/e/c/」の優先度を比較する。トライ木生成部２５０ａは、ノードhの一致数が「０」であるため、入力キーの先頭から順に比較を行う。
【０２５５】
すると、入力キーの１７文字目がcであり、タグキーの１７文字目が空であるため、トライ木生成部２５０ａは、入力キーの優先度が、タグキーの優先度よりも大きいと判定する。また、トライ木生成部２５０ａは、入力キーとタグキーを比較し、１６文字「ttp://aaa.aaa/e/」が一致していると判定する（ステップＳ７４）。
【０２５６】
続いて、図６２に移行する。トライ木生成部２５０ａは、ノードhに一致数「１６」を登録し、ノードhのタグキー「ttp://aaa.aaa/e/」のポインタを１６文字進める。その結果、ノードhに接続されるタグキーは空となる。
【０２５７】
また、トライ木生成部２５０ａは、入力キー「ttp://aaa.aaa/e/c/」の２文字目の「t」をキーとして新しいノードtを生成し、入力キーのポインタを３文字目の「t」に進める（ステップＳ７５ａ）。
【０２５８】
実データ上において、トライ木生成部２５０ａは、ノードtに対応するポインタ配列３２を生成し、ポインタ配列３１のキー番号「０×７４」で、ポインタ配列３１とポインタ配列３２を接続する。トライ木生成部２５０ａは、ノードhの「一致」に一致数「１６」を登録し、「TAG」に接続される文字を１６文字進め、テキスト表３４の１行目１８列目の空に設定する。トライ木生成部２５０ａは、入力キーのポインタを１つ進め、テキスト表３４の２行目３列目の「t」に入力キーのポインタを接続する（ステップＳ７５ｂ）。
【０２５９】
トライ木生成部２５０ａは、入力キー「http://aaa.aaa/e/c/」からトライ部分の「ht」を取り除いた残りのキー「tp://aaa.aaa/e/c/」を、ノードtのタグキーとして登録する。トライ木生成部２５０ａは、入力キー「http://aaa.aaa/e/c/」に対応する値「２」をノードtに登録する。また、トライ木生成部２５０ａは、一致数「０」をノードtに登録する（ステップＳ７６ａ）。
【０２６０】
実データ上において、トライ木生成部２５０ａは、ポインタ配列３２の「TAG」をテキスト表３４の２行目３列目の「t」に接続し、ポインタ配列３２の「Data」と値「２」を接続する。また、トライ木生成部２５０ａは、ポインタ配列３２の「一致」に、一致数「０」を登録する（ステップＳ７６ｂ）。
【０２６１】
続いて、図６３に移行し、ステップＳ７６ａ、７６ｂにおいて作成したトライ木に、入力キー「http://aaa.aaa/d/」、値「３」を追加する場合について説明する。トライ木生成部２５０ａは、入力キー「http://aaa.aaa/d/」の先頭文字から１文字ずつ取り出して、トライ木上をノードh、tの順に遷移する。そして、トライ木生成部２５０ａは、遷移したノード数に応じて、入力キー「http://aaa.aaa/d/」のポインタを２つ進め、３文字目の「t」に設定する。
【０２６２】
トライ木生成部２５０ａは、ノードtにおいて、「t」をキーとする子ノードが存在しないので、ノードtのタグキー「tp://aaa.aaa/e/c」の優先度と、トライ部分の「ht」を取り除いた入力キー「tp://aaa.aaa/d/」の優先度を比較する。すると、タグキーの１４文字目が「e」であり、入力キーの１４文字目が「d」であるため、タグキーの優先度の方が、入力キーの優先度よりも大きくなる（ステップＳ７７ａ）。
【０２６３】
実データ上において、トライ木生成部２５０ａは、テキスト表３４に最後に登録されたキー「http://aaa.aaa/e/c」との間を１つ空けて、キー「http://aaa.aaa/d/」を登録する。そして、トライ木生成部２５０ａは、テキスト表３４の３行目５列目の文字「t」に入力キーのポインタを接続する。また、ポインタ配列３２の「TAG」に接続された文字を先頭とする文字列と、入力キーのポインタに接続された文字を先頭とする文字列とを順次比較すると、タグキーの１４文字目が「e」であり、入力キーの１４文字目が「d」であるため、タグキーの優先度の方が、入力キーの優先度よりも大きくなる（ステップＳ７７ｂ）。
【０２６４】
トライ木生成部２５０ａは、入力キーとタグキーを比較して、世代数を判定する。この世代数は、入力キーが何文字目までタグキーと同じであるか否かを示す数値である。トライ木生成部２５０ａは、ノードtに登録されたタグキー「tp://aaa.aaa/e/c」と入力キーからトライ部分「ht」を取り除いたキー「tp://aaa.aaa/d/」とを比較した場合に、先頭から１３文字「tp://aaa.aaa/」が一致しているので、世代数が１３となる。
【０２６５】
トライ木生成部２５０ａは、入力キー「http://aaa.aaa/d/」のポインタを現在の３文字目の「t」から１３文字進めて、「d」に設定する。そして、トライ木生成部２５０ａは、現在のノードをノードhに移行し、世代数に１を加算して、世代数を１４とする（ステップＳ７８ａ）。これは、親ノードとなるノードhに遷移することで、比較対象となる入力キーの文字が１文字増えるが、かかる増加分の文字は、親ノードのタグキーと一致しているためである。
【０２６６】
実データ上において、トライ木生成部２５０ａは、テキスト表３４の３行目１８列目の文字「d」に、入力キーのポインタを接続する。また、トライ木生成部２５０ａは、世代数を判定し、世代数に「１４」を登録する。また、現在のノードのポインタをポインタ配列３１に接続する（ステップＳ７８ｂ）。
【０２６７】
続いて、図６４に移行する。トライ木生成部２５０ａは、ノードhのタグキーの優先度と、入力キー「http://aaa.aaa/d/」の優先度を比較する前に、ノードhに登録された一致数と、入力キーの世代数とを比較する。ノードhのタグキーの一致数は「１６」であり、入力キーの世代数は「１４」であるため、一致数の方が世代数よりも大きい。
【０２６８】
一致数が世代数よりも大き場合には、トライ木生成部２５０ａは、ノードhのタグキーの優先度と、入力キー「http://aaa.aaa/d/」の優先度を直接比較しなくても、ノードhのタグキーの優先度の方が大きいと判定できる。
【０２６９】
例えば、世代数１４の入力キーは、先頭文字から１３文字目までは、ノードhの子ノードとなるノードtのタグキーと同じであることを示し、１４文字目において、入力キーの優先度がノードtの優先度よりも小さい。そして、ノードhの一致数が入力キーの世代数より大きいということは、ノードtのタグキーの優先度が入力キーの優先度よりも大きいという決め手になった文字まで、ノードhのタグキーは少なくとも同じである。したがって、トライ木生成部２５０ａは、ノードhのタグキーの優先度と、入力キー「http://aaa.aaa/d/」の優先度を直接比較しなくても、ノードhのタグキーの優先度の方が大きいと判定できる。
【０２７０】
ノードhの親ノードがルートノードであるため、トライ木生成部２５０ａは、ノードhのデータ（一致数、タグキー、値）と、入力データ（世代数、入力キー、値）を交換する。具体的に、トライ木生成部２５０ａは、入力キーの世代数「１４」を一致数としてノードhに登録し、入力キーの値「３」もノードhに登録する。また、入力キー「http://aaa.aaa/d/」のポインタ以降の文字列「d/」をノードhのタグキーに登録する。
【０２７１】
そして、トライ木生成部２５０ａは、現在の入力キーを「http://aaa.aaa/e/」、値「１」、世代数「１６」に設定する。また、トライ木生成部２５０ａは、入力キーのポインタを先頭文字から１６文字ずらした「/」に設定する。トライ木生成部２５０ａは、ノードhの子ノードとなるノードtに移行し、入力キーのポインタを１文字ずらした「空」に設定する（ステップＳ７９ａ）。
【０２７２】
実データ上において、トライ木生成部２５０ａは、ポインタ配列３１の「TAG」と、テキスト表３４の３行目８列目の「t」に接続し、ポインタ配列３１の「一致」に「１４」を登録する。また、入力キーのポインタを、テキスト表３４の１行目１８列目の「空」に接続する。また、トライ木生成部２５０ａは、現在の世代数を「１６」に設定する（ステップＳ７９ｂ）。
【０２７３】
トライ木生成部２５０ａは、ノードtに移行した場合に、世代数１６から１を減算することで、世代数を「１５」に設定する。そして、トライ木生成部２５０ａは、ノードtのデータ（一致数、タグキー、値）と、入力データ（世代数、入力キー、値）を交換する。具体的に、トライ木生成部２５０ａは、入力キーの世代数「１５」を一致数としてノードtに登録し、入力キーの値「１」もノードtに登録する。また、入力キー「http://aaa.aaa/e/」のポインタ以降の文字「空」をノードtのタグキーに登録する。
【０２７４】
そして、トライ木生成部２５０ａは、現在の入力キーを「http://aaa.aaa/e/c/」、値「２」、世代数「０」に設定する。また、トライ木生成部２５０ａは、入力キーのポインタを、トライ部分に対応して、３文字目の「t」に設定する（ステップＳ８０ａ）。
【０２７５】
実データ上において、トライ木生成部２５０ａは、現在のノードのポインタをポインタ配列３２に接続する。トライ木生成部２５０ａは、ポインタ配列３２の「TAG」を、テキスト表３４の１行目１８列目の「空」に接続し、「一致」を１５に設定する。また、トライ木生成部２５０ａは、入力キーのポインタを、テキスト表３４の２行目３列目に接続し、世代数を「０」に設定する（ステップＳ８０ｂ）。
【０２７６】
続いて、図６５の説明に移行する。トライ木生成部２５０ａは、入力キー「http://aaa.aaa/e/c/」の３文字目に対応するノードtが、ノードtの配下に存在しないので、ノードtの配下に新たなノードｔを生成する。ここで、各ノードtを区別するために以下の説明では、親側のノードtをノードｔ（親）と表記し、子側のノードｔをノードｔ（子）と表記する。また、トライ木生成部２５０ａは、入力キーのポインタを３文字目の「p」に設定する（ステップＳ８１ａ）。
【０２７７】
実データ上において、トライ木生成部２５０ａは、ノードt（子）に対応するポインタ配列３３を生成し、ポインタ配列３２のキー番号「０×７４」で、ポインタ配列３２とポインタ配列３３を接続する。また、トライ木生成部２５０ａは、入力キーのポインタを、テキスト表３４の２行目４列目の「p」に接続する（ステップＳ８１ｂ）。
【０２７８】
続いて、図６６の説明に移行する。トライ木生成部２５０ａは、入力キー「http://aaa.aaa/e/c/」からトライ部分を取り除いた残りのキー「p://aaa.aaa/e/c/」をノードt（子）に接続する。また、トライ木生成部２５０ａは、入力キー「http://aaa.aaa/e/c/」に対応する値「２」をノードt（子）に接続する（ステップＳ８２ａ）。
【０２７９】
実データ上において、トライ木生成部２５０ａは、ポインタ配列３３の「TAG」をテキスト表３４の２行目４列目の「p」に接続し、入力キーのポインタを開放する。また、トライ木生成部２５０ａは、ポインタ配列３３の「Data」に値「２」を接続する（ステップＳ８２ｂ）。
【０２８０】
続いて、図６７に移行し、ステップＳ８２ａ、８２ｂにおいて作成したトライ木に、キー「http://aaa.aaa/e/」、値「４」を追加する場合について説明する。トライ木生成部２５０ａは、入力キー「http://aaa.aaa/e/」の先頭から文字を順次読み出し、ノードh、ノードt（親）、ノードt（子）に遷移する。そして、トライ木生成部２５０ａは、入力キー「http://aaa.aaa/e/」のポインタを４文字目の「p」に設定する（ステップＳ８３ａ）。
【０２８１】
実データ上において、トライ木生成部２５０ａは、テキスト表３４において最後に登録されたキー「http://aaa.aaa/e/d/」との間を１つ空けて、キー「http://aaa.aaa/e/」を登録する。そして、トライ木生成部２５０ａは、テキスト表３４の４行目６列目の文字「p」に入力キーのポインタを接続する（ステップＳ８３ｂ）。
【０２８２】
続いて、図６８に移行する。トライ木生成部２５０ａは、ノードt（子）において、「p」をキーとする子ノードが存在しないので、ノードtのタグキー「p://aaa.aaa/e/c/」の優先度と、トライ部分の「htt」を取り除いた入力キー「p://aaa.aaa/e/」の優先度を比較する。トライ木生成部２５０ａは、ノードt（子）の一致数が「０」であるため、入力キーの先頭から順に比較を行う。
【０２８３】
すると、入力キーのトライ木部分を除いた１５文字目が「空」であり、タグキーの１５文字目が「c」であるため、トライ木生成部２５０ａは、入力キーの優先度がタグキーの優先度よりも小さいと判定する。また、トライ木生成部２５０ａは、入力キーとタグキーを比較し、１４文字「p://aaa.aaa/e/」が一致していると判定する。
【０２８４】
トライ木生成部２５０ａは、入力キーのポインタを４文字目「p」から１４文字進める。また、トライ木生成部２５０ａは、親ノードとなるノードt（親）に遷移し、世代数「１４」に１を加算して「１５」とする（ステップＳ８４ａ）。
【０２８５】
実データ上において、トライ木生成部２５０ａは、入力キーのポインタをテキスト表３４の５行目２列目の空に接続する。また、トライ木生成部２５０ａは、現在のノードをポインタ配列３２に接続し、世代数を「１５」に設定する（ステップＳ８４ｂ）。
【０２８６】
続いて、図６９の説明に移行する。トライ木生成部２５０ａは、ノードt（親）の一致数と、世代数を比較すると双方とも「１５」で一致し、かつ、入力キーの優先度とタグキーの優先度が等しくなるので、ノードt（親）に値「４」を登録する（ステップＳ８５ａ）。
【０２８７】
実データ上において、トライ木生成部２５０ａは、ポインタ配列３１の一致と世代数とを比較しと双方とも「１５」で位置し、かつ、入力キーのポインタに接続された文字と、ポインタ配列３２に接続された文字が「空」で一致するので、ポインタ配列３２の「Data」に値「４」を接続する（ステップＳ８５ｂ）。
【０２８８】
図５６の説明に戻ると、トライ木探索部２５０ｂは、トライ木２４０ｂに登録された値の集計値を抽出する処理、所定のキーに対応する値をトライ木２４０ｂから検索する処理を実行する処理部である。
【０２８９】
まず、トライ木探索部２５０ｂが、トライ木２４０ｂに登録された値の集計値を抽出する処理について説明する。図７０〜図７２は、本実施例２における集計値を抽出する処理を説明するための図である。図７０に示すように、トライ木２４０ｂは、ルートノードの配下に、ノードh、ノードt（親）、ノードt（子）が順に接続されている。ノードhは、一致数「１４」、タグキー「d/（http://aaa.aaa/d/）」、値「３」を登録し、ノードt（親）は、一致数「１５」、タグキー「空（http://aaa.aaa/e/）」、値「１、４」を登録する。また、ノードt（子）は、一致数「０」、タグキー「p://aaa.aaa/e/c/（http://aaa.aaa/e/c/）」、値「２」を登録する。
【０２９０】
また、図７０〜７２における説明では、ルートノード、ノードh、ノードt（親）、ノードt（子）の順に、集計値を抽出する場合について説明する。図７０において、トライ木探索部２５０ｂは、ルートノードからノードhに移行する。ノードhは、タグキー「d/（http://aaa.aaa/d/」、値「３」が登録されているので、トライ木探索部２５０ｂは、キー「http://aaa.aaa/d/」と、値（合計値）「３」を出力する（ステップＳ８６ａ）。
【０２９１】
実データ上において、トライ木探索部２５０ｂは、現在のノードをノードhに対応するポインタ配列３１に接続する。トライ木探索部２５０ｂは、ノードhの階層数「１」と一致「１４」を加算した値「１５」を算出し、「TAG」に接続された文字「ｄ」を起点として１５文字戻す。そして、トライ木探索部２５０ｂは、戻した文字「h」から「空」までのキー「http://aaa.aaa/d/」を出力する。また、トライ木探索部２５０ｂは、ポインタ配列３１の「Data」に接続された値「３」を出力する（ステップＳ８６ｂ）。
【０２９２】
図７１の説明に移行する。トライ木探索部２５０ｂは、ノードhからノードt（親）に移行する。ノードt（親）は、タグキー「空（http://aaa.aaa/e/）」、値「１、４」が登録されているので、トライ木探索部２５０ｂは、キー「http://aaa.aaa/e/」と、値「１、４」を合計した値「５」を出力する（ステップＳ８７ａ）。
【０２９３】
実データ上において、トライ木探索部２５０ｂは、現在のノードをノードt（親）に対応するポインタ配列３２に接続する。トライ木探索部２５０ｂは、ノードt（親）の階層数「２」と一致「１５」を加算した値「１７」を算出し、「TAG」に接続された「空」を起点として１７文字戻す。そして、トライ木探索部２５０ｂは、戻した文字「h」から「空」までのキー「http://aaa.aaa/e/」を出力する。また、トライ木探索部２５０ｂは、「Data」に接続された値「１、４」の合計値「５」を出力する（ステップＳ８７ｂ）。
【０２９４】
図７２の説明に移行する。トライ木探索部２５０ｂは、ノードt（親）からノードt（子）に移行する。ノードt（子）は、タグキー「p://aaa.aaa/e/c/（http://aaa.aaa/e/c/）」、値「２」が登録されているので、トライ木探索部２５０ｂは、キー「http://aaa.aaa/e/c/」と、値「２」を出力する（ステップＳ８８ａ）。
【０２９５】
実データ上において、トライ木探索部２５０ｂは、現在のノードをノードt（子）に対応するポインタ配列３３に接続する。トライ木探索部２５０ｂは、ノードt（子）の階層数「３」と一致「０」を加算した値「３」を算出し、「TAG」に接続された「p」を起点として３文字戻す。そして、トライ木探索部２５０ｂは、戻した文字「h」から「空」までのキー「http://aaa.aaa/e/c/」を出力する。また、トライ木探索部２５０ｂは、「Data」に接続された値「２」を出力する（ステップＳ８８ｂ）。
【０２９６】
図７０〜図７２では、ルートノードから順にノードを辿って、各ノードに登録されたキー、値を出力する場合について説明した。しかし、実施例１に示したように、所定のキーを指定し、指定したキーに基づいて集計値を抽出しても良い。
【０２９７】
次に、トライ木探索部２５０ｂが、指定された入力キーに対応する値をトライ木２４０ｂから検索する処理について説明する。トライ木探索部２５０ｂは、トライ木２４０ｂが、深さ優先探索順でタグキーが並ぶように生成されているので、比較対象ノードに登録されたタグキーと入力キーを比較すればよい。また、図６０〜６９に示したトライ木を生成する処理と同様にして、一致数、世代数を利用することで、比較する文字数を削減することも可能である。
【０２９８】
図７３〜図７７は、本実施例２にかかる探索処理を説明するための図である。図７３に示すように、トライ木２４０ｂは、ルートノードの配下にノードb、ノードa、ノードb、ノードcが接続されている。ここで、各ノードbを区別するために、ルートノードの子ノードに対応するノードbをノードb（１）と表記し、もう一方のノードbをノードb（２）と表記する。
【０２９９】
ノードb（１）は、一致数「１」、タグキー「空」、値「１」を登録し、ノードaは、一致数「０」、タグキー「aa」、値「３」を登録する。ノードb（２）は、一致数「０」、タグキー「c」、値「１」を登録し、ノードcは、一致数「０」、タグキー「b」、値「２」を登録する。
【０３００】
また、図７３〜図７７における説明では、入力キー「baca」が指定された場合の検索処理について説明する。図７３において、トライ木探索部２５０ｂは、入力キーのポインタを先頭文字「b」に設定し、ポインタの指定する「b」により、ルートノードからノードb（１）に遷移する。そして、トライ木探索部２５０ｂは、入力キーのポインタを「b」から１文字ずらした「a」に設定する（ステップＳ８９ａ）。
【０３０１】
実データ上では、トライ木探索部２５０ｂは、テキスト表３４に入力キー「baca」を登録し、入力キーのポインタをテキスト表３４の２行目１列目の「b」に接続する。トライ木探索部２５０ｂは、入力キーのポインタに接続された「b」により、ポインタ配列４０からポインタ配列４１に現在のノードのポインタを移動させ、入力キーのポインタを１文字ずらした「a」に設定する（ステップＳ８９ｂ）。
【０３０２】
続いて、図７４の説明に移行する。トライ木探索部２５０ｂは、ポインタの指定する「a」により、ノードb（１）からノードaに遷移し、入力キーのポインタを「a」から１文字ずらした「c」に設定する（ステップＳ９０ａ）。
【０３０３】
実データ上では、トライ木探索部２５０ｂは、入力キーのポインタに接続された「a」により、ポインタ配列４１からポインタ配列４２に現在のノードのポインタを遷移させ、入力キーのポインタを１文字ずらした「c」に設定する（ステップＳ９０ｂ）。
【０３０４】
続いて、図７５の説明に移行する。トライ木探索部２５０ｂは、ポインタの指定する「c」により、ノードaからノードcに遷移し、入力キーのポインタを「c」から１文字ずらした「a」に設定する（ステップＳ９１ａ）。
【０３０５】
実データ上では、トライ木探索部２５０ｂは、入力キーのポインタに接続された「c」により、ポインタ配列４２からポインタ配列４３に現在のノードのポインタを遷移させ、入力キーのポインタを１文字ずらした「a」に設定する（ステップＳ９１ｂ）。
【０３０６】
続いて、図７６の説明に移行する。トライ木探索部２５０ｂは、ポインタの指定する「a」に対応する子ノードが、ノードaに存在しないので、ノードcの一致数と世代数を比較する。一致数と世代数が等しいので、トライ木探索部２５０ｂは、ノードcのタグキー「b」と、トライ部分「bac」を取り除いた入力キー「a」の優先度とを比較する。トライ木探索部２５０ｂは、ノードcの一致数が「０」であるため、キーの先頭から順に比較を行う。トライ木探索部２５０ｂは、比較した結果、入力キーの優先度よりもタグキーの優先度の方が大きいと判定する（ステップＳ９２ａ）。
【０３０７】
実データ上において、トライ木探索部２５０ｂは、ポインタ配列４４の「一致」と世代数を比較する。一致数と世代数が等しいので、トライ木探索部２５０ｂは、ポインタ配列４４の「TAG」に接続された文字「b」の優先度と、入力キーのポインタに接続された文字「a」の優先度を比較する。トライ木探索部２５０ｂは、比較した結果、入力キーの優先度よりもタグキーの優先度の方が大きいと判定する（ステップＳ９２ｂ）。
【０３０８】
図７７の説明に移行する。トライ木探索部２５０ｂは、ノードcが兄ノード「ノードb（２）」を有するので、ノードcより前のノード（ノードa、ノードb（１））に、入力キーと一致するタグキーを有するノードは存在しないと判定する。トライ木探索部２５０ｂは、該当データが存在しない旨を出力する（ステップＳ９３）。
【０３０９】
次に、本実施例２にかかる検索装置２００の各種の処理手順について説明する。まず、本実施例２にかかる検索装置２００がトライ木２４０ｂを生成する処理について説明する。図７８は、本実施例２にかかるトライ木生成処理の処理手順を示すフローチャートである。
【０３１０】
図７８に示すように、トライ木生成部２５０ａは、ルートノードを生成し（ステップＳ５００）、次の入力データ（キー、値）が登録データ管理テーブル２４０ａに存在するか否かを判定する（ステップＳ５０１）。
【０３１１】
トライ木生成部２５０ａは、次の入力データが登録データ管理テーブル２４０ａに存在しないと判定した場合には（ステップＳ５０２，Ｎｏ）、処理を終了する。一方、トライ木生成部２５０ａは、次の入力データが登録データ管理テーブル２４０ａに登録されている場合には（ステップＳ５０２，Ｙｅｓ）、未読の入力データを読み出し（ステップＳ５０３）、データ追加処理を実行する（ステップＳ５０４）。
【０３１２】
次に、図７８のステップＳ５０４に示したデータ追加処理の処理手順について説明する。ここでは、二分探索法を用いないでデータ追加処理を実行する場合について説明するが、実施例１と同様にして、二分探索法を用いても良い。
【０３１３】
図７９〜図８１は、本実施例２にかかるデータ追加処理の処理手順を示すフローチャートである。図７９に示すように、トライ木生成部２５０ａは、現在のノードをルートノードに設定し（ステップＳ５１０）、入力キーが空であるか否かを判定する（ステップＳ５１１）。
【０３１４】
トライ木生成部２５０ａは、入力キーが空の場合に（ステップＳ５１２，Ｙｅｓ）、世代数を０に設定し（ステップＳ５１３）、図８０のステップＳ５１９に移行する。一方、トライ木生成部２５０ａは、入力キーが空ではない場合に（ステップＳ５１２，Ｎｏ）、入力キーの先頭文字のキーで子ノードを参照し、子ノードが存在するか否かを判定する（ステップＳ５１４）。
【０３１５】
トライ木生成部２５０ａは、子ノードが存在する場合に（ステップＳ５１５，Ｙｅｓ）、入力キーの先頭の１文字を読み取り、入力キーのポインタを１文字進め、読み出した文字をキーとして子ノードに遷移し（ステップＳ５１６）、ステップＳ５１１に移行する。
【０３１６】
一方、トライ木生成部２５０ａは、子ノードが存在しない場合に（ステップＳ５１５，Ｎｏ）、長男キーの優先度が入力キーの先頭文字のキーの優先度よりも小さいか否かを判定する（ステップＳ５１７）。トライ木生成部２５０ａは、長男キーの優先度が入力キーの先頭文字のキーの優先度よりも小さくない場合に（ステップＳ５１８，Ｎｏ）、ステップＳ５１３に移行する。
【０３１７】
一方、トライ木生成部２５０ａは、長男キーの優先度が入力キーの先頭文字のキーの優先度よりも小さい場合に（ステップＳ５１８，Ｙｅｓ）、図８１のステップ５３６に移行する。
【０３１８】
続いて、図８０の説明に移行し、トライ木生成部２５０ａは、ノードの情報を参照し（ステップＳ５１９）、一致数と世代数が等しいか否かを判定する（ステップＳ５２０）。トライ木生成部２５０ａは、一致数と世代数が異なる場合に（ステップＳ５２１，Ｎｏ）、一致数が世代数よりも大きいか否かを判定する（ステップＳ５２２）。
【０３１９】
トライ木生成部２５０ａは、一致数が世代数よりも大きくない場合には（ステップＳ５２３，Ｎｏ）、図８１のステップＳ５３８に移行する。一方、トライ木生成部２５０ａは、一致数が世代数よりも大きい場合に（ステップＳ５２３，Ｙｅｓ）、ステップＳ５３０に移行する。
【０３２０】
ところで、トライ木生成部２５０ａは、ステップＳ５２５において、タブキーの優先度と入力キーの優先度が等しい場合に（ステップＳ５２５，Ｙｅｓ）、現在のノードのデータに入力値を追加し（ステップＳ５２６）、データ追加処理を終了する（ステップＳ５２７）。
【０３２１】
一方、トライ木生成部２５０ａは、タグキーの優先度と入力キーの優先度が異なる場合に（ステップＳ５２５，Ｎｏ）、タグキーの優先度が入力キーの優先度よりも大きいか否かを判定する（ステップＳ５２７）。トライ木生成部２５０ａは、タグキーの優先度が入力キーの優先度よりも大きくない場合には（ステップＳ５２８，Ｎｏ）、図８１のステップＳ５３３に移行する。
【０３２２】
一方、トライ木生成部２５０ａは、タグキーの優先度が入力キーの優先度よりも大きい場合に（ステップＳ５２８，Ｙｅｓ）、前方一致した文字数を世代数に追加し、入力キーのポインタを前方一致した文字数分だけ進める（ステップＳ５２９）。
【０３２３】
トライ木生成部２５０ａは、兄ノードが存在する、または、親ノードがルートノードであるか否かを判定する（ステップＳ５３０）。トライ木生成部２５０ａは、兄ノードが存在せず、かつ、親ノードがルートノードでない場合（条件を満たさない場合）に（ステップＳ５３１，Ｎｏ）、世代数に１を加算し、親ノードへ遷移し（ステップＳ５３２）、ステップＳ５２９に移行する。
【０３２４】
一方、トライ木生成部２５０ａは、兄ノードが存在する、または、親ノードがルートノードである場合（条件を満たす場合）に（ステップＳ５３１，Ｙｅｓ）、図８１のステップＳ５３９に移行する。
【０３２５】
続いて、図８１の説明に移行し、トライ木生成部２５０ａは、現在のタグ情報において、一致数に前方一致した文字数を加算し、タグキーのポインタを前方一致した文字数分だけ進め（ステップＳ５３３）、世代数が０であるか否かを判定する（ステップＳ５３４）。
【０３２６】
トライ木生成部２５０ａは、世代数が０の場合に（ステップＳ５３５，Ｙｅｓ）、新しいノードを生成し、現在のノードから入力キーの先頭文字をキーとして新しいノードに接続し、入力キーのポインタを進める（ステップＳ５３６）。
【０３２７】
トライ木生成部２５０ａは、世代数、入力キーをタグ情報として新しいノードに付加し（ステップＳ５３７）、入力値を新しいノードに付加し（ステップＳ５３８）、データ追加処理を終了する。
【０３２８】
一方、トライ木生成部２５０ａは、世代数が０ではない場合に（ステップＳ５３５，Ｎｏ）、世代数から１を減算し、長男ノードへ遷移する（ステップＳ５３８）。トライ木生成部２５０ａは、現在のノードの一致数、タグキー、値と世代数、入力キー、入力値をぞれぞれ交換し（ステップＳ５３９）、世代数が０であるか否かを判定する（ステップＳ５４０）。
【０３２９】
トライ木生成部２５０ａは、世代数が０の場合に（ステップＳ５４１，Ｙｅｓ）、入力キーの先頭文字のキーで子ノードを参照し（ステップＳ５４２）、ステップＳ５３６に移行する。一方、トライ木生成部２５０ａは、世代数が０ではない場合に（ステップＳ５４１，Ｎｏ）、ステップＳ５３８に移行する。
【０３３０】
次に、本実施例２にかかる検索装置２００がトライ木２４０ｂを用いて検索を行う処理について説明する。ここでは、二分探索法を用いないで検索処理を実行する場合について説明するが、実施例１と同様にして、二分探索法を用いても良い。
【０３３１】
図８２および図８３は、本実施例２にかかる検索処理の処理手順を示すフローチャートである。図８２に示すように、トライ木探索部２５０ｂは、現在のノードをルートノードに設定し（ステップＳ５５０）、入力キーが存在するか否かを判定する（ステップＳ５５１）。
【０３３２】
トライ木探索部２５０ｂは、入力キーが存在する場合に（ステップＳ５５２，Ｙｅｓ）、入力キーの先頭文字のキーで子ノードを参照し、キーの子ノードが存在するか否かを判定する（ステップＳ５５３）。
【０３３３】
トライ木探索部２５０ｂは、子ノードが存在する場合に（ステップＳ５５４，Ｙｅｓ）、先頭キーで子ノードへ遷移し、入力キーのポインタを進め（ステップＳ５５５）、ステップＳ５５１に移行する。
【０３３４】
一方、トライ木探索部２５０ｂは、子ノードが存在しない場合に（ステップＳ５５４，Ｎｏ）、長男キーの優先度が入力キーの先頭のキーの優先度よりも小さいか否かを判定する（ステップＳ５５６）。
【０３３５】
トライ木探索部２５０ｂは、長男キーの優先度が入力キーの先頭のキーの優先度よりも小さい場合に（ステップＳ５５７，Ｙｅｓ）、一致データが無い旨を出力する（ステップＳ５５８）。一方、トライ木探索部２５０ｂは、長男キーの優先度が入力キーの先頭のキーの優先度よりも小さくない場合には（ステップＳ５５７，Ｎｏ）、ステップＳ５５９に移行する。
【０３３６】
ところで、トライ木探索部２５０ｂは、ステップＳ５５２において、入力キーが存在しない場合に（ステップＳ５５２，Ｎｏ）、世代数を０に設定し（ステップＳ５５９）、図８３のステップＳ５６０に移行する。
【０３３７】
続いて、図８３の説明に移行し、トライ木探索部２５０ｂは、ノードの情報を参照し、一致数が世代数と等しいか否かを判定する（ステップＳ５６０）。トライ木探索部２５０ｂは、一致数と世代数が等しくない場合に（ステップＳ５６１，Ｎｏ）、一致数が世代数よりも大きいか否かを判定する（ステップＳ５６２）。
【０３３８】
トライ木探索部２５０ｂは、一致数が世代数よりも大きくない場合に（ステップＳ５６３，Ｎｏ）、一致データが無い旨を出力する（ステップＳ５６４）。トライ木探索部２５０ｂは、一致数が世代数よりも大きい場合に（ステップＳ５６３，Ｙｅｓ）、ステップＳ５７１に移行する。
【０３３９】
ところで、トライ木探索部２５０ｂは、ステップＳ５６１において、一致数と世代数が等しい場合に（ステップＳ５６１，Ｙｅｓ）、タグキーの優先度と入力キーの優先度が等しいか否かを判定する（ステップＳ５６５）。
【０３４０】
トライ木探索部２５０ｂは、タグキーの優先度と入力キーの優先度が等しい場合に（ステップＳ５６６，Ｙｅｓ）、現在のノードのデータを出力する（ステップＳ５６７）。一方、トライ木探索部２５０ｂは、タグキーの優先度と入力キーの優先度が異なる場合に（ステップＳ５６６，Ｎｏ）、タグキーの優先度が入力キーの優先度よりも大きいか否かを判定する（ステップＳ５６８）。
【０３４１】
トライ木探索部２５０ｂは、タグキーの優先度が入力キーの優先度よりも大きくない場合には（ステップＳ５６９，Ｎｏ）、ステップＳ５６４に移行する。一方、トライ木探索部２５０ｂは、タグキーの優先度が入力キーの優先度よりも大きい場合に（ステップＳ５６９，Ｙｅｓ）、前方一致した文字数を世代数に追加し、入力キーのポインタを前方一致した文字数分だけ進める（ステップＳ５７０）。
【０３４２】
トライ木探索部２５０ｂは、兄ノードが存在する、または、親ノードがルートノードであるか否かを判定する（ステップＳ５７１）。トライ木探索部２５０ｂは、兄ノードが存在しない、かつ、親ノードがルートノードでない場合（条件を満たさない場合）に（ステップＳ５７２，Ｎｏ）、世代数に１を加算し、親ノードへ遷移し（ステップＳ５７３）、ステップＳ５６０に移行する。
【０３４３】
一方、トライ木探索部２５０ｂは、兄ノードが存在する、または、親ノードがルートノードである場合（条件を満たす場合）に（ステップＳ５７２，Ｙｅｓ）、ステップＳ５６４に移行する。
【０３４４】
次に、本実施例２にかかる検索装置２００が実行する集計値の抽出処理について説明する。図８４は、本実施例２にかかる集計値の抽出処理の処理手順を示すフローチャートである。図８４に示すように、トライ木探索部２５０ｂは、現在のノードをルートノードに設定し（ステップＳ６００）、子ノードが存在するか否かを判定する（ステップＳ６０１）。
【０３４５】
トライ木探索部２５０ｂは、子ノードが存在しない場合には（ステップＳ６０２，Ｎｏ）、弟ノードが存在するか否かを判定する（ステップＳ６０３）。トライ木探索部２５０ｂは、弟ノードが存在しない場合に（ステップＳ６０４，Ｎｏ）、親ノードへ遷移し（ステップＳ６０５）、ステップＳ６０３に移行する。
【０３４６】
一方、トライ木探索部２５０ｂは、弟ノードが存在する場合に（ステップＳ６０４，Ｙｅｓ）、次弟ノードへ遷移し（ステップＳ６０６）、ステップＳ６０９に移行する。
【０３４７】
ところで、トライ木探索部２５０ｂは、ステップＳ６０２において、子ノードが存在する場合に（ステップＳ６０２，Ｙｅｓ）、タグキーのポインタから一致数＋階層数分だけ戻した位置から、キーを取得する（ステップＳ６０８）。そして、トライ木探索部２５０ｂは、現在のノードの各種値を加工し出力し（ステップＳ６０９）、ステップＳ６０１に移行する。
【０３４８】
次に、本実施例２にかかる検索装置２００が実行する削除処理の処理手順について説明する。図８５〜図８８は、本実施例２にかかる削除処理の処理手順を示すフローチャートである。図８５に示すように、トライ木探索部２５０ｂは、入力キーが存在するか否かを判定し（ステップＳ６１０）、入力キーが存在する場合（ポインタの示す文字が空でない場合）には（ステップＳ６１１，Ｙｅｓ）、入力キーの先頭文字のキーで子ノードを参照し、子ノードが存在するか否かを判定する（ステップＳ６１２）。
【０３４９】
トライ木探索部２５０ｂは、子ノードが存在する場合には（ステップＳ６１３，Ｙｅｓ）、先頭キーで子ノードへ遷移し、入力キーのポインタを進め（ステップＳ６１４）、ステップＳ６１０に移行する。
【０３５０】
一方、トライ木探索部２５０ｂは、子ノードが存在しない場合には（ステップＳ６１３，Ｎｏ）、ノードの一致数が０であるか否かを判定する（ステップＳ６１５）。トライ木探索部２５０ｂは、一致数が０でない場合に（ステップＳ６１６，Ｎｏ）、長男キーの優先度が入力キーの先頭文字のキーの優先度よりも小さいか否かを判定する（ステップＳ６１７）。トライ木探索部２５０ｂは、長男キーの優先度が入力キーの先頭文字のキーの優先度よりも小さい場合には（ステップＳ６１８，Ｙｅｓ）、削除データが存在しない旨を出力する（ステップＳ６１９）。
【０３５１】
ところで、トライ木探索部２５０ｂは、ステップＳ６１１において、入力キーが存在しない場合（ポインタの文字が空の場合）には（ステップＳ６１１，Ｎｏ）、世代数を０に設定し（ステップＳ６２０）、図８６のステップＳ６２１に移行する。
【０３５２】
続いて、トライ木探索部２５０ｂは、図８６において、ノードの情報を参照し（ステップＳ６２１）、一致数が世代数と等しいか否かを判定する（ステップＳ６２２）。トライ木探索部２５０ｂは、一致数と世代数が等しくない場合に（ステップＳ６２３，Ｎｏ）、一致数が世代数よりも大きいか否かを判定する（ステップＳ６２４）。
【０３５３】
トライ木探索部２５０ｂは、一致数が世代数よりも大きい場合に（ステップＳ６２５，Ｙｅｓ）、ステップＳ６３１に移行する。一方、トライ木探索部２５０ｂは、一致数が世代数よりも大きくない場合に（ステップＳ６２５，Ｎｏ）、ステップＳ６３４に移行する。
【０３５４】
ところで、トライ木探索部２５０ｂは、ステップＳ６２３において、一致数と世代数が等しい場合に（ステップＳ６２３，Ｙｅｓ）、タグキーの優先度が入力キーの優先度と等しいか否かを判定する（ステップＳ６２６）。
【０３５５】
トライ木探索部２５０ｂは、タグキーの優先度が入力キーの優先度と等しい場合に（ステップＳ６２７，Ｙｅｓ）、図８７のステップＳ６３５に移行する。一方、トライ木探索部２５０ｂは、タグキーの優先度が入力キーの優先度と等しくない場合に（ステップＳ６２７，Ｎｏ）、タグキーの優先度が入力キーの優先度よりも大きいか否かを判定する（ステップＳ６２８）。
【０３５６】
トライ木探索部２５０ｂは、タグキーの優先度が入力キーの優先度よりも大きくない場合には（ステップＳ６２９，Ｎｏ）、ステップＳ６３４に移行する。一方、トライ木探索部２５０ｂは、タグキーの優先度が入力キーの優先度よりも大きい場合に（ステップＳ６２９，Ｙｅｓ）、前方一致した文字を世代数に追加し、入力キーのポインタを前方一致した文字数分だけ進める（ステップＳ６３０）。
【０３５７】
トライ木探索部２５０ｂは、兄ノードが存在する、または、親ノードがルートノードであるか否かを判定する（ステップＳ６３１）。トライ木探索部２５０ｂは、兄ノードが存在せず、かつ、親ノードがルートノードでない場合（条件を満たさない場合）に（ステップＳ６３２，Ｎｏ）、世代数に１を加算し、親ノードへ遷移し（ステップＳ６３３）、ステップＳ６２１に移行する。
【０３５８】
一方、トライ木探索部２５０ｂは、兄ノードが存在する、または、親ノードがルートノードの場合に（ステップＳ６３２，Ｙｅｓ）、削除データが存在しない旨を出力する（ステップＳ６３４）。
【０３５９】
続いて、図８７に移行し、トライ木探索部２５０ｂは、削除対象データが存在するか否かを判定する（ステップＳ６３５）。トライ木探索部２５０ｂは、削除対象データが存在しない場合に（ステップＳ６３６，Ｎｏ）削除データが存在しない旨を出力する（ステップＳ６３７）。
【０３６０】
一方、トライ木探索部２５０ｂは、削除対象データが存在する場合に（ステップＳ６３８）、他のデータが存在するか（ノードに他の値が登録されているか否か）否かを判定する（ステップＳ６３９）。トライ木探索部２５０ｂは、他のノードが存在する場合に（ステップＳ６４０，Ｙｅｓ）、処理を終了する。一方、トライ木探索部２５０ｂは、他のデータが存在しない場合に（ステップＳ６４０，Ｎｏ）、図８８のステップＳ６４１に移行する。
【０３６１】
続いて、図８８に移行し、トライ木探索部２５０ｂは、現在のノードが長男であるか否かを判定し（ステップＳ６４１）、長男ではない場合に（ステップＳ６４２，Ｎｏ）、ステップＳ６４７に移行する。
【０３６２】
一方、トライ木探索部２５０ｂは、現在のノードが長男の場合に（ステップＳ６４２，Ｙｅｓ）、親ノードの一致数が現在のノードの一致数よりも大きいか否かを判定する（ステップＳ６４３）。トライ木探索部２５０ｂは、親ノードの一致数が現在のノードの一致数よりも大きくない場合に（ステップＳ６４４，Ｎｏ）、ステップＳ６４７に移行する。
【０３６３】
一方、トライ木探索部２５０ｂは、親ノードの一致数が現在のノードの一致数よりも大きい場合に（ステップＳ６４４，Ｙｅｓ）、親ノードの一致数から現在のノードの一致数を減算したものから更に１を減算したものを差分一致数として算出する（ステップＳ６４５）。
【０３６４】
トライ木探索部２５０ｂは、現在のノードの一致数に１を加算したものを親ノードの一致数に設定し、親ノードのタグ文字列のポインタを差分一致数分戻し（ステップＳ６４６）、子ノードが存在するか否かを判定する（ステップＳ６４７）。
【０３６５】
トライ木探索部２５０ｂは、子ノードが存在する場合に（ステップＳ６４８，Ｙｅｓ）、現在のノードのデータを長男ノードのデータとし、一致数に１加算する（ステップＳ６４９）。トライ木探索部２５０ｂは、長男ノードへ遷移し（ステップＳ６５０）、ステップＳ６４７に移行する。
【０３６６】
一方、トライ木探索部２５０ｂは、子ノードが存在しない場合に（ステップＳ６４８，Ｎｏ）、現在のノードが長男であるか否かを判定する（ステップＳ６１２）。トライ木探索部２５０ｂは、現在のノードが長男ではない場合に（ステップＳ６５２，Ｎｏ）、ステップＳ６５４に移行する。
【０３６７】
一方、トライ木探索部２５０ｂは、現在のノードが長男ノードの場合に（ステップＳ６５２，Ｙｅｓ）、親ノードのタグ文字列のポインタを親ノードの一致数分だけ戻し、親ノードの一致数を０にする（ステップＳ６５３）。そして、トライ木探索部２５０ｂは、親ノードの現在のノードへのエッジを削除し、現在のノードを削除する（ステップＳ６５４）。
【０３６８】
上述してきたように、本実施例２にかかる検索装置２００は、各ノードのタグキーと入力キーとを比較する場合に、先頭文字から順に各キー（タグキーと入力キー）の文字を比較するのではなく、子ノードに登録されたタグキーとの一致数だけ比較する文字をスキップするので、入力キーをトライ木に登録する処理を高速化することが出来る。
【０３６９】
なお、本実施例２では一例として、子ノードの文字列と一部一致する文字列を親ノードに登録する場合に、文字列をそのまま親ノードに登録する代わりに、一致する文字列の長さと、残りの文字列を親ノードに登録していた。しかし、本願発明は、これに限定されるものではない。例えば、親ノードの文字列と一部一致する文字列を子ノードに登録する場合に、文字列をそのまま子ノードに登録する代わりに、一致する文字列の長さと、残りの文字列を子ノードに登録してもよい。
【０３７０】
ところで、本実施例において説明した各処理のうち、自動的におこなわれるものとして説明した処理の全部または一部を手動的におこなうこともでき、あるいは、手動的におこなわれるものとして説明した処理の全部または一部を公知の方法で自動的におこなうこともできる。この他、上記文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
【０３７１】
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。さらに、各装置にて行なわれる各処理機能は、その全部または任意の一部が、ＣＰＵおよび当該ＣＰＵにて解析実行されるプログラムにて実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。
【０３７２】
図８９は、実施例２に示した検索装置２００（あるいは、実施例１にかかる検索装置１００）に対応するコンピュータのハードウェア構成を示す図である。図８９に示すように、このコンピュータ（検索装置）１０は、入力装置１１、モニタ１２、ＲＡＭ（Random  Access  Memory）１３、ＲＯＭ（Read  Only  Memory）１４、ネットワークを介して他の装置とデータ通信を実行する通信制御装置１５、媒体読取装置１６、ＣＰＵ（Central  Processing  Unit）１７、ＨＤＤ（Hard  Disk  Drive）１８をバス１９で接続している。
【０３７３】
そして、ＨＤＤ１８には、上述した検索装置２００の機能と同様の機能を発揮するトライ木生成プログラム１８ｂ、トライ木探索プログラム１８ｃが記憶されている。ＣＰＵ１７が、トライ木生成プログラム１８ｂ、トライ木探索プログラム１８ｃを読み出して実行することにより、トライ木生成プロセス１７ａ、トライ木探索プロセス１７ｂが起動される。
【０３７４】
ここで、トライ木生成プロセス１７ａは、図５６に示したトライ木生成部２５０ａに対応する。また、トライ木探索プロセス１７ｂは、図５６に示したトライ木探索部２５０ｂに対応する。
【０３７５】
なお、ＨＤＤ１８は、図５６で示した記憶部２４０に記憶されたデータに対応する各種データ１８ａを記憶している。ＣＰＵ１７は、ＨＤＤ１８に記憶された各種データ１８ａをＲＡＭ１３に読み出し、各種データ１３ａを利用して、トライ木の構築等を実行する。
【０３７６】
以上の各実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０３７７】
（付記１）コンピュータに、
所定の文字に対応するノードが木構造にて接続されるトライ木を記憶装置に記憶し、当該トライ木に新規の文字列を登録する場合に、当該新規の文字列の文字を先頭から順に読み出して前記トライ木に含まれるノードを当該ノードに対応する文字に応じて辿り、単一のノードに対して単一の文字列が登録されるように、辿ったノードの何れかに新規の文字列を登録する場合に、登録対象のノードの子ノードに登録された文字列と新規の文字列とを比較して一致する文字を判定し、新規の文字列から一致する文字を除いた残りの文字列と一致文字数を、登録対象のノードに登録する文字列登録機能
を実現させるためのプログラムを格納した記憶媒体。
【０３７８】
（付記２）前記文字列登録機能は、各ノードに登録される各文字列に対して所定も文字順序に基づく優先度を設定し、当該優先度に基づいて各ノードに各文字列を登録することを特徴とする付記１に記載の記憶媒体。
【０３７９】
（付記３）前記文字列登録機能は、ノードに登録された文字列の優先度と、新規の文字列の優先度とを比較して、登録されたノードの文字列の優先度よりも新規の文字列の優先度の方が小さい場合に、登録された文字列と新規の文字列で一致する文字数を判定する判定機能と、前記ノードの親ノードに遷移し、前記判定機能で判定した一致する文字数と、前記親ノードに登録された一致文字数とを基にして、新規のノードを前記親ノードに登録するか否かを判定する登録機能を更に実現させるためのプログラムを格納した付記１または２に記載の記憶媒体。
【０３８０】
（付記４）検索文字列を検索する場合に、ノードに登録された文字列と、該検索文字列とを比較して、各文字列が一致しない場合に、登録された文字列と該検索文字列で一致する文字数を判定する検索判定機能と、前記ノードの親ノードに遷移し、前記検索判定機能で判定した一致する文字数に応じて、該検索文字列と前記親ノードの文字列の一部を除いた後に、各文字列が一致するか否かを判定する一致判定機能を更に実現させるためのプログラムを格納した記憶媒体。
【０３８１】
（付記５）検索装置が、
所定の文字に対応するノードが木構造にて接続されるトライ木を記憶装置に記憶するステップと、
前記記憶装置に記憶されたトライ木に新規の文字列を登録する場合に、当該新規の文字列の文字を先頭から順に読み出して前記トライ木に含まれるノードを当該ノードに対応する文字に応じて辿り、単一のノードに対して単一の文字列が登録されるように、辿ったノードの何れかに新規の文字列を登録する場合に、登録対象のノードの子ノードに登録された文字列と新規の文字列とを比較して一致する文字を判定し、新規の文字列から一致する文字を除いた残りの文字列と一致文字数を、登録対象のノードに登録するステップと
を含んだことを特徴とするトライ木生成方法。
【０３８２】
（付記６）所定の文字に対応するノードが木構造にて接続されるトライ木を記憶装置に記憶し、当該トライ木に新規の文字列を登録する場合に、当該新規の文字列の文字を先頭から順に読み出して前記トライ木に含まれるノードを当該ノードに対応する文字に応じて辿り、単一のノードに対して単一の文字列が登録されるように、辿ったノードの何れかに新規の文字列を登録する場合に、登録対象のノードの子ノードに登録された文字列と新規の文字列とを比較して一致する文字を判定し、新規の文字列から一致する文字を除いた残りの文字列と一致文字数を、登録対象のノードに登録する文字列登録手段
を有することを特徴とするトライ木生成装置。
【符号の説明】
【０３８３】
１０    コンピュータ
１１    入力装置
１２    モニタ
１３    ＲＡＭ
１３ａ，１８ａ  各種データ
１４    ＲＯＭ
１５    通信制御装置
１６    媒体読取装置
１７    ＣＰＵ
１７ａ  トライ木生成プロセス
１７ｂ  トライ木探索プロセス
１８ｂ  トライ木生成プログラム
１８ｃ  トライ木探索プログラム
１９    バス
１００，２００    検索装置
１１０，２１０    入力部
１２０，２２０    出力部
１３０，２３０    入出力制御部
１４０，２４０    記憶部
１４０ａ，２４０ａ  登録データ管理テーブル
１４０ｂ，２４０ｂ  トライ木
１５０，２５０    制御部
１５０ａ，２５０ａ  トライ木生成部
１５０ｂ，２５０ｂ  トライ木探索部
【図１】
2010231643.tif 000003
【図２】
2010231643.tif 000004
【図３】
2010231643.tif 000005
【図４】
2010231643.tif 000006
【図５】
2010231643.tif 000007
【図６】
2010231643.tif 000008
【図７】
2010231643.tif 000009
【図８】
2010231643.tif 000010
【図９】
2010231643.tif 000011
【図１０】
2010231643.tif 000012
【図１１】
2010231643.tif 000013
【図１２】
2010231643.tif 000014
【図１３−１】
2010231643.tif 000015
【図１３−２】
2010231643.tif 000016
【図１４】
2010231643.tif 000017
【図１５】
2010231643.tif 000018
【図１６】
2010231643.tif 000019
【図１７】
2010231643.tif 000020
【図１８】
2010231643.tif 000021
【図１９】
2010231643.tif 000022
【図２０】
2010231643.tif 000023
【図２１】
2010231643.tif 000024
【図２２】
2010231643.tif 000025
【図２３】
2010231643.tif 000026
【図２４】
2010231643.tif 000027
【図２５】
2010231643.tif 000028
【図２６】
2010231643.tif 000029
【図２７】
2010231643.tif 000030
【図２８】
2010231643.tif 000031
【図２９】
2010231643.tif 000032
【図３０】
2010231643.tif 000033
【図３１】
2010231643.tif 000034
【図３２】
2010231643.tif 000035
【図３３】
2010231643.tif 000036
【図３４】
2010231643.tif 000037
【図３５】
2010231643.tif 000038
【図３６】
2010231643.tif 000039
【図３７】
2010231643.tif 000040
【図３８】
2010231643.tif 000041
【図３９】
2010231643.tif 000042
【図４０】
2010231643.tif 000043
【図４１】
2010231643.tif 000044
【図４２】
2010231643.tif 000045
【図４３】
2010231643.tif 000046
【図４４】
2010231643.tif 000047
【図４５】
2010231643.tif 000048
【図４６】
2010231643.tif 000049
【図４７】
2010231643.tif 000050
【図４８】
2010231643.tif 000051
【図４９】
2010231643.tif 000052
【図５０】
2010231643.tif 000053
【図５１】
2010231643.tif 000054
【図５２】
2010231643.tif 000055
【図５３】
2010231643.tif 000056
【図５４】
2010231643.tif 000057
【図５５】
2010231643.tif 000058
【図５６】
2010231643.tif 000059
【図５７】
2010231643.tif 000060
【図５８】
2010231643.tif 000061
【図５９】
2010231643.tif 000062
【図６０】
2010231643.tif 000063
【図６１】
2010231643.tif 000064
【図６２】
2010231643.tif 000065
【図６３】
2010231643.tif 000066
【図６４】
2010231643.tif 000067
【図６５】
2010231643.tif 000068
【図６６】
2010231643.tif 000069
【図６７】
2010231643.tif 000070
【図６８】
2010231643.tif 000071
【図６９】
2010231643.tif 000072
【図７０】
2010231643.tif 000073
【図７１】
2010231643.tif 000074
【図７２】
2010231643.tif 000075
【図７３】
2010231643.tif 000076
【図７４】
2010231643.tif 000077
【図７５】
2010231643.tif 000078
【図７６】
2010231643.tif 000079
【図７７】
2010231643.tif 000080
【図７８】
2010231643.tif 000081
【図７９】
2010231643.tif 000082
【図８０】
2010231643.tif 000083
【図８１】
2010231643.tif 000084
【図８２】
2010231643.tif 000085
【図８３】
2010231643.tif 000086
【図８４】
2010231643.tif 000087
【図８５】
2010231643.tif 000088
【図８６】
2010231643.tif 000089
【図８７】
2010231643.tif 000090
【図８８】
2010231643.tif 000091
【図８９】
2010231643.tif 000092
【図９０】
2010231643.tif 000093
【図９１】
2010231643.tif 000094