(57)【特許請求の範囲】
【請求項１】
基数検索に用いられるツリー型の検索データ構造の一部に、ツリーの或るノードによって指定されるデータ集合に包含されるような被検索データのすべてを並置したものを並置テーブルとして、前記或るノード以下のすべてのツリー構造の代わりに保持した構造を有する検索用データを構築する検索用データ構造構築方法であって、
コンピュータが備える置換ノード選択部が、任意の並置テーブルに含まれる被検索データに対する検索時間中の最大が、並置テーブルに含まれず、ツリーの最下位に位置する被検索データの検索時間の最大を超えないようなノードを選択するステップと、
コンピュータが備える並置テーブル構成部が、前記選択されたノード以下のツリー構造を、前記並置テーブルで置き換えるステップとを含むことを特徴とする検索用データ構造構築方法。
【請求項２】
コンピュータが備えるツリー構成部が、複数の被検索データに基づいて、基数検索に用いられるツリー型の検索データ構造を構成するツリー構成処理と、
コンピュータが備える置換ノード選択部が、該ツリー構成処理で構成されたツリー型の検索データ構造における最大検索時間を求める最大検索時間算出処理と、
コンピュータが備える置換ノード選択部が、前記ツリー構成処理で構成された前記ツリー型の検索データ構造のノードについて、そのノード以下のツリー構造を並置テーブルで置き換えたときの検索データ構造の最大検索時間が、前記最大検索時間算出処理で算出された最大検索時間を超えないノードを選択する置換ノード選択処理と、
コンピュータが備える並置テーブル構成部が、前記ツリー構成処理によって構成されたツリー型の検索データ構造中の、前記置換ノード選択処理で選択されたノード以下のツリー構造を、前記選択されたノードによって指定されるデータ集合に包含される全ての被検索データを格納した並置テーブルで置き換える並置テーブル構成処理とを含むことを特徴とする検索用データ構造構築方法。
【請求項３】
複数の被検索データに基づいて、基数検索に用いられるツリー型の検索データ構造を構成するツリー構成部と、
該ツリー構成部で構成されたツリー型の検索データ構造における最大検索時間を求めると共に、前記ツリー型の検索データ構造のノードについて、そのノード以下のツリー構造を並置テーブルで置き換えたときの検索データ構造の最大検索時間が、前記求めた最大検索時間を超えないノードを選択する置換ノード選択部と、
前記ツリー構成部によって構成されたツリー型の検索データ構造中の、前記置換ノード選択部で選択されたノード以下のツリー構造を、前記選択されたノードによって指定されるデータ集合に包含される全ての被検索データを格納した並置テーブルで置き換える並置テーブル構成部とを備えたことを特徴とする検索用データ構造構築装置。
【請求項４】
コンピュータを、
複数の被検索データに基づいて、基数検索に用いられるツリー型の検索データ構造を構成するツリー構成部、
該ツリー構成部で構成されたツリー型の検索データ構造における最大検索時間を求めると共に、前記ツリー型の検索データ構造のノードについて、そのノード以下のツリー構造を並置テーブルに置き換えたときの検索データ構造の最大検索時間が、前記求めた最大検索時間を超えないノードを選択する置換ノード選択部、
前記ツリー構成部によって構成されたツリー型の検索データ構造中の、前記置換ノード選択部で選択されたノード以下のツリー構造を、前記選択されたノードによって指定されるデータ集合に包含される全ての被検索データを格納した並置テーブルで置き換える並置テーブル構成部、
として機能させるためのプログラムを記録した機械可読プログラム記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、検索用データ構造構築技術に関し、特に、最大検索時間を基数検索法と同等以上のものにすることができ、且つ被検索データを格納するためのメモリ使用量を少なくすることができる検索用データ構造構築技術に関する。
【０００２】
【従来の技術】
データ検索を行う従来の方法としては、テーブルを利用した検索法や、ツリー型の検索データ構造を利用した基数検索法がある。
【０００３】
テーブルを利用した検索法としては、テーブルに被検索データを並べておき、テーブルの先頭エントリから順に検索データと比較していく順次検索法や、テーブルに被検索データをソートして配置しておき、バイナリサーチするバイナリサーチ法がある。しかし、これらのテーブルを利用した検索法は、被検索データの数が多くなると、多大な検索時間を要するという問題がある。
【０００４】
ツリー型の検索データ構造を利用した基数検索法では、検索データを有限個の種類の記号からなる記号列とみなし、被検索データの集まりを記号列の先頭の記号から順に記号毎に分類し、分類が進む毎に枝分かれして行くようなツリー状のデータ構造に格納しておく。ツリーのノードには、記号列の種類数に応じた子ノードへのポインタが格納されており、検索データが与えられると、検索データの先頭の記号から順にツリーのノードを辿って探索範囲を狭めて検索を行う。
【０００５】
基数検索法を、最長プレフィクス検索法と呼ばれる検索法を例にとって説明する。最長プレフィクス検索法では、被検索データは、或る固定長（Ｌビット）以下の任意の長さのビット列で表され、各被検索データは、それぞれ関連情報を持っている。検索データが与えられると、検索データと一致するすべての被検索データの中で最も長いもの求める。今、例えば、図９ような、６つの被検索データ（それぞれはビット列）と関連情報との組がある場合を考える。
【０００６】
従来の基数検索法で、検索データを表す記号の集合を（０，１）にした場合、図９の被検索データは、図１０のような２分木で格納される。図の黒丸が、被検索データが格納されているノードを示し、白丸は、分岐を示すノードである。各ノードには、ツリーの子ノードへの２個のポインタと、被検索データを格納しているか否かを示すノード情報フラグが含まれる（格納していればフラグが立つ）。例えば、検索データ“０００１１１１  ”が与えられると、ノードＮ１，Ｎ２，Ｎ３，Ｎ４，Ｎ６，Ｎ７  を辿る事になる。途中で、ノード情報フラグが立っているノードを経由すれば、そのノードに格納されている関連情報は記憶しておく。この場合、ノードＮ３，Ｎ６，Ｎ７でノード情報フラグが立っていることを検出する（即ち，被検索データと検索データが一致する）が、最も長い（最もツリーの下位にある）ノードＮ７の関連情報「Ｄ」を得る。
【０００７】
検索時間は、ノードを一つ辿る時間をＴとすると、レベルＮのノードまで検索した場合は、ＴのＮ倍である。従って、図１０に示すツリー型の検索データ構造における最大検索時間は、ツリーの最も深いノードがレベル６であるので、６Ｔとなる。
【０００８】
検索において、最大検索時間が重要な性能指標である場合には、レベル数を減らし最大検索時間を減らすために、検索データを一度に１ｂｉｔ  より多く調べて行く、Ｎ分木（Ｎ＞２）が用いられる。
【０００９】
例えば、同じ図９の例を、検索データを表す記号を（００，０１，１０，１１）  にし、４分木で構成する場合を考える。４分木では、検索データを２ｂｉｔ  ずつ見てゆくので、奇数ビット長の被検索データは、一度に調べるビット数２の倍数になる長さまで展開されており、展開されたものは、展開前と同じ関連情報をもつ。例えば、図９の被検索データの中の、“０００１１  ”はビット長が５であるので、４分木に合うようにビット長６まで展開され、“０００１１０”，  “０００１１１”の２つになる。これらは、共に、“０００１１  ”の関連情報「Ｄ」を持つ。図１１は、図９に示した被検索データを４分木で格納するために展開した例を示す。
【００１０】
図１１に示す被検索データ（展開被検索データ）を４分木で構成した場合の検索データ構造が、図１２である。図１２における黒丸，白丸の意味は２分木の場合と同様で、各ノードは、そのノードの種類を示すノード情報フラグＦＧと、４個の子ノードへのポインタと、関連情報とを含んでいる。ノード情報フラグＦＧは、“１”，“０”の何れかの値をとり、それぞれ、被検索データ格納しているノード、被検索データを格納していないノードを示す。
【００１１】
例えば，ノードＮ２は、値が“１”のノード情報フラグＦＧと、ノードＮ３，Ｎ４，Ｎ５へのポインタ及びヌルポインタ（”１１”側への分岐が無いことを示す）からなる４つの子ノードへのポインタと、関連情報Ａを持つ。
【００１２】
検索においては、たとえば、検索データ“０００１１１１  ”が与えられると、ノードＮ１，Ｎ２，Ｎ４，Ｎ７  と辿ることにより、ノード情報フラグＦＧの立っているノードＮ２，Ｎ４，Ｎ７を発見するが、より長い被検索データを示すノードＮ７の関連情報Ｄを得る。
【００１３】
４分木にした場合には、最大検索時間は、ノードを１つ辿る時間を２分木と同じＴとすると、ツリーの最も深いノードがレベル４であるので、４Ｔとなり、最大検索時間が６Ｔであった２分木に比較して最大検索時間を２／３に短縮することができる。
【００１４】
しかしながら、一般的に、被検索データのツリーが粗な場合、最大検索時間を短くするために、Ｎ分木のＮを大きく取ると、被検索データをＮ分木構造に合わせるための展開によって、同じ関連情報をもつノードが増加し、また、１つのノードの大きさも、ポインタ数がＮに比例して増大することから、メモリ使用量が増大してしまう。
【００１５】
例えば、ノード情報フラグＦＧが１ｂｉｔ  、ポインタが１つ６ｂｉｔ  、関連情報が８ｂｉｔ  とすると、２分木，４分木の１ノード当たりのビット数は、それぞれ１＋６×２＋８＝２１ｂｉｔ  ，１＋６×４＋８＝３３ｂｉｔ  となり、また、図１０，図１２に示す２分木，４分木の総ビット数は、ノード数が１５ノード，１４ノードであるので、２１×１５＝３１５ｂｉｔ  ，３３×１４＝４６２ｂｉｔ  となる。また、被検索データを格納するメモリの１アドレス当たりのビット数が３２ビットであるとすると、２分木の場合には、１５アドレスで済むが、４分木の場合は、２８アドレスが必要になってしまう。
【００１６】
【発明が解決しようとする課題】
上述したような、従来のＮ分木のツリーデータ構造では、ツリーのノードに、子ノードへのポインタを格納するため、メモリ使用量が大きくなるという問題があった。また、各ノードそれぞれに必要な子ノードへのポインタの数は、Ｎに比例して増加する。このため、検索速度を速める目的でＮを大きくすれば、１ノード内のポインタの数が増加する上、プレフィクス展開により、多くのノードを使用することになる為、この問題がより顕著になっていた。
【００１７】
【発明の目的】
そこで、本発明の目的は、最大検索時間を基数検索法と同等以上にし、且つ、メモリの使用量を基数検索に比較して少なくすることにある。
【００１８】
【課題を解決するための手段】
本発明の検索用データ構造構築方法は、最大検索時間を基数検索法と同等以上にし、且つ、メモリ使用量を削減するため、
基数検索に用いられるツリー型の検索データ構造の一部に、ツリーの或るノードによって指定されるデータ集合に包含されるような被検索データのすべてを並置したものを並置テーブルとして、前記或るノード以下のすべてのツリー構造の代わりに保持した構造を有する検索用データを構築する検索用データ構造構築方法であって、
コンピュータが備える置換ノード選択部が、任意の並置テーブルに含まれる被検索データに対する検索時間中の最大が、並置テーブルに含まれず、ツリーの最下位に位置する被検索データの検索時間の最大を超えないようなノードを選択するステップと、
コンピュータが備える並置テーブル構成部が、前記選択されたノード以下のツリー構造を、前記並置テーブルで置き換えるステップとを含むことを特徴とする。
【００１９】
被検索データが、検索データの取りうるすべての値の中で、粗に分布している場合、従来の基数検索法のための、ノード間をポインタで接続するような複雑なツリー型の検索データ構造よりも、データを並置する、並置テーブルの方が、ツリー構造のような子へのポインタが不要であるため、データ構造の大きさを小さくすることができる。
【００２１】
並置テーブルは、検索データの数が十分小さいと、従来のツリー型の検索データ構造を用いる基数検索法より検索時間が短く、大きくなると急激に検索時間が増大する傾向がある。このため、従来のツリー型の検索データ構造で、或るノードより先に存在する被検索データの数が十分小さい時（或るノードより先に存在する被検索データの数が、上記或るノードが位置するレベル以下に存在するレベルの数に、１ノード当たりの検索時間と並置テーブルの１エントリ当たりの検索時間との比を乗じた値以下の時）には、並置テーブルに置き換えることで、最大検索時間を増大させることなく、データ構造を小さくすることができる。
【００２２】
【発明の実施の形態】
次に本発明の実施の形態について図面を参照して詳細に説明する。
【００２３】
図１は本発明の第１の実施の形態のブロック図であり、コンピュータ１１と、キーボード等の入力装置２１と、ディスプレイ装置等の出力装置３１とを備えている。コンピュータ１１は、検索部１２と、主記憶装置等の記録媒体１３とを備えている。
【００２４】
図２は記録媒体１３に記録された被検データ構造の一例を示す図であり、被検索データの一部は、基数検索に用いられる４分木のツリー型の検索データ構造で記録され、残りは、並置テーブルＮ２’に記録されている。尚、本実施の形態では、検索データの最大ビット長Ｌ＝８ｂｉｔ  とする。
【００２５】
図２の各ノードＮ１，Ｎ８，Ｎ９，Ｎ１０，Ｎ１１，Ｎ１２，Ｎ１３，Ｎ１４は、ノードの種類を示すノード情報フラグＦＧと、“００”方向，“０１”方向，“１０”方向，“１１”方向の４個のポインタと、関連情報とを含んでいる。ノード内のノード情報フラグＦＧは、“０”，“１”の何れかの値をとり、それぞれ、被検索データを格納していないノード、被検索データを格納しているノードを示す。尚、本実施の形態においては、ノードの格納されている情報の先頭２ｂｉｔ  がノード情報フラグＦＧに割り当てられているとする。
【００２６】
例えば、ノードＮ１は、被検索データに対応する関連情報を格納していないノードであるので、値“０”のノード情報フラグＦＧを持ち、“００”方向，“０１”方向，“１０”方向，“１１”方向のポインタとしてそれぞれ並置テーブルＮ２’へのポインタ，ＮＵＬＬ（無効ポインタ），ＮＵＬＬ，ノードＮ８へのポインタを持つ。更に、被検索データを格納していないため、関連情報には無効値が入っている。
【００２７】
また、例えば、ノードＮ８は、被検索データを格納していないノードであるので、値“０”のノード情報フラグＦＧを持ち、“００”方向，“０１”方向，“１０”方向，“１１”方向へのポインタとしてそれぞれＮＵＬＬ，ノードＮ９へのポインタ，ＮＵＬＬ，ノードＮ１０  へのポインタを持つ。更に、被検索データを格納していないため、関連情報には無効値が入っている。
【００２８】
また、ノードＮ１１  は、被検索データを格納しているノードであるので、値“１”のノード情報フラグＦＧを持ち、“００”方向，“０１”方向，“１０”方向，“１１”方向へのポインタとしてＮＵＬＬを持つ。更に、被検索データ１１０１００を格納しているので、関連情報にはＥが入っている。
【００２９】
並置テーブルＮ２’  は、被検索データを並置したものである。被検索データの並置方法はさまざま考えられるが、本実施の形態では、連続したアドレスに並置するものとする。並置テーブルＮ２’の各エントリは、ノード情報フラグＦＧ，最終エントリフラグ，データビット列，検索ビット長，関連情報の５つのフィールドを持つ。尚、本実施の形態においては、エントリの先頭２ｂｉｔ  がノード情報フラグＦＧに割り当てられているとする。
【００３０】
並置テーブルＮ２’内のノード情報フラグＦＧは、常に値“２”を持つ。最終エントリフラグは、並置テーブルＮ２’の最終エントリのみ“１”で、それ以外のエントリは“０”の値をとる。データビット列は、被検索データのビット列に、検索データの最大ビット長Ｌ（この例では、Ｌ＝８）までビット“０”を付加したビット列である。検索ビット長は、データビット列中の最上位ビットから何ビットが被検索データであるかを示している。関連情報フィールドは、被検索データに対応する関連情報を格納するフィールドである。
【００３１】
図２に示した検索データ構造は、図１２に示したノードＮ２以下のツリー構造を並置テーブルＮ２’  で置き換えた点以外は、図１２と同じ構造を持っている。並置テーブルＮ２’  には、図１２のノードＮ２が表すデータの集合、即ち、“００”で始まるビット列という集合に包含される被検索データが全て格納されている。
【００３２】
次に、検索時の動作を説明する。本実施の形態では、ツリー型の検索データ構造を辿って行く場合（分岐先のノード情報フラグＦＧの値が“０”或いは“１”の場合）は、従来と同じく、検索データのビットを２ｂｉｔ  ずつ調べながらツリー構造を辿って行く。しかし、分岐先のノード情報フラグＦＧの値が“２”である場合には、分岐先が並置テーブルＮ２’であるので、並置テーブルＮ２’の各エントリを検索データを使用して単純検索して行く。
【００３３】
図３は検索部１２の処理例を示す流れ図であり、以下各図を参照して検索時の動作を説明する。
【００３４】
入力装置２１から検索データが入力されると、検索部１２は、図３の流れ図に示すように、記録媒体１３に格納されている検索データ構造のルートノードの内容を入力し、ノード情報フラグＦＧの値が“０”であるか、“１”であるかを調べる（Ａ１，Ａ２）。そして、ノード情報フラグＦＧの値が“０”であった場合は、直ちにＡ４の処理を行い、“１”であった場合は、ルートノード中の関連情報と一致ビット長との組を、図示を省略した記憶領域に保存した後（Ａ３）、Ａ４の処理を行う。尚、一致ビット長は、ノードのレベルに応じた値をとるものであり、レベルＮＬのノードの一致ビット長は、２×（ＮＬ−１）となる。
【００３５】
Ａ４では、４つのポインタの内の、検索データの先頭２ｂｉｔ  のビットパターンと対応するポインタを取得し、次のＡ５ではポインタの値がＮＵＬＬであるか否かを調べる。
【００３６】
そして、ポインタの値がＮＵＬＬの場合（Ａ５がＹＥＳ）は、保存している関連情報の内の、それと組になって保存されている一致ビット長が最も長いものを検索結果として出力装置３１等に出力した後（Ａ１２）、処理を終了する。これに対して、ポインタの値がＮＵＬＬでない場合（Ａ５がＮＯ）は、Ａ４で取得したポインタが指し示すノード或いは並置テーブルＮ２’の先頭エントリの内容を入力し（Ａ６）、ノード情報フラグＦＧの値が“２”であるか否かを調べる（Ａ７）。尚、Ａ６の実行時点では、Ａ４で取得したポインタのポイント先が、ノードであるのか、並置テーブル２Ｎ’の先頭エントリであるのかが不明であるため、ポインタが指し示すアドレスから、１ノード分のデータを格納するのに必要なアドレス数と１エントリ分のデータを格納するのに必要なアドレス数との内の、大きな方のアドレス数分のアドレスをアクセスし、データを入力する。例えば、１ノード分のデータを格納するのに必要なアドレス数が「２」で、１エントリ分のデータを格納するのに必要なアドレス数が「１」である場合は、ポインタが指し示すアドレスＸと次のアドレス（Ｘ＋１）とをアクセスすることになる。
【００３７】
そして、ノード情報フラグＦＧが“２”でなかった場合（Ａ７がＮＯ）は、再びＡ２の処理を行い、ツリー構造を辿る。これに対してノード情報フラグＦＧが“２”であった場合（Ａ７がＹＥＳ）は、検索データと並置テーブルＮ２’の先頭エントリに格納されているデータビット列との、検索ビット長によって示される部分が一致するか否かを判断する（Ａ８）。
【００３８】
Ａ８で不一致と判断した場合は、現在処理対象にしているエントリが最終エントリであるか否かを最終エントリフラグに基づいて判断する（Ａ１０）。これに対して、Ａ８で一致と判断した場合は、現在処理対象にしているエントリ中の関連情報と一致ビット長（エントリ中の検索ビット長と同じ値を有する）との組を記憶領域に保存した後（Ａ９）、Ａ１０の処理を行う。
【００３９】
Ａ１０で最終エントリであると判断した場合は、保存している関連情報の内の、それと組になって登録されている一致ビット長が最も長いものを検索結果として出力装置３１等へ出力した後（Ａ１２）、処理を終了する。これに対して、Ａ１０で最終エントリでないと判断した場合は、次のエントリを処理対象にした後（Ａ１１）、再びＡ８の処理を行う。
【００４０】
次に、具体例を挙げて検索時の動作を説明する。
【００４１】
今、例えば、本発明の記録媒体１３に図２に示す検索データ構造が記録されている状態において、検索データとして“０００１１１１１”が入力されたとする。
【００４２】
検索部１２は、検索データ“０００１１１１１”が入力されると、ルートノードＮ１の内容を入力し、ノード状態フラグＦＧの値を調べる（Ａ１，Ａ２）。この例の場合、ノード状態フラグＦＧの値が“０”であるので、検索部１２は、Ａ４の処理を行う。Ａ４では、検索データの先頭２ビットが“００”であるので、ノードＮ１に設定されている４個のポインタの内の、“００”方向のポインタを取得する。ノードＮ１の“００”方向のポインタは、「Ｎ２」であるので、検索部１２は、並置テーブルＮ２’  の先頭エントリの内容を入力する（Ａ６）。
【００４３】
Ａ６で入力した並置テーブルＮ２’の先頭エントリのノード情報フラグＦＧの値は“２”であるので（Ａ７がＹＥＳ）、検索部１２は、検索データと先頭エントリ中のデータビット列との、検索ビット長によって示される部分が一致するか否かを調べる（Ａ８）。この例の場合、先頭エントリに格納されているデータビット列，検索ビット長はそれぞれ“００００００００”，「２」であり、検索データ“０００１１１１１”の上位２ｂｉｔ  “００”と、データビット列“００００００００”の上位２ｂｉｔ  “００”とは一致するので、Ａ８の判断結果はＹＥＳとなる。
【００４４】
Ａ８の判断結果がＹＥＳとなると、検索部１２は、先頭エントリ中の関連情報Ａと一致ビット長「２」との組を記憶領域に保存した後（Ａ９）、第２番目のエントリを処理対象にする（Ａ１１）。以下、最終エントリとなるまで（Ａ１０がＹＥＳとなるまで）、並置テーブルＮ２’の各エントリを対象にして前述した処理と同様の処理を繰り返し行う。この例の場合、第３番目，第４番目のエントリを処理対象にした時、Ａ８の判断結果がＹＥＳとなり、関連情報「Ｃ」と一致ビット長「４」との組、関連情報「Ｄ」と一致ビット長「５」との組が記憶領域に保存される。
【００４５】
そして、最終エントリまで処理を行うと（Ａ１０がＹＥＳ）、検索部１２は、一致ビット長が最も長い関連情報「Ｄ」を検索結果として出力装置３１等に出力する（Ａ１２）。
【００４６】
尚、上述した説明では、Ａ３，Ａ９において、関連情報と検索ビット長との組を記憶領域に保存するようにしたが、並置テーブルＮ２’の各エントリが検索ビット長が短い順にソートされている場合には、関連情報のみを記憶領域に保存し、最も後に保存した関連情報を検索結果として出力するようにしても良い。
【００４７】
ところで、検索時間は、メモリアクセス時間が大部分を占めるため、並置テーブルＮ２’の１エントリを調べる時間は、ツリーのノードを１つ辿る時間Ｔと同じと考えられる。並置テーブルＮ２’を調べる場合の最大検索時間は、ノードＮ１を調べるのにＴ、並置テーブルＮ２’を調べるのに４Ｔかかるため、５Ｔとなる。並置テーブルＮ２’を調べない場合は、ノードＮ１１，Ｎ１２，Ｎ１３，Ｎ１４  のいずれかに到達するような検索の場合が最大の検索時間となり、その時間は、４Ｔである。このため、全体の最大検索時間は、５Ｔとなる。
【００４８】
【第１の実施の形態の効果】
本実施の形態の検索データ構造における並置テーブルＮ２’は、被検索データを並べているだけであり、従来のツリー構造のように、子ノードへのポインタが不要であるため、データ構造の大きさを小さくすることが可能である。
【００４９】
例えば、図２に示す本実施の形態の検索データ構造と、図２と同じ被検索データを対象にしている図１２に示す従来の検索データ構造とを、データ構造の大きさで比較する。本実施の形態における各ノードは、ノード情報フラグＦＧが並置テーブルＮ２’の識別の為に１ｂｉｔ  増加して２ｂｉｔ  になる以外は、図１２に示した従来のノードと同じ構成を有する。従って、本実施の形態におけるノードのビット数は、従来のノードのビット数が３３ビットであるので、３４ビットとなる。また、並置テーブルＮ２’の１エントリ当たりのビット数は、ノード情報フラグＦＧを２ｂｉｔ  、最終エントリフラグを１ｂｉｔ  、データビット列を８ｂｉｔ  （検索データの最大ビット長Ｌ＝８としたので）、検索データ長を４ｂｉｔ  （０から８を示すため）、関連情報を８ｂｉｔ  とすると、２３ｂｉｔ  となる。従って、ノード数が８個，エントリ数が４個である、図２に示す本実施の形態の検索データ構造において必要になるビット数は、３４×８＋２３×４＝３６４ｂｉｔ  となる。これに対して、図１２に示した従来例において必要になるビット数は、１ノード当たりのビット数が３３ｂｉｔ  で、ノード数が１４個であるので、３３×１４＝４６２ｂｉｔ  となる。以上の事から、本実施の形態によれば、検索データ構造の大きさを、約２２％削減することができる。
【００５０】
また、本実施の形態によれば、検索データ構造を格納する際に使用するメモリのアドレス数を削減することもできる。例えば、メモリの１アドレス当たりのビット数が３２ｂｉｔ  であるとすると、図１２に示す従来の検索データ構造においては、ノード数が１４個で、１ノード分のデータを格納するのに、２アドレスを必要とするので、２×１４＝２８アドレスが必要となる。これに対して、図２に示す本実施の形態の検索データ構造では、ノード数が８個、並置テーブルＮ２’のエントリ数が４個で、１ノード分のデータ，１エントリ分のデータを格納するのに必要なアドレス数はそれぞれ２個，１個であるので、検索データ構造を格納するために必要となるアドレス数は、２×８＋１×４＝２０アドレスとなる。以上の事から、本実施の形態によれば、使用するメモリのアドレス数を約２９％削減することができる。
【００５１】
次に、本発明の第２の実施の形態を説明する。図４は本発明の第２の実施の形態のブロック図であり、コンピュータ４１と、キーボード等の入力装置５１と、ディスプレイ装置等の出力装置６１と、記録媒体７１とから構成されている。
【００５２】
コンピュータ４１は、データ構築部４２と、検索部４３と、主記憶装置等の記録媒体４４とを備えている。
【００５３】
記録媒体４４には、図５に示すような、被検索データと関連情報との組が予め格納されている。
【００５４】
検索部４３は、図１に示した検索部１２と同様の機能を有している。
【００５５】
データ構築部４２は、制御部４２１  と、ルートポインタレジスタ４２３  を有するツリー構成部４２２  と、置換ノード選択部４２４  と、並置テーブル構成部４２５  とを備えている。
【００５６】
制御部４２１  は、データ構築部４２内の各部の動作を制御する機能を有する。
【００５７】
ツリー構成部４２２  は、記録媒体４４に格納されている被検索データと関連情報との組に基づいて、基数検索に用いられる４分木のツリー型の検索データ構造を記憶媒体４４上に構成する機能を有する。
【００５８】
置換ノード選択部４２４  は、ツリー構成部４２２  が構成したツリー型の検索データ構造における最大検索時間を求める機能を有すると共に、上記ツリー型の検索データ構造のノードの中から、それを並置テーブルで置き換えた場合の検索データ構造の最大検索時間が上記求めた最大検索時間を越えず、且つメモリ使用量が低減されるノードを選択する機能を有する。
【００５９】
並置テーブル構成部４２５  は、ツリー構成部４２２  が構成したツリー型の検索データ構造中の、置換ノード選択部４２４  で選択されたノード以下のツリー構造を、上記選択されたノードによって指定されるデータ集合に包含される全ての被検索データを格納した並置テーブルで置き換える機能を有する。
【００６０】
記録媒体７１は、ディスク，半導体メモリ，その他の記録媒体であり、コンピュータ４１を検索用データ構造構築装置として機能させるためのプログラムが記録されている。このプログラムは、コンピュータ４１によって読み取られ、コンピュータ４１の動作を制御することで、コンピュータ４１上に、制御部４２１，ツリー構成部４２２，置換ノード選択部４２４，並置テーブル構成部４２５  ，検索部４３を実現する。
【００６１】
図６はデータ構築部４２の処理例を示す流れ図であり、以下各図を参照して検索データ構造構築時の動作を説明する。
【００６２】
検索データ構造の構築時、データ構築部４２内の制御部４２１  は、ツリー構成部４２２  に対して、ツリー型の基数検索用の検索データ構造を記録媒体４４上に構成するように指示する。これにより、ツリー構成部４２２  は、記録媒体４４に格納されている、図５に示す被検索データと関連情報との組に基づいて、図７に示すようなツリー型の基数検索用の検索データ構造を記録媒体４４上に構成する（図６，Ｂ１）。尚、図７に示す各ノードＮ１〜Ｎ１３  が有している情報は、図２に示した各ノードが有している情報と同様のものである。その後、ツリー構成部４２２  は、図７に示す検索データ構造の最上位のノードであるルートノードＮ１へのポインタを、ルートポインタレジスタ４２３  に格納する（Ｂ２）。ツリー構成部４２２  の処理が終了すると、制御部４２１  は、置換ノード選択部４２４  を起動する。
【００６３】
これにより、置換ノード選択部４２４  は、ルートポインタレジスタ４２３  中のポインタによってルートノードＮ１が指し示されている、図７の検索データ構造の最大検索時間を求める（Ｂ３）。この最大検索時間Ｔｍａｘ  は、ツリーのノードを１つ辿る時間Ｔｎ  に、ツリーの最も深いノードのレベルＮＬｍａｘ  を乗じることにより求めることができ、Ｔｍａｘ  ＝Ｔｎ  ×ＮＬｍａｘ  となる。
【００６４】
次に、置換ノード選択部４２４  は、図７に示す検索データ構造中に存在する各ノードを予め決められている規則（例えば、上位レベルに存在するノードを優先し、同一レベルに存在するノードについては、“００”方向，“０１”方向，“１０”方向，“１１”方向の順にするという規則）に従って順次処理対象にし、下記の条件ａ，ｂを満たすノードを１つ探し出し、探し出したノードへのポインタｒを並置テーブル構成部４２５  へ渡す（Ｂ４）。
【００６５】
ａ．処理対象にしているノードを並置テーブルに置き換えた場合、置き換え後の検索データ構造の最大検索時間がＢ３で求めた最大検索時間Ｔｍａｘ  より長くならない。
ｂ．  処理対処にしているノードを並置テーブルに置き換えた場合、置き換え後のメモリ使用量の方が、置き換え前のメモリ使用量よりも少なくなる。
【００６６】
尚、処理対象にしているノードが、上記条件ａを満たすか否かの判断は、例えば、次のようにして行う。処理対象としたノードによって指定されるデータ集合に包含される被検索データの数（並置テーブルのエントリ数と同数）が、処理対象のノードが位置するレベル以下に存在するレベルの数に、１ノード当たりの検索時間Ｔｎ  と並置テーブルの１エントリ当たりの検索時間Ｔｅ  との比Ｋ＝Ｔｅ  ／Ｔｎ  を乗じた値以下になった場合、条件ａを満たすと判断する。
【００６７】
制御部４２１  は、置換ノード選択部４２４  の処理が終了すると、並置テーブル構成部４２５  を起動する。
【００６８】
これにより、並置テーブル構成部４２５  では、ポインタｒが指し示すノード以下のツリー構造を解放し、上記ノードによって指定されるデータ集合に包含される被検索データと関連情報との組を記録媒体４４上から探し、並置テーブルとして再構成する（Ｂ５）。その後、並置テーブル構成部４２５  は、Ｂ５で構成した並置テーブルを、記録媒体４４上のポインタｒによってポイントされる位置に保存する（Ｂ６）。制御部４２１  は、上で示した、置換ノード選択部４２４  と並置テーブル構成部４２５  の起動を任意回繰り返しても良い。尚、置換ノード選択部４２４  は、制御部４２１  によって複数回起動された場合は、既に選択しているノードは処理対象から除外して、前述した処理を行う。
【００６９】
図８は、ツリー構成部４２２  が構築した図７の検索データ構造に対して、置換ノード選択部４２４  と並置テーブル構成部４２５  とを１度ずつ動作させた時に得られた検索データ構造の例を示した図である。図８に示すように、ノードＮ６以下のツリー構造が並置テーブルＮ６’で置き換えられている。
【００７０】
次に、上述したデータ構築部４２の動作を具体例を挙げて説明する。尚、以下の説明では、ノード当たりの検索時間Ｔｎ，１エントリ当たりの検索時間Ｔｅ  は、共にＴであるとする。
【００７１】
ツリー構成部４２２  が、記録媒体４４上に、図７に示す基数検索用のツリー型の検索データ構造を構築し、ルートポインタレジスタ４２３  にルートノードＮ１へのポインタを格納すると（図６のＢ１，Ｂ２）、置換ノード選択部４２４  は、図７の検索データ構造における最大検索時間Ｔｍａｘ  を求める（Ｂ３）。図７の検索データ構造の最大レベルは「４」であるので、最大検索時間Ｔｍａｘ  ＝４Ｔとなる。
【００７２】
次に、ノードＮ１から幅優先探索でノードを調べて行く。ノードＮ１を並置テーブルに置き換えると、並置テーブルのエントリ数は「８」となり、置き換え後の検索データ構造における最大検索時間は８Ｔとなる。これは、最大検索時間を増加させることになり、条件ａを満たさないので、置換ノード選択部４２４  は、次のノードＮ２を処理対象にする。
【００７３】
ノードＮ２を並置テーブルに置き換えるとすると、並置テーブルのエントリ数は「４」となる。従って、ノードＮ２を並置テーブルに置き換えた時の検索データ構造における最大検索時間は、ノードＮ１の検索時間Ｔと、エントリ数が「４」の並置テーブルの検索時間４Ｔとの和である５Ｔとなり、Ｂ３で求めた最大検索時間Ｔｍａｘ  ＝４Ｔを越えてしまう。このため、このノードＮ２も選択せず、幅優先探索を進め、ノードＮ６を処理対象ノードにする。
【００７４】
ノードＮ６を並置テーブルに置き換えた場合の、並置テーブルのエントリ数は「２」となる。従って、並置テーブルの最終エントリまで検索するのに要する時間は、ノードＮ１の検索時間Ｔと、エントリ数が「２」の並置テーブルの検索時間２Ｔとの和である３Ｔとなる。このことは、ノードＮ６を並置テーブルで置き換えても、置き換え後の検索データ構造における最大検索時間が、Ｂ３で求めた最大検索時間Ｔｍａｘ  を越えないことを示している。従って、ノードＮ６は上記した条件ａを満たすノードとなる。
【００７５】
更に、ノードＮ６，Ｎ７，Ｎ８，Ｎ９  をなくすことによる削減ビット数は、１ノード当たりのビット数を第１の実施の形態と同じ３４ｂｉｔ  とすると、３４×４＝１３６ｂｉｔ  となる。これに対して、並置テーブルＮ６’の為に必要なビット数は、並置テーブルの１エントリ当たりのビット数が第１の実施の形態と同じ２３ｂｉｔ  であるとすると、２３×２＝４６ｂｉｔ  となる。よって、１３６−４６＝９０ｂｉｔ  の削減が達成できる。従って、置換ノード選択部４２４  は、ノードＮ６を選択し、ノードＮ６へのポインタを並置テーブル構成部４２５  へ渡す。
【００７６】
並置ノード構成部４２５  は、ノードＮ６以下のツリー構造を構成するノードＮ６，Ｎ７，Ｎ８，Ｎ９  のメモリ領域を解放する。そして、ノードＮ６が示すデータ集合が、“１０”で始まる全てのビット列であることから、この集合に含まれる被検索データと関連情報との組を、記録媒体４４から探し出す。この例の場合、記録媒体４４には、図５に示す被検索データと関連情報との組が記録されているので、並置テーブル構成部４２５  は、被検索データと関連情報との組として（１０００，Ｅ），  （１００００，Ｆ）  を見つける。その後、見つけ出した被検索データと関連情報の組それぞれ対して、ノード情報フラグＦＧ，  最終エントリフラグ，  データビット列，  検索ビット長，  関連情報からなる並置テーブルＮ６’の１エントリ分のデータを作成する。尚、データビット列は、探し出した被検索データに、“０”を付加してその長さを検索データの最大ビット長と一致させたものである。その後、作成した各データを並置テーブルＮ６’として、記録媒体４４上の、ポインタＮ６によって示される位置に格納する。
【００７７】
【第２の実施の形態の効果】
上に示したとおり、従来の基数検索法を用いたデータ構造の最大検索時間４Ｔを変えずに、メモリ領域を９０ｂｉｔ  節約している。即ち、最大検索時間を増加させる事無く、メモリ使用量を削減することができる。また、本実施の形態によれば、検索データ構造を格納する際に使用するメモリのアドレス数を削減することもできる。例えば、メモリの１アドレス当たりのビット数が３２ｂｉｔ  であるとすると、図１２に示す従来の検索データ構造においては、ノード数が１４個で、１ノード分のデータを格納するのに、２アドレスを必要とするので、２×１４＝２８アドレスが必要となる。これに対して、図８に示す本実施の形態の検索データ構造では、ノード数が９個、並置テーブルＮ６’のエントリ数が２個で、１ノード分のデータ，１エントリ分のデータを格納するのに必要なアドレス数はそれぞれ２個，１個であるので、検索データ構造を格納するために必要となるアドレス数は、２×９＋１×２＝２０アドレスとなる。以上の事から、本実施の形態によれば、使用するメモリのアドレス数を約２９％削減することができる。
【００７８】
【発明の効果】
本発明の第１の効果は、検索データ構造を格納するためのメモリ使用量を削減できるということである。その理由は、基数検索に用いられるツリー型の検索データ構造の一部を、子ノードへのポインタが不要な、データサイズを小さくすることができる並置テーブルで置き換えているからである。
【００７９】
本発明の第２の効果は、最大検索時間を基数検索法と同等以上にし、且つ、メモリの使用量を削減できるということである。その理由は、ツリー型の検索データ構造で、或るノードより先に存在する被検索データの数が十分小さい時（或るノードより先に存在する被検索データの数が、上記或るノードが位置するレベル以下に存在するレベルの数に、１ノード当たりの検索時間と並置テーブルの１エントリ当たりの検索時間との比を乗じた値以下の時）には、並置テーブルに置き換えるようにしているからである。
【図面の簡単な説明】
【図１】本発明の第１の実施の形態のブロック図である。
【図２】記録媒体１３に記録された検索データ構造の一例を示す図である。
【図３】検索部１２の処理例を示す流れ図である。
【図４】本発明の第２の実施の形態のブロック図である。
【図５】被検索データと関連情報との組の一例を示す図である。
【図６】データ構築部４２の処理例を示す流れ図である。
【図７】ツリー構成部４２３  によって構成される検索データ構造の一例を示した図である。
【図８】記録媒体４４に記録された検索データ構造を示す図である。
【図９】被検索データと関連情報との組の一例を示す図である。
【図１０】従来の２分木の検索データ構造の一例を示す図である。
【図１１】図９に示す被検索データと関連情報との組を４分木で格納できるように展開した図である。
【図１２】従来の４分木の検索データ構造の一例を示す図である。
【符号の説明】
１１…コンピュータ
１２…検索部
１３…記録媒体
２１…入力装置
３１…出力装置
４１…コンピュータ
４２…データ構築部
４２１  …制御部
４２２  …ツリー構成部
４２３  …ルートポインタレジスタ
４２４  …置換ノード選択部
４２５  …並置テーブル構成部
４３…検索部
４４…記録媒体
５１…入力装置
６１…出力装置
７１…記録媒体
【図１】
0003630057.tif 000002
【図２】
0003630057.tif 000003
【図３】
0003630057.tif 000004
【図４】
0003630057.tif 000005
【図５】
0003630057.tif 000006
【図６】
0003630057.tif 000007
【図７】
0003630057.tif 000008
【図８】
0003630057.tif 000009
【図９】
0003630057.tif 000010
【図１０】
0003630057.tif 000011
【図１１】
0003630057.tif 000012
【図１２】
0003630057.tif 000013