JP5220057B2 - ビット列検索装置、検索方法及びプログラム - Google Patents

Description

本発明は、ビット列検索の技術に関し、特にカップルドノードツリーを用いたビット列検索に関する。

近年、社会の情報化が進展し、大規模なデータベースが各所で利用されるようになってきている。このような大規模なデータベースからレコードを検索するには、各レコードの記憶されたアドレスと対応づけられたレコード内の項目をインデックスキーとして検索をし、所望のレコードを探し出すことが通例である。また、全文検索における文字列も、文書のインデックスキーと見なすことができる。

そして、それらのインデックスキーはビット列で表現されることから、データベースの検索はビット列データの検索に帰着されるということができる。
ビット列データを検索するビット列検索に関するものとして、下記特許文献１、特許文献２及び特許文献３等に開示されたカップルドノードツリーを用いた検索技術がある。

図１Ａに示すのは、従来の、配列に配置されたカップルドノードツリーの構成例を説明する図である。
図１Ａを参照すると、ノード１０１が配列１００の配列番号１０の配列要素に配置されている。ノード１０１はノード種別１０２、弁別ビット位置１０３及び代表ノード番号１０４で構成されている。ノード種別１０２は０であり、ノード１０１がブランチノードであることを示している。弁別ビット位置１０３には１が格納されている。代表ノード番号１０４にはリンク先のノード対の代表ノードの配列番号２０が格納されている。なお、以下では表記の簡略化のため、代表ノード番号に格納された配列番号を代表ノード番号ということもある。また、代表ノード番号に格納された配列番号をそのノードに付した符号あるいはノード対に付した符号で表すこともある。

配列番号２０の配列要素には、ノード対１１１の代表ノードであるノード［０］１１２が格納されている。そして隣接する次の配列要素（配列番号２０＋１）に代表ノードと対になるノード［１］１１３が格納されている。ノード［０］１１２のノード種別１１４には０が、弁別ビット位置１１５には３が、代表ノード番号１１６には３０が格納されている。またノード［１］１１３のノード種別１１７には１が格納されており、ノード［１］１１３がリーフノードであることを示している。インデックスキー１１８には、“０００１”が格納されている。

なお、代表ノードをノード［０］で表し、それと対になるノードをノード［１］で表すことがある。また、ある配列番号の配列要素に格納されたノードを、その配列番号のノードということがあり、ノードの格納された配列要素の配列番号を、ノードの配列番号ということもある。
配列番号３０及び３１の配列要素に格納されたノード１２２とノード１２３からなるノード対１２１の内容は省略されている。

ノード［０］１１２、ノード［１］１１３、ノード１２２、及びノード１２３の格納された配列要素にそれぞれ付された０あるいは１は、検索キーで検索を行う場合にノード対のどちらのノードにリンクするかを示すものである。前段のブランチノードの弁別ビット位置にある検索キーのビット値である０か１を代表ノード番号に加えた配列番号のノードにリンクする。
したがって、前段のブランチノードの代表ノード番号に、検索キーの弁別ビット位置のビット値を加えることにより、リンク先のノードが格納された配列要素の配列番号を求めることができる。
なお、上記の例では代表ノード番号をノード対の配置された配列番号のうち小さい方を採用しているが、大きいほうを採用することも可能であることは明らかである。

図１Ｂは、従来のカップルドノードツリーのツリー構造を概念的に示す図である。
符号２１０ａで示すのが図１Ｂに例示するカップルドノードツリー２００のルートノードである。図示の例では、ルートノード２１０ａは配列番号２２０に配置されたノード対２０１ａの代表ノードとしている。

ツリー構造としては、ルートノード２１０ａの下にノート対２０１ｂが、その下層にノード対２０１ｃとノード対２０１ｆが配置され、ノード対２０１ｆの下層にはノード対２０１ｈとノード対２０１ｇが配置されている。ノード対２０１ｃの下にはノード対２０１ｄが、さらにその下にはノード対２０１ｅが配置されている。

各ノードの前に付された０あるいは１の符号は、図１において説明した配列要素の前に付された符号と同じである。検索キーの弁別ビット位置のビット値に応じてツリーをたどり、検索対象のリーフノードを見つけることになる。

図示された例では、ルートノード２１０ａのノード種別２６０ａは０でブランチノードであることを示し、弁別ビット位置２３０ａは０を示している。代表ノード番号は２２０ａであり、それはノード対２０１ｂの代表ノード２１０ｂの格納された配列要素の配列番号である。
ノード対２０１ｂはノード２１０ｂと２１１ｂで構成され、それらのノード種別２６０ｂ、２６１ｂはともに０であり、ブランチノードであることを示している。ノード２１０ｂの弁別ビット位置２３０ｂには１が格納され、リンク先の代表ノード番号にはノード対２０１ｃの代表ノード２１０ｃの格納された配列要素の配列番号２２０ｂが格納されている。

ノード２１０ｃのノード種別２６０ｃには１が格納されているので、このノードはリーフノードであり、したがって、インデックスキーを含んでいる。インデックスキー２５０ｃには“０００１１１”が格納されている。一方ノード２１１ｃのノード種別２６１ｃは０、弁別ビット位置２３１ｃは２であり、代表ノード番号にはノード対２０１ｄの代表ノード２１０ｄの格納された配列要素の配列番号２２１ｃが格納されている。
ノード２１０ｄのノード種別２６０ｄは０、弁別ビット位置２３０ｄは５であり、代表ノード番号にはノード対２０１ｅの代表ノード２１０ｅの格納された配列要素の配列番号２２０ｄが格納されている。ノード２１０ｄと対になるノード２１１ｄのノード種別２６１ｄは１であり、インデックスキー２５１ｄには“０１１０１０”が格納されている。
ノード対２０１ｅのノード２１０ｅ、２１１ｅのノード種別２６０ｅ、２６１ｅはともに１であり双方ともリーフノードであることを示し、それぞれのインデックスキー２５０ｅ、２５１ｅにはインデックスキーとして“０１００１０”と“０１００１１”が格納されている。

ノード対２０１ｂのもう一方のノードであるノード２１１ｂの弁別ビット位置２３１ｂには２が格納され、リンク先の代表ノード番号にはノード対２０１ｆの代表ノード２１０ｆの格納された配列要素の配列番号２２１ｂが格納されている。
ノード対２０１ｆのノード２１０ｆ、２１１ｆのノード種別２６０ｆ、２６１ｆはともに０であり双方ともブランチノードである。それぞれの弁別ビット位置２３０ｆ、２３１ｆには５、３が格納されている。ノード２１０ｆの代表ノード番号にはノード対２０１ｇの代表ノード２１０ｇの格納された配列要素の配列番号２２０ｆが格納され、ノード２１１ｆの代表ノード番号にはノード対２０１ｈの代表ノードであるノード［０］２１０ｈの格納された配列要素の配列番号２２１ｆが格納されている。
ノード対２０１ｇのノード２１０ｇ、２１１ｇのノード種別２６０ｇ、２６１ｇはともに１であり双方ともリーフノードであることを示し、それぞれのインデックスキー２５０ｇ、２５１ｇには“１０００１０”と“１０００１１”が格納されている。
また同じくノード対２０１ｈの代表ノードであるノード［０］２１０ｈとそれと対をなすノード［１］２１１ｈのノード種別２６０ｈ、２６１ｈはともに１であり双方ともリーフノードであることを示し、それぞれのインデックスキー２５０ｈ、２５１ｈには“１０１０１１”と“１０１１００“が格納されている。

次に、上述のカップルドノードツリーを用いた基本的な検索処理について説明する。以下の説明においては、特に図示されてはいないが、処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶領域が用いられる。また、あるデータ格納領域に格納されるデータ自体にデータ格納領域の符号を付して説明する場合があるし、データ自体の名前をそのデータを格納する一時記憶領域の名前として用いることもある。

まず、検索開始ノードの配列番号を取得する。取得された配列番号に対応する配列は、カップルドノードツリーを構成する任意のノードを格納したものである。検索開始ノードの指定は、オペレータからの入力によってもよいし、検索処理の結果を利用するアプリケーションプログラムによるものでもよい。
取得された検索開始ノードの配列番号は、図示しない検索開始ノード設定エリアに設定されるが、この検索開始ノード設定エリアは、先に述べた「処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶領域」の一つである。以下の説明では、「図示しない検索開始ノード設定エリアに設定する」のような表現に変えて、「検索開始ノードの配列番号を得る。」、「検索開始ノードとして設定する」あるいは単に「検索開始ノードに設定する」のように記述することもある。

次に、探索経路スタックに取得された配列番号を格納し、その配列番号に対応する配列要素を参照すべきノードとして読み出す。そして、読み出したノードから、ノード種別を取り出し、ノード種別がブランチノードであるか否かを判定する。
この判定において、読み出したノードがブランチノードである場合は、ノードから弁別ビット位置についての情報を取り出し、更に、取り出した弁別ビット位置に対応するビット値を検索キーから取り出す。そして、ノードから代表ノード番号を取り出して、検索キーから取り出したビット値と代表ノード番号とを加算し、新たな配列番号として、上述の探索経路スタックに取得された配列番号を格納する処理に戻るループ処理を実行する。

