説明

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

【課題】より記憶容量の小さい記憶手段に収容可能なカップルドノードツリーのツリー構造を提供する。
【解決手段】ブランチノードから、代表ノード番号を格納する領域を削除する。ルートノードは配列の配列番号1の配列要素に配置し、ブランチノードのリンク先のノード対の代表ノードは、ブランチノードの配置された配列要素の配列番号の2倍の配列番号の配列要素に配置する。リンク先のノードの配置された配列要素の配列番号は、リンク元のブランチノードの配列番号を2倍し、検索キーの弁別ビット位置のビット値と加算して求める。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、ビット列検索の技術に関し、特にカップルドノードツリーを用いたビット列検索に関する。
【背景技術】
【0002】
近年、社会の情報化が進展し、大規模なデータベースが各所で利用されるようになってきている。このような大規模なデータベースからレコードを検索するには、各レコードの記憶されたアドレスと対応づけられたレコード内の項目をインデックスキーとして検索をし、所望のレコードを探し出すことが通例である。また、全文検索における文字列も、文書のインデックスキーと見なすことができる。
【0003】
そして、それらのインデックスキーはビット列で表現されることから、データベースの検索はビット列データの検索に帰着されるということができる。
ビット列データを検索するビット列検索に関するものとして、下記特許文献1、特許文献2及び特許文献3等に開示されたカップルドノードツリーを用いた検索技術がある。
【0004】
図1Aに示すのは、従来の、配列に配置されたカップルドノードツリーの構成例を説明する図である。
図1Aを参照すると、ノード101が配列100の配列番号10の配列要素に配置されている。ノード101はノード種別102、弁別ビット位置103及び代表ノード番号104で構成されている。ノード種別102は0であり、ノード101がブランチノードであることを示している。弁別ビット位置103には1が格納されている。代表ノード番号104にはリンク先のノード対の代表ノードの配列番号20が格納されている。なお、以下では表記の簡略化のため、代表ノード番号に格納された配列番号を代表ノード番号ということもある。また、代表ノード番号に格納された配列番号をそのノードに付した符号あるいはノード対に付した符号で表すこともある。
【0005】
配列番号20の配列要素には、ノード対111の代表ノードであるノード[0]112が格納されている。そして隣接する次の配列要素(配列番号20+1)に代表ノードと対になるノード[1]113が格納されている。ノード[0]112のノード種別114には0が、弁別ビット位置115には3が、代表ノード番号116には30が格納されている。またノード[1]113のノード種別117には1が格納されており、ノード[1]113がリーフノードであることを示している。インデックスキー118には、“0001”が格納されている。
【0006】
なお、代表ノードをノード[0]で表し、それと対になるノードをノード[1]で表すことがある。また、ある配列番号の配列要素に格納されたノードを、その配列番号のノードということがあり、ノードの格納された配列要素の配列番号を、ノードの配列番号ということもある。
配列番号30及び31の配列要素に格納されたノード122とノード123からなるノード対121の内容は省略されている。
【0007】
ノード[0]112、ノード[1]113、ノード122、及びノード123の格納された配列要素にそれぞれ付された0あるいは1は、検索キーで検索を行う場合にノード対のどちらのノードにリンクするかを示すものである。前段のブランチノードの弁別ビット位置にある検索キーのビット値である0か1を代表ノード番号に加えた配列番号のノードにリンクする。
したがって、前段のブランチノードの代表ノード番号に、検索キーの弁別ビット位置のビット値を加えることにより、リンク先のノードが格納された配列要素の配列番号を求めることができる。
なお、上記の例では代表ノード番号をノード対の配置された配列番号のうち小さい方を採用しているが、大きいほうを採用することも可能であることは明らかである。
【0008】
図1Bは、従来のカップルドノードツリーのツリー構造を概念的に示す図である。
符号210aで示すのが図1Bに例示するカップルドノードツリー200のルートノードである。図示の例では、ルートノード210aは配列番号220に配置されたノード対201aの代表ノードとしている。
【0009】
ツリー構造としては、ルートノード210aの下にノート対201bが、その下層にノード対201cとノード対201fが配置され、ノード対201fの下層にはノード対201hとノード対201gが配置されている。ノード対201cの下にはノード対201dが、さらにその下にはノード対201eが配置されている。
【0010】
各ノードの前に付された0あるいは1の符号は、図1において説明した配列要素の前に付された符号と同じである。検索キーの弁別ビット位置のビット値に応じてツリーをたどり、検索対象のリーフノードを見つけることになる。
【0011】
図示された例では、ルートノード210aのノード種別260aは0でブランチノードであることを示し、弁別ビット位置230aは0を示している。代表ノード番号は220aであり、それはノード対201bの代表ノード210bの格納された配列要素の配列番号である。
ノード対201bはノード210bと211bで構成され、それらのノード種別260b、261bはともに0であり、ブランチノードであることを示している。ノード210bの弁別ビット位置230bには1が格納され、リンク先の代表ノード番号にはノード対201cの代表ノード210cの格納された配列要素の配列番号220bが格納されている。
【0012】
ノード210cのノード種別260cには1が格納されているので、このノードはリーフノードであり、したがって、インデックスキーを含んでいる。インデックスキー250cには“000111”が格納されている。一方ノード211cのノード種別261cは0、弁別ビット位置231cは2であり、代表ノード番号にはノード対201dの代表ノード210dの格納された配列要素の配列番号221cが格納されている。
ノード210dのノード種別260dは0、弁別ビット位置230dは5であり、代表ノード番号にはノード対201eの代表ノード210eの格納された配列要素の配列番号220dが格納されている。ノード210dと対になるノード211dのノード種別261dは1であり、インデックスキー251dには“011010”が格納されている。
ノード対201eのノード210e、211eのノード種別260e、261eはともに1であり双方ともリーフノードであることを示し、それぞれのインデックスキー250e、251eにはインデックスキーとして“010010”と“010011”が格納されている。
【0013】
ノード対201bのもう一方のノードであるノード211bの弁別ビット位置231bには2が格納され、リンク先の代表ノード番号にはノード対201fの代表ノード210fの格納された配列要素の配列番号221bが格納されている。
ノード対201fのノード210f、211fのノード種別260f、261fはともに0であり双方ともブランチノードである。それぞれの弁別ビット位置230f、231fには5、3が格納されている。ノード210fの代表ノード番号にはノード対201gの代表ノード210gの格納された配列要素の配列番号220fが格納され、ノード211fの代表ノード番号にはノード対201hの代表ノードであるノード[0]210hの格納された配列要素の配列番号221fが格納されている。
ノード対201gのノード210g、211gのノード種別260g、261gはともに1であり双方ともリーフノードであることを示し、それぞれのインデックスキー250g、251gには“100010”と“100011”が格納されている。
また同じくノード対201hの代表ノードであるノード[0]210hとそれと対をなすノード[1]211hのノード種別260h、261hはともに1であり双方ともリーフノードであることを示し、それぞれのインデックスキー250h、251hには“101011”と“101100“が格納されている。
【0014】
次に、上述のカップルドノードツリーを用いた基本的な検索処理について説明する。以下の説明においては、特に図示されてはいないが、処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶領域が用いられる。また、あるデータ格納領域に格納されるデータ自体にデータ格納領域の符号を付して説明する場合があるし、データ自体の名前をそのデータを格納する一時記憶領域の名前として用いることもある。
【0015】
図2は、従来のカップルドノードツリーを用いたビット列検索の処理フロー例を説明する図である。
まず、ステップS201で、検索開始ノードの配列番号を取得する。取得された配列番号に対応する配列は、カップルドノードツリーを構成する任意のノードを格納したものである。検索開始ノードの指定は、オペレータからの入力によってもよいし、図2に例示する処理を利用するアプリケーションプログラムによるものでもよい。
取得された検索開始ノードの配列番号は、図示しない検索開始ノード設定エリアに設定されるが、この検索開始ノード設定エリアは、先に述べた「処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶領域」の一つである。以下の説明では、「図示しない検索開始ノード設定エリアに設定する」のような表現に変えて、「検索開始ノードの配列番号を得る。」、「検索開始ノードとして設定する」あるいは単に「検索開始ノードに設定する」のように記述することもある。
【0016】
次に、ステップS202で、探索経路スタックに取得された配列番号を格納し、ステップS203で、その配列番号に対応する配列要素を参照すべきノードとして読み出す。そして、ステップS204で、読み出したノードから、ノード種別を取り出し、ステップS205で、ノード種別がブランチノードであるか否かを判定する。
ステップS205の判定において、読み出したノードがブランチノードである場合は、ステップS206に進み、ノードから弁別ビット位置についての情報を取り出し、更に、ステップS207で、取り出した弁別ビット位置に対応するビット値を検索キーから取り出す。そして、ステップS208で、ノードから代表ノード番号を取り出して、ステップS209で、検索キーから取り出したビット値と代表ノード番号とを加算し、新たな配列番号として、ステップS202に戻る。
【0017】
以降、ステップS205の判定においてリーフノードと判定されてステップS210に進むまで、ステップS202からステップS209までの処理を繰り返す。ステップS210で、リーフノードからインデックスキーを検索結果キーとして取り出して、処理を終了する。
【0018】
ルートノードを検索開始ノードとして図1Bに例示するカップルドノードツリー200からインデックスキー“100010”を検索する処理を簡単に説明する。弁別ビット位置は、最上位ビットの位置から0、1、2、・・・とする。
【0019】
検索開始ノードがルートノードであるので、ビット列“100010”を検索キーとしてルートノード210aから処理をスタートする。ルートノード210aの弁別ビット位置230aは0であるので、検索キー“100010”の弁別ビット位置が0のビット値をみると1である。そこで代表ノード番号の格納された配列番号220aに1を加えた配列番号の配列要素に格納されたノード211bにリンクする。ノード211bの弁別ビット位置231bには2が格納されているので、検索キー“100010”の弁別ビット位置が2のビット値をみると0であるから、代表ノード番号の格納された配列番号221bの配列要素に格納されたノード210fにリンクする。
ノード210fの弁別ビット位置230fには5が格納されているので、検索キー“100010”の弁別ビット位置が5のビット値をみると0であるから、代表ノード番号の格納された配列番号220fの配列要素に格納されたノード210gにリンクする。
ノード210gのノード種別260gは1でありリーフノードであることを示しているので、インデックスキー250gを検索結果キーとして読み出す。このようにしてカップルドノードツリーを用いた検索が行われる。なお、検索結果キーを検索キーと比較すると両方とも“100010”であって一致している。
【0020】
上述の図2に示すフローチャート例では、検索処理をノードからインデックスキーを検索結果キーとして取り出すことで終了しているが、さらに検索結果キーと検索キーの一致判定を行い、一致すれば検索成功とし、一致しなければ検索失敗とすることもできる。
【0021】
図1A及び図1Bに示すカップルドノードツリーのリーフノードは、リーフノードインデックスキーを直接含むものであり、図2に示す検索処理は、リーフノードからインデックスキーを取り出すものである。このリーフノードの構成と検索処理におけるインデックスキーの取り出しは、特許文献1及び特許文献2に開示されたものと同様である。
【0022】
一方、特許文献3に開示されたカップルドノードツリーのリーフノードには、インデックスキーに替えて、インデックスキーの記憶された記憶領域の位置を示すポインタである参照ポインタが格納されている。そして、検索処理におけるインデックスキーの取り出しは、リーフノードから参照ポインタを取り出し、参照ポインタの指す記憶領域にアクセスすることにより行われる。
また、特許文献4には、カップルドノードツリーのノードを順次巡回して退避することが記載されている。
【先行技術文献】
【特許文献】
【0023】
【特許文献1】特開2008−015872号公報
【特許文献2】特開2008−112240号公報
【特許文献3】特開2008−269503号公報
【特許文献4】特開2008−269197号公報
【発明の概要】
【発明が解決しようとする課題】
【0024】
カップルドノードツリーは、それ以前に検索処理に用いられていたツリーと比べてツリーを記憶する記憶容量が少ないという特徴を有する。しかしながら、検索対象のデータサイズが非常に大きくなると、より小さい容量の記憶手段に配置可能なツリー構造であることが望ましい。
そこで、本発明が解決しようとする課題は、より小さい容量の記憶手段に配置可能なカップルドノードツリーのツリー構造を提供することである。
【課題を解決するための手段】
【0025】
本発明によれば、カップルドノードツリーの各ノードは、ツリー上の位置に応じた配列の配列要素に配置される。ルートノードの配置される配列要素の配列番号は1とされ、ブランチノードのリンク先のノード対の代表ノードの配置された配列要素の配列番号は、ブランチノードが配置された配列要素の配列番号を2倍することにより求められる。したがって、本発明によるブランチノードは、代表ノード番号を含む必要がない。
【0026】
本発明の第1の態様によれば、ブランチノードはノード種別と弁別ビット位置を含むが、代表ノード番号は含まない。また、リーフノードは、ノード種別とインデックスキーあるいはインデックスキーにアクセスするための情報を含む。インデックスキーにアクセスするための情報は、上述の特許文献3に記載されたインデックスキーの記憶された記憶領域の位置を示す参照ポインタであってもよいし、それに限らず、インデックスキーの記憶された記憶領域の位置を求める索引のインデックスであってもよい。
【0027】
また、本発明の第2の態様によれば、検索対象のインデックスキーのある特定のビット位置に特定のビット値“0”あるいは“1”を挿入したものによりカップルドノードツリーを構成し、同様に検索キーの、検索対象のインデックスキーと同一の特定のビット位置に同一の特定のビット値“0”あるいは“1”を挿入したものにより検索を行う。そして、ブランチノードとリーフノードはノード種別を含まず、ブランチノードは弁別ビット位置を含むが代表ノード番号は含まず、リーフノードはインデックスキーあるいはインデックスキーにアクセスするための情報を含む。
【0028】
そして、リーフノードは、カップルドノードツリーの最大段数をNとしたとき、N段目にのみ存在し、かつN段目にはリーフノードしか存在しないようにツリーを構成することにより、ノードの種別の判別を可能としている。したがって、検索処理は、ルートノードから最終段であるN段目のノードまでのリンク動作を繰り返すことで行われる。
【発明の効果】
【0029】
本発明によれば、ブランチノードは少なくともリンク先を識別する代表ノード番号を含まないので、ノードのサイズを小さくすることができる。例えばインデックキーの数が16とすると、リーフノードのサイズを規定するインデックスキーを表現するためのビット数は4である。一方、従来のブランチノードのサイズを規定する弁別ビット位置に必要なビット数は2、代表ノード番号に必要なビット数は、ルートノードを含めたリンク先となるノード対の数が1+1+2+4+8=16であることから4であるので、必要なビット数は合計で6となる。
【0030】
したがって、従来のブランチノードは、リーフノードと比べて大きな記憶容量を必要としていた。この記憶容量の差は、インデックスキーの数が大きくなるとさらに拡大する。しかし、本発明によれば、代表ノード番号を格納する記憶領域が必要なくなることから、カップルドノードツリーを配置する配列のサイズを小さくすることができる。
【0031】
さらに、本発明の第2の実施形態によれば、カップルドノードツリーを配置する配列のサイズを小さくすることに加えて、検索処理におけるノード種別の判定による分岐動作が削除されるので、処理速度を向上させることができる。
【図面の簡単な説明】
【0032】
【図1A】従来の、配列に配置されたカップルドノードツリーの構成例を説明する図である。
【図1B】従来のカップルドノードツリーのツリー構造を概念的に示す図である。
【図2】従来のカップルドノードツリーを用いたビット列検索の処理フロー例を説明する図である。
【図3】本発明を実施するためのハードウェア構成例を説明する図である。
【図4A】本発明の第1の実施形態における配列に配置されたカップルドノードツリーの構成例を説明する図である。
【図4B】本発明の第1の実施形態に係るカップルドノードツリーのツリー構造を概念的に示す図である。
【図5】本発明の第1の実施形態におけるビット列検索装置の機能ブロック構成例を説明する図である。
【図6】本発明の第1の実施形態におけるビット列検索の処理フロー例を説明する図である。
【図7】本発明の第1の実施形態におけるカップルドノードツリーを用いた検索例を示す図である。
【図8A】本発明の第2の実施形態における配列に配置されたカップルドノードツリーの構成例を説明する図である。
【図8B】本発明の第2の実施形態に係るカップルドノードツリーのツリー構造を概念的に示す図である。
【図9】本発明の第2の実施形態におけるビット列検索装置の機能ブロック構成例を説明する図である。
【図10】本発明の第2の実施形態におけるビット列検索の処理フロー例を説明する図である。
【図11】本発明の第2の実施形態におけるリンク先の配列番号を求める処理フロー例を説明する図である。
【図12】本発明の第2の実施形態におけるカップルドノードツリーを用いた検索例を示す図である。
【図13】本発明の第1の実施形態の変形例における配列に配置されたカップルドノードツリーの構成例を説明する図である。
【図14】本発明の第1の実施形態の変形例におけるビット列検索の処理フロー例を説明する図である。
【図15】本発明の第2の実施形態の変形例における配列に配置されたカップルドノードツリーの構成例を説明する図である。
【図16】本発明の第2の実施形態の変形例におけるビット列検索の処理フロー例を説明する図である。
【図17】リンク先の配列番号を求める処理フロー例を説明する図である。
【図18A】本発明の第1及び第2の実施形態におけるポインタレスツリーを生成する処理の前段の処理フロー例を説明する図である。
【図18B】本発明の第1及び第2の実施形態におけるポインタレスツリーを生成する処理の後段の処理フロー例を説明する図である。
【図19】巡回開始ノードよりツリーを巡回し、ノードをポインタレスツリーに格納する処理フロー例を説明する図である。
【図20A】本発明の第1の実施形態におけるノードを生成する処理の処理フロー例を説明する図である。
【図20B】本発明の第2の実施形態におけるノードを生成する処理の処理フロー例を説明する図である。
【図21】変換前のツリーの最大段数を求める処理フロー例を説明する図である。
【図22】巡回開始ノードよりツリーを巡回し、ノードの段数をカウントして巡回済みノードの最大段数を求める処理フロー例を示す図である。
【発明を実施するための形態】
【0033】
図3は、本発明を実施するためのハードウェア構成例を説明する図である。本発明の検索装置による検索処理は中央処理装置302及びキャッシュメモリ303を少なくとも備えたデータ処理装置301によりデータ格納装置308を用いて実施することができる。カップルドノードツリーが配置される配列309と検索中にたどるノードが格納された配列要素の配列番号を記憶する探索経路スタック310を有するデータ格納装置308は、主記憶装置305または外部記憶装置306で実現することができ、あるいは通信装置307を介して接続された遠方に配置された装置を用いることも可能である。
なお、リーフノードにインデックスキーではなくインデックスキーにアクセスするための情報を格納する場合には、データ格納装置には、インデックスキーを記憶する記憶領域が設けられる。
【0034】
図3の例示では、主記憶装置305、外部記憶装置306及び通信装置307が一本のバス304によりデータ処理装置301に接続されているが、接続方法はこれに限るものではない。また、主記憶装置305をデータ処理装置301内のものとすることもできるし、探索経路スタック310を中央処理装置302内のハードウェアとして実現することも可能である。あるいは、配列309は外部記憶装置306に、探索経路スタック310を主記憶装置305に持つなど、使用可能なハードウェア環境、インデックスキー集合の大きさ等に応じて適宜ハードウェア構成を選択できることは明らかである。
また、特に図示されてはいないが、処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶装置が用いられることは当然である。
【0035】
次に図4A〜図7を参照して、本発明の第1の実施形態について説明する。
図4Aは、本発明の第1の実施形態における配列に配置されたカップルドノードツリーの構成例を説明する図である。図1Aに示す構成例と比べると、ブランチノードから代表ノード番号を格納する領域がなくなっている。また、配列番号は、1から15への連続した番号のものが記載されている。
【0036】
図4Aを参照すると、ルートノード401が配列400の配列番号1の配列要素に配置されている。ルートノード401はノード種別402及び弁別ビット位置403で構成されている。ノード種別402は0であり、ルートノード401がブランチノードであることを示している。弁別ビット位置403には1が格納されている。
【0037】
配列番号が1であるルートノード401からの点線の矢印410で示すリンク先ノード対411の代表ノードであるノード[0]412は、ツリー上で直近上位に位置する親ノードであるルートノード401の配列番号1の2倍の値を持つ配列番号2の配列要素に配置されている。そして隣接する次の配列要素(配列番号3)に代表ノードと対になるノード[1]413が配置されている。ノード[0]412のノード種別には1が格納されており、ノード[0]412がリーフノードであることを示している。インデックスキー418には、“0001”が格納されている。一方、ノード[1]413のノード種別には0が格納されており、ノード[1]413がブランチノードであることを示している。ブランチノード413の弁別ビット位置には3が格納されている。
【0038】
配列番号が3であるブランチノード413からの点線の矢印420で示すリンク先ノード対421の代表ノードであるノード422は、親ノードであるノード413の配列番号3の2倍の値を持つ配列番号6の配列要素に配置されている。そして隣接する次の配列要素(配列番号7)に代表ノードと対になるノード423が配置されている。ノード422のノード種別には0が格納されており、ノード422がブランチノードであることを示している。ブランチノード422の弁別ビット位置には4が格納されている。また、ノード423のノード種別にも0が格納されており、ノード423がブランチノードであることを示している。ブランチノード422の弁別ビット位置には5が格納されている。
【0039】
そして、配列番号4及び配列番号5の配列要素には、ノードは配置されていない。
上述の例示から明らかなとおり、リンク先のノード対の代表ノードの配列番号は、親ノードの配列番号の2倍となる。
【0040】
そこで、配列番号が6であるブランチノード422からの点線の矢印430で示すリンク先ノード対431の代表ノードであるノード432は、配列番号12の配列要素に配置されている。そして隣接する次の配列要素(配列番号13)に代表ノードと対になるノード433が配置されている。ノード432及びノード433の内容の記載は省略されている。
【0041】
同様に、配列番号が7であるブランチノード423からの点線の矢印440で示すリンク先ノード対441の代表ノードであるノード442は、配列番号14の配列要素に配置されている。そして隣接する次の配列要素(配列番号15)に代表ノードと対になるノード443が配置されている。ノード442及びノード443の内容の記載は省略されている。
また、配列番号8から配列番号11の配列要素には、ノードは配置されていない。
【0042】
図4Bは、本発明の第1の実施形態におけるカップルドノードツリーのツリー構造を概念的に示す図である。図1Bに示すカップルドノードツリー200のツリー構造と比べると、図4Bに示すカップルドノードツリー200aのリーフノードについては同一であり、ブランチノードの弁別ビット位置の値も図1Bに示すものと同一なので、ツリー自体の分岐パターンも同一である。しかし、ブランチノードは、リンク先のノード対の代表ノードの配列番号である代表ノード番号を含まない。代表ノード番号はブランチノードの配列番号を2倍することにより得られるので、代表ノード番号によるリンク先への結合を、代表ノード番号の符号を付した点線の矢印により表している。また、各ノードを示す符号の近傍に、各ノードが配置される配列要素の配列番号を、ルートノード210aに対して[1]のように表示している。代表ノード番号と配列番号の表記以外は図1Bに記載したものと同じなので、これ以上の説明は省略する。
【0043】
図5は、本発明の第1の実施形態におけるビット列検索装置の機能ブロック構成例を説明する図である。
図5に例示する本実施態様に係るビット列検索装置500は、検索ツリー記憶手段510、検索開始位置設定手段520、ノード読出手段530、ノード種別判定手段540、検索キー設定手段550、ノードリンク手段560及び検索結果出力手段570を備えている。
【0044】
検索ツリー記憶手段510の記憶領域には配列が確保され、その配列にカップルドノードツリーが配置される。検索開始位置設定手段520には、検索開始ノードの配列番号が設定される。ルートノードを検索開始ノードとする場合は、配列番号として1が設定される。検索開始位置の設定は、検索処理の結果を利用するユーザにより設定することができる。
【0045】
ノード読出手段530は、検索開始位置設定手段520に設定された配列番号の検索開始ノード、あるいはノードリンク手段560により設定された配列番号のリンク先のノードを読み出す。ノード種別識別手段540は、ノード読出手段530が読みだしたノードの種別を判定し、リーフノードであればそのリーフノードを検索結果出力手段570に渡し、ブランチノードであればそのブランチノードをノードリンク手段560に渡す。
【0046】
検索キー設定手段550には、検索キーが設定される。検索キーの設定は、検索処理の結果を利用するユーザにより設定することができる。ノードリンク手段560は、ノード種別判定手段540から渡されたブランチノードの弁別ビット位置にある、検索キー設定手段550に設定された検索キーのビットの値とブランチノードの配置されている配列要素の配列番号を2倍した値を加算した値を、次に読み出すノードの配置された配列要素の配列番号として設定する。
【0047】
検索結果出力手段570は、ノード種別判定手段540から渡されたリーフノードからインデックスキーあるいはインデックスキーにアクセスするための情報を取り出す。リーフノードから取り出すものがインデックスキーであるときは、そのインデックスキーを検索結果キーとして出力する。リーフノードから取り出すものがインデックスキーにアクセスするための情報であるときは、取り出したインデックスキーにアクセスするための情報に基づき、インデックスキーを読み出して検索結果キーとして出力する。
なお、検索結果キーと検索キーを比較し、一致すれば検索成功とし、一致しなければ検索失敗とする検索結果を出力することも可能である。
上記図5を参照して説明した機能ブロック構成はあくまで1つの例であり、種々の変形が可能であることは明らかである。
【0048】
以下、本発明の第1の実施形態における検索処理について、図6を参照して説明する。図6は、本発明の第1の実施形態におけるビット列検索の処理フロー例を説明する図である。
【0049】
まず、ステップS601で、リンク先配列番号に1を設定する。ここでいうリンク先配列番号は、先に述べた図示しない一時的記憶領域の1つの例である。リンク先配列番号には、検索開始ノードの配列番号と、リンク先のノード対の代表ノードの配列番号が設定される。図6に示す例では、検索開始ノードをルートノードとしたものである。検索開始ノードをルートノード以外のものとした場合でも、以下の処理フローは同様である。
【0050】
次にステップS603で、配列からリンク先配列番号に設定された配列番号の配列要素を参照すべきノードとして読み出す。そして、ステップS604で、読み出したノードから、ノード種別を取り出し、ステップS605で、ノード種別がブランチノードであるか否かを判定する。
【0051】
ステップS605の判定において、読み出したノードがブランチノードである場合はステップS606に進み、ノードから弁別ビット位置についての情報を取り出し、更に、ステップS607で、取り出した弁別ビット位置に対応するビット値を検索キーから取り出す。そして、ステップS608で、リンク先配列番号に設定された配列番号を2倍にしてリンク先配列番号に設定する。さらにステップS609で、ステップS607で検索キーから取り出したビット値をステップS608でリンク先配列番号に設定した配列番号に加算し、新たな配列番号としてリンク先配列番号に設定して、ステップS603に戻る。
【0052】
以降、ステップS605の判定においてリーフノードと判定されてステップS610に進むまで、ステップS603からステップS609までの処理を繰り返す。ステップS610では、リーフノードからインデックスキーを取り出して、処理を終了する。
なお、上述の例では、リーフノードにインデックスキーが直接含まれているものとしたが、リーフノードにインデックスキーにアクセスするための情報が含まれている場合には、ステップS610においてリーフノードからインデックスキーにアクセスするための情報を取り出し、さらに追加ステップにおいて、取り出されたインデックスキーにアクセスするための情報を用いてインデックスキーを取り出す。
また、インデックスキーを取り出したのち、そのインデックスキーを検索結果キーとして他のアプリケーションで用いることもできるし、検索キーとの一致判定を行い、検索成功あるいは検索失敗とすることもできる。
【0053】
次に、図7を参照して、本発明の第1の実施形態に係るカップルドノードツリーを用いた検索例を説明する。図7には、図4Bに例示したカップルドノードツリーのうち、説明に必要な部分のみ記載しており、ノード211bより下位の部分は省略されている。
図7に示す例では、検索キー設定エリア270には検索キーとしてビット列“011010”(以下、検索キー270と表記する。)が設定され、検索開始ノードはルートノード210aとされている。また、リンク先の配列番号が、リンク元のブランチノードの配列番号を2倍した代表ノード番号と検索キーの弁別ビット位置のビット値の和で求められることも記載されている。
【0054】
以下、図7の記載に沿って、検索処理の流れを説明する。
検索開始ノードがルートノードであることから、検索の開始時には、リンク先配列番号には1が設定されるので、ノード210aが読み出される。そして、ノード210aのノード種別220aは0であり、ブランチノードであることを示しているので弁別ビット位置230aからその値0が取り出される。検索キー270のビット位置0の値は0であるので、リンク先配列番号は、配列番号1を2倍した代表ノード番号220aに0を加えた2となり、配列番号2の配列要素に配置されたノード210bが次に読み出される。
【0055】
ノード210bのノード種別220bは0であり、ブランチノードであることを示しているので弁別ビット位置230bからその値1が取り出される。検索キー270のビット位置1の値は1であるので、リンク先配列番号は、配列番号2を2倍した代表ノード番号220bに1を加えた5となり、配列番号5の配列要素に配置されたノード211cが次に読み出される。
【0056】
ノード211cのノード種別221cは0であり、ブランチノードであることを示しているので弁別ビット位置231cからその値2が取り出される。検索キー270のビット位置2の値は1であるので、リンク先配列番号は、配列番号5を2倍した代表ノード番号221cに1を加えた11となり、配列番号11の配列要素に配置されたノード211dが次に読み出される。
【0057】
ノード211dのノード種別221dは1であり、リーフノードであることを示しているのでインデックスキー251dからインデックスキー“011010”が取り出され、検索処理が終了する。
【0058】
次に図8A〜図12を参照して、本発明の第2の実施形態について説明する。
図8Aは、本発明の第2の実施形態における配列に配置されたカップルドノードツリーの構成例を説明する図である。本実施形態は、リーフノード、ブランチノードからノード種別を削除し、リーフノードをツリーの最下段にのみに配置している。さらに、インデックスキー、検索キーは、本来のインデックスキー、検索キーに対して、ある特定のビット位置である最上位ビットに0を挿入したものとしている。リンク先の配列番号の求め方は、第1の実施形態と同様である。なお、最上位ビットとして付加するビット値は、0ではなく1とすることもできる。要するに、同一のビット値を最上位ビットとして付加すればよい。また、特定のビット値を挿入するある特定のビット位置も、最上位のビット位置に限ることなく、任意のビット位置とすることができる。同一のビット値を挿入したビット位置は、カップルドノードツリーの本来のブランチノードの弁別ビット位置に現れることはない。そこで、後に説明するダミーのブランチノードの弁別ビット位置として用い、ダミーのブランチノードを挿入することにより、リーフノードをツリーの最下段にのみに配置することを可能としている。
【0059】
図8Aを参照すると、ルートノード801が配列800の配列番号1の配列要素に配置されている。ルートノード801は弁別ビット位置803で構成されている。弁別ビット位置803には2が格納されている。
【0060】
配列番号が1であるルートノード801からの点線の矢印810で示すリンク先ノード対811の代表ノードであるノード[0]812は、ツリー上で直近上位に位置する親ノードであるルートノード801の配列番号1の2倍の値を持つ配列番号2の配列要素に配置されている。そして隣接する次の配列要素(配列番号3)に代表ノードと対になるノード[1]813が配置されている。
【0061】
ノード[0]812の弁別ビット位置には0が格納されており、そのリンク先は、点線の矢印840で示すように、ノード[0]812の配列番号2の2倍の配列番号4の配列要素に格納されたノード842である。また、ノード842の弁別ビット位置には0が格納されており、そのリンク先は、点線の矢印850で示すように、ノード842の配列番号4の2倍の配列番号8の配列要素に格納されたノード852である。
【0062】
ノード852は、図8Aに例示するカップルドノードツリーの最下段に位置するので、リーフノードであり、インデックスキー818には最上位ビットに0が挿入されたインデックスキー“00001”が格納されている。
図8Aに示す例では、インデックスキー“00001”は、ルートノード801の弁別ビット位置803のビット位置2におけるビット値0によりすでに他の配列要素に格納されたインデックスキーとは弁別されている。したがって、図4Aに示す第1の実施形態のように、ルートノードの直近下位の配列番号2の配列要素に格納されたノードが本来のリーフノードの位置であるが、本実施形態においてはリーフノードであることを識別するノード種別を用いないので、弁別ビット位置が最上位ビット位置の0であるダミーのブランチノード812、842を挿入して最下段に位置するようにしている。なお、図8Aに示す配列番号5の配列要素が空きとなっているように、2段目のダミーのブランチノード842と対をなすノードは実質的に存在しない空きノードとなる。
【0063】
一方、ノード[1]813の弁別ビット位置には4が格納されている。配列番号が3であるブランチノード813からの点線の矢印820で示すリンク先ノード対821の代表ノードであるノード822は、親ノードであるノード813の配列番号3の2倍の値を持つ配列番号6の配列要素に配置されている。そして隣接する次の配列要素(配列番号7)に代表ノードと対になるノード823が配置されている。ノード822の弁別ビット位置には5が格納されている。また、ノード823の弁別ビット位置には6が格納されている。
【0064】
配列番号が6であるブランチノード822からの点線の矢印830で示すリンク先ノード対831の代表ノードであるノード832は、配列番号12の配列要素に配置されている。そして隣接する次の配列要素(配列番号13)に代表ノードと対になるノード833が配置されている。ノード832及びノード833の内容の記載は省略されている。また、ブランチノード823のリンク先の記載も省略されている。
【0065】
図8Bは、本発明の第2の実施形態におけるカップルドノードツリーのツリー構造を概念的に示す図である。図8Bに示すツリー構造においては、図4Bに示すツリー構造に格納されている各インデックスキーの最上位のビット位置に0が追加され、ビット長が6ビットから7ビットになっている。それに伴い、図4Bに示すブランチノードと同一の符号を付したブランチノードの弁別ビット位置は1つシフトされ、値が1つ大きくなっている。
【0066】
また、図4Bに示すツリー構造における段数は5段であるので、図8Bに示すツリー構造においては、5段目にのみリーフノードが位置している。そして、図4Aに示すツリー構造において5段目より上位の階層に位置するリーフノードは、弁別ビット位置が0のダミーのブランチノードとなっている。そして、ダミーのブランチノードの直近下位のノードが5段目のノードとなるまで、ダミーのブランチノードが挿入されている。
直近下位のノード対の代表ノードが配置された配列要素の配列番号である代表ノード番号の算出方法は、第1の実施形態のものと同じである。
【0067】
図4Bに示す例示では、最上位ビットとして0を付加しているため、例えば本来的なインデックスキー“000111”はリーフノード210jに格納されているが、最上位ビットとして1を付加した場合はリーフノード211jに格納することは明らかである。
【0068】
図9は、本発明の第2の実施形態におけるビット列検索装置の機能ブロック構成例を説明する図である。
図9に例示する本実施態様に係るビット列検索装置900は、検索ツリー記憶手段910、検索開始位置設定手段920、ノード読出手段9301〜930n、検索キー設定手段950、ノードリンク手段9601〜960n−1及び検索結果出力手段970を備えている。ただし、nはカップルドノードツリーの段数である。
【0069】
先に説明した第1の実施形態と同様に、検索ツリー記憶手段910の記憶領域には配列が確保され、その配列に本発明の第2の実施形態に係るカップルドノードツリーが配置される。また、検索開始位置設定手段920には、検索開始ノードの配列番号として、ルートノードの配列番号である1が設定される。
【0070】
ノード読出手段9301は、検索開始位置設定手段に設定された配列番号1のルートノードを読み出す。
検索キー設定手段950には、検索キーが設定される。検索キーの設定は、検索処理の結果を利用するユーザにより設定することができる。ノードリンク手段9601は、ノード読出手段9601が読み出したブランチノードの弁別ビット位置にある、検索キー設定手段950に設定された検索キーのビットの値とルートノードの配列番号1を2倍した値とを加算した値を、次に読み出すノードの配置された配列要素の配列番号として設定する。
【0071】
以下同様に、ノードリンク手段9602〜960n−1は、ノード読出手段9302〜930n−1が読み出したブランチノードの弁別ビット位置にある、検索キー設定手段950に設定された検索キーのビットの値と、前段のノードリンク手段9601〜960n−2により設定された配列番号を2倍した値とを加算した値を、それぞれ次に読み出すノードの配置された配列要素の配列番号として設定する。
【0072】
ノード読出手段9302〜930n−1は、前段のノードリンク手段9601〜960n−2が設定した配列番号のブランチノードを読み出し、ノード読出手段930nは、ノードリンク手段960n−1が設定した配列番号のリーフノードを読み出して、検索結果出力手段970に渡す。
【0073】
検索結果出力手段970は、ノード読出手段930nから渡されたリーフノードから、第1の実施形態の場合と同様に、インデックスキーあるいはインデックスキーにアクセスするための情報を取り出す。リーフノードから取り出すものがインデックスキーであるときは、そのインデックスキーを検索結果キーとして出力する。リーフノードから取り出すものがインデックスキーにアクセスするための情報であるときは、取り出したインデックスキーにアクセスするための情報に基づき、インデックスキーを読み出して検索結果キーとして出力する。
また、検索結果キーと検索キーを比較し、一致すれば検索成功とし、一致しなければ検索失敗とする検索結果を出力することが可能であることも、第1の実施形態の場合と同様である。
【0074】
次に、本発明の第2の実施形態における検索処理について、図10及び図11を参照して説明する。
図10は、本発明の第2の実施形態におけるビット列検索の処理フロー例を説明する図である。図10に示す例では、カップルドノードツリーの段数はnとする。
【0075】
まず、ステップS1001で、リンク先配列番号に1を設定する。
次にステップS1002において、リンク先配列番号(ルートノードの配列番号)の指す配列に格納された弁別ビット位置と検索キーにより、2段目のノードの配列番号を求める。
【0076】
続いてステップS1003において、2段目のノードの配列番号の指す配列に格納された弁別ビット位置と検索キーにより、3段目のノードの配列番号を求める。
以下同様に、ステップS1004〜ステップS100nにおいて、3段目〜n−1段目のノードの配列番号の指す配列に格納された弁別ビット位置と検索キーにより、それぞれ4段目〜n段目のノードの配列番号を求める。ステップS1002〜ステップS100nの処理の詳細は、後に図11を参照して説明する。
【0077】
最後に、n段目のノードの配列番号の指す配列に格納されたビット列をインデックスキーとして取り出し、処理を終了する。
なお、図10に例示する処理フロー例は、特定の段数nを有する本実施形態のカップルドノードツリーを用いたものであるが、段数nをパラメータとしたアセンブラマクロにより、本実施形態の任意の段数のカップルドノードツリーを用いた検索処理を実現するための処理フローを生成することが可能である。
【0078】
図11は、本発明の第2の実施形態におけるリンク先の配列番号を求める処理フロー例を説明する図であり、図10に示すステップS1002〜ステップS100nの処理の詳細を示すものである。
【0079】
まず、ステップS1101において、配列から、リンク先配列番号の指す配列要素に格納された内容を弁別ビット位置として読み出し、ステップS1102において、検索キーから、該読み出した弁別ビット位置の指すビット値を取り出す。
【0080】
次にステップS1103において、リンク先配列番号に設定された配列番号を2倍にしてリンク先配列番号に設定する。さらにステップS1104で、ステップS1103でリンク先配列番号に設定された配列番号に、ステップS1102で取り出したビット値を加算してリンク先配列番号に設定して処理を終了する。
【0081】
次に、図12を参照して、本発明の第2の実施形態に係るカップルドノードツリーを用いた検索例を説明する。図12には、図8Bに例示したカップルドノードツリーのうち、説明に必要な部分のみ記載しており、ノード211bより下位の部分は省略されている。
図12に示す例では、検索キー設定エリア280には検索キーとしてビット列“0011010”(以下、検索キー280と表記する。)が設定されている。検索キー280は、図4Bに示す本発明の第1の実施形態に係るカップルドノードツリーを用いた検索例における検索キー270に最上位ビットとして0を付加したものである。検索開始ノードはルートノード210aである。図4Bに示す検索例と同様に、リンク先の配列番号が、リンク元のブランチノードの配列番号を2倍した代表ノード番号と検索キーの弁別ビット位置のビット値の和で求められることも記載されている。
【0082】
以下、図12の記載に沿って、検索処理の流れを説明する。
検索開始ノードがルートノードであることから、検索の開始時には、リンク先配列番号には1が設定されるので、ノード210aが読み出される。そして、ノード210aの弁別ビット位置230aからその値1が取り出される。検索キー280のビット位置1の値は0であるので、リンク先配列番号は、配列番号1を2倍した代表ノード番号220aに0を加えた2となり、配列番号2の配列要素に配置されたノード210bが次に読み出される。
【0083】
そして、ノード210bの弁別ビット位置230bからその値2が取り出される。検索キー280のビット位置2の値は1であるので、リンク先配列番号は、配列番号2を2倍した代表ノード番号220bに1を加えた5となり、配列番号5の配列要素に配置されたノード211cが次に読み出される。
【0084】
そして、ノード211cの弁別ビット位置231cからその値3が取り出される。検索キー280のビット位置3の値は1であるので、リンク先配列番号は、配列番号5を2倍した代表ノード番号221cに1を加えた11となり、配列番号11の配列要素に配置されたノード211dが次に読み出される。
【0085】
そして、ノード211dの弁別ビット位置231dからその値0が取り出される。検索キー280のビット位置0の値は0であるので、リンク先配列番号は、配列番号11を2倍した代表ノード番号221iに0を加えた22となり、配列番号22の配列要素に配置されたノード210lが次に読み出される。
【0086】
ノード210lはカップルドノードツリーの最下位段に位置するので、インデックスキー250lから検索結果のインデックスキー“0011010”が取り出され、検索処理が終了する。
【0087】
次に、上述の第1の実施形態及び第2の実施形態の変形例について説明する。これらの変形例は、ツリーを格納する配列を記憶装置の領域に柔軟に配置可能とする、あるいは記憶装置の任意の領域に存在する配列にツリーを配置可能とするためのものである。
【0088】
図13は、本発明の第1の実施形態の変形例における配列に格納されたカップルドノードツリーの構成例を説明する図である。図4Aに示す構成例と比較すると、ベース番号600とオフセット番号610が追加されている。また、図4Aの配列番号1〜15に替えて、ノード参照番号620の値1〜15が記載されている。図13においては、配列番号630については、その番号の値として、100、111、122、123、134〜137、148〜155が記載されている。
また、図13には、ベース番号600の値として100が、オフセット番号610の値として10、20、30、40が例示されている。
その他の符号については、図4Aに示された対応する符号にaを付加したものが使用されている。
【0089】
ベース番号は、後述の1段目のオフセット番号と組み合わせてツリーのルートノードの位置を定める番号である。ベース番号を用いることにより、ルートノードの配列番号が、図4A及び図4Bの例示のように1に制約される必要をなくすことができる。
オフセット番号は、ツリーの各段のノードの格納される開始位置を定める番号である。オフセット番号を用いることにより、ツリーのノードを、そのノードが位置するツリー上の段数毎に配置することができる。オフセット番号は、段数毎にオフセット番号表に設定しておく。
ノード参照番号は、ノードの順番を定める番号であり、図4に例示する配列番号に相当する。
配列番号は、ベース番号、オフセット番号及びノード参照番号の和により求めることができる。
本変形例において、ベース番号を0、各段のオフセット番号を0とすると、ノード参照番号は図4A及び図4Bに例示する配列番号と一致し、本変形例のカップルドノードツリーは、図4A及び図4Bに例示する第1の実施形態のカップルドノードツリーと一致する。
【0090】
図13を参照すると、ベース番号600が100(以下、ベース番号100という。)、オフセット番号610(1段目)が10(以下、オフセット番号10、のようにいう。)であって、ノード参照番号620は1(以下、ノード参照番号1、のようにいう。)であるから、ルートノード401aは配列400aの配列番号630が111(以下、配列番号111、のようにいう。)の配列要素に配置されている。ルートノード401aはノード種別402a及び弁別ビット位置403aで構成されている。ノード種別402aは0であり、ルートノード401aがブランチノードであることを示している。弁別ビット位置403aには1が格納されている。
【0091】
ノード参照番号1のルートノード401aからの点線の矢印410aで示すリンク先ノード対411aの代表ノードであるノード[0]412aは、ツリー上で直近上位に位置する親ノードであるルートノード401aのノード参照番号1の2倍の値を持つノード参照番号2に、ベース番号100とオフセット番号20の和を加えた配列番号122の配列要素に配置されている。そして隣接する次の配列要素(ノード参照番号3、配列番号123)に代表ノードと対になるノード[1]413aが配置されている。ノード[0]412aのノード種別には1が格納されており、ノード[0]412aがリーフノードであることを示している。インデックスキー418aには、“0001”が格納されている。一方、ノード[1]413aのノード種別には0が格納されており、ノード[1]413aがブランチノードであることを示している。ブランチノード413aの弁別ビット位置には3が格納されている。
【0092】
ノード参照番号が3であるブランチノード413aからの点線の矢印420aで示すリンク先ノード対421aの代表ノードであるノード422aは、親ノードであるノード413aのノード参照番号3の2倍の値を持つノード参照番号6に、ベース番号100とオフセット番号30の和を加えた配列番号136の配列要素に配置されている。そして隣接する次の配列要素(ノード参照番号7、配列番号137)に代表ノードと対になるノード423aが配置されている。ノード422aのノード種別には0が格納されており、ノード422aがブランチノードであることを示している。ブランチノード422aの弁別ビット位置には4が格納されている。また、ノード423aのノード種別にも0が格納されており、ノード423aがブランチノードであることを示している。ブランチノード422aの弁別ビット位置には5が格納されている。
【0093】
そして、配列番号134及び配列番号135の配列要素には、ノードは配置されていない。
上述の例示から明らかなとおり、リンク先のノード対の代表ノードのノード参照番号は、親ノードのノード参照番号の2倍となる。
【0094】
そこで、ノード参照番号が6であるブランチノード422aからの点線の矢印430aで示すリンク先ノード対431aの代表ノードであるノード432aは、ノード参照番号12に、ベース番号100とオフセット番号40の和を加えた配列番号152の配列要素に配置されている。そして隣接する次の配列要素(ノード参照番号13、配列番号153)に代表ノードと対になるノード433aが配置されている。ノード432a及びノード433aの内容の記載は省略されている。
【0095】
同様に、ノード参照番号が7であるブランチノード423aからの点線の矢印440aで示すリンク先ノード対441aの代表ノードであるノード442aは、ノード参照番号14に、ベース番号100とオフセット番号40の和を加えた配列番号154の配列要素に配置されている。そして隣接する次の配列要素(ノード参照番号15、配列番号155)に代表ノードと対になるノード443aが配置されている。ノード442a及びノード443aの内容の記載は省略されている。
また、配列番号148から配列番号151の配列要素には、ノードは配置されていない。
【0096】
本変形例においても、カップルドノードツリーのツリー構造自体は、図4Bに示すものと同じである。違う点は、図4A及び図4Bに示すものにおいては、ノードのツリー上の位置が配列に結びついた配列番号で規定されるのに対して、本変形例においては、配列とは独立のノード参照番号で規定される点である。
そして、ノード参照番号とベース番号及びオフセット番号を組み合わせることにより、ノードにアクセスすることが可能である。
【0097】
したがって、オフセット番号を適宜選択することにより、例えばツリーのうち上位n段を主記憶装置に配置し、n段目より下位のノードを外部記憶装置に配置するようなことが可能である。
【0098】
次に、本発明の第1の実施形態の変形例における検索処理について、図14を参照して説明する。図14は、本発明の第1の実施形態の変形例におけるビット列検索の処理フロー例を説明する図である。図6に示す処理フロー例と比較すると、ノード参照番号、ベース番号及びオフセット番号の取り扱いが加わったことと、これらの番号により配列番号を求めることが異なる。
【0099】
まず、ステップS1401aで、ベース番号を設定し、ステップS1401bで、オフセット番号表を設定する。さらに、ステップS1401cで、段数カウンタに値1を設定し、ステップS1401dで、ノード参照番号に値1を設定する。図14に示す例では、検索開始ノードをルートノードとするものであるが、段数カウンタとノード参照番号に1以外の番号が指定され、検索開始ノードをルートノード以外のものとした場合でも、以下の処理フローは同様である。
【0100】
次にステップS1402aで、オフセット番号表より、段数カウンタの指すオフセット番号を取り出し、ステップS1402bで、リンク先配列番号に、ノード参照番号にベース番号とオフセット番号を加えた値を設定する。
次にステップS1403で、配列からリンク先配列番号に設定された配列番号の配列要素を参照すべきノードとして読み出す。そして、ステップS1404で、読み出したノードから、ノード種別を取り出し、ステップS1405で、ノード種別がブランチノードであるか否かを判定する。
【0101】
ステップS1405の判定において、読み出したノードがブランチノードである場合はステップS1406に進み、ノードから弁別ビット位置についての情報を取り出し、更に、ステップS1407で、取り出した弁別ビット位置に対応するビット値を検索キーから取り出す。そして、ステップS1408で、ノード参照番号に、ノード参照番号を2倍した値にステップS1407で得た値を設定する。さらにステップS1409で、段数カウンタに1を加えて、ステップS1403に戻る。
【0102】
以降、ステップS1405の判定においてリーフノードと判定されてステップS1410に進むまで、ステップS1402aからステップS1409までの処理を繰り返す。 ステップS1410では、リーフノードからインデックスキーを取り出して、処理を終了する。
なお、上述の例では、リーフノードにインデックスキーが直接含まれているものとしたが、リーフノードにインデックスキーにアクセスするための情報が含まれている場合には、ステップS1410においてリーフノードからインデックスキーにアクセスするための情報を取り出し、さらに追加ステップにおいて、取り出されたインデックスキーにアクセスするための情報を用いてインデックスキーを取り出す。
また、インデックスキーを取り出したのち、そのインデックスキーを検索結果キーとして他のアプリケーションで用いることもできるし、検索キーとの一致判定を行い、検索成功あるいは検索失敗とすることもできる。
【0103】
次に、本発明の第2の実施形態の変形例について説明する。ベース番号、オフセット番号及びノード参照番号の技術的意義、及び配列番号との関係は、第1の実施態様の変形例と同じである。
図15は、本発明の第2の実施形態の変形例における配列に格納されたカップルドノードツリーの構成例を説明する図である。図8Aに示す構成例と比較すると、ベース番号700とオフセット番号710が追加されている。また、図8Aの配列番号1〜15に替えて、ノード参照番号720の値1〜15が記載されている。図15においては、配列番号730については、その番号の値として、100、111、122、123、134〜137、148〜155が記載されている。
また、図15には、ベース番号700の値として100が、オフセット番号710の値として10、20、30、40が例示されている。
その他の符号については、図8Aに示された対応する符号にaを付加したものが使用されている。
本変形例において、第1の実施形態の変形例と同様に、ベース番号を0、各段のオフセット番号を0とすると、ノード参照番号は図8A及び図8Bに例示する配列番号と一致し、本変形例のカップルドノードツリーは、図8A及び図8Bに例示する第2の実施形態のカップルドノードツリーと一致する。
【0104】
図15を参照すると、ベース番号が100、オフセット番号が10であって、ノード参照番号は1であるから、ルートノード801aは配列800aの配列番号111の配列要素に配置されている。ルートノード801aは弁別ビット位置803aで構成されている。弁別ビット位置803aには2が格納されている。
【0105】
ノード参照番号が1であるルートノード801aからの点線の矢印810aで示すリンク先ノード対811aの代表ノードであるノード[0]812aは、ツリー上で直近上位に位置する親ノードであるルートノード801aのノード参照番号1の2倍の値を持つノード参照番号2に、ベース番号100とオフセット番号20の和を加えた配列番号122の配列要素に配置されている。そして隣接する次の配列要素(ノード参照番号3、配列番号123)に代表ノードと対になるノード[1]813aが配置されている。
【0106】
ノード[0]812aの弁別ビット位置には0が格納されており、そのリンク先は、点線の矢印840aで示すように、ノード[0]812aのノード参照番号2の2倍の値を持つノード参照番号4に、ベース番号100とオフセット番号30の和を加えた配列番号134の配列要素に格納されたノード842aである。また、ノード842の弁別ビット位置には0が格納されており、そのリンク先は、点線の矢印850aで示すように、ノード842aのノード参照番号4の2倍の値を持つノード参照番号8に、ベース番号100とオフセット番号40の和を加えた配列番号148の配列要素に格納されたノード852aである。
【0107】
ノード852aは、図15に例示するカップルドノードツリーの最下段に位置するので、リーフノードであり、インデックスキー818aには最上位ビットに0が挿入されたインデックスキー“00001”が格納されている。
【0108】
一方、ノード[1]813aの弁別ビット位置には4が格納されている。ノード参照番号が3であるブランチノード813aからの点線の矢印820aで示すリンク先ノード対821aの代表ノードであるノード822aは、親ノードであるノード813aのノード参照番号3の2倍の値を持つノード参照番号6に、ベース番号100とオフセット番号30の和を加えた配列番号136の配列要素に配置されている。そして隣接する次の配列要素(ノード参照番号7、配列番号137)に代表ノードと対になるノード823aが配置されている。ノード822aの弁別ビット位置には5が格納されている。また、ノード823aの弁別ビット位置には6が格納されている。
【0109】
ノード参照番号が6であるブランチノード822aからの点線の矢印830aで示すリンク先ノード対831aの代表ノードであるノード832aは、ノード参照番号6の2倍の値を持つノード参照番号12に、ベース番号100とオフセット番号40の和を加えた配列番号152の配列要素に配置されている。そして隣接する次の配列要素(ノード参照番号13、配列番号153)に代表ノードと対になるノード833aが配置されている。ノード832及びノード833の内容の記載は省略されている。また、ブランチノード823aのリンク先の記載も省略されている。
【0110】
本変形例においても、カップルドノードツリーのツリー構造自体は、図8Bに示すものと同じである。違う点は、図8A及び図8Bに示すものにおいては、ノードのツリー上の位置が配列に結びついた配列番号で規定されるのに対して、第1の実施形態の変形例と同様に、本変形例においても、配列とは独立のノード参照番号で規定される点である。
そして、ノード参照番号とベース番号及びオフセット番号を組み合わせることにより、ノードにアクセスすることが可能である。
【0111】
したがって、オフセット番号を適宜選択することにより、例えばツリーのうち上位n段を主記憶装置に配置し、n段目より下位のノードを外部記憶装置に配置するようなことが可能である。
【0112】
次に、本発明の第2の実施形態の変形例における検索処理について、図16を参照して説明する。図16は、本発明の第2の実施形態の変形例におけるビット列検索の処理フロー例を説明する図である。図10に示す処理フロー例と比較すると、ノード参照番号、ベース番号及びオフセット番号の取り扱いが加わったことと、これらの番号により配列番号を求めることが異なる。
【0113】
まず、ステップS1601aで、ベース番号を設定し、ステップS1601bで、オフセット番号表を設定する。さらに、ステップS1601cで、ノード参照番号に値1を設定する。さらにステップS1601dにおいて、リンク先配列番号に、ノード参照番号にベース番号とオフセット番号を加えた値を設定する。ステップS1601dの処理により、リンク先配列番号には、ルートノードの配列番号が設定される。
【0114】
次にステップS1602において、ルートノードの配列番号(リンク先配列番号)の指す配列に格納された弁別ビット位置と検索キーにより、2段目のノードの配列番号を求める。
続いてステップS1603において、2段目のノードの配列番号の指す配列に格納された弁別ビット位置と検索キーにより、3段目のノードの配列番号を求める。
以下同様に、ステップS1604〜ステップS160nにおいて、3段目〜n−1段目のノードの配列番号の指す配列に格納された弁別ビット位置と検索キーにより、それぞれ4段目〜n段目のノードの配列番号を求める。ステップS1602〜ステップS160nの処理の詳細は、後に図17を参照して説明する。
【0115】
最後に、n段目のノードの配列番号の指す配列に格納されたビット列をインデックスキーとして取り出し、処理を終了する。
なお、図10に例示する処理フロー例と同様に、図16に例示する処理フロー例は、特定の段数nを有する本実施形態のカップルドノードツリーを用いたものであるが、段数nをパラメータとしたアセンブラマクロにより、本実施形態の任意の段数のカップルドノードツリーを用いた検索処理を実現するための処理フローを生成することが可能である。
【0116】
図17は、本発明の第2の実施形態の変形例におけるリンク先の配列番号を求める処理フロー例を説明する図であり、図16に示すステップS1602〜ステップS160nの処理の詳細を示すものである。
【0117】
まず、ステップS1701において、配列から、リンク先配列番号の指す配列要素に格納された内容を弁別ビット位置として読み出し、ステップS1702において、検索キーから、該読み出した弁別ビット位置の指すビット値を取り出す。
【0118】
次にステップS1703aにおいて、オフセット番号表より、次段のオフセット番号を取り出し、ステップS1703bにおいて、ノード参照番号に、ノード参照番号を2倍した値にステップS1702で得た値を加えた値を設定する。さらにステップS1704で、リンク先配列番号に、ノード参照番号にベース番号とオフセット番号を加えた値を設定して処理を終了する。
【0119】
次に、本発明の第1の実施形態及び第2の実施形態のカップルドノードツリーの生成について説明する。なお、以下の説明において、本発明の第1の実施形態及び第2の実施形態のツリーをポインタレスツリーといい、従来のカップルドノードツリーを単にツリー、あるいは変換前のツリーということがある。
本発明のポインタレスツリーの生成は、例えば次のようにして実現することができる。すなわち、ポインタレスツリーを生成する際には、ポインタレスツリーに格納されるインデックスキーにより、図1A及び図1Bに例示する形態のツリーが生成されているものとする。そして、ポインタレスツリーの生成は、ツリーのノードをルートノードから順次巡回し、本発明の第1の実施形態あるいは第2の実施形態のノードに変換することにより、実現される。このノードの巡回は、以下において詳細に説明するが、前記特許文献4として引用した特開2008−269197号公報の図10A〜図12及びそれに関連した明細書の記載に開示されたノードの退避処理で用いられるものと類似するものである。
ツリーの生成は、前記特許文献1として引用した特開2008−15872号公報の図5〜図8及びそれに関連した明細書の記載に開示され、詳細に説明されているので、ここでの説明は省略する。
【0120】
図18Aは、本発明の第1及び第2の実施形態におけるポインタレスツリーを生成する処理の前段の処理フロー例を示す図である。図18Aに示すように、まずステップS1801において、ポインタレスツリーを生成するための配列を取得し、ステップS1802おいて、配列要素を初期化する。このステップS1802の処理は、ダミーのブランチノードを用いる第2の実施形態における処理例において必要となるものであり、第1の実施形態では省略可能である。
次にステップS1802aにおいて変換前のツリーの最大段数を求め、ステップS1802bにおいて該最大段数を段数カウンタの上限値に設定する。段数カウンタの上限値は、第2の実施形態においてリーフノードをポインタレスツリーの最下段に配置するために用いられるものである。したがって、ステップS1802の処理と同様に、第1の実施形態では省略可能である。
ステップS1802aの処理の詳細については、後に図21及び図22を参照して説明する。
【0121】
次にステップS1803において、ベース番号を設定し、ステップS1804において、オフセット番号表を設定する。
さらに、ステップS1805において、段数カウンタに1を設定し、ステップS1806において、ノード参照番号に1を設定し、ステップS1807において、巡回開始ノードの配列番号に、ツリーのルートノードの配列番号を設定して図18Bに示すステップS1812に進む。
【0122】
なお、上述の図18A及び以下の図面に例示するフローは、図13あるいは図15に示す変形例に対応するものである。しかし、変形例においてベース番号を0、各段におけるオフセット番号を0、ノード参照番号を配列番号とすれば、図4Aあるいは図8Aに示す形態のツリーの生成処理を示すものである。したがって、図18A及び以下の図面に例示するフローは、変形例を含む第1の実施形態及び第2の実施形態のポインタレスツリーの生成処理を説明するものである。
【0123】
図18Bは、本発明の第1及び第2の実施形態におけるポインタレスツリーを生成する処理の後段の処理フロー例を示す図である。図18Bに示すように、ステップS1812において、巡回開始ノードよりツリーを巡回し、巡回先のノードを変換してポインタレスツリーに格納する。ステップS1812の処理の詳細は、後に図19を参照して説明する。
【0124】
次にステップS1813において、探索経路スタックのスタックポインタはツリーのルートノードの配列番号を指しているか判定する。配列番号の探索経路スタックへの格納は、ステップS1812の処理で行われる。
探索経路スタックのスタックポインタはツリーのルートノードの配列番号を指していれば、ツリーの全てのノードの処理は完了しているので処理を終了する。そうでなければ、ステップS1814に進む。
【0125】
ステップS1814では、探索経路スタックから配列番号を取り出し、探索経路スタックのスタックポインタを1つ減らす。次にステップS1815において、ステップS1814で取り出した配列番号からノード位置を求め、そのノード位置がノード[0]であるかを、ステップS1816において判定する。ノード位置がノード[0]でなければ、ステップS1817で段数カウンタから値1を減じてステップS1813に戻る。ノード位置がノード[0]であれば、ステップS1818に進む。
【0126】
ステップS1818では、ステップS1814で取り出した配列番号に値1を加えて、ノード[1]の配列番号を得る。そして、ステップS1819で巡回開始ノードの配列番号に、ステップS1818で得たノード[1]の配列番号を設定し、ステップS1820で、ノード参照番号に1を加えてステップS1812に戻る。
上述のステップS1812〜ステップS1820のループ処理を、ステップS1813において探索経路スタックのスタックポインタがツリーのルートノードの配列番号を指していると判定されるまで繰り返すことにより、ツリー上のすべてのノードの巡回が行われ、各ノードがポインタレスツリーのノードに変換されてポインタレスツリーが生成される。
【0127】
図19は、巡回開始ノードよりツリーを巡回し、ノードをポインタレスツリーに格納する処理フロー例を説明する図であり、図18BのステップS1812の処理の詳細を説明する図である。
図に示すように、まずステップS1901において、巡回開始ノードの配列番号を配列番号に設定する。巡回開始ノードの配列番号は、図18Bに示すステップS1812〜ステップS1820のループ処理の初回の処理においては、図18AのステップS1807で設定されており、それ以降の処理においては、図18Bに示すステップS1819で設定される。
【0128】
次にステップS1902において、探索経路スタックに配列番号を格納する。この配列番号は、ステップS1901あるいは後記ステップS1910で設定されているものである。
【0129】
次にステップS1903において、変換前のツリーが格納された配列から、配列番号の指す配列要素をノードとして読み出し、ステップS1904において、ノード参照番号をもとに、図18AのステップS1801で取得した配列の配列要素にノードを書き込むことでポインタレスツリーのノードを生成する。ステップS1904の処理の詳細は、後に図20A及び図20Bを参照して説明する。図20Aは第1の実施形態のためのもの、図20Bは第2の実施形態のためのものである。
【0130】
次にステップS1905において、ステップS1903で読み出したノードからノード種別を取り出し、ステップS1906で、該取り出したノード種別はブランチノードを示すものか判定する。ステップS1906の判定が、ノード種別はブランチノードを示すものではなくリーフノードを示すものであれば処理を終了し、ブランチノードを示すものであれば、ステップS1907に進む。
【0131】
ステップS1907では、段数カウンタに値1を加え、ステップS1908に進み、ノード参照番号を2倍にする。さらにステップS1909において、ステップS1903で読み出したノードから、代表番号を取り出し、ステップS1910で、該取り出した代表ノード番号に値0を加えた値を配列番号に設定し、ステップS1902に戻る。
【0132】
上述のステップS1902〜ステップS1910のループ処理を、ステップS1906においてノード種別がリーフノードを示すまで繰り返す。つまり、ひとまとまりの処理として、巡回開始ノードから最初のリーフノードまでノードを巡回してノードを読み出し、それを変換してポインタレスツリーのノードを書き込む。図19に示す処理フロー例では、ステップS1910において、代表ノード番号に値0を加えて配列番号に設定していることから、ノード[0]側を優先してノードを巡回しているが、ノード[1]側を優先してノードを巡回することも可能であることは、以上の説明から当業者に明らかである。
【0133】
図20Aは、本発明の第1の実施形態におけるノードを生成する処理の処理フロー例を説明する図であり、図19に示すステップS1904の第1の実施形態における処理の詳細を説明する図である。
【0134】
図に示すように、まずステップS2001において、オフセット番号表より、段数カウンタの指すオフセット番号を取り出し、ステップS2002において、配列番号に、ノード参照番号にベース番号とオフセット番号を加えた値を設定する。ここでの配列番号は、ポインタレスツリーを格納する配列の配列要素の配列番号を設定する一時記憶領域であり、図19AのステップS1901やステップS1910で設定される変換前のツリーを格納する配列の配列要素の配列番号を設定する一時記憶領域とは異なる。
【0135】
次にステップS2003において、図19のステップS1903で読み出しているノードから、ノード種別を取り出し、ステップS2004において、該取り出したノード種別はブランチノードのものか判定する。判定結果が肯定的なものであれば、ステップS2005に進み、否定的なものであれば、ステップS2007に進む。
【0136】
ステップS2005では、ノードから弁別ビット位置を取り出し、ステップS2006において、ステップS2002で設定した配列番号の指す配列要素にノード種別と弁別ビット位置を書き込み、ブランチノードを生成して処理を終了する。
ステップS2007では、ノードからインデックスキーを取り出し、ステップS2008において、ステップS2002で設定した配列番号の指す配列要素にノード種別とインデックスキーを書き込み、ブランチノードを生成して処理を終了する。
【0137】
図20Bは、本発明の第2の実施形態におけるノードを生成する処理の処理フロー例を説明する図であり、図19に示すステップS1904の第2の実施形態における処理の詳細を説明する図である。
【0138】
図に示すように、まずステップS2021において、オフセット番号表より、段数カウンタの指すオフセット番号を取り出し、ステップS2023において、図19のステップS1903で読み出しているノードから、ノード種別を取り出し、ステップS2024に進む。
【0139】
ステップS2024では、ステップS2023で取り出したノード種別はブランチノードのものか判定する。判定結果が肯定的なものであれば、ステップS2025に進み、否定的なものであれば、ステップS2029に進む。
【0140】
ステップS2025では、配列番号に、ノード参照番号にベース番号とオフセット番号を加えた値を設定する。そしてステップS2026で、ノードから弁別ビット位置を取り出し、ステップS2027で、該弁別ビット位置に値1を加え、ステップS2028において、ステップS2025で設定した配列番号の指す配列要素に弁別ビット位置を書き込み、ブランチノードを生成して処理を終了する。
【0141】
一方、ステップS2024の判定が否定的なものであって、ステップS2023で取り出したノード種別がリーフノードのものであるときは、ステップS2029に進み、ノード参照番号と段数カウンタを退避し、ステップS2030に進む。
【0142】
ステップS2030では、段数カウンタは上限値か判定し、上限値でなければ、ステップS2031でノード参照番号を2倍し、ステップS2032で段数カウンタに値1を加え、ステップS2033で、オフセット番号表より、段数カウンタの指すオフセット番号を取り出してステップS2030に戻る。
【0143】
上述のステップS2030〜S2033のループ処理は、第2の実施形態におけるリーフノードをポインタレスツリーの最下段のレベルに配置するためのものである。図1B、図8Bの例示では、例えば図1Bの変換前のツリーでは3段目にあるリーフノード210cは、図8Bでは5段目のノード210jに変換されている。そして、図8Bにおけるノード210cの位置情報は、図20BのステップS2029の処理により、退避される。
【0144】
なお、段数カウンタの上限値については、図18Aに示すステップS1802bで設定されているが、それに替えて、変換前のツリーを生成するときに、リーフノードを挿入するごとにそのリーフノードの段数をカウントし、その最大値をツリーの属性として記憶しておき、第2の実施形態のポインタレスツリーを生成するときに、その最大値を段数カウンタの上限値とすることができる。
【0145】
上述のステップS2030で、段数カウンタは上限値であると判定されると、ステップS2034に進み、配列番号に、ノード参照番号にベース番号とオフセット番号を加えた値を設定する。そしてステップS2035で、ノードからインデックスキーを取り出し、ステップS2036で、該インデックスキーの最上位のビット位置にビット値“0”を挿入し、ステップS2037において、ステップS2034で設定した配列番号の指す配列要素にインデックスキーを書き込み、リーフノードを生成してステップS2038に進む。
ステップS2038では、ノード参照番号と段数カウンタに、ステップS2029で退避したノード参照番号と段数カウンタをそれぞれ設定して処理を終了する。
【0146】
次に、変換前のツリーの最大段数を求める処理について説明する。
図21は、変換前のツリーの最大段数を求める処理フロー例を説明する図であり、図18AのステップS1802aの処理の詳細を説明するものである。
【0147】
図21に示すように、まずステップS2101において、段数カウンタに値1を設定し、ステップS2102において、最大段数カウンタに、段数カウンタに設定された値を設定する。すなわち、段数カウンタ及び最大段数カウンタには、初期値として値1が設定される。
【0148】
次にステップS2112において、巡回開始ノードよりツリーを巡回し、巡回先のノードの段数をカウントして巡回済みノードの最大段数を求める。ステップS2112の処理の詳細は、後に図22を参照して説明する。
【0149】
次にステップS2113において、探索経路スタックのスタックポインタはツリーのルートノードの配列番号を指しているか判定する。配列番号の探索経路スタックへの格納は、ステップS2112の処理で行われる。
探索経路スタックのスタックポインタはツリーのルートノードの配列番号を指していれば、ツリーの全てのノードの巡回は完了しているので処理を終了する。そうでなければ、ステップS2114に進む。
【0150】
ステップS2114では、探索経路スタックから配列番号を取り出し、探索経路スタックのスタックポインタを1つ減らす。次にステップS2115において、ステップS2114で取り出した配列番号からノード位置を求め、そのノード位置がノード[0]であるかを、ステップS2116において判定する。ノード位置がノード[0]でなければ、ステップS2117で段数カウンタから値1を減じてステップS2113に戻る。ノード位置がノード[0]であれば、ステップS2118に進む。
【0151】
ステップS2118では、ステップS2114で取り出した配列番号に値1を加えて、ノード[1]の配列番号を得る。そして、ステップS2119で巡回開始ノードの配列番号に、ステップS2118で得たノード[1]の配列番号を設定してステップS2112に戻る。
上述のステップS2112〜ステップS2119のループ処理を、ステップS2113において探索経路スタックのスタックポインタがツリーのルートノードの配列番号を指していると判定されるまで繰り返すことにより、ツリー上のすべてのノードの巡回が行われ、巡回済みノードの最大段数、すなわち、変換前ツリーの最大段数が求められる。
【0152】
図22は、巡回開始ノードよりツリーを巡回し、ノードの段数をカウントして巡回済みノードの最大段数を求める処理フロー例を示す図であり、図21のステップS2112の処理の詳細を説明する図である。
図に示すように、まずステップS2201において、巡回開始ノードの配列番号を配列番号に設定する。巡回開始ノードの配列番号は、図21に示すステップS2112〜ステップS2119のループ処理の初回の処理においては、図21のステップS2107で設定されており、それ以降の処理においては、図21に示すステップS2119で設定される。
【0153】
次にステップS2202において、探索経路スタックに配列番号を格納する。この配列番号は、ステップS2201あるいは後記ステップS2210で設定されているものである。
【0154】
次にステップS2203において、変換前のツリーが格納された配列から、配列番号の指す配列要素をノードとして読み出し、次にステップS2205において、該読み出したノードからノード種別を取り出す。
【0155】
次にステップS2206で、該取り出したノード種別はブランチノードを示すものか判定する。ステップS2206において、ノード種別はブランチノードを示すものであると判定されれば、ステップS2207に進み、ノード種別はブランチノードを示すものではなくリーフノードを示すものとであると判定されると、ステップS2210に進む。
【0156】
ステップS2207では、段数カウンタに値1を加え、ステップS2209において、ステップS2203で読み出したノードから、代表番号を取り出し、ステップS2210で、該取り出した代表ノード番号に値0を加えた値を配列番号に設定し、ステップS2202に戻る。
【0157】
上述のステップS2202〜ステップS2210のループ処理を、ステップS2206においてノード種別がリーフノードを示すまで繰り返す。なお、図22に示す処理フロー例では、ステップS2210において、代表ノード番号に値0を加えて配列番号に設定していることから、ノード[0]側を優先してノードを巡回しているが、先に説明した図19の処理と同様に、ノード[1]側を優先してノードを巡回することも可能であることは、当業者に明らかである。
【0158】
上述のステップS2206において、ノード種別がリーフノードを示すものと判定されると、ステップS2210に進み、段数カウンタの値は最大段数カウンタに設定された値より大きいか判定し、大きくなければそのまま処理を終了し、大きければ、ステップS2211で、最大段数カウンタに段数カウンタの値を設定して処理を終了する。
【0159】
以上本発明を実施するための形態について詳細に説明したが、本発明の実施の形態はそれに限ることなく種々の変形が可能であることは当業者に明らかである。
また、本発明の第1の実施形態及び第2の実施形態に係るビット列検索装置が、図6、図10及び図11、あるいは図14、図16及び図17に例示した処理をコンピュータに実行させるプログラムによりコンピュータ上に構築可能なことは明らかである。
したがって、上記プログラム、及びプログラムを記憶したコンピュータ読み取り可能な記憶媒体は、本発明の実施の形態に含まれる。さらに、本発明のカップルドノードツリーのデータ構造も、本発明の実施の形態に含まれる。
【符号の説明】
【0160】
100、400、800 配列
101 ノード
102、402 ノード種別
103、403、803 弁別ビット位置
104 代表ノード番号
118、418、818 インデックスキー
200、200a、200b カップルドノードツリー
210a、401、801 ルートノード
270、280 検索キー
301 データ処理装置
302 中央処理装置
303 キャッシュメモリ
304 バス
305 主記憶装置
306 外部記憶装置
307 通信装置
308 データ格納装置
309 配列
310 探索経路スタック
500、900 ビット列検索装置
510、910 検索ツリー記憶手段
520、920 検索開始位置設定手段
530 ノード読出手段
540 ノード種別判定手段
550、950 検索キー設定手段
560 ノードリンク手段
570、970 検索結果出力手段
9301、・・・、930n ノード読出手段
9601、・・・、960n−1 ノードリンク手段
600、700 ベース番号
610、710 オフセット番号
620、720 ノード参照番号
630、730 配列番号