以降、ノード種別の判定においてリーフノードと判定されるまで、上述のループ処理を繰り返す。ノード種別の判定においてリーフノードと判定されると、リーフノードからインデックスキーを検索結果キーとして取り出して、処理を終了する。

次に、ルートノードを検索開始ノードとして図１Ｂに例示するカップルドノードツリー２００からインデックスキー“１０００１０”を検索する処理を簡単に説明する。弁別ビット位置は、最上位ビットの位置から０、１、２、・・・とする。

検索開始ノードがルートノードであるので、ビット列“１０００１０”を検索キーとしてルートノード２１０ａから処理をスタートする。ルートノード２１０ａの弁別ビット位置２３０ａは０であるので、検索キー“１０００１０”の弁別ビット位置が０のビット値をみると１である。そこで代表ノード番号の格納された配列番号２２０ａに１を加えた配列番号の配列要素に格納されたノード２１１ｂにリンクする。ノード２１１ｂの弁別ビット位置２３１ｂには２が格納されているので、検索キー“１０００１０”の弁別ビット位置が２のビット値をみると０であるから、代表ノード番号の格納された配列番号２２１ｂの配列要素に格納されたノード２１０ｆにリンクする。
ノード２１０ｆの弁別ビット位置２３０ｆには５が格納されているので、検索キー“１０００１０”の弁別ビット位置が５のビット値をみると０であるから、代表ノード番号の格納された配列番号２２０ｆの配列要素に格納されたノード２１０ｇにリンクする。
ノード２１０ｇのノード種別２６０ｇは１でありリーフノードであることを示しているので、インデックスキー２５０ｇを検索結果キーとして読み出す。このようにしてカップルドノードツリーを用いた検索が行われる。なお、検索結果キーを検索キーと比較すると両方とも“１０００１０”であって一致している。

上述の検索処理の説明では、検索処理をノードからインデックスキーを検索結果キーとして取り出すことで終了しているが、さらに検索結果キーと検索キーの一致判定を行い、一致すれば検索成功とし、一致しなければ検索失敗とすることもできる。

図１Ａ及び図１Ｂに示すカップルドノードツリーのリーフノードは、リーフノードインデックスキーを直接含むものであり、上述の検索処理は、リーフノードからインデックスキーを取り出すものである。このリーフノードの構成と検索処理におけるインデックスキーの取り出しは、特許文献１及び特許文献２に開示されたものと同様である。

一方、特許文献３に開示されたカップルドノードツリーのリーフノードには、インデックスキーに替えて、インデックスキーの記憶された記憶領域の位置を示すポインタである参照ポインタが格納されている。そして、検索処理におけるインデックスキーの取り出しは、リーフノードから参照ポインタを取り出し、参照ポインタの指す記憶領域にアクセスすることにより行われる。

特開２００８−０１５８７２号公報 特開２００８−１１２２４０号公報 特開２００８−２６９５０３号公報

カップルドノードツリーは、それ以前に検索処理に用いられていたツリーと比べてツリーを記憶する記憶容量が少ないという特徴を有する。しかしながら、検索対象のデータサイズが非常に大きくなると、より小さい容量の記憶手段に配置可能なツリー構造であることが望ましい。
そこで、本発明が解決しようとする課題は、より小さい容量の記憶手段に配置可能なカップルドノードツリーのツリー構造を提供することである。

本発明によれば、カップルドノードツリーの各ノードは、ツリー上の位置に応じた配列の配列要素に配置される。ルートノードの配置される配列要素の仮想的な配列番号であるノード参照番号は１とされ、ブランチノードのリンク先のノード対の代表ノードの配置された配列要素のノード参照番号は、ブランチノードが配置された配列要素のノード参照番号を２倍することにより求められる。したがって、本発明によるブランチノードは、代表ノード番号を含む必要がない。

また、本発明によれば、検索対象のインデックスキーのある特定のビット位置に特定のビット値“０”あるいは“１”を挿入したものによりカップルドノードツリーを構成し、同様に検索キーの、検索対象のインデックスキーと同一の特定のビット位置に同一の特定のビット値“０”あるいは“１”を挿入したものにより検索を行う。そして、ブランチノードとリーフノードはノード種別を含まず、ブランチノードは弁別ビット位置を含むが代表ノード番号は含まず、リーフノードはインデックスキーあるいはインデックスキーにアクセスするための情報を含む。

リーフノードは、カップルドノードツリーの最大段数をＮとしたとき、Ｎ段目にのみ存在し、かつＮ段目にはリーフノードしか存在しないようにツリーを構成することにより、ノードの種別の判別を可能としている。

さらに、本発明によれば、検索キーによる検索処理の始めに、ブランチノードの弁別ビット位置と検索キーのビット値により、各ブランチノードにおけるリンク先においてノード位置［０］とノード位置［１］のどちらに分岐するかを示す分岐先情報を求める。そして、検索処理は、ルートノードから最終段であるＮ段目のノードまでの各段の分岐先情報をたどるリンク動作を繰り返すことで行われる。

本発明によれば、ブランチノードはリンク先を識別する代表ノード番号を含まないので、ノードのサイズを小さくすることができる。例えばインデックキーの数が１６とすると、リーフノードのサイズを規定するインデックスキーを表現するためのビット数は４である。一方、従来のブランチノードのサイズを規定する弁別ビット位置に必要なビット数は２、代表ノード番号に必要なビット数は、ルートノードを含めたリンク先となるノード対の数が１＋１＋２＋４＋８＝１６であることから４であるので、必要なビット数は合計で６となる。

したがって、従来のブランチノードは、リーフノードと比べて大きな記憶容量を必要としていた。この記憶容量の差は、インデックスキーの数が大きくなるとさらに拡大する。しかし、本発明によれば、代表ノード番号を格納する記憶領域が必要なくなることから、カップルドノードツリーを配置する配列のサイズを小さくすることができる。

さらに、本発明によれば、カップルドノードツリーを配置する配列のサイズを小さくすることに加えて、検索処理におけるノード種別の判定による分岐動作が削除されるので、処理速度を向上させることができる。

従来の、配列に配置されたカップルドノードツリーの構成例を説明する図である。 従来のカップルドノードツリーのツリー構造を概念的に示す図である。 本発明の一実施形態における配列に配置されたカップルドノードツリーの構成例を説明する図である。 本発明の一実施形態におけるカップルドノードツリーのツリー構造を概念的に示す図である。 本発明を実施するためのハードウェア構成例を説明する図である。 本発明の一実施形態における検索処理の概念を説明する図である。 本発明の一実施形態における検索処理の処理フロー例を説明する図である。 検索キーによりブランチノード配列から分岐先配列を求める処理フロー例を説明する図である。 弁別ビット位置と検索キーにより、分岐先配列に分岐先情報を設定する処理フロー例を説明する図である。 分岐先配列をもとにリーフノード配列のノード参照番号を求める処理フロー例を説明する図である。 分岐先情報により次段のノードの配列番号を求める処理フロー例を説明する図である。 分岐先情報によりリーフノード配列のノード参照番号を求める処理フロー例を説明する図である。 本発明の一実施形態におけるビット列検索装置の機能ブロック構成例を説明する図である。 本発明の一実施形態におけるポインタレスツリーを生成する処理の前段の処理フロー例を説明する図である。 本発明の一実施形態におけるポインタレスツリーを生成する処理の後段の処理フロー例を説明する図である。 本発明の一実施形態におけるブランチノードを生成する処理の処理フロー例を説明する図である。 本発明の一実施形態におけるリーフノードを生成する処理の処理フロー例を説明する図である。 変換前のツリーの最大段数を求める処理の前段の処理フロー例を説明する図である。 変換前のツリーの最大段数を求める処理の後段の処理フロー例を説明する図である。

次に図２Ａ〜図４を参照して、本発明の基本的な概念について説明する。
図２Ａは、本発明の一実施形態における配列に配置されたカップルドノードツリーの構成例を説明する図である。図１Ａに示す構成例と比べると、リーフノード、ブランチノードからノード種別を格納する領域を削除し、またブランチノードから代表ノード番号を格納する領域がなくなっている。また、図２Ａに示す構成例では、後に説明する仮想的な配列番号は、配列番号と一致するものとしているので、表示されていない。

本構成例は、リーフノードをツリーの最下段にのみに配置している。また、各ノードが配置される配列要素は、配列番号が、１から１５への連続した番号のものが使用されている。そして、インデックスキー、検索キーは、本来のインデックスキー、検索キーに対して、ある特定のビット位置である最上位ビットに０を挿入したものとしている。なお、最上位ビットとして付加するビット値は、０ではなく１とすることもできる。要するに、同一のビット値を最上位ビットとして付加すればよい。また、特定のビット値を挿入するある特定のビット位置も、最上位のビット位置に限ることなく、任意のビット位置とすることができる。同一のビット値を挿入したビット位置は、カップルドノードツリーの本来のブランチノードの弁別ビット位置に現れることはない。そこで、上記特定のビット位置を、後に説明するダミーのブランチノードの弁別ビット位置として用い、そのダミーのブランチノードをツリーに挿入することにより、リーフノードをツリーの最下段にのみに配置することを可能としている。

図２Ａを参照すると、ルートノード４０１が配列４００の配列番号１の配列要素に配置されている。ルートノード４０１は弁別ビット位置４０３で構成されている。弁別ビット位置４０３には２が格納されている。

配列番号が１であるルートノード４０１からの点線の矢印４１０で示すリンク先ノード対４１１の代表ノードであるノード［０］４１２は、ツリー上で直近上位に位置する親ノードであるルートノード４０１の配列番号１の２倍の値を持つ配列番号２の配列要素に配置されている。そして隣接する次の配列要素（配列番号３）に代表ノードと対になるノード［１］４１３が配置されている。

ノード［０］４１２の弁別ビット位置には０が格納されており、そのリンク先は、点線の矢印４４０で示すように、ノード［０］４１２の配列番号２の２倍の配列番号４の配列要素に格納されたノード４４２である。また、ノード４４２の弁別ビット位置には０が格納されており、そのリンク先は、点線の矢印４５０で示すように、ノード４４２の配列番号４の２倍の配列番号４の配列要素に格納されたノード４５２である。

ノード４５２は、図２Ａに例示するカップルドノードツリーの最下段に位置するので、リーフノードであり、インデックスキー４１８には最上位ビットに０が挿入されたインデックスキー“００００１”が格納されている。
図２Ａに示す例では、インデックスキー“００００１”は、ルートノード４０１の弁別ビット位置４０３のビット位置２におけるビット値０によりすでに他の配列要素に格納されたインデックスキーとは弁別されている。したがって、ルートノードの直近下位の配列番号２の配列要素に格納されたノードが本来のリーフノードの位置であるが、本実施形態においてはリーフノードであることを識別するノード種別を用いないので、弁別ビット位置が最上位ビット位置の０であるダミーのブランチノード４１２、４４２を挿入して最下段に位置するようにしている。なお、図２Ａに示す配列番号５の配列要素が空きとなっているように、２段目のダミーのブランチノード４４２と対をなすノードは実質的に存在しない空きノードとなる。

一方、ノード［１］４１３の弁別ビット位置には４が格納されている。配列番号が３であるブランチノード４１３からの点線の矢印４２０で示すリンク先ノード対４２１の代表ノードであるノード４２２は、親ノードであるノード４１３の配列番号３の２倍の値を持つ配列番号６の配列要素に配置されている。そして隣接する次の配列要素（配列番号７）に代表ノードと対になるノード４２３が配置されている。ノード４２２の弁別ビット位置には５が格納されている。また、ノード４２３の弁別ビット位置には６が格納されている。

配列番号が６であるブランチノード４２２からの点線の矢印４３０で示すリンク先ノード対４３１の代表ノードであるノード４３２は、配列番号１２の配列要素に配置されている。そして隣接する次の配列要素（配列番号１３）に代表ノードと対になるノード４３３が配置されている。ノード４３２及びノード４３３の内容の記載は省略されている。また、ブランチノード４２３のリンク先の記載も省略されている。

図２Ｂは、本発明の一実施形態におけるカップルドノードツリーのツリー構造を概念的に示す図である。図２Ｂに示すツリー構造を、図１Ｂに示すツリー構造と比較すると、先に述べたように、ブランチノードとリーフノードからノード種別がなくなり、ブランチノードからは代表ノード番号もなくなっている。代表ノード番号は、ブランチノードの配列番号を２倍することにより得られるので、代表ノード番号によるリンク先への結合を、代表ノード番号の符号を付した点線の矢印により表している。また、各ノードの近傍に、各ノードが配置される配列要素の配列番号を、ルートノード２１０ａに対して、［１］のように表示している。また、図２Ｂの説明においても、図２Ａの例示と同様に、後に説明する仮想的な配列番号は、配列番号と一致するものとしているので、表示されていない。

さらに、図２Ｂに示すツリー構造を、図１Ｂに示すツリー構造と比較すると、図２Ｂに示すツリー構造では、リーフノードに格納された各インデックスキーの最上位のビット位置に０が追加され、ビット長が６ビットから７ビットになっている。それに伴い、図１Ｂに示すブランチノードと同一の符号を付したブランチノードの弁別ビット位置は１つシフトされ、値が１つ大きくなっている。

また、図１Ｂに示すツリー構造における段数は５段であるので、図２Ｂに示すツリー構造においては、最下段である５段目にのみリーフノードが位置している。そして、図１Ｂに示すツリー構造において５段目より上位の階層に位置するリーフノードは、弁別ビット位置が０のダミーのブランチノードとなっている。そして、ダミーのブランチノードの直近下位のノードが５段目のノードとなるまで、ダミーのブランチノードが挿入されている。

なお、図２Ｂに示す例示では、最上位ビットとして０を付加しているため、例えば本来的なインデックスキー“０００１１１”はリーフノード２１０ｊに格納されているが、最上位ビットとして１を付加した場合はリーフノード２１１ｊに格納することは明らかである。

図３は、本発明を実施するためのハードウェア構成例を説明する図である。本発明の検索装置による検索処理は中央処理装置３０２及びキャッシュメモリ３０３を少なくとも備えたデータ処理装置３０１によりデータ格納装置３０８を用いて実施することができる。カップルドノードツリーが配置される配列３０９と検索中にたどるノードが格納された配列要素の配列番号を記憶する探索経路スタック３１０、及びカップルドノードツリーに格納されたブランチノードの弁別ビット位置と検索キーの該弁別ビット位置のビット値により決定される分岐先を示す分岐先情報を格納する分岐先配列３１１を有するデータ格納装置３０８は、主記憶装置３０５または外部記憶装置３０６で実現することができ、あるいは通信装置３０７を介して接続された遠方に配置された装置を用いることも可能である。
なお、リーフノードにインデックスキーではなくインデックスキーにアクセスするための情報を格納する場合には、データ格納装置には、インデックスキーを記憶する記憶領域が設けられる。

図３の例示では、主記憶装置３０５、外部記憶装置３０６及び通信装置３０７が一本のバス３０４によりデータ処理装置３０１に接続されているが、接続方法はこれに限るものではない。また、主記憶装置３０５をデータ処理装置３０１内のものとすることもできるし、探索経路スタック３１０を中央処理装置３０２内のハードウェアとして実現することも可能である。あるいは、配列３０９は外部記憶装置３０６に、探索経路スタック３１０と分岐先配列３１１を主記憶装置３０５に、持つなど、使用可能なハードウェア環境、インデックスキー集合の大きさ等に応じて適宜ハードウェア構成を選択できることは明らかである。
また、特に図示されてはいないが、処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶装置が用いられることは当然である。

図４は、本発明の一実施形態による検索処理の概念を説明する図である。
図３に示すカップルドノードツリーを格納する配列３０９は、ブランチノードを格納するブランチノード配列３０９ａとリーフノードを格納するリーフノード配列３０９ｂに分離されている。それぞれの配列には、図２Ｂに示すカップルドノードツリー２００ｂのブランチノードとリーフノードが格納されている。

ブランチノード配列３０９ａとリーフノード配列３０９ｂの配列要素には、それぞれの配列番号７３０ａ、７３０ｂに加えて、それぞれノード参照番号７２０ａ、７２０ｂが付されている。そして、ブランチノード配列３０９ａとリーフノード配列３０９ｂには、さらにベース番号７００ａ、７００ｂがそれぞれ付されている。ノード参照番号は、いわば仮想的なあるいは論理的な配列番号であり、１から始まる連続番号である。

ベース番号は配列の配列要素のノード参照番号を１番から開始するためのものである。ベース番号とノード参照番号の和が配列番号となる。図４の例では、ブランチノード配列３０９ａの配列番号７３０ａの先頭の値は１１であるから、ベース番号７００ａの値を１０とすることにより、ノード参照番号７２０ａの値は１から始まるものとなる。リーフノード配列３０９ｂの配列番号７３０ｂの先頭の値は５１であるから、ベース番号７００ｂの値を５０とすることにより、ノード参照番号７２０ｂの値は、ノード参照番号７２０ａと同様に、１から始まるものとなる。
ベース番号とノード参照番号を導入することにより、ブランチノード配列３０９ａとリーフノード配列３０９ｂの配列内での配置の自由度を高めることができる。また、ブランチノード配列３０９ａとリーフノード配列３０９ｂを格納する記憶手段の選択度も高めることができる。
なお、ベース番号を０とするとノード参照番号と配列番号は等しくなる。ブランチノード配列とリーフノード配列を分離せず、ベース番号を０とした配列に格納されたカップルドノードツリーの構成例が、図２Ａに例示するものである。また、ブランチノード配列とリーフノード配列を分離せず、ベース番号を０とした配列に格納されたカップルドノードツリーのツリー構造を概念的に示す図が、図２Ｂである。