【特許請求の範囲】
【請求項1】
ビット列からなる検索キーにより、検索対象であるビット列からなるインデックスキーあるいは該インデックスキーにアクセスするための情報が格納されたツリーのデータ構造に基づいて、前記インデックスキーを検索するビット列検索装置において、
前記ツリーは配列に記憶されたものであり、該ツリーの始点であって、前記配列の配列番号1の配列要素に配置されるルートノードと、前記配列の隣接した配列要素に配置される代表ノードと非代表ノードである2つのノードを有する、ツリーの構成要素としてのノード対を有し、前記ノードは該ノードがブランチノードであるかリーフノードであるかを示すノード種別を格納する領域を有し、前記ブランチノードは、前記ノード種別に加えて、前記検索キーの弁別ビット位置を格納する領域を含むが、リンク先である直近下位のノード対の代表ノードの配置された配列要素の配列番号を格納する領域及び前記検索対象のビット列からなるインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含まないものであり、前記リーフノードは、前記ノード種別に加えて、前記検索対象のビット列からなるインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含むが、前記検索キーの弁別ビット位置を格納する領域を含まないものであって、前記代表ノードは該代表ノードの直近上位のブランチノードの配置された配列要素の配列番号の2倍の値の配列番号の配列要素に配置される、カップルドノードツリーと、
検索を開始するノードの配置された配列要素の配列番号を取得し、該取得した配列番号をリンク先ノードの配列番号として設定する検索開始位置設定手段と、
前記検索開始位置設定手段あるいは後記リンク手段によりリンク先ノードの配列番号として設定された配列番号の配列要素から該配列要素に配置されたノードを読み出すノード読出手段と、
前記ノード読出手段により読み出されたノードのノード種別を格納する領域から当該ノード種別を読み出し、該ノード種別が前記リーフノードを示すものであるかブランチノードを示すものであるかを判定するノード種別判定手段と、
前記リーフノードのインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域から直接当該インデックスキーを読み出す、あるいは該インデックスキーにアクセスするための情報に基づき当該インデックスキーを読み出すインデックスキー読出手段と、
前記ノード種別判定手段で判定されたノード種別がブランチノードを示すものであるとき、該ブランチノードの弁別ビット位置を格納する領域から当該弁別ビット位置を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記ブランチノードの配置された配列要素の配列番号の2倍の値との和を前記リンク先ノードの配列番号として設定するリンク手段と、
を備え、
前記ノード読出手段で読み出したノードのノード種別を前記ノード種別判定手段で判定し、該ノード種別がリーフノードを示すものであれば、前記インデックスキー読出手段によりインデックスキーを読み出し、該ノード種別がブランチノードを示すものであれば、前記リンク手段により前記リンク先ノードの配列番号を設定し、該設定されたリンク先ノードの配列番号の配列要素に配置されたノードを前記ノード読出手段で読み出し、該読み出したノードのノード種別を前記ノード種別判定手段で判定することを該ノード種別がリーフノードを示すものとなるまで繰り返し、該ノード種別がリーフノードを示すときに前記インデックスキー読出手段によりインデックスキーを読み出すことを特徴とするビット列検索装置。
【請求項2】
請求項1記載のビット列検索装置が実行するビット列検索方法において、
検索を開始するノードの配置された配列要素の配列番号を取得し、該取得した配列番号をリンク先ノードの配列番号として設定する検索開始位置設定ステップと、
前記検索開始位置設定ステップあるいは後記リンクステップにおいてリンク先ノードの配列番号として設定された配列番号の配列要素から該配列要素に配置されたノードを読み出すノード読出ステップと、
前記ノード読出ステップで読み出されたノードのノード種別を格納する領域から当該ノード種別を読み出し、該ノード種別が前記リーフノードを示すものであるかブランチノードを示すものであるかを判定するノード種別判定ステップと、
前記リーフノードのインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域から直接当該インデックスキーを読み出す、あるいは該インデックスキーにアクセスするための情報に基づき当該インデックスキーを読み出すインデックスキー読出ステップと、
前記ノード種別判定ステップで判定されたノード種別がブランチノードを示すものであるとき、該ブランチノードの弁別ビット位置を格納する領域から当該弁別ビット位置を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記ブランチノードの配置された配列要素の配列番号の2倍の値との和を前記リンク先ノードの配列番号として設定するリンクステップと、
を備え、
前記ノード読出ステップで読み出したノードのノード種別を前記ノード種別判定ステップで判定し、該ノード種別がリーフノードを示すものであれば、前記インデックスキー読出ステップにおいてインデックスキーを読み出し、該ノード種別がブランチノードを示すものであれば、前記リンクステップにおいて前記リンク先ノードの配列番号を設定し、該設定されたリンク先ノードの配列番号の配列要素に配置されたノードを前記ノード読出ステップで読み出し、該読み出したノードのノード種別を前記ノード種別判定ステップで判定することを該ノード種別がリーフノードを示すものとなるまで繰り返し、該ノード種別がリーフノードを示すときに前記インデックスキー読出ステップにおいてインデックスキーを読み出すことを特徴とするビット列検索方法。
【請求項3】
請求項2記載のビット列検索方法をコンピュータに実行させることを特徴とするプログラム。
【請求項4】
請求項2記載のビット列検索方法をコンピュータに実行させるプログラムを記憶したことを特徴とするコンピュータ読み取り可能な記憶媒体。
【請求項5】
ビット列からなる検索キーによるビット列検索に用いられる、検索対象であるビット列からなるインデックスキーあるいは該インデックスキーにアクセスするための情報が格納されたツリーのデータ構造において、
前記ツリーは配列に記憶されたものであり、該ツリーの始点であって、前記配列の配列番号1の配列要素に配置されるルートノードと、前記配列の隣接した配列要素に配置される代表ノードと非代表ノードである2つのノードを有する、ツリーの構成要素としてのノード対を有し、前記ノードは該ノードがブランチノードであるかリーフノードであるかを示すノード種別を格納する領域を有し、前記ブランチノードは、前記ノード種別に加えて、前記検索キーの弁別ビット位置を格納する領域を含むが、リンク先である直近下位のノード対の代表ノードの配置された配列要素の配列番号を格納する領域及び前記検索対象のビット列からなるインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含まないものであり、前記リーフノードは、前記ノード種別に加えて、前記検索対象のビット列からなるインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含むが、前記検索キーの弁別ビット位置を格納する領域を含まないものであって、前記代表ノードは該代表ノードの直近上位のブランチノードの配置された配列要素の配列番号の2倍の値の配列番号の配列要素に配置されるものであり、
前記ツリーの記憶手段を備えたビット列検索装置により、
検索を開始するノードの配置された配列要素の配列番号を取得し、該取得した配列番号をリンク先ノードの配列番号として設定する検索開始位置設定ステップと、
前記検索開始位置設定ステップあるいは後記リンクステップにおいてリンク先ノードの配列番号として設定された配列番号の配列要素から該配列要素に配置されたノードを読み出すノード読出ステップと、
前記ノード読出ステップで読み出されたノードのノード種別を格納する領域から当該ノード種別を読み出し、該ノード種別が前記リーフノードを示すものであるかブランチノードを示すものであるかを判定するノード種別判定ステップと、
前記リーフノードのインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域から直接当該インデックスキーを読み出す、あるいは該インデックスキーにアクセスするための情報に基づき当該インデックスキーを読み出すインデックスキー読出ステップと、
前記ノード種別判定ステップで判定されたノード種別がブランチノードを示すものであるとき、該ブランチノードの弁別ビット位置を格納する領域から当該弁別ビット位置を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記ブランチノードの配置された配列要素の配列番号の2倍の値との和を前記リンク先ノードの配列番号として設定するリンクステップと、
を備え、
前記ノード読出ステップで読み出したノードのノード種別を前記ノード種別判定ステップで判定し、該ノード種別がリーフノードを示すものであれば、前記インデックスキー読出ステップにおいてインデックスキーを読み出し、該ノード種別がブランチノードを示すものであれば、前記リンクステップにおいて前記リンク先ノードの配列番号を設定し、該設定されたリンク先ノードの配列番号の配列要素に配置されたノードを前記ノード読出ステップで読み出し、該読み出したノードのノード種別を前記ノード種別判定ステップで判定することを該ノード種別がリーフノードを示すものとなるまで繰り返し、該ノード種別がリーフノードを示すときに前記インデックスキー読出ステップにおいてインデックスキーを読み出す検索方法の実行を可能とすることを特徴とするデータ構造。
【請求項6】
請求項5記載のデータ構造を記憶したことを特徴とするコンピュータ読み取り可能な記憶媒体。
【請求項7】
ビット列からなる検索キーにより、検索対象であるビット列からなるインデックスキーあるいは該インデックスキーにアクセスするための情報が格納されたツリーのデータ構造に基づいて、前記インデックスキーを検索するビット列検索装置において、
前記ツリーは配列に記憶されたものであり、該ツリーの始点であるルートノードであって、ノード参照番号1に、該ルートノードの位置を定める配列番号であるベース番号と前記ツリーの各段のノードの開始位置を定める番号であるオフセット番号を加えた値の配列番号の配列要素に配置されるルートノードと、前記配列の隣接した配列要素に配置される代表ノードと非代表ノードである2つのノードを有する、ツリーの構成要素としてのノード対を有し、前記ノードは該ノードがブランチノードであるかリーフノードであるかを示すノード種別を格納する領域を有し、前記ブランチノードは、前記ノード種別に加えて、前記検索キーの弁別ビット位置を格納する領域を含むが、リンク先である直近下位のノード対の代表ノードの配置された配列要素の配列番号を格納する領域及び前記検索対象のビット列からなるインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含まないものであり、前記リーフノードは、前記ノード種別に加えて、前記検索対象のビット列からなるインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含むが、前記検索キーの弁別ビット位置を格納する領域を含まないものであって、前記代表ノードは該代表ノードの直近上位のブランチノードのノード参照番号の2倍の値のノード参照番号に、前記ベース番号と該直近上位のブランチノードの次の段のオフセット番号を加えた値の配列番号の配列要素に配置される、カップルドノードツリーと、
検索を開始するノードのノード参照番号と該ノードについての前記オフセット番号と前記ベース番号に基づいて該ノードの配置された配列要素の配列番号を取得し、該取得した配列番号をリンク先ノードの配列番号として設定する検索開始位置設定手段と、
前記検索開始位置設定手段あるいは後記リンク手段によりリンク先ノードの配列番号として設定された配列番号の配列要素から該配列要素に配置されたノードを読み出すノード読出手段と、
前記ノード読出手段により読み出されたノードのノード種別を格納する領域から当該ノード種別を読み出し、該ノード種別が前記リーフノードを示すものであるかブランチノードを示すものであるかを判定するノード種別判定手段と、
前記リーフノードのインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域から直接当該インデックスキーを読み出す、あるいは該インデックスキーにアクセスするための情報に基づき当該インデックスキーを読み出すインデックスキー読出手段と、
前記ノード種別判定手段で判定されたノード種別がブランチノードを示すものであるとき、該ブランチノードの弁別ビット位置を格納する領域から当該弁別ビット位置を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記ブランチノードのノード参照番号の2倍の値との和を前記リンク先ノードのノード参照番号とし、該ノード参照番号と前記ベース番号と前記ブランチノードの次の段のオフセット番号の和をリンク先ノードの配列番号として設定するリンク手段と、
を備え、
前記ノード読出手段で読み出したノードのノード種別を前記ノード種別判定手段で判定し、該ノード種別がリーフノードを示すものであれば、前記インデックスキー読出手段によりインデックスキーを読み出し、該ノード種別がブランチノードを示すものであれば、前記リンク手段により前記リンク先ノードの配列番号を設定し、該設定されたリンク先ノードの配列番号の配列要素に配置されたノードを前記ノード読出手段で読み出し、該読み出したノードのノード種別を前記ノード種別判定手段で判定することを該ノード種別がリーフノードを示すものとなるまで繰り返し、該ノード種別がリーフノードを示すときに前記インデックスキー読出手段によりインデックスキーを読み出すことを特徴とするビット列検索装置。
【請求項8】
請求項1記載のビット列検索装置が実行するビット列検索方法において、
検索を開始するノードのノード参照番号と該ノードについての前記オフセット番号と前記ベース番号に基づいて該ノードの配置された配列要素の配列番号を取得し、該取得した配列番号をリンク先ノードの配列番号として設定する検索開始位置設定ステップと、
前記検索開始位置設定ステップあるいは後記リンクステップにおいてリンク先ノードの配列番号として設定された配列番号の配列要素から該配列要素に配置されたノードを読み出すノード読出ステップと、
前記ノード読出ステップで読み出されたノードのノード種別を格納する領域から当該ノード種別を読み出し、該ノード種別が前記リーフノードを示すものであるかブランチノードを示すものであるかを判定するノード種別判定ステップと、
前記リーフノードのインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域から直接当該インデックスキーを読み出す、あるいは該インデックスキーにアクセスするための情報に基づき当該インデックスキーを読み出すインデックスキー読出ステップと、
前記ノード種別判定ステップで判定されたノード種別がブランチノードを示すものであるとき、該ブランチノードの弁別ビット位置を格納する領域から当該弁別ビット位置を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記ブランチノードのノード参照番号の2倍の値との和を前記リンク先ノードのノード参照番号とし、該ノード参照番号と前記ベース番号と前記ブランチノードの次の段のオフセット番号の和をリンク先ノードの配列番号として設定するリンクステップと、
を備え、
前記ノード読出ステップで読み出したノードのノード種別を前記ノード種別判定ステップで判定し、該ノード種別がリーフノードを示すものであれば、前記インデックスキー読出ステップにおいてインデックスキーを読み出し、該ノード種別がブランチノードを示すものであれば、前記リンクステップにおいて前記リンク先ノードの配列番号を設定し、該設定されたリンク先ノードの配列番号の配列要素に配置されたノードを前記ノード読出ステップで読み出し、該読み出したノードのノード種別を前記ノード種別判定ステップで判定することを該ノード種別がリーフノードを示すものとなるまで繰り返し、該ノード種別がリーフノードを示すときに前記インデックスキー読出ステップにおいてインデックスキーを読み出すことを特徴とするビット列検索方法。
【請求項9】
請求項8記載のビット列検索方法をコンピュータに実行させることを特徴とするプログラム。
【請求項10】
請求項8記載のビット列検索方法をコンピュータに実行させることを特徴とするプログラムを記憶したことを特徴とするコンピュータ読み取り可能な記憶媒体。
【請求項11】
ビット列からなる検索キーによるビット列検索に用いられる、検索対象であるビット列からなるインデックスキーあるいは該インデックスキーにアクセスするための情報が格納されたツリーのデータ構造において、
前記ツリーは配列に記憶されたものであり、該ツリーの始点であるルートノードであって、ノード参照番号1に、該ルートノードの位置を定める配列番号であるベース番号と前記ツリーの各段のノードの開始位置を定める番号であるオフセット番号を加えた値の配列番号の配列要素に配置されるルートノードと、前記配列の隣接した配列要素に配置される代表ノードと非代表ノードである2つのノードを有する、ツリーの構成要素としてのノード対を有し、前記ノードは該ノードがブランチノードであるかリーフノードであるかを示すノード種別を格納する領域を有し、前記ブランチノードは、前記ノード種別に加えて、前記検索キーの弁別ビット位置を格納する領域を含むが、リンク先である直近下位のノード対の代表ノードの配置された配列要素の配列番号を格納する領域及び前記検索対象のビット列からなるインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含まないものであり、前記リーフノードは、前記ノード種別に加えて、前記検索対象のビット列からなるインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含むが、前記検索キーの弁別ビット位置を格納する領域を含まないものであって、前記代表ノードは該代表ノードの直近上位のブランチノードのノード参照番号の2倍の値のノード参照番号に、前記ベース番号と該直近上位のブランチノードの次の段のオフセット番号を加えた値の配列番号の配列要素に配置されるものであり、
前記ツリーの記憶手段を備えたビット列検索装置により、
検索を開始するノードのノード参照番号と該ノードについての前記オフセット番号と前記ベース番号に基づいて該ノードの配置された配列要素の配列番号を取得し、該取得した配列番号をリンク先ノードの配列番号として設定する検索開始位置設定ステップと、
前記検索開始位置設定ステップあるいは後記リンクステップにおいてリンク先ノードの配列番号として設定された配列番号の配列要素から該配列要素に配置されたノードを読み出すノード読出ステップと、
前記ノード読出ステップで読み出されたノードのノード種別を格納する領域から当該ノード種別を読み出し、該ノード種別が前記リーフノードを示すものであるかブランチノードを示すものであるかを判定するノード種別判定ステップと、
前記リーフノードのインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域から直接当該インデックスキーを読み出す、あるいは該インデックスキーにアクセスするための情報に基づき当該インデックスキーを読み出すインデックスキー読出ステップと、
前記ノード種別判定ステップで判定されたノード種別がブランチノードを示すものであるとき、該ブランチノードの弁別ビット位置を格納する領域から当該弁別ビット位置を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記ブランチノードのノード参照番号の2倍の値との和を前記リンク先ノードのノード参照番号とし、該ノード参照番号と前記ベース番号と前記ブランチノードの次の段のオフセット番号の和をリンク先ノードの配列番号として設定するリンクステップと、
を備え、
前記ノード読出ステップで読み出したノードのノード種別を前記ノード種別判定ステップで判定し、該ノード種別がリーフノードを示すものであれば、前記インデックスキー読出ステップにおいてインデックスキーを読み出し、該ノード種別がブランチノードを示すものであれば、前記リンクステップにおいて前記リンク先ノードの配列番号を設定し、該設定されたリンク先ノードの配列番号の配列要素に配置されたノードを前記ノード読出ステップで読み出し、該読み出したノードのノード種別を前記ノード種別判定ステップで判定することを該ノード種別がリーフノードを示すものとなるまで繰り返し、該ノード種別がリーフノードを示すときに前記インデックスキー読出ステップにおいてインデックスキーを読み出す検索方法の実行を可能とすることを特徴とするデータ構造。
【請求項12】
請求項11記載のデータ構造を記憶したことを特徴とするコンピュータ読み取り可能な記憶媒体。
【請求項13】
ビット列からなる検索キーにより、検索対象であるビット列からなるインデックスキーあるいは該インデックスキーにアクセスするための情報が格納されたツリーのデータ構造に基づいて、前記インデックスキーを検索するビット列検索装置において、
前記インデックスキーは、本来のインデックスキーのある特定のビット位置に特定のビット値を挿入したものであり、
前記検索キーは、本来の検索キーの、前記本来のインデックスキーと同一の特定のビット位置に前記特定のビット値を挿入したものであり、
前記ツリーは配列に記憶され、n段目(nは正整数)までのツリーの構成要素を有するものであり、該ツリーの始点であって、前記配列の配列番号1の配列要素に配置されるルートノードと、前記配列の隣接した配列要素に配置される代表ノードと非代表ノードである2つのノードを有する、ツリーの構成要素としてのノード対を有し、前記ブランチノードは、前記検索キーの弁別ビット位置を格納する領域を含むが、ブランチノードとリーフノードを識別するノード種別を格納する領域、リンク先である直近下位のノード対の代表ノードの配置された配列要素の配列番号を格納する領域、及び前記インデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含まないものであり、前記リーフノードは、前記インデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含むが、前記ノード種別を格納する領域、及び前記検索キーの弁別ビット位置を格納する領域を含まないものであって、前記代表ノードは該代表ノードの直近上位のブランチノードの配置された配列要素の配列番号の2倍の値の配列番号の配列要素に配置され、前記リーフノードはn段目にのみ位置する、カップルドノードツリーと、
検索を開始するルートノードの配置された配列要素の配列番号1をリンク先ノードの配列番号として設定する検索開始位置設定手段と、
第1〜第nのノード読出手段と、
第1〜第n−1のリンク手段と、
インデックスキー読出手段と、
を備え、
前記第1のノード読出手段は、前記検索開始位置設定手段によりリンク先ノードの配列番号として設定された配列番号1の配列要素から該配列要素に配置されたルートノードを読み出し、
前記第1のリンク手段は、前記第1のノード読出手段により読み出されたルートノードの弁別ビット位置を格納する領域から当該弁別ビット位置を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記ルートノードの配置された配列要素の配列番号の2倍の値との和を前記リンク先ノードの配列番号として設定し、
前記第2〜第n−1のノード読出手段は、それぞれ前記第1〜第n−2のリンク手段が設定したリンク先ノードの配列番号が指す配列要素をブランチノードとして読み出し、
前記第2〜第n−1のリンク手段は、それぞれ前記第2〜第n−1のノード読出手段により読み出されたブランチノードの弁別ビット位置を格納する領域から当該弁別ビット位置を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記ブランチノードの配置された配列要素の配列番号の2倍の値との和を前記リンク先ノードの配列番号として設定するものであり、
前記第nのノード読出手段は、前記第n−1リンク手段が設定したリンク先ノードの配列番号が指す配列要素をリーフノードとして読み出し、
インデックスキー読出手段は、前記第nのノード読出手段が読みだした前記リーフノードのインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域から直接当該インデックスキーを読み出す、あるいは該インデックスキーにアクセスするための情報に基づき当該インデックスキーを読み出す、
ことを特徴とするビット列検索装置。
【請求項14】
請求項13記載のビット列検索装置が実行するビット列検索方法において、
検索を開始するルートノードの配置された配列要素の配列番号1をリンク先ノードの配列番号として設定する検索開始位置設定ステップと、
第1〜第nのノード読出ステップと、
第1〜第n−1のリンクステップと、
インデックスキー読出ステップと、
を備え、
前記第1のノード読出ステップにおいて、前記検索開始位置設定ステップでリンク先ノードの配列番号として設定された配列番号1の配列要素から該配列要素に配置されたルートノードを読み出し、
前記第1のリンクステップにおいて、前記第1のノード読出ステップで読み出されたルートノードの弁別ビット位置を格納する領域から当該弁別ビット位置を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記ルートノードの配置された配列要素の配列番号の2倍の値との和を前記リンク先ノードの配列番号として設定し、
前記第2〜第n−1のノード読出ステップにおいて、それぞれ前記第1〜第n−2のリンクステップで設定したリンク先ノードの配列番号が指す配列要素をブランチノードとして読み出し、
前記第2〜第n−1のリンクステップは、それぞれ前記第2〜第n−1のノード読出ステップで読み出されたブランチノードの弁別ビット位置を格納する領域から当該弁別ビット位置を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記ブランチノードの配置された配列要素の配列番号の2倍の値との和を前記リンク先ノードの配列番号として設定するものであり、
前記第nのノード読出ステップにおいて、前記第n−1リンクステップで設定したリンク先ノードの配列番号が指す配列要素をリーフノードとして読み出し、
前記インデックスキー読出ステップにおいて、前記第nのノード読出ステップで読みだした前記リーフノードのインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域から直接当該インデックスキーを読み出す、あるいは該インデックスキーにアクセスするための情報に基づき当該インデックスキーを読み出す、
ことを特徴とするビット列検索方法。
【請求項15】
請求項14記載のビット列検索方法をコンピュータに実行させることを特徴とするプログラム。
【請求項16】
請求項14記載のビット列検索方法をコンピュータに実行させるプログラムを記憶したことを特徴とするコンピュータ読み取り可能な記憶媒体。
【請求項17】
ビット列からなる検索キーによるビット列検索に用いられる、検索対象であるビット列からなるインデックスキーあるいは該インデックスキーにアクセスするための情報が格納されたツリーのデータ構造において、
前記インデックスキーは、本来のインデックスキーのある特定のビット位置に特定のビット値を挿入したものであり、
前記検索キーは、本来の検索キーの、前記本来のインデックスキーと同一の特定のビット位置に前記特定のビット値を挿入したものであり、
前記ツリーは配列に記憶され、n段目(nは正整数)までのツリーの構成要素を有するものであり、該ツリーの始点であって、前記配列の配列番号1の配列要素に配置されるルートノードと、前記配列の隣接した配列要素に配置される代表ノードと非代表ノードである2つのノードを有する、ツリーの構成要素としてのノード対を有し、前記ブランチノードは、前記検索キーの弁別ビット位置を格納する領域を含むが、ブランチノードとリーフノードを識別するノード種別を格納する領域、リンク先である直近下位のノード対の代表ノードの配置された配列要素の配列番号を格納する領域、及び前記インデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含まないものであり、前記リーフノードは、前記インデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含むが、前記ノード種別を格納する領域、及び前記検索キーの弁別ビット位置を格納する領域を含まないものであって、前記代表ノードは該代表ノードの直近上位のブランチノードの配置された配列要素の配列番号の2倍の値の配列番号の配列要素に配置され、前記リーフノードはn段目にのみ位置するものであり、
前記ツリーの記憶手段を備えたビット列検索装置により、
検索を開始するルートノードの配置された配列要素の配列番号1をリンク先ノードの配列番号として設定する検索開始位置設定ステップと、
第1〜第nのノード読出ステップと、
第1〜第n−1のリンクステップと、
インデックスキー読出ステップと、
を備え、
前記第1のノード読出ステップにおいて、前記検索開始位置設定ステップでリンク先ノードの配列番号として設定された配列番号1の配列要素から該配列要素に配置されたルートノードを読み出し、
前記第1のリンクステップにおいて、前記第1のノード読出ステップで読み出されたルートノードの弁別ビット位置を格納する領域から当該弁別ビット位置を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記ルートノードの配置された配列要素の配列番号の2倍の値との和を前記リンク先ノードの配列番号として設定し、
前記第2〜第n−1のノード読出ステップにおいて、それぞれ前記第1〜第n−2のリンクステップで設定したリンク先ノードの配列番号が指す配列要素をブランチノードとして読み出し、
前記第2〜第n−1のリンクステップは、それぞれ前記第2〜第n−1のノード読出ステップで読み出されたブランチノードの弁別ビット位置を格納する領域から当該弁別ビット位置を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記ブランチノードの配置された配列要素の配列番号の2倍の値との和を前記リンク先ノードの配列番号として設定するものであり、
前記第nのノード読出ステップにおいて、前記第n−1リンクステップで設定したリンク先ノードの配列番号が指す配列要素をリーフノードとして読み出し、
前記インデックスキー読出ステップにおいて、前記第nのノード読出ステップで読みだした前記リーフノードのインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域から直接当該インデックスキーを読み出す、あるいは該インデックスキーにアクセスするための情報に基づき当該インデックスキーを読み出す検索方法の実行を可能とすることを特徴とするデータ構造。
【請求項18】
請求項17記載のデータ構造を記憶したことを特徴とするコンピュータ読み取り可能な記憶媒体。
【請求項19】
ビット列からなる検索キーにより、検索対象であるビット列からなるインデックスキーあるいは該インデックスキーにアクセスするための情報が格納されたツリーのデータ構造に基づいて、前記インデックスキーを検索するビット列検索装置において、
前記インデックスキーは、本来のインデックスキーのある特定のビット位置に特定のビット値を挿入したものであり、
前記検索キーは、本来の検索キーの、前記本来のインデックスキーと同一の特定のビット位置に前記特定のビット値を挿入したものであり、
前記ツリーは配列に記憶され、n段目(nは正整数)までのツリーの構成要素を有するものであり、該ツリーの始点であるルートノードであって、ノード参照番号1に、該ルートノードの位置を定める配列番号であるベース番号と前記ツリーの各段のノードの開始位置を定める番号であるオフセット番号を加えた値の配列番号の配列要素に配置されるルートノードと、前記配列の隣接した配列要素に配置される代表ノードと非代表ノードである2つのノードを有する、ツリーの構成要素としてのノード対を有し、前記ブランチノードは、前記検索キーの弁別ビット位置を格納する領域を含むが、ブランチノードとリーフノードを識別するノード種別を格納する領域、リンク先である直近下位のノード対の代表ノードの配置された配列要素の配列番号を格納する領域、及び前記インデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含まないものであり、前記リーフノードは、前記インデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含むが、前記ノード種別を格納する領域、及び前記検索キーの弁別ビット位置を格納する領域を含まないものであって、前記代表ノードは該代表ノードの直近上位のブランチノードのノード参照番号の2倍の値のノード参照番号に、前記ベース番号と該直近上位のブランチノードの次の段のオフセット番号を加えた値の配列番号の配列要素に配置され、前記リーフノードはn段目にのみ位置する、カップルドノードツリーと、
検索を開始するルートノードのノード参照番号1と該ノードについての前記オフセット番号と前記ベース番号に基づいて該ルートノードの配置された配列要素の配列番号を取得し、該取得した配列番号をリンク先ノードの配列番号として設定する検索開始位置設定手段と、
第1〜第nのノード読出手段と、
第1〜第n−1のリンク手段と、
インデックスキー読出手段と、
を備え、
前記第1のノード読出手段は、前記検索開始位置設定手段によりリンク先ノードの配列番号として設定された配列番号の配列要素から該配列要素に配置されたルートノードを読み出し、
前記第1のリンク手段は、前記第1のノード読出手段により読み出されたルートノードの弁別ビット位置を格納する領域から当該弁別ビット位置を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記ルートノードのノード参照番号1の2倍の値との和を前記リンク先ノードのノード参照番号とし、該ノード参照番号と前記ベース番号と前記ルートノードの次の段のオフセット番号の和をリンク先ノードの配列番号として設定し、
前記第2〜第n−1のノード読出手段は、それぞれ前記第1〜第n−2のリンク手段が設定したリンク先ノードの配列番号が指す配列要素をブランチノードとして読み出し、
前記第2〜第n−1のリンク手段は、それぞれ前記第2〜第n−1のノード読出手段により読み出されたブランチノードの弁別ビット位置を格納する領域から当該弁別ビット位置を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記ブランチノードのノード参照番号の2倍の値との和を前記リンク先ノードのノード参照番号とし、該ノード参照番号と前記ベース番号と前記ブランチノードの次の段のオフセット番号の和をリンク先ノードの配列番号として設定するものであり、
前記第nのノード読出手段は、前記第n−1リンク手段が設定したリンク先ノードの配列番号が指す配列要素をリーフノードとして読み出し、
インデックスキー読出手段は、前記第nのノード読出手段が読みだした前記リーフノードのインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域から直接当該インデックスキーを読み出す、あるいは該インデックスキーにアクセスするための情報に基づき当該インデックスキーを読み出す、
ことを特徴とするビット列検索装置。
【請求項20】
請求項19記載のビット列検索装置が実行するビット列検索方法において、
検索を開始するルートノードのノード参照番号1と該ルートノードについての前記オフセット番号と前記ベース番号に基づいて該ルートノードの配置された配列要素の配列番号を取得し、該取得した配列番号をリンク先ノードの配列番号として設定する検索開始位置設定ステップと、
第1〜第nのノード読出ステップと、
第1〜第n−1のリンクステップと、
インデックスキー読出ステップと、
を備え、
前記第1のノード読出ステップにおいて、前記検索開始位置設定ステップでリンク先ノードの配列番号として設定された配列番号の配列要素から該配列要素に配置されたルートノードを読み出し、
前記第1のリンクステップにおいて、前記第1のノード読出ステップで読み出されたルートノードの弁別ビット位置を格納する領域から当該弁別ビット位置を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記ルートノードのノード参照番号1の2倍の値との和を前記リンク先ノードのノード参照番号とし、該ノード参照番号と前記ベース番号と前記ルートノードの次の段のオフセット番号の和をリンク先ノードの配列番号として設定し、
前記第2〜第n−1のノード読出ステップにおいて、それぞれ前記第1〜第n−2のリンクステップで設定したリンク先ノードの配列番号が指す配列要素をブランチノードとして読み出し、
前記第2〜第n−1のリンクステップは、それぞれ前記第2〜第n−1のノード読出ステップで読み出されたブランチノードの弁別ビット位置を格納する領域から当該弁別ビット位置を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記ブランチノードのノード参照番号の2倍の値との和を前記リンク先ノードのノード参照番号とし、該ノード参照番号と前記ベース番号と前記ブランチノードの次の段のオフセット番号の和をリンク先ノードの配列番号として設定するものであり、
前記第nのノード読出ステップにおいて、前記第n−1リンクステップで設定したリンク先ノードの配列番号が指す配列要素をリーフノードとして読み出し、
前記インデックスキー読出ステップにおいて、前記第nのノード読出ステップで読みだした前記リーフノードのインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域から直接当該インデックスキーを読み出す、あるいは該インデックスキーにアクセスするための情報に基づき当該インデックスキーを読み出す、
ことを特徴とするビット列検索方法。
【請求項21】
請求項20記載のビット列検索方法をコンピュータに実行させることを特徴とするプログラム。
【請求項22】
請求項20記載のビット列検索方法をコンピュータに実行させるプログラムを記憶したことを特徴とするコンピュータ読み取り可能な記憶媒体。
【請求項23】
ビット列からなる検索キーによるビット列検索に用いられる、検索対象であるビット列からなるインデックスキーあるいは該インデックスキーにアクセスするための情報が格納されたツリーのデータ構造において、
前記インデックスキーは、本来のインデックスキーのある特定のビット位置に特定のビット値を挿入したものであり、
前記検索キーは、本来の検索キーの、前記本来のインデックスキーと同一の特定のビット位置に前記特定のビット値を挿入したものであり、
前記ツリーは配列に記憶され、n段目(nは正整数)までのツリーの構成要素を有するものであり、該ツリーの始点であるルートノードであって、ノード参照番号1に、該ルートノードの位置を定める配列番号であるベース番号と前記ツリーの各段のノードの開始位置を定める番号であるオフセット番号を加えた値の配列番号の配列要素に配置されるルートノードと、前記配列の隣接した配列要素に配置される代表ノードと非代表ノードである2つのノードを有する、ツリーの構成要素としてのノード対を有し、前記ブランチノードは、前記検索キーの弁別ビット位置を格納する領域を含むが、ブランチノードとリーフノードを識別するノード種別を格納する領域、リンク先である直近下位のノード対の代表ノードの配置された配列要素の配列番号を格納する領域、及び前記インデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含まないものであり、前記リーフノードは、前記インデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含むが、前記ノード種別を格納する領域、及び前記検索キーの弁別ビット位置を格納する領域を含まないものであって、前記代表ノードは該代表ノードの直近上位のブランチノードのノード参照番号の2倍の値のノード参照番号に、前記ベース番号と該直近上位のブランチノードの次の段のオフセット番号を加えた値の配列番号の配列要素に配置され、前記リーフノードはn段目にのみ位置するものであり、
前記ツリーの記憶手段を備えたビット列検索装置により、
検索を開始するルートノードのノード参照番号1と該ルートノードについての前記オフセット番号と前記ベース番号に基づいて該ルートノードの配置された配列要素の配列番号を取得し、該取得した配列番号をリンク先ノードの配列番号として設定する検索開始位置設定ステップと、
第1〜第nのノード読出ステップと、
第1〜第n−1のリンクステップと、
インデックスキー読出ステップと、
を備え、
前記第1のノード読出ステップにおいて、前記検索開始位置設定ステップでリンク先ノードの配列番号として設定された配列番号の配列要素から該配列要素に配置されたルートノードを読み出し、
前記第1のリンクステップにおいて、前記第1のノード読出ステップで読み出されたルートノードの弁別ビット位置を格納する領域から当該弁別ビット位置を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記ルートノードのノード参照番号1の2倍の値との和を前記リンク先ノードのノード参照番号とし、該ノード参照番号と前記ベース番号と前記ルートノードの次の段のオフセット番号の和をリンク先ノードの配列番号として設定し、
前記第2〜第n−1のノード読出ステップにおいて、それぞれ前記第1〜第n−2のリンクステップで設定したリンク先ノードの配列番号が指す配列要素をブランチノードとして読み出し、
前記第2〜第n−1のリンクステップは、それぞれ前記第2〜第n−1のノード読出ステップで読み出されたブランチノードの弁別ビット位置を格納する領域から当該弁別ビット位置を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記ブランチノードのノード参照番号の2倍の値との和を前記リンク先ノードのノード参照番号とし、該ノード参照番号と前記ベース番号と前記ブランチノードの次の段のオフセット番号の和をリンク先ノードの配列番号として設定するものであり、
前記第nのノード読出ステップにおいて、前記第n−1リンクステップで設定したリンク先ノードの配列番号が指す配列要素をリーフノードとして読み出し、
前記インデックスキー読出ステップにおいて、前記第nのノード読出ステップで読みだした前記リーフノードのインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域から直接当該インデックスキーを読み出す、あるいは該インデックスキーにアクセスするための情報に基づき当該インデックスキーを読み出す検索方法の実行を可能とすることを特徴とするデータ構造。
【請求項24】
請求項23記載のデータ構造を記憶したことを特徴とするコンピュータ読み取り可能な記憶媒体。

【図1A】
image rotate

【図1B】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4A】
image rotate

【図4B】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8A】
image rotate

【図8B】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15】
image rotate

【図16】
image rotate

【図17】
image rotate

【図18A】
image rotate

【図18B】
image rotate

【図19】
image rotate

【図20A】
image rotate

【図20B】
image rotate

【図21】
image rotate

【図22】
image rotate


【公開番号】特開2011−134289(P2011−134289A)
【公開日】平成23年7月7日(2011.7.7)
【国際特許分類】
【出願番号】特願2010−43644(P2010−43644)
【出願日】平成22年2月28日(2010.2.28)
【出願人】(506235616)株式会社エスグランツ (32)
【Fターム(参考)】