図４には、さらに、検索キー２８０と分岐先配列３１１が記載されている。検索キー２８０にはビット列“００１１０１０”が格納されている。
ブランチノード配列３０９ａのノード参照番号７２０ａの値１の配列要素（以下、ノード参照番号１の配列要素のようにいう。）には、ルートノード２２０ａの弁別ビット位置の値１（以下、弁別ビット位置１のようにいう。）が格納され、検索キー２８０に格納されたビット列のビット位置１のビット値が０であるので、分岐先配列の配列番号１の配列要素には０が格納される。
この分岐先配列の配列番号１の配列要素に格納された分岐先情報０は、検索キー２８０で図２Ｂに示すカップルドノードツリーを検索すると、ルートノード２１０ａの直近下位のノード対２１０ｂにおいて、ノード位置が０であるノード２１０ｂにサーチパスが分岐することを示している。

次に、ブランチノード配列３０９ａのノード参照番号２の配列要素には、ノード２１０ｂの弁別ビット位置２が格納され、検索キー２８０に格納されたビット列のビット位置２のビット値が１であるので、分岐先配列の配列番号２の配列要素には１が格納される。
以下同様に、ブランチノード配列３０９ａのノード参照番号３の配列要素には、ノード２１１ｂの弁別ビット位置３が格納され、検索キー２８０に格納されたビット列のビット位置３のビット値が１であるので、分岐先配列の配列番号３の配列要素には１が格納される。

ブランチノード配列３０９ａのノード参照番号５の配列要素には、ノード２１１ｃの弁別ビット位置３が格納され、検索キー２８０に格納されたビット列のビット位置３のビット値が１であるので、分岐先配列の配列番号５の配列要素には１が格納される。
ブランチノード配列３０９ａのノード参照番号６の配列要素には、弁別ビット位置６が格納され、検索キー２８０に格納されたビット列のビット位置６のビット値が０であるので、分岐先配列の配列番号６の配列要素には０が格納される。

ブランチノード配列３０９ａのノード参照番号７の配列要素には、弁別ビット位置４が格納され、検索キー２８０に格納されたビット列のビット位置４のビット値が０であるので、分岐先配列の配列番号４の配列要素には０が格納される。
ブランチノード配列３０９ａのノード参照番号１０の配列要素には、弁別ビット位置６が格納され、検索キー２８０に格納されたビット列のビット位置６のビット値が０であるので、分岐先配列の配列番号１０の配列要素には０が格納される。

ブランチノード配列３０９ａのノード参照番号１１の配列要素には、ノード２１１ｄの弁別ビット位置０が格納され、検索キー２８０に格納されたビット列のビット位置０のビット値が０であるので、分岐先配列の配列番号１１の配列要素には０が格納される。同様に、その他のブランチノード配列３０９ａの、弁別ビット位置０が格納された配列要素のノード参照番号と同一の値の配列番号が指す分岐先配列３１１の配列要素には０が格納される。

本発明の一実施形態においては、ビット列検索の対象となるビット列の集合からブランチノード配列３０９ａとリーフノード配列３０９ｂが生成されており、検索キー２８０が指定されると、検索キー２８０とブランチノード配列により分岐先配列３１１が生成される。
そして、分岐先配列により、検索結果であるインデックスキーが格納されたリーフノード配列の配列番号を求める。

まず、分岐先配列３１１の配列番号１の太枠で示した配列要素に格納された分岐先情報（以下、配列番号１の分岐先情報のようにいう。）を読み出し、配列番号を２倍した値に加えて、次に読み出す分岐先情報が格納されて配列要素の配列番号を求める。図４の例示では、図２Ｂにおける表記と同様に符号を付した点線の矢印２２０ａで示すように、配列番号１を２倍して０を加えて配列番号２を求める。太枠で示した配列要素に格納された分岐先情報の値１を読み出す。

次に、点線の矢印２２０ｂで示すように、配列番号２の太枠で示した配列要素に格納された分岐先情報の値１を読み出し、配列番号２を２倍した値に加えて配列番号５を求める。
さらに、点線の矢印２２１ｃで示すように、配列番号５の太枠で示した配列要素に格納された分岐先情報の値１を読み出し、配列番号５を２倍した値に加えて配列番号１１を求める。

次の分岐先は、カップルドノードツリーの最下段である。点線の矢印２２１ｉで示すように、配列番号１１の太枠で示した配列要素に格納された分岐先情報の値０を読み出し、それを、配列番号１１を２倍した値に加えて求められる値からブランチノード配列３０９ａの最大のノード参照番号である１５を減じてリーフノード配列３０９ｂのノード参照番号７を得る。太枠で示したリーフノード配列３０９ｂのノード参照番号７の配列要素に格納されたリーフノード２１０ｉからインデックスキー“００１１０１０”を取り出して、検索処理を終了する。

なお、上述の図４の例示では、ブランチノード配列３０９ａとリーフノード配列３０９ｂが分離されたものとして説明し、リーフノード配列３０９ｂのノード参照番号７を求めるために、分岐先情報０を分区先配列の配列番号１１を２倍した値に加えて求められる値からブランチノード配列３０９ａの最大のノード参照番号である１５を減じたが、ブランチノードとリーフノードを１つの配列に格納する場合は、ノード参照番号は一連の番号となるので、リーフノードの格納された配列要素のノード参照番号を求めるときに、ブランチノードを格納する最後の配列要素のノード参照番号を減じる必要はない。

次に、図５〜図７を参照して、本発明の一実施形態における検索処理について詳細に説明する。
図５は、本発明の一実施形態における検索処理の処理フロー例を示す図である。

図５に示すように、まずステップＳ５０１において、検索キーを設定する。この検索キーの設定は、図４に示す例では、検索キー２８０にビット列“００１１０１０”を設定することに相当する。
次にステップＳ５０２において、検索キーをもとに、ブランチノード配列から分岐先配列を求める。この処理は、図４に示す例では、先に説明した検索キー２８０とブランチノード配列３０９ａから分岐先配列３１１を生成する処理に相当する。ステップＳ５０２の詳細な処理フローは、後に図６Ａ及び図６Ｂを参照して説明する。

次にステップＳ５０３において、分岐先配列をもとに、リーフノード配列のノード参照番号を求める。この処理は、図４に示す例では、先に説明した分岐先配列の配列番号１の配列要素に格納された分岐先情報から配列番号１１までの配列要素に格納された分岐先情報を順次読み出し、配列番号１１の配列要素に格納された分岐先情報とブランチノード配列のノード参照番号の最大値にもとづいてリーフノード配列のノード参照番号を求める処理に相当する。ステップＳ５０３の詳細な処理フローは、後に図７Ａ及び図７Ｂを参照して説明する。

最後に、ステップＳ５０４において、ステップＳ５０３で求めたノード参照番号の指すリーフノード配列の配列要素の内容をインデックスキーとして取り出し、処理を終了する。ここで、ステップＳ５０４で取り出したインデックスキーを検索結果キーとすることもできるし、該インデックスキーを検索キーと比較し、一致すれば検索成功とし、一致しなければ検索失敗とすることもできる。

図６Ａは、検索キーによりブランチノード配列から分岐先配列を求める処理フロー例を説明する図であり、図５に示すステップＳ５０２の詳細な処理フローを説明する図である。図６Ａに示す例では、ブランチノード配列に配置されたブランチノードの数はｍとする。

まず、ステップＳ６００において、配列番号及びノード参照番号に１を設定する。
次にステップＳ６０１において、ノード参照番号１の指すブランチノード配列の配列要素に格納された弁別ビット位置と検索キーにより、配列番号１の指す分岐先配列の配列要素に分岐先情報を示すビット値を設定する。

続いてステップＳ６０２において、ノード参照番号２の指すブランチノード配列の配列要素に格納された弁別ビット位置と検索キーにより、配列番号２の指す分岐先配列の配列要素に分岐先情報を示すビット値を設定する。

以下同様に、ステップＳ６０３〜ステップＳ６０ｍにおいて、ノード参照番号３〜ｍの指すブランチノード配列の配列要素に格納された弁別ビット位置と検索キーにより、配列番号３〜ｍの指す分岐先配列の配列要素に分岐先情報を示すビット値をそれぞれ設定する。

なお、図６Ａに例示する処理フロー例は、特定の数であるｍ個のブランチノードが配置されたブランチノード配列により分岐先配列を生成するものであるが、個数ｍをパラメータとしたアセンブラマクロにより、任意の個数のブランチノードが配置されたブランチノード配列により分岐先配列を生成する処理を実現するための処理フローを生成することが可能である。

また、図６Ａに例示するように、ブランチノード配列に配置された各弁別ビット位置に対応して、該弁別ビット位置を用いた処理を順次直列的に実行する処理フローに替えて、ブランチノード配列に配置された弁別ビット位置に対応する処理が全て終了したかを判定する判定処理を設け、終了していなければ次の弁別ビット位置を用いた処理を繰り返すループ処理を含む処理フローにより、同一の処理結果が得られることは明らかである。ステップＳ６０１〜ステップＳ６０ｍの処理の詳細は、次に図６Ｂを参照して説明する。

図６Ｂは、ブランチノード配列の配列要素に格納された弁別ビット位置と検索キーにより、分岐先配列の配列要素に分岐先情報を示すビット値を設定する処理フロー例を説明する図である。

まずステップＳ６１０において、ブランチノード配列から、ノード参照番号の指す配列要素の内容を弁別ビット位置として読み出す。ステップＳ６１０の最初の処理では、図６ＡのステップＳ６００における処理で、ノード参照番号に１が設定されている。

次にステップＳ６１１において、検索キーから、ステップＳ６１０で読み出した弁別ビット位置の指すビット値を取り出し、ステップＳ６１２において、該取り出したビット値を、配列番号の指す分岐先配列の配列要素に分岐先情報として設定する。ステップＳ６１２の最初の処理では、図６ＡのステップＳ６００における処理で、配列番号に１が設定されている。

次にステップＳ６１３において、配列番号に１を加え、ステップＳ６１４において、ノード参照番号に１を加えて処理を終了する。以上説明したステップＳ６１０〜ステップＳ６１４の処理がブランチノード配列の配列要素毎に順次実行されることにより、分岐先配列の配列要素に分岐先情報を順次設定することができる。

図７Ａは、分岐先配列をもとにリーフノード配列のノード参照番号を求める処理フロー例を説明する図であり、図５に示すステップＳ５０３の詳細な処理フローを説明する図である。図７Ａに示す例では、カップルドノードツリーの段数はｎとする。

まず、ステップＳ７００で、配列番号に１を設定する。次にステップＳ７０１において、１段目のノード（ルートノード）に対応する配列番号（以下、１段目のノードの配列番号のようにいう。）、すなわち配列番号１の指す分岐先配列に格納された分岐先情報により、２段目のノードの配列番号を求める。

続いてステップＳ７０２において、２段目のノードの配列番号の指す分岐先配列に格納された分岐先情報により、３段目のノードの配列番号を求める。
以下同様に、ステップＳ７０３〜ステップＳ７０ｎ−２において、３段目〜ｎ−２段目のノードの配列番号の指す分岐先配列に格納された分岐先情報により、それぞれ４段目〜ｎ−１段目のノードの配列番号を求める。ステップＳ７０１〜ステップＳ７０ｎ−２の処理の詳細は、後に図７Ｂを参照して説明する。

最後にステップＳ７０ｎ−１において、ｎ−１段目のノードの配列番号の指す分岐先配列に格納された分岐先情報により、リーフノード配列のノード参照番号を求めて処理を終了する。ステップＳ７０ｎ−１の処理の詳細は、後に図７Ｃを参照して説明する。
なお、図７Ａに例示する処理フロー例は、特定の段数ｎを有する本実施形態のカップルドノードツリーを用いたものであるが、段数ｎをパラメータとしたアセンブラマクロにより、本実施形態の任意の段数のカップルドノードツリーを用いた検索処理を実現するための処理フローを生成することが可能である。

また、図７Ａに例示するように、分岐先配列に配置されたカップルドノードツリーの各段のノードの分岐先情報に対応して、該分岐先情報を用いた処理を順次直列的に実行する処理フローに替えて、最下段の１つ上位の段のノードの分岐先情報に対応する処理が終了したかを判定する判定処理を設け、終了していなければ次の段のノードの分岐先情報を用いた処理を繰り返すループ処理を含む処理フローにより、同一の処理結果が得られることは明らかである。

図７Ｂは、分岐先情報により次段のノードの配列号を求める処理フロー例を説明する図であり、図７Ａに示すステップＳ７０２〜ステップＳ７０ｎ−２の処理の詳細な処理フローを説明する図である。

図に示すように、まずステップＳ７１１において、分岐先配列から、配列番号の指す分岐先情報を読み出す。ステップＳ７１１の最初の処理では、図７ＡのステップＳ７００における処理で、配列番号に１が設定されている。

次にステップＳ７１２において、配列番号を２倍し、ステップＳ７１３において、配列番号にステップＳ７１１で得た分岐先情報を加えて処理を終了する。
上述の図７Ｂの処理は、図４に示す例示では、点線の矢印２２０ａ、２２０ｂ、２２１ｃで示す処理である。例えば点線の矢印２２０ｂで示すように、配列番号２の太枠で示した配列要素に格納された分岐先情報の値１を読み出し、配列番号２を２倍した値に加えて配列番号５を求める処理である。

図７Ｃは、分岐先情報によりリーフノード配列のノード参照番号を求める処理フロー例を説明する図であり、図７Ａに示すステップＳ７０ｎ−１の詳細な処理フローを説明する図である。

図に示すように、まずステップＳ７２１において、分岐先配列から、（ｎ−１）段目のノードの配列番号の指す分岐先情報を読み出す。（ｎ−１）段目のノードの配列番号は、図７ＡのステップＳ７０ｎ−２における処理で、設定されている。

次にステップＳ７２２において、配列番号を２倍し、ステップＳ７２３において、配列番号にステップＳ７１１で得た分岐先情報を加えた値をリーフノード配列のノード参照番号に設定する。

そしてさらにステップＳ７２４において、ステップＳ７２３で設定したリーフノード配列のノード参照番号からブランチノード配列のノード参照番号の最大値を減じた値をリーフノード配列のノード参照番号に設定して処理を終了する。

上述の図７Ｃの処理は、図４に示す例示では、点線の矢印２２１ｉで示す処理である。
先に述べたように、ブランチノードとリーフノードを１つの配列に格納する場合は、ノード参照番号は一連の番号となるので、リーフノードの格納された配列要素のノード参照番号を求めるときに、ブランチノードを格納する最後の配列要素のノード参照番号を減じる必要はない。したがって、その場合には、図７Ｃに示すステップＳ７２４の処理は処理フローから削除される。

図８は、本発明の一実施形態におけるビット列検索装置の機能ブロック構成例を説明する図である。
図８に例示する本実施態様に係るビット列検索装置８００は、検索ツリー記憶手段８１０、検索開始位置設定手段８２０、検索キー設定手段８５０、分岐先情報設定実行部８０２、分岐先情報記憶手段８１２、初段ノード分岐先情報格納位置設定手段８８０、次段ノード分岐先情報格納位置計算実行部８０４、及びリーフノード出力実行部８０６を備えている。

検索ツリー記憶手段８１０の記憶領域には配列が確保され、その配列に本発明の一実施形態に係るカップルドノードツリーが配置される。カップルドノードツリーは、図４に例示するように、ブランチノードを格納するブランチノード配列とリーフノードを格納するリーフノード配列に分離して配置することもできる。
検索開始位置設定手段８２０は、検索開始ノードのノード参照番号に、ルートノードのノード参照番号である１を設定するとともに、分岐先情報を格納する分岐先配列の配列番号に１を設定する。検索開始位置設定手段８２０の機能は、図６Ａに示すステップＳ６００の処理に対応する。また、検索キー設定手段８５０には、検索キーが設定される。

分岐先情報設定実行部８０２は、ブランチノード読出手段８３０１〜８３０ｍ及び分岐先情報抽出手段８６０１〜８６０ｍを含む。ｍは検索ツリー記憶手段８１０に格納されたブランチノードの数である。図４に示す例では、ｍ＝１５である。
ブランチノード読出手段８３０１〜８３０ｍは、検索ツリー記憶手段８１０に配置されたブランチノード配列から、ノード参照番号の指す配列要素の内容を弁別ビット位置として読み出し、分岐先配列の配列番号とともに分岐先情報抽出手段に出力する。そして、分岐先配列の配列番号とブランチノード配列のノード参照番号にそれぞれ１を加えて次のブランチノード読出手段に出力する。

分岐先情報抽出手段８６０１〜８６０ｍは、検索キー設定手段８５０に設定された検索キーから、ブランチノード読出手段８３０１〜８３０ｍが出力した弁別ビット位置の指すビット値を取り出し、該ビット値を、ブランチノード読出手段８３０１〜８３０ｍが出力した配列番号が指す分岐先配列の配列要素に、分岐先情報として設定する。ブランチノード読出手段８３０１と分岐先情報抽出手段８６０１の機能は、図６Ａに示すステップＳ６０１の処理に対応する。同様に、ブランチノード読出手段８３０ｍと分岐先情報抽出手段８６０ｍまでの各ブランチノード読出手段と分岐先情報抽出手段の機能は、図６Ａに示すステップＳ６０ｍまでの各処理に対応する。
分岐先配列は、分岐先情報記憶手段８１２の記憶領域に確保される。

初段ノード分岐先情報格納位置設定手段８８０は、分岐先配列の配列番号に１を設定する。初段ノード分岐先情報格納位置設定手段８８０の機能は、図７Ａに示すステップＳ７００の処理に対応する。

次段ノード分岐先情報格納位置計算実行部８０４は、次段ノード分岐先情報格納位置計算算手段８４０１〜８４０ｎ−２を含む。ｎは、カップルドノードツリーの段数である。

次段ノード分岐先情報格納位置計算手段８４０１〜８４０ｎ−２は、分岐先配列から、配列番号の指す分岐先情報を読み出し、配列番号を２倍し、２倍した配列番号に分岐先情報を加えた値を次段のノードに対応する分岐先情報の格納された分岐先配列の配列要素の配列番号として求める。次段ノード分岐先情報格納位置計算手段８４０１〜８４０ｎ−２の機能は、図７Ａに示すステップＳ７０１〜Ｓ７０ｎ−２の処理にそれぞれ対応する。

次段ノード分岐先情報格納位置計算手段８４０１が分岐先情報を読み出すための配列番号は、初段ノード分岐先情報格納位置設定手段８８０が設定したものである。次段ノード分岐先情報格納位置計算手段８４０２〜８４０ｎ−２が分岐先情報を読み出すための配列番号は、それぞれ前の段の次段ノード分岐先情報格納位置計算手段が求めた配列番号である。
次段ノード分岐先情報格納位置計算手段８４０ｎ−２が求めた配列番号は、次に説明するリーフノード出力実行部８０６に入力され、リーフノードの読み出しに用いられる。

リーフノード出力実行部８０６は、リーフノード格納位置計算手段８０６１及び検索結果出力手段８０６２を含む。
リーフノード格納位置計算手段８０６１は、次段ノード分岐先情報格納位置計算手段８４０ｎ−２が求めた配列番号の指す分岐先情報を読み出し、配列番号を２倍し、２倍した配列番号に分岐先情報を加えた値をリーフノード配列の配列要素の仮のノード参照番号として求める。そして、仮のノード参照番号からブランチノード配列のノード参照番号の最大値、すなわち検索ツリー記憶手段８１０に格納されたブランチノードの数ｍを減じた値をリーフノード配列の配列要素のノード参照番号として求める。リーフノード格納位置計算手段８０６１の機能は、図７ＡのステップＳ７０ｎ−１、すなわち図７Ｃに示す処理に対応する。

検索結果出力手段８０６２は、リーフノード格納位置計算手段８０６１が求めたリーフノード配列の配列要素のノード参照番号により、検索ツリー記憶手段８１０からリーフノードを読み出し、インデックスキーあるいはインデックスキーにアクセスするための情報を取り出す。リーフノードから取り出すものがインデックスキーであるときは、そのインデックスキーを検索結果キーとして出力する。リーフノードから取り出すものがインデックスキーにアクセスするための情報であるときは、取り出したインデックスキーにアクセスするための情報に基づき、インデックスキーを読み出して検索結果キーとして出力する。
また、検索結果キーと検索キーを比較し、一致すれば検索成功とし、一致しなければ検索失敗とする検索結果を出力することも可能である。

次に、本発明の一実施形態に係るカップルドノードツリーの生成について説明する。なお、以下の説明において、本発明の一実施形態に係るカップルドノードツリーをポインタレスツリーといい、従来のカップルドノードツリーを単にツリー、あるいは変換前のツリーということがある。
本発明のポインタレスツリーの生成は、例えば次のようにして実現することができる。すなわち、ポインタレスツリーを生成する際には、ポインタレスツリーに格納されるインデックスキーにより、図１Ａ及び図１Ｂに例示する形態のツリーが生成されているものとする。そして、ポインタレスツリーの生成は、ツリーのノードをルートノードから順次巡回し、本発明の一実施形態のノードに変換することにより、実現される。
ツリーの生成は、前記特許文献１として引用した特開２００８−１５８７２号公報の図５〜図８及びそれに関連した明細書の記載に開示され、詳細に説明されているので、ここでの説明は省略する。

図９Ａは、本発明の一実施形態におけるポインタレスツリーを生成する処理の前段の処理フロー例を説明する図である。図９Ａに示すように、まずステップＳ９０１において、ポインタレスツリーを生成するための配列（ブランチノード配列とリーフノード配列）を取得し、ステップＳ９０２おいて、配列要素を初期化する。このステップＳ９０２の処理は、ダミーのブランチノードを用いるために必要となるものである。

次にステップＳ９０２ａにおいて変換前のツリーの最大段数を求め、ステップＳ９０２ｂにおいて該最大段数を段数カウンタの上限値に設定する。
ステップＳ９０２ａの処理の詳細については、後に図１２Ａ及び図１２Ｂを参照して説明する。

次にステップＳ９０３において、ブランチノード配列とリーフノード配列のベース番号を設定し、ステップＳ９０５において、段数カウンタに１を設定する。次にステップＳ９０６において、ノード参照番号に１を設定し、ステップＳ９０７において、配列番号に、ツリーのルートノードの配列番号を設定する。さらにステップＳ９０８において、探索経路スタックに配列番号と段数カウンタのカウント値を格納して図９Ｂに示すステップＳ９１３に進む。

図９Ｂは、本発明の一実施形態におけるポインタレスツリーを生成する処理の後段の処理フロー例を示す図である。図９Ｂに示すように、ステップＳ９１３において、変換前のツリーが格納された配列から、配列番号の指す配列要素をノードとして読み出す。ステップＳ９１３の最初の処理においては、配列番号にはステップＳ９０７でルートノードの配列番号が設定されている。２回目以降の処理においては、後に説明するステップＳ９２０あるいはステップＳ９２８で設定される。以下の説明において、ステップＳ９１３で読み出されたノードを巡回開始ノードということがある。

次にステップＳ９１５において、ステップＳ９１３で読み出したノードからノード種別を取り出し、ステップＳ９１６で、該取り出したノード種別はブランチノードを示すものか判定する。ステップＳ９１６の判定が、ノード種別はブランチノードを示すものではなくリーフノードを示すものであればステップＳ９２２に進み、ブランチノードを示すものであれば、ステップＳ９１６ａに進む。

ステップＳ９１６ａでは、ノード参照番号をもとに、ブランチノード配列の配列要素にノードを書き込む。ステップＳ９１６ａの処理の詳細は、後に図１０を参照して説明する。

次にステップＳ９１７において、段数カウンタに値１を加え、ステップＳ９１８に進み、ノード参照番号を２倍にする。さらにステップＳ９１９において、ステップＳ９１３で読み出したノードから、代表ノード番号を取り出し、ステップＳ９２０で、該取り出した代表ノード番号に値０を加えた値を配列番号に設定する。
そして、ステップＳ９２１において、探索経路スタックに、配列番号と段数カウンタのカウント値を格納してステップＳ９１３に戻る。ここで探索経路スタックに格納される配列番号は、ステップＳ９２０で代表ノード番号に値０を加えた値のものであるから、ノード［０］の配列番号である。

上述のステップＳ９１３〜ステップＳ９２１のループ処理を、ステップＳ９１６においてノード種別がリーフノードを示すまで繰り返す。つまり、ひとまとまりの処理として、巡回開始ノードから最初のリーフノードまでノードを巡回してノードを読み出し、それを変換してポインタレスツリーのノードを書き込む。図９Ｂに示す処理フロー例では、ステップＳ９２０において、代表ノード番号に値０を加えて配列番号に設定していることから、ノード［０］側を優先してノードを巡回しているが、ノード［１］側を優先してノードを巡回することも可能であることは、以上の説明から当業者に明らかである。

一方ステップＳ９１６において、ノード種別はブランチノードを示すものではなくリーフノードを示すものと判定され、ステップＳ９２２に進むと、ノード参照番号をもとに、リーフノード配列の配列要素にノードを書き込む。ステップＳ９２２の処理の詳細は、後に図１１を参照して説明する。

次にステップＳ９２３において、探索経路スタックのスタックポインタはツリーのルートノードの配列番号を指しているか判定する。
探索経路スタックのスタックポインタはツリーのルートノードの配列番号を指していれば、ツリーの全てのノードの処理は完了しているので処理を終了する。そうでなければ、ステップＳ９２４に進む。

ステップＳ９２４では、探索経路スタックから配列番号と段数カウンタのカウント値を取り出し、探索経路スタックのスタックポインタを１つ減らす。次にステップＳ９２８において、ステップＳ９２４で取り出した配列番号に値１を加えて、巡回開始ノードの配列番号としてノード［１］の配列番号を得る。そして、ステップＳ９３０で、ノード参照番号に１を加えてステップＳ９１３に戻る。

上述のステップＳ９１３〜ステップＳ９３０のループ処理を、ステップＳ９２３において探索経路スタックのスタックポインタがツリーのルートノードの配列番号を指していると判定されるまで繰り返すことにより、ツリー上のすべてのノードの巡回が行われ、各ノードがポインタレスツリーのノードに変換されてポインタレスツリーが生成される。

図１０は、本発明の一実施形態におけるブランチノードを生成する処理の処理フロー例を説明する図であり、図９Ｂに示すステップＳ９１６ａの処理の詳細を説明する図である。

図に示すように、まずステップＳ１０２５において、配列番号に、ノード参照番号にブランチノード配列のベース番号を加えた値を設定する。そしてステップＳ１０２６で、ノードから弁別ビット位置を取り出し、ステップＳ１０２７で、該弁別ビット位置に値１を加え、ステップＳ１０２８において、ステップＳ１０２５で設定した配列番号の指すブランチノード配列の配列要素に弁別ビット位置を書き込み、ブランチノードを生成して処理を終了する。

図１１は、本発明の一実施形態におけるリーフノードを生成する処理の処理フロー例を説明する図であり、図９Ｂに示すステップＳ９２２の処理の詳細を説明する図である。

図に示すように、まずステップＳ１１２９において、ノード参照番号と段数カウンタを退避し、ステップＳ１１３０に進む。
ステップＳ１１３０では、段数カウンタは上限値か判定し、上限値でなければ、ステップＳ１１３１でノード参照番号を２倍し、ステップＳ１１３２で段数カウンタに値１を加えてステップＳ１１３０に戻る。

上述のステップＳ１１３０〜Ｓ１１３２のループ処理は、リーフノードをポインタレスツリーの最下段のレベルに配置するためのものである。図１Ｂ、図２Ｂの例示では、例えば図１Ｂの変換前のツリーでは３段目にあるリーフノード２１０ｃは、図２Ｂでは５段目のノード２１０ｊに変換されている。そして、図２Ｂにおけるノード２１０ｃの位置情報は、図１１のステップＳ１１２９の処理により、退避される。

なお、段数カウンタの上限値については、図９Ａに示すステップＳ９０２ｂで設定されているが、それに替えて、変換前のツリーを生成するときに、リーフノードを挿入するごとにそのリーフノードの段数をカウントし、その最大値をツリーの属性として記憶しておき、本発明の一実施形態のポインタレスツリーを生成するときに、その最大値を段数カウンタの上限値とすることができる。

上述のステップＳ１１３０で、段数カウンタは上限値であると判定されると、ステップＳ１１３４に進む。ステップＳ１１３４では、段数カウンタの上限値から１を減じた値による２のべき乗の数値を求め、ノード参照番号から該数値を減じた値とリーフノード配列のベース番号との和を、リーフノード配列の配列番号に設定する。図２Ｂの例示では、段数カウンタの上限値は５であり、該上限値から１を減じた値による２のべき乗数は１６となる。この値から１を減じた値１５は、ブランチノード配列に配置されたブランチノードの数になる。ここでノード参照番号はブランチノード配列のノード参照番号であるから、このノード参照番号から１５を減じた値は図４の例示で説明したように、リーフノード配列のノード参照番号である。そして、ノード参照番号とベース番号の和により、配列番号が求められる。

そしてステップＳ１１３５で、図９Ｂに示すステップＳ９１３で読み出されているノードからインデックスキーを取り出し、ステップＳ１１３６で、該インデックスキーの最上位のビット位置にビット値“０”を挿入し、ステップＳ１１３７において、ステップＳ１１３４で設定した配列番号の指すリーフノード配列の配列要素にインデックスキーを書き込み、リーフノードを生成してステップＳ１１３８に進む。
ステップＳ１１３８では、ノード参照番号と段数カウンタに、ステップＳ１１２９で退避したノード参照番号と段数カウンタをそれぞれ設定して処理を終了する。

次に、変換前のツリーの最大段数を求める処理について図１２Ａ及び図１２Ｂを参照して説明する。図１２Ａ及び図１２Ｂに示す処理フロー例は、図９Ａに示すステップＳ９０２ａの処理の詳細を説明するものである。
図１２Ａは、変換前のツリーの最大段数を求める処理の前段の処理フロー例を説明する図である。

図１２Ａに示すように、まずステップＳ１２０１において、段数カウンタに値１を設定し、ステップＳ１２０２において、最大段数カウンタに、段数カウンタに設定された値を設定する。すなわち、段数カウンタ及び最大段数カウンタには、初期値として値１が設定される。
次にステップＳ１２０７において、配列番号に、ツリーのルートノードの配列番号を設定して図１２Ｂに示すステップＳ１２１３に進む。

図１２Ｂは、変換前のツリーの最大段数を求める処理の後段の処理フロー例を説明する図である。図１２Ｂに示すように、ステップＳ１２１３において、変換前のツリーが格納された配列から、配列番号の指す配列要素をノードとして読み出す。ステップＳ１２１３の最初の処理においては、配列番号にはステップＳ１２０７でルートノードの配列番号が設定されている。２回目以降の処理においては、後に説明するステップＳ１２２０あるいはステップＳ１２２８で設定される。図９Ｂにおける説明と同様に、以下の説明において、ステップＳ１２１３で読み出されたノードを巡回開始ノードということがある。

次にステップＳ１２１５において、ステップＳ１２１３で読み出したノードからノード種別を取り出し、ステップＳ１２１６で、該取り出したノード種別はブランチノードを示すものか判定する。ステップＳ１２１６の判定が、ノード種別はブランチノードを示すものではなくリーフノードを示すものであればステップＳ１２２１に進み、ブランチノードを示すものであれば、ステップＳ１２１７に進む。

ステップＳ１２１７では、段数カウンタに値１を加え、ステップＳ１２１９に進み、ステップＳ１２１３で読み出したノードから、代表ノード番号を取り出し、ステップＳ１２２０で、該取り出した代表ノード番号に値０を加えた値を配列番号に設定する。
そして、ステップＳ１２２０ａにおいて、探索経路スタックに、配列番号と段数カウンタのカウント値を格納してステップＳ１２１３に戻る。ここで探索経路スタックに格納される配列番号は、ステップＳ１２２０で代表ノード番号に値０を加えた値のものであるから、ノード［０］の配列番号である。

上述のステップＳ１２１３〜ステップＳ１２２０ａのループ処理を、ステップＳ１２１６においてノード種別がリーフノードを示すまで繰り返す。つまり、ひとまとまりの処理として、巡回開始ノードから最初のリーフノードまでノードを巡回してリーフノードの段数を求める。図１２Ｂに示す処理フロー例では、ステップＳ１２２０において、代表ノード番号に値０を加えて配列番号に設定していることから、ノード［０］側を優先してノードを巡回しているが、ノード［１］側を優先してノードを巡回することも可能であることは、以上の説明から当業者に明らかである。

一方ステップＳ１２１６において、ノード種別はブランチノードを示すものではなくリーフノードを示すものと判定されると、ステップＳ１２２１に進み、段数カウンタのカウント値は最大段数カウンタに設定された値より大きいか判定する。ステップＳ１２１６の判定結果が、段数カウンタのカウント値は最大段数カウンタに設定された値より大きい、であれば、ステップＳ１２２２で、最大段数カウンタに、段数カウンタのカウント値を設定してステップＳ１２２３に進み、前記判定結果が、段数カウンタのカウント値は最大段数カウンタに設定された値より大きくない、であれば、ステップＳ１２２３に進む。

ステップＳ１２２３では、探索経路スタックのスタックポインタはツリーのルートノードの配列番号を指しているか判定する。
探索経路スタックのスタックポインタはツリーのルートノードの配列番号を指していれば、ツリーの全てのリーフノードについての段数の処理は完了しているので処理を終了する。そうでなければ、ステップＳ１２２４に進む。

ステップＳ１２２４では、探索経路スタックから配列番号と段数カウンタのカウント値を取り出し、探索経路スタックのスタックポインタを１つ減らす。次にステップＳ１２２８において、ステップＳ１２２４で取り出した配列番号に値１を加えて、巡回開始ノードの配列番号としてノード［１］の配列番号を得てステップＳ１２１３に戻る。

上述のステップＳ１２１３〜ステップＳ１２２８のループ処理を、ステップＳ１２２３において探索経路スタックのスタックポインタがツリーのルートノードの配列番号を指していると判定されるまで繰り返すことにより、ツリー上のすべてのノードの巡回が行われ、ツリーの最大段数が求められる。

以上本発明を実施するための形態について詳細に説明したが、本発明の実施の形態はそれに限ることなく種々の変形が可能であることは当業者に明らかである。
また、本発明の一実施形態に係るビット列検索装置が、図５〜図７Ｃに例示した処理をコンピュータに実行させるプログラムによりコンピュータ上に構築可能なことは明らかである。
したがって、上記プログラム、及びプログラムを記憶したコンピュータ読み取り可能な記憶媒体は、本発明の実施の形態に含まれる。さらに、本発明のカップルドノードツリーのデータ構造も、本発明の実施の形態に含まれる。

１００、４００ 配列
１０１ ノード
１０２ ノード種別
１０３、４０３ 弁別ビット位置
１０４ 代表ノード番号
１１８、４１８ インデックスキー
２００、２００ｂ カップルドノードツリー
２１０ａ、４０１ ルートノード
２８０ 検索キー
３０１ データ処理装置
３０２ 中央処理装置
３０３ キャッシュメモリ
３０４ バス
３０５ 主記憶装置
３０６ 外部記憶装置
３０７ 通信装置
３０８ データ格納装置
３０９ 配列
３０９ａ ブランチノード配列
３０９ｂ リーフノード配列
３１０ 探索経路スタック
３１１ 分岐先配列
７００ａ、７００ｂ ベース番号
７２０ａ、７２０ｂ ノード参照番号
７３０ａ、７３０ｂ 配列番号
８００ ビット列検索装置
８０２ 分岐先情報設定実行部
８０４ 次段ノード分岐先情報格納位置計算実行部
８０６ リーフノード出力実行部
８１０ 検索ツリー記憶手段
８１２ 分岐先情報記憶手段
８２０ 検索開始位置設定手段

Claims (6)

1. ビット列からなる検索キーにより、検索対象であるビット列からなるインデックスキーあるいは該インデックスキーにアクセスするための情報が格納されたツリーのデータ構造に基づいて、前記インデックスキーを検索するビット列検索装置において、
   前記インデックスキーは、本来のインデックスキーのある特定のビット位置に特定のビット値を挿入したものであり、
   前記検索キーは、本来の検索キーの、前記本来のインデックスキーと同一の特定のビット位置に前記特定のビット値を挿入したものであり、
   前記ツリーは配列に記憶され、ｎ段目（ｎは正整数）までのツリーの構成要素を有するものであり、
   該ツリーの始点であるルートノードであって、ノード参照番号１に、前記配列の先頭の配列要素の位置を定める番号であるベース番号を加えた値の配列番号の配列要素に配置されるルートノードと、前記配列の隣接した配列要素に配置される代表ノードと非代表ノードである２つのノードを有する、ツリーの構成要素としてのノード対を有し、前記ノードはブランチノードかリーフノードであって、前記ブランチノードは、前記検索キーの弁別ビット位置を格納する領域を含むが、ブランチノードとリーフノードを識別するノード種別を格納する領域、リンク先である直近下位のノード対の代表ノードの配置された配列要素の配列番号を格納する領域、及び前記インデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含まないものであり、前記リーフノードは、前記インデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含むが、前記ノード種別を格納する領域、及び前記検索キーの弁別ビット位置を格納する領域を含まないものであって、前記代表ノードは該代表ノードの直近上位のブランチノードのノード参照番号の２倍の値のノード参照番号に、前記ベース番号を加えた値の配列番号の配列要素に配置され、前記リーフノードはｎ段目にのみ位置する、カップルドノードツリーを記憶する検索ツリー記憶手段と、
   前記検索キーの、各ブランチノードの前記弁別ビット位置と一致するビット位置のビット値を分岐先情報として前記ブランチノードに対応して格納する分岐先配列を記憶する分岐先情報記憶手段と、
   前記検索ツリー記憶手段に記憶されたカップルドノードツリーからブランチノードをノード参照番号順に読み出し、該ブランチノードの弁別ビット位置と前記検索キーにより前記分岐先情報を抽出して前記分岐先配列の配列番号１の配列要素から順次各配列要素に設定する分岐先情報設定実行部と、
   前記分岐先配列に設定された配列番号１の配列要素に格納された分岐先情報を前記カップルドノードツリーの第１段のノードの分岐先情報として読み出し、該読み出した分岐先情報に前記配列番号１を２倍した値を加えて得られる値を、前記カップルドノードツリーの第２段のノードの分岐先情報が格納された前記分岐先配列の配列要素の配列番号とし、以下、第２段のノードの分岐先情報に該第２段のノードの分岐先情報が格納された前記配列要素の配列番号を２倍した値を加えて得られる値を、前記カップルドノードツリーの第３段のノードの分岐先情報が格納された前記分岐先配列の配列要素の配列番号とするように、自段のノードの分岐先情報に該自段のノードの分岐先情報が格納された前記配列要素の配列番号を２倍した値を加えて得られる値を、前記カップルドノードツリーの次段のノードの分岐先情報が格納された前記分岐先配列の配列要素の配列番号とすることを前記カップルドノードツリーの第ｎ−２段のノードまで繰り返して前記カップルドノードツリーの第ｎ−１段のノードの分岐先情報の格納された前記分岐先配列の配列要素の配列番号を求める次段ノード分岐先情報格納位置計算実行部と、
   前記次段ノード分岐先情報格納位置計算実行部が求めた配列番号により、前記分岐先配列から前記カップルドノードツリーの第ｎ−１段のノードの分岐先情報を読み出し、該読み出した分岐先情報と該配列番号に基づいてリーフノードの格納位置を求め、前記検索ツリー記憶手段に記憶されたカップルドノードツリーから該格納位置に格納されたリーフノードを読み出すリーフノード出力実行部と、
   を備えることを特徴とするビット列検索装置
   
2. 請求項１記載のビット列検索装置において、
   前記カップルドノードツリーを記憶する配列は、ブランチノードを記憶するブランチノード配列とリーフノードを記憶するリーフノード配列から構成され、該ブランチノード配列は、前記カップルドノードツリーを記憶する配列のうち、前記カップルドノードツリーのｎ−１段目までのツリーの構成要素を記憶する部分と一致するものであり、
   前記リーフノード出力実行部は、前記次段ノード分岐先情報格納位置計算実行部が求めた配列番号により、前記分岐先配列から前記カップルドノードツリーの第ｎ−１段のノードの分岐先情報を読み出し、該読み出した分岐先情報と該配列番号を２倍した値の和から前記ブランチノード配列のノード参照番号の最大値を減じたリーフノード配列のノード参照番号を求め、該リーフノード配列のノード参照番号に該リーフノード配列の先頭の配列要素の位置を定める番号であるベース番号を加えた値の配列番号を前記リーフノードの格納位置として求め、前記検索ツリー記憶手段に記憶されたカップルドノードツリーから該格納位置に格納されたリーフノードを読み出し、該リーフノードからインデックスキーを読み出す、あるいはインデックスキーにアクセスするための情報に基づき当該インデックスキーを読み出すことを特徴とするビット列検索装置。
3. 請求項１記載のビット列検索装置が実行するビット列検索方法において、
   前記検索ツリー記憶手段に記憶されたカップルドノードツリーからブランチノードをノード参照番号順に読み出し、該ブランチノードの弁別ビット位置と前記検索キーにより前記分岐先情報を抽出して前記分岐先配列の配列番号１の配列要素から順次各配列要素に設定する分岐先情報設定ステップと、
   前記分岐先配列に設定された配列番号１の配列要素に格納された分岐先情報を前記カップルドノードツリーの第１段のノードの分岐先情報として読み出し、該読み出した分岐先情報に前記配列番号１を２倍した値を加えて得られる値を、前記カップルドノードツリーの第２段のノードの分岐先情報が格納された前記分岐先配列の配列要素の配列番号とし、以下、第２段のノードの分岐先情報に該第２段のノードの分岐先情報が格納された前記配列要素の配列番号を２倍した値を加えて得られる値を、前記カップルドノードツリーの第３段のノードの分岐先情報が格納された前記分岐先配列の配列要素の配列番号とするように、自段のノードの分岐先情報に該自段のノードの分岐先情報が格納された前記配列要素の配列番号を２倍した値を加えて得られる値を、前記カップルドノードツリーの次段のノードの分岐先情報が格納された前記分岐先配列の配列要素の配列番号とすることを前記カップルドノードツリーの第ｎ−２段のノードまで繰り返して前記カップルドノードツリーの第ｎ−１段のノードの分岐先情報の格納された前記分岐先配列の配列要素の配列番号を求める次段ノード分岐先情報格納位置計算ステップと、
   前記次段ノード分岐先情報格納位置計算ステップで求めた配列番号により、前記分岐先配列から前記カップルドノードツリーの第ｎ−１段のノードの分岐先情報を読み出し、該読み出した分岐先情報と該配列番号に基づいてリーフノードの格納位置を求め、前記検索ツリー記憶手段に記憶されたカップルドノードツリーから該格納位置に格納されたリーフノードを読み出すリーフノード出力ステップと、
   を備えることを特徴とするビット列検索方法。
4. 請求項３記載のビット列検索方法において、
   前記カップルドノードツリーを記憶する配列は、ブランチノードを記憶するブランチノード配列とリーフノードを記憶するリーフノード配列から構成され、該ブランチノード配列は、前記カップルドノードツリーを記憶する配列のうち、前記カップルドノードツリーのｎ−１段目までのツリーの構成要素を記憶する部分と一致するものであり、
   前記リーフノード出力ステップは、前記次段ノード分岐先情報格納位置計算ステップで求めた配列番号により、前記分岐先配列から前記カップルドノードツリーの第ｎ−１段のノードの分岐先情報を読み出し、該読み出した分岐先情報と該配列番号を２倍した値の和から前記ブランチノード配列のノード参照番号の最大値を減じたリーフノード配列のノード参照番号を求め、該リーフノード配列のノード参照番号に該リーフノード配列の先頭の配列要素の位置を定める番号であるベース番号を加えた値の配列番号を前記リーフノードの格納位置として求め、前記検索ツリー記憶手段に記憶されたカップルドノードツリーから該格納位置に格納されたリーフノードを読み出し、該リーフノードからインデックスキーを読み出す、あるいはインデックスキーにアクセスするための情報に基づき当該インデックスキーを読み出すことを特徴とするビット列検索方法。
   
5. 請求項３又は請求項４記載のビット列検索方法をコンピュータに実行させることを特徴とするプログラム。
6. 請求項３又は請求項４記載のビット列検索方法をコンピュータに実行させるプログラムを記憶したことを特徴とするコンピュータ読み取り可能な記憶媒体。

Images