最初に、本出願人により先の上記出願に� ��いて提案された、本発明の前提となるカッ� ��ルドノードツリーについて、カップルドノ� ��ドツリーを配列に格納する例を説明する。� ��ランチノードが保持するリンク先の位置を� ��すデータとして、記憶装置のアドレス情報� ��することもできるが、ブランチノードある� ��はリーフノードのうち占有する領域の記憶� ��量の大きい方を格納可能な配列要素からな� ��配列を用いることにより、ノードの位置を� ��列番号で表すことができ、位置情報の情報� ��を削減することができる。

 図2Aは、配列に格納されたカップルドノー� �ツリーの構成例を説明する図である。
 図2Aを参照すると、ノード101が配列100の配� �番号10の配列要素に配置されている。ノード 101はノード種別102、弁別ビット位置103及び代 表ノード番号104で構成されている。ノード種 別102は0であり、ノード101がブランチノード� �あることを示している。弁別ビット位置103� �は1が格納されている。代表ノード番号104に� ��リンク先のノード対の代表ノードの配列番� ��20が格納されている。なお、以下では表記� �簡略化のため、代表ノード番号に格納され� �配列番号を代表ノード番号ということもあ� �。また、代表ノード番号に格納された配列� �号をそのノードに付した符号あるいはノー� �対に付した符号で表すこともある。

 配列番号20の配列要素には、ノード対111� �代表ノードであるノード[0]112が格納されて� �る。そして隣接する次の配列要素(配列番号2 0+1)に代表ノードと対になるノード[1]113が格� �されている。ノード[0]112のノード種別114に� �0が、弁別ビット位置115には3が、代表ノード 番号116には30が格納されている。またノード[ 1]113のノード種別117には1が格納されており、 ノード[1]113がリーフノードであることを示し ている。インデックスキー118には、“0001”� �格納されている。パトリシアツリーについ� �先に述べたと同様に、リーフノードにイン� �ックスキーと対応するレコードにアクセス� �る情報が含まれることは当然であるが、表� �は省略している。

 なお、代表ノードをノード[0]で表し、それ� ��対になるノードをノード[1]で表すことがあ� ��。また、ある配列番号の配列要素に格納さ� ��たノードを、その配列番号のノードという� ��とがあり、ノードの格納された配列要素の� ��列番号を、ノードの配列番号ということも� ��る。
 配列番号30及び31の配列要素に格納されたノ ード122とノード123からなるノード対121の内容 は省略されている。

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

 図2Bは、カップルドノードツリーのツリー� �造を概念的に示す図である。図示の6ビット� ��インデックスキーは、図1に例示されたパト リシアツリーのものと同じである。
 符号210aで示すのがルートノードである。図 示の例では、ルートノード210aは配列番号220� �配置されたノード対201aの代表ノードとして� ��る。
 ツリー構造としては、ルートノード210aの下 にノート対201bが、その下層にノード対201cと� ��ード対201fが配置され、ノード対201fの下層� �はノード対201hとノード対201gが配置されてい る。ノード対201cの下にはノード対201dが、さ� ��にその下にはノード対201eが配置されている 。
 各ノードの前に付された0あるいは1の符号� �、図2Aにおいて説明した配列要素の前に付さ れた符号と同じである。検索キーの弁別ビッ ト位置のビット値に応じてツリーをたどり、 検索対象のリーフノードを見つけることにな る。

 図示された例では、ルートノード210aのノー ド種別260aは0でブランチノードであることを� ��し、弁別ビット位置230aは0を示している。� �表ノード番号は220aであり、それはノード対2 01bの代表ノード210bの格納された配列要素の� �列番号である。
 ノード対201bはノード210bと211bで構成され、� ��れらのノード種別260b、261bはともに0であり� ��ブランチノードであることを示している。� ��ード210bの弁別ビット位置230bには1が格納さ� ��、リンク先の代表ノード番号にはノード対2 01cの代表ノード210cの格納された配列要素の� �列番号220bが格納されている。

 ノード210cのノード種別260cには1が格納され� ��いるので、このノードはリーフノードであ� ��、したがって、インデックスキー250cを含ん でいる。インデックスキー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のノード種別2 60e、261eはともに1であり双方ともリーフノー� ��であることを示し、それぞれのインデック� ��キー250e、251eにはインデックスキーとして� �010010”と“010011”が格納されている。

 ノード対201bのもう一方のノードであるノー ド211bの弁別ビット位置231bには2が格納され、 リンク先の代表ノード番号にはノード対201f� �代表ノード210fの格納された配列要素の配列� ��号221bが格納されている。
 ノード対201fのノード210f、211fのノード種別2 60f、261fはともに0であり双方ともブランチノ� ��ドである。それぞれの弁別ビット位置230f、 231fには5、3が格納されている。ノード210fの� �表ノード番号にはノード対201gの代表ノード2 10gの格納された配列要素の配列番号220fが格� �され、ノード211fの代表ノード番号にはノー� ��対201hの代表ノードであるノード[0]210hの格� �された配列要素の配列番号221fが格納されて� ��る。
 ノード対201gのノード210g、211gのノード種別2 60g、261gはともに1であり双方ともリーフノー� ��であることを示し、それぞれのインデック� ��キー250g、251gには“100010”と“100011”が格� �されている。
 また同じくノード対201hの代表ノードである ノード[0]210hとそれと対をなすノード[1]211hの� ��ード種別260h、261hはともに1であり双方とも� ��ーフノードであることを示し、それぞれの� ��ンデックスキー250h、251hには“101011”と“10 1100”が格納されている。

 以下、上述のツリーからインデックスキー� ��100010”を検索する処理の流れを簡単に説明� ��る。弁別ビット位置は、左から0、1、2、・� ��・とする。
 まず、ビット列“100010”を検索キーとして� ��ートノード210aから処理をスタートする。ル ートノード210aの弁別ビット位置230aは0である ので、検索キー“100010”の弁別ビット位置が 0のビット値をみると1である。そこで代表ノ� ��ド番号の格納された配列番号220aに1を加え� �配列番号の配列要素に格納されたノード211b� ��リンクする。ノード211bの弁別ビット位置231 bには2が格納されているので、検索キー“1000 10”の弁別ビット位置が2のビット値をみると 0であるから、代表ノード番号の格納された� �列番号221bの配列要素に格納されたノード210f にリンクする。

 ノード210fの弁別ビット位置230fには5が格納� ��れているので、検索キー“100010”の弁別ビ� ��ト位置が5のビット値をみると0であるから� �代表ノード番号の格納された配列番号220fの� ��列要素に格納されたノード210gにリンクする 。
 ノード210gのノード種別260gは1でありリーフ� ��ードであることを示しているので、インデ� ��クスキー250gを読み出して検索キーと比較す ると両方とも“100010”であって一致している 。このようにしてカップルドノードツリーを 用いた検索が行われる。

 次に、図2Bを参照してカップルドノードツ� �ーの構成の意味について説明する。
 カップルドノードツリーの構成はインデッ� ��スキーの集合により規定される。図2Bの例� �、ルートノード210aの弁別ビット位置が0であ るのは、図2に例示されたインデックスキー� �0ビット目が0のものと1のものがあるからで� �る。0ビット目が0のインデックスキーのグル ープはノード210bの下に分類され、0ビット目� ��1のインデックスキーのグループはノード211 bの下に分類されている。

 ノード211bの弁別ビット位置が2であるのは� �ノード211h、210h、211g、210gに格納された0ビッ ト目が1のインデックスキーの1ビット目がす� ��て0で等しく、2ビット目で初めて異なるも� �があるという、インデックスキーの集合の� �質を反映している。
 以下0ビット目の場合と同様に、2ビット目� �1であるものはノード211f側に分類され、2ビ� �ト目が0であるものはノード210f側に分類され る。
 そして2ビット目が1であるインデックスキ� �は3ビット目の異なるものがあるのでノード2 11fの弁別ビット位置には3が格納され、2ビッ� ��目が0であるインデックスキーでは3ビット� �も4ビット目も等しく5ビット目で異なるので ノード210fの弁別ビット位置には5が格納され� ��。
 ノード211fのリンク先においては、3ビット� �が1のものと0のものがそれぞれ1つしかない� �とから、ノード210h、211hはリーフノードとな り、それぞれインデックスキー250hと251hに“1 01011”と“101100”が格納されている。
 仮にインデックスキーの集合に“101100”の� ��わりに“101101”か“101110”が含まれていた� ��しても、3ビット目までは“101100”と等しい ので、ノード211hに格納されるインデックス� �ーが変わるだけで、ツリー構造自体は変わ� �ことはない。しかし、“101100”に加えて“10 1101”が含まれていると、ノード211hはブラン� ��ノードとなり、その弁別ビット位置は5にな る。追加されるインデックスキーが“101110” であれば、弁別ビット位置は4となる。

 以上説明したように、カップルドノードツ� ��ーの構造は、インデックスキーの集合に含� ��れる各インデックスキーの各ビット位置の� ��ット値により決定される。
 そしてさらにいえば、異なるビット値とな� ��ビット位置ごとにビット値が“1”のノード とビット値が“0”のノードとに分岐してい� �ことから、ノード[1]側とツリーの深さ方向� �優先させてリーフノードをたどると、それ� �に格納されたインデックスキーは、ノード21 1hのインデックスキー251hの“101100”、ノード 210hのインデックスキー250hの“101011”、・・� ��、ノード210cのインデックスキー250cの“00011 1”となり降順にソートされている。
 すなわち、カップルドノードツリーにおい� ��は、インデックスキーはソートされてツリ� ��上に配置されている。

 検索キーで検索するときはインデックスキ� ��がカップルドノードツリー上に配置された� ��ートをたどることになり、例えば検索キー� ��“101100”であればノード211hに到達すること ができる。また、上記説明からも想像がつく ように、“101101”か“101110”を検索キーとし た場合でもノード211hにたどり着き、検索結� �のインデックスキーとして“101100”が得ら� �る。
 また、例えば“100100”で検索した場合でも� ��ノード210a、211b、210fのリンク経路では検索� ��ーの3ビット目と4ビット目は使われること� �なく、“100100”の5ビット目が0なので、“100 010”で検索した場合と同様にノード210gに到� �することになる。このように、カップルド� �ードツリーに格納されたインデックスキー� �ビット構成に応じた弁別ビット位置を用い� �分岐が行われる。

図3は、本発明を実施するためのハードウェ� �構成例を説明する図である。
 本発明の検索装置による検索処理及びデー� ��メンテナンスは中央処理装置302及びキャッ� ��ュメモリ303を少なくとも備えたデータ処理� ��置301によりデータ格納装置308を用いて実施� ��れる。カップルドノードツリーが配置され� ��配列309と検索中にたどるノードが格納され� ��配列要素の配列番号を記憶する探索経路ス� ��ック310を有するデータ格納装置308は、主記� ��装置305または外部記憶装置306で実現するこ� ��ができ、あるいは通信装置307を介して接続� ��れた遠方に配置された装置を用いることも� ��能である。図1の配列100は、配列309の一例で ある。

 図3の例示では、主記憶装置305、外部記憶装 置306及び通信装置307が一本のバス304によりデ ータ処理装置301に接続されているが、接続方 法はこれに限るものではない。また、主記憶 装置305をデータ処理装置301内のものとするこ ともできるし、探索経路スタック310を中央処 理装置302内のハードウェアとして実現するこ とも可能である。あるいは、配列309は外部記 憶装置306に、探索経路スタック310を主記憶装 置305に持つなど、使用可能なハードウェア環 境、インデックスキー集合の大きさ等に応じ て適宜ハードウェア構成を選択できることは 明らかである。
 また、特に図示されてはいないが、処理の� ��中で得られた各種の値を後の処理で用いる� ��めにそれぞれの処理に応じた一時記憶装置� ��用いられることは当然である。
 次に、上述の出願において、本出願人によ� ��提案されたカップルドノードツリーを用い� ��基本的な検索処理について、本発明を理解� ��るために必要な範囲で紹介する。

 図4は、本出願人による出願である上記特願 2006-293619で提案されたビット列検索の基本動� ��を示したフローチャートである。
 まず、ステップS401で、検索開始ノードの配 列番号を取得する。取得された配列番号に対 応する配列要素は、カップルドノードツリー を構成する任意のノードを格納したものであ る。検索開始ノードの指定は、後述の各種応 用検索において行われる。

 次に、ステップS402で、探索経路スタック310 に取得された配列番号を格納し、ステップS40 3で、その配列番号に対応する配列要素を参� �すべきノードとして読み出す。そして、ス� �ップS404で、読み出したノードから、ノード� ��別を取り出し、ステップS405で、ノード種別 がブランチノードであるか否かを判定する。
 ステップS405の判定において、読み出したノ ードがブランチノードである場合は、ステッ プS406に進み、ノードから弁別ビット位置に� �いての情報を取り出し、更に、ステップS407� ��、取り出した弁別ビット位置に対応するビ� ��ト値を検索キーから取り出す。そして、ス� ��ップS408で、ノードから代表ノード番号を取 り出して、ステップS409で、検索キーから取� �出したビット値と代表ノード番号とを加算� �、新たな配列番号として、ステップS402に戻� ��。

 以降、ステップS405の判定においてリーフ ノードと判定されてステップS410に進むまで� �ステップS402からステップS409までの処理を繰 り返す。ステップS410で、リーフノードから� �ンデックスキーを取り出して、処理を終了� �る。

 なお、カップルドノードツリーは、リー� ��ノードを挿入する処理を繰り返すことによ� ��生成することが可能である。上記特願2006-18 7827によれば、その挿入処理ではまず、指定� �れた挿入キーを検索キーとしてカップルド� �ードツリーから該当するリーフノードを検� �する。その際、そのリーフノードに至るま� �たどった経路上のブランチノード及び当該� �ーフノードが格納された配列要素の配列番� �をスタックに順次格納する。そして、検索� �ーと、リーフノードに含まれるインデック� �キーの間で大小比較とビット列比較を行う� �続いて、ビット列比較で異なるビット値と� �る先頭のビット位置と、スタックに格納さ� �ているブランチノードの弁別ビット位置と� �相対的位置関係により、挿入キーを含むリ� �フノードともう一方のノードからなる新た� �ノード対の挿入位置を決定する。そして、� �小関係により、挿入キーを含むリーフノー� �を、挿入されるノード対のどちらのノード� �するかを決定し、ノード対を挿入する。

 また、指定されたインデックスキーを含� ��リーフノードをカップルドノードツリーか� ��削除する方法も、上記特願2006-187827に記載� �れている。それによれば、削除キーを検索� �ーとしてカップルドノードツリーから該当� �るリーフノードを検索し、そのリーフノー� �とノード対を構成するノードの内容を、当� �ノード対のリンク元のブランチノードに書� �込み、当該ノード対を削除することで、指� �されたインデックスキーを含むリーフノー� �を削除することができる。

 また、特願2006-293619には、0~n(n≧0)ビット� ��までの値が指定された前方一致キーと、0~n� ��ット目が完全に一致するインデックスキー� ��すべて取り出す前方一致検索の方法も記載� ��れている。例えば、前方一致キーとして“1 0****”が指定された場合、n=1であり、0~1ビッ� ��目が前方一致キーと一致するインデックス� ��ーがすべて取り出される。

 その具体的な方法は、次のとおりである。� ��ず、前方一致キーのすべての“*”を“0”� �置き換えた下限キーと、前方一致キーのす� �ての“*”を“1”で置き換えた上限キーを取 得する。そして、下限キーと上限キーで指定 される検索範囲のインデックスキーを昇順で カップルドノードツリーから取り出す。
 指定された検索範囲のインデックスキーを� ��順でカップルドノードツリーから取り出す� ��理は、次のように行われる。まず、下限キ� ��以上のインデックスキーの最小値である下� ��値を下限キーから取得し、上限キー以下の� ��ンデックスキーの最大値である上限値を上� ��キーから取得する。

 下限値の取得は、ノード[0]側及び深さ方向� ��優先させた深さ優先探索順にカップルドノ� ��ドツリーのリーフノードを探索しながら、� ��ーフノードのインデックスキーと下限キー� ��比較することにより行われる。上限値の取� ��方法は、探索順をノード[1]側及び深さ方向� ��優先させた深さ優先探索順とする以外は、� ��限値の取得と同様の方法である。
 そして、下限値のインデックスキーを格納� ��たリーフノードから開始して、上限値のイ� ��デックスキーが見つかるまで、ノード[0]側� ��び深さ方向を優先させた深さ優先探索順に� ��ップルドノードツリーのリーフノードを探� ��し、順次リーフノードからインデックスキ� ��を取り出す。
 以上の処理により、前方一致キーと0~nビッ� ��目が完全に一致するインデックスキーをす� ��て取り出すことができる。

 また、特願2007-132289には、指定された最� �一致検索キーと部分一致するインデックス� �ーのうち、差分ビット位置が最も下位とな� �インデックスキーを検索する最長一致検索� �方法が記載されている。なお、ここで差分� �ット位置とは、2つのビット列を比較したと� ��にビット値が一致しない不一致ビットのう� ��、最も上位の位置である。

 その具体的な方法は、次のとおりである。� ��ず、最長一致検索キーを検索キーとし、ル� ��トノードを検索開始ノードとして図4の検索 を行い、その結果得られたインデックスキー と最長一致検索キーとを比較し、差分ビット 位置を求める。
 そして、図4の検索において記憶された探索 経路スタックを遡り、弁別ビット位置が差分 ビット位置よりも上位にあるブランチノード のうち、弁別ビット位置が最下位のブランチ ノードの次に探索経路スタックに記憶された ノードを最長一致ノードとして取得する。

 カップルドノードツリーの構造から、以上� ��ようにして取得された最長一致ノードをル� ��トノードとする部分木に含まれるすべての� ��ンデックスキーは、最長一致検索キーと部� ��一致するインデックスキーのうち差分ビッ� ��位置が最も下位であるという上記の条件を� ��たす。よって、必要に応じて、この部分木� ��中から適宜インデックスキーを取り出せば� ��い。
 以上、本発明の前提となる技術を説明した� ��、必要とあれば、上述の特許出願の明細書� ��び図面の記載を参照されたい。

 なお、上記特願2006-293619による前方一致検� �及び特願2007-132289による最長一致検索と、本 発明による検索との関連性を説明すれば、下 記のごとくである。
 上記の前方一致検索における前方一致キー� ��ドントケアビットを含む。また、上記の最� ��一致検索は、最長一致検索キーと部分的に� ��か一致しないインデックスキーが結果とし� ��得られることがあるという点で、不一致の� ��囲をドントケアビットとして扱っていると� ��ることもできる。
 しかし、上記の前方一致検索と最長一致検� ��はいずれも、一意に定まる1つのインデック スキーを取得する処理ではない。
 すなわち、上記の前方一致検索で取り出さ� ��るインデックスキーの数は、2以上のことが ある。また、上記の最長一致検索において、 最長一致ノードをルートノードとする部分木 は複数のリーフノードを有することがあり、 この部分木の中からどのインデックスキーを 取り出すかは任意である。
 つまり、上記の前方一致検索と最長一致検� ��では、検索の条件を満たすという点で互い� ��対等な複数のインデックスキーが存在する� ��とがある。よって、検索の目的によっては� ��それら複数のインデックスキーの中から、� ��らかの基準によって1つを選択することが必 要である。

 一方で、ルータにおけるルーティングテー� ��ルの検索など、非常に高速な処理が求めら� ��る分野では、上記のような検索と選択とい� ��2段階の処理を行うことは好ましくない。そ のため、前方一致検索や最長一致検索のよう に部分的な一致に基づく検索の場合でも、最 適な1つのインデックスキーが一意に定まり� �2段階目の選択処理を必要とせずに、その一� ��なインデックスキーを取得する方法が望ま� ��る。
 以下に説明するとおり、本発明によるドン� ��ケアビットを考慮した検索は、そのような� ��望を満たすものである。上記の前方一致検� ��、最長一致検索、及び、以下に述べるドン� ��ケアビットを考慮した検索は、検索の目的� ��応じて使い分けるべきものである。

 次に、本発明の実施形態について詳しく� ��明する。以下では、ビット列の符号化方法� ��例と、カップルドノードツリーの例を説明� ��てから、検索、挿入、削除の各処理につい� ��説明する。

 以下の説明では、符号化の前と後のビット� ��をそれぞれ「元ビット列」、「符号化ビッ� ��列」という。「インデックスキー」や「検� ��キー」という語は、特に断らない限り符号� ��ビット列の状態であることを示し、元ビッ� ��列の状態を示す場合には「元インデックス� ��ー」や「元検索キー」のように表記する。
 また、値が“0”または“1”に定まってい� �ビットを「有意ビット」と呼び、値が“0”� ��“1”のいずれでもよく、一意に定まらない ビットを「ドントケアビット」と呼ぶ。なお 、ドントケアビットは、“0”または“1”に� ��り表される有意ビットと区別して、符号“* ”により表記する。

 また、以下では、ドントケアビットが有� ��ビットよりも前に存在していないことを前� ��とする。つまり、元ビット列は、ドントケ� ��ビットのみからなるか、有意ビットのみか� ��なるか、1ビット以上の有意ビットに1ビッ� �以上のドントケアビットが後続するかのい� �れかである。

 このようにドントケアビットを含む可能性� ��ある元ビット列を符号化するために、各ビ� ��トを2ビットに符号化する符号化方法を採用 する。
 符号化ビット列は、2ビットからなるビット 対を単位とする。各ビット対の0ビット目は� �ドントケアビットであるか有意ビットであ� �かを示す識別ビットである。各ビット対の1� ��ット目は、データビットと呼ぶ。
 識別ビットは、値が“0”のときドントケア ビットを示し、値が“1”のとき有意ビット� �示す。

 識別ビットの値が“0”のとき、対となるデ ータビットの値は必ず、予め決められた値で あり、以下の実施形態では、予め決められた その値として“0”を採用する。識別ビット� �値が“1”のとき、データビットは元ビット� ��のビットの値を表す。
 つまり、元ビット列の各ビットは、“0”な る値の有意ビットのとき“10”なるビット対� ��符号化され、“1”なる値の有意ビットのと き“11”なるビット対に符号化され、ドント� ��アビットのとき“00”なるビット対に符号� �される。
 この符号化方法によれば、元ビット列にお� ��て後続の有意ビットがあるか否かを、符号� ��ビット列から簡単に判断することができる� ��なぜなら、符号化ビット列中の任意のビッ� ��は、そのビットの位置が偶数であるか奇数� ��あるかによって、そのビットが識別ビット� ��あるかデータビットであるかを簡単に区別� ��ることができ、上記の前提からドントケア� ��ットが有意ビットよりも前に存在すること� ��ないからである。

 次に図5を参照して、符号化ビット列を利用 したカップルドノードツリーの例を説明する 。図5の(a)は、6つの符号化されていない元イ� ��デックスキー“*****”、“1****”、“101**”� ��“1011*”、“1100*”、“111**”の集合に対応� ��るカップルドノードツリーの概念的な構造� ��示す。
 なお、図5は、後述の検索処理のための説明 に関する部分(b)と(c)も含むが、ここでは先に カップルドノードツリーの構造についてのみ 説明する。

 図5の(a)のカップルドノードツリーの各リー フノードは、インデックスキーとして、上記 6つの元インデックスキーをそれぞれ符号化� �た符号化ビット列を格納している。図5では� ��理解の助けとするために、元インデックス� ��ーの値が、各インデックスキーの近傍の括� ��内に示されている。
 インデックスキーに格納されるのが符号化� ��ット列であるという点以外は、図5は図2Bと� ��様なので、図5においても図2Bと同様の符号� ��用いる。

 すなわち、ルートノード210aは、配列番号220 に配置され、ノード対201aの代表ノードであ� �。ツリー構造としては、ルートノード210aの� ��にノード対201bが、その下層にノード対201c� �、さらにその下層にノード対201dが配置され� ��いる。そして、ノード対201dの下層には、ノ ード対201eとノード対201fが配置されている。
 ルートノード210aのノード種別260aは0でブラ� ��チノードであることを示し、弁別ビット位� ��230aは0であり、代表ノード番号には、ノー� �対201bの代表ノードであるノード210bの格納さ れた配列要素の配列番号220aが格納されてい� �。

 ノード対201bは、ノード種別260bが1であって� ��ーフノードであるノード210bと、ノード種別 261bが0であってブランチノードであるノード2 11bで構成される。
 ノード210bのインデックスキー250bには、元� �ンデックスキー“*****”を符号化した“000000 0000”が格納されている。
 一方、ノード211bの弁別ビット位置231bには2� ��格納され、代表ノード番号には、ノード対2 01cの代表ノード210cの格納された配列要素の� �列番号221bが格納されている。

 ノード対201cは、ノード種別260cが1であって� ��ーフノードであるノード210cと、ノード種別 261cが0であってブランチノードであるノード2 11cで構成される。
 ノード210cのインデックスキー250cには、元� �ンデックスキー“1****”を符号化した“110000 0000”が格納されている。
 一方、ノード211cの弁別ビット位置231cには3� ��格納され、代表ノード番号には、ノード対2 01dの代表ノード210dの格納された配列要素の� �列番号221cが格納されている。

 ノード対201dは、ノード210dと211dで構成され� ��それぞれのノード種別260dと261dはブランチ� �ードであることを示す0である。
 ノード210dの弁別ビット位置230dには6が格納� ��れ、代表ノード番号には、ノード対201eの代 表ノード210eの格納された配列要素の配列番� �220dが格納されている。
 一方、ノード211dの弁別ビット位置231dには5� ��格納され、代表ノード番号には、ノード対2 01fの代表ノード210fの格納された配列要素の� �列番号221dが格納されている。

 ノード対201eは、ノード210eと211eで構成され� ��それぞれのノード種別260eと261eはリーフノ� �ドであることを示す1である。
 ノード210eのインデックスキー250eには、元� �ンデックスキー“101**”を符号化した“111011 0000”が格納されている。
 一方、ノード211eのインデックスキー251eに� �、元インデックスキー“1011*”を符号化した “1110111100”が格納されている。

 ノード対201fは、ノード210fと211fで構成され� ��それぞれのノード種別260fと261fはリーフノ� �ドであることを示す1である。
 ノード210fのインデックスキー250fには、元� �ンデックスキー“1100*”を符号化した“111110 1000”が格納されている。
 一方、ノード211fのインデックスキー251fに� �、元インデックスキー“111**”を符号化した “1111110000”が格納されている。

 検索キーとして使われる符号化ビット列が� ��カップルドノードツリーに含まれるインデ� ��クスキーのうちの1つと完全に一致する場合 は、図4と同様の処理により、検索キーと等� �いインデックスキーが検索結果として得ら� �る。
 しかし、ドントケアビットを考慮すると、� ��索キーと部分的に一致するインデックスキ� ��を検索結果として得るべき場合がある。そ� ��ような部分的な一致に基づく検索の詳細は� ��図6~図11を参照して後述する。

 次に、図5の(a)のカップルドノードツリーの 構成の意味について説明する。図5の(a)のよ� �に、符号化ビット列を用いる場合でも、図2B と同様に、カップルドノードツリーの構成は インデックスキーの集合により規定される。
 図5の(a)の例で、ルートノード210aの弁別ビ� �ト位置が0であるのは、図5中のインデックス キーに0ビット目が0のものと1のものがあるか らである。0ビット目が0のインデックスキー� ��1つしかないためノード210bに分類され、0ビ� ��ト目が1のインデックスキーはノード211bの� �層に分類されている。

 ノード211bの弁別ビット位置231bが2であるの� ��、ノード211bの下層の各ノードに格納された 0ビット目が1のインデックスキーの1ビット目 がすべて1で等しく、2ビット目で初めて異な� ��ものがあるという、インデックスキーの集� ��の性質を反映している。
 以下同様に、0~1ビット目が“11”であるイ� �デックスキーのうちで、2ビット目が0のイン デックスキーは1つしかないのでノード210cに� ��類され、2ビット目が1のインデックスキー� �ノード211cの下層に分類される。ノード211cの 弁別ビット位置231が3であるのは、ノード211c� ��下層の各ノードに格納されたインデックス� ��ーには、3ビット目が0のものと1のものがあ� ��ことを反映している。

 ノード210dの弁別ビット位置230dが6である理� ��は、ノード210dの下層の各ノードに格納され た0~3ビット目が“1110”であるインデックス� �ーは、4~5ビット目がいずれも“11”で等しく 、6ビット目で初めて異なるという、インデ� �クスキーの性質を反映しているからである� �
 ノード210dのリンク先においては、6ビット� �が0のインデックスキーと1のインデックスキ ーがそれぞれ1つしかない。よって、ノード21 0eと211eはリーフノードであり、ノード210eと21 1eのインデックスキー250eと251eにはそれぞれ� �“101**”の符号化ビット列である“1110110000� �と“1011*”の符号化ビット列である“111011110 0”が格納されている。

 一方、ノード211dの弁別ビット位置231dが5で� ��る理由は、ノード211dの下層の各ノードに格 納された0~3ビット目が“1111”であるインデ� �クスキーは、4ビット目がいずれも1で等しく 、5ビット目で初めて異なるという、インデ� �クスキーの性質を反映しているからである� �
 ノード211dのリンク先においては、5ビット� �が0のインデックスキーと1のインデックスキ ーがそれぞれ1つしかない。よって、ノード21 0fと211fはリーフノードであり、ノード210fと21 1fのインデックスキー250fと251fにはそれぞれ� �“1100*”の符号化ビット列である“1111101000� �と“111**”の符号化ビット列である“111111000 0”が格納されている。

 このように、図5の(a)においては符号化ビッ ト列であるインデックスキーの集合がカップ ルドノードツリーのツリー構造と対応してい る。
 また、本実施形態における符号化方法では� ��2つの元ビット列の0~m(0≦m)ビット目が一致� �ることと、その2つの元ビット列を符号化し� ��2つの符号化ビット列の0~(2m+1)ビット目が一� ��することは同値である。したがって、カッ� ��ルドノードツリーのツリー構造は、符号化� ��る前の元インデックスキーの集合により規� ��されるということもでき、ツリー構造と元� ��ンデックスキーの集合との間に対応関係が� ��る。

 すなわち、元インデックスキーのうち0ビッ ト目がドントケアビットのものは“*****”の� ��なので、“*****”がルートノード210aの直下� ��ノード210bに分類され、0ビット目が有意ビ� �トである元インデックスキーはノード210bと� ��をなすノード211bの下層に分類される。
 ノード211bの下層に分類された元インデック スキーは、すべて0ビット目が“1”で等しい� ��よって、0ビット目が“0”と“1”のいずれ� ��あるかという分類は不要である。
 一方、これらの元インデックスキーのうち� ��1ビット目がドントケアビットのものは“1** **”という元インデックスキーだけなので、� ��れがノード210cに分類され、1ビット目が有� �ビットの元インデックスキーはノード210cと� ��になるノード211cの下層に分類される。

 ノード211cの下層に分類される、少なくとも 0~1ビット目が有意ビットである元インデック スキーには、1ビット目が“0”のものと“1” のものがある。そこで、0~1ビット目が“10”� ��ものはノード210dの下層に分類され、0~1ビッ ト目が“11”のものはノード211dの下層に分類 される。
 ノード210dの下層に分類される元インデック スキーは“101**”と“1011*”の2つである。こ� ��2つの元インデックスキーは、0~2ビット目ま でが完全に一致するが、3ビット目がドント� �アビットであるか有意ビットであるかが異� �る。

 本実施形態ではドントケアビット“*”を“ 00”と符号化している。よって、このようにn ビット目(n≧1)以降がドントケアビットであ� �元インデックスキーと、nビット目が有意ビ� ��トである元インデックスキーが、0~(n-1)ビッ ト目の範囲において完全に一致する場合、前 者がノード[0]側に分類される。
 したがって、元インデックスキー“101**”� �ノード210eに、“1011*”が211eに、それぞれ分� ��される。

 一方、ノード211dの下層に分類される元イン デックスキーは“1100*”と“111**”の2つであ� ��。この2つの元インデックスキーは、0~1ビッ ト目が完全に一致するが、2ビット目の値が� �なる。
 このように、先頭の0ビット目から順に比較 して、いずれの元インデックスキーのドント ケアビットにも達しないうちに値の異なる有 意ビットが見つかる場合は、その有意ビット の値が“0”である元インデックスキーがノ� �ド[0]側に分類され、その有意ビットの値が� �1”である元インデックスキーがノード[1]側� ��分類される。
 したがって、元インデックスキー“1100*”� �ノード210fに、元インデックスキー“111**”� �ノード211fに、それぞれ分類される。

 以上のとおり、符号化ビット列を分類して� ��られる階層構造と、元ビット列を分類して� ��られる階層構造は同値である。
 また、ドントケアビットの値は不定である� ��とから、ドントケアビットと有意ビットの� ��のうちいずれが大きいかということは、本� ��は定まらない。しかし、便宜上、ドントケ� ��ビット“*”が“0”なる値の有意ビットよ� �も小さいと定義すれば、カップルドノード� �リーの構造は元インデックスキーの順序性� �反映したものであると言うことができる。
 すなわち、図2Bと同様に、図5のカップルド� ��ードツリーにおいても、ノード[1]側を優先� ��せた深さ優先探索順にリーフノードをたど� ��と、それらリーフノードに格納されたイン� ��ックスキーが表す元インデックスキーは降� ��にソートされている。換言すれば、元イン� ��ックスキーを降順にソートした順に対応し� ��、各インデックスキーはカップルドノード� ��リー上に配置されている。
 なお、本実施形態において、ドントケアビ� ��トを示す識別ビットの値を“0”としている のは、“*”が“0”よりも小さいという上記� ��定義と合わせるためである。

 次に、本発明の一実施形態における検索� ��理について、図6のフローチャートを参照し て説明する。図6の検索処理では、符号化さ� �ていない元ビット列である元検索キーが入� �として指定され、例えば図5のように符号化� ��ット列を用いたカップルドノードツリーが� ��索される。

 図6の検索処理は、以下に述べる「最長一 致キー」の条件を満たすインデックスキーが カップルドノードツリー内に存在すればその 最長一致キーを得る処理である。もし、最長 一致キーの条件を満たすインデックスキーが カップルドノードツリー内に含まれなければ 、検索は失敗して終了する。

 本実施形態において最長一致キーとは、下� ��の(a)と(b)のいずれかに相当するインデック� ��キーを示す。
 (a) 元検索キーを符号化した符号化ビット� �と全く同一のインデックスキー。
 (b) 有意ビットが存在しないか、元検索キ� �よりも少ない数の有意ビットが存在するが� �べての有意ビットの値が元検索キーのもの� �一致する元インデックスキーの中で、有意� �ットの数が最大のものを符号化したインデ� �クスキー。
 なお、上記の(a)は(b)よりも優先度が高い。� ��まり、もし(a)に該当するインデックスキー� ��存在すればそのインデックスキーが最長一� ��キーであり、このとき、(b)に該当するイン� ��ックスキーは、たとえ存在したとしても最� ��一致キーではない。

 図6の具体的な説明を始める前に、上記(a)と (b)の定義についていくつか例を挙げて説明す る。
 上記(a)の例は、図5の(a)のカップルドノード ツリーにおいて、元検索キーが“1100*”のと� ��の、“1100*”を符号化した符号化ビット列� �ある、ノード210fのインデックスキー250fであ る。
 また、図5の(a)のカップルドノードツリーに おいて、上記(b)に該当する最長一致キーの例 を3つ挙げると、次のとおりである。

 1つ目の例は、元検索キーが“11001”のとき� ��例である。この元検索キーの有意ビットの� ��は5である。
 図5の(a)には、有意ビットが存在しない元イ ンデックスキー“*****”がある。また、5より も少ない数の有意ビットが存在するが、すべ ての有意ビットの値が元検索キーのものと一 致する元インデックスキーには、“1****”と� ��1100*”がある。
 これらの3つの元インデックスキーのうち、 有意ビットの数が最大の“1100*”を符号化し� ��、ノード210fのインデックスキー250fが、最� �一致キーである。

 2つ目の例は、元検索キーが“11***”のとき� ��例である。この元検索キーの有意ビットの� ��は2である。
 図5には、有意ビットが存在しない元インデ ックスキー“*****”がある。また、2よりも少 ない数の有意ビットが存在するが、すべての 有意ビットの値が元検索キーのものと一致す る元インデックスキーには、“1****”がある� ��
 これらの2つの元インデックスキーのうち、 有意ビットの数が最大の“1****”を符号化し� ��、ノード210cのインデックスキー250cが、最� �一致キーである。

 なお、カップルドノードツリー内には、元� ��ンデックスキー“1100*”や“111**”を符号化 したインデックスキー250f及び251fも存在する� ��“11***”と一致する範囲は、一見、“1****” よりも“1100*”や“111**”の方が広いように� �える。
 しかし、インデックスキー250f及び251fは、� �長一致キーの定義から外れている。最長一� �キーがこのように定義されている理由につ� �て補足すると下記のごとくである。
 ドントケアビットは任意の値を表すので、� ��ントケアビットを含む元ビット列は、ビッ� ��列の集合を表していると見なすことができ� ��。例えば、“11***”が表す集合は“11011”と いう元ビット列などを包含する。
 しかし、“11011”は、“1100*”と3ビット目� �異なり、“111**”と2ビット目で異なる。つ� �り、“11011”は、“1100*”や“111**”に包含� �れない。よって、インデックスキー250fまた� ��251fを、元検索キー“11***”に対する最長一� ��キーとすることは不適切である。

 一方、元検索キー“11***”のドントケアビ� �トがどのような値をとろうとも、ドントケ� �ビットに値が設定されたそのビット列は、� �インデックスキー“*****”が表す集合や、元 インデックスキー“1****”が表す集合には必� ��包含される。
 そして、2つの元インデックスキーのうち、 より多くの有意ビットを有する元インデック スキー“1****”が表す集合の方がより小さく� ��元検索キー“11***”が表す集合により近い� �よって、元検索キー“11***”に対する最長一 致キーは元インデックスキー“1****”である� ��

 3つ目の例は、元検索キーが“0****”のとき� ��例である。図5の(a)のカップルドノードツリ ーには、“0”から始まる元インデックスキ� �を符号化したインデックスキーは含まれな� �。
 しかし、このとき、上記(b)の定義によれば� ��元インデックスキー“*****”を符号化した� �号化ビット列である、ノード210bのインデッ� ��スキー250bが最長一致キーである。実際、元 検索キー“0****”のドントケアビットがどの� ��うな値をとろうとも、ドントケアビットに� ��が設定されたそのビット列は、元インデッ� ��スキー“*****”が表す集合に包含される。
 上記のように定義される最長一致キーを取� ��することは、例えばIPアドレスのように、� �ット列の値と、ビット列が表す内容の階層� �な分類とが対応するような場合において、� �も適切な分類を選択するのに好適である。

 次に、図6フローチャートを参照して、図 6の処理の詳細を説明する。図6に示す処理に� ��り、上記の(a)及び(b)により定義される最長� ��致キーが存在すればそれを得ることができ� ��存在しなければ検索失敗という結果が得ら� ��る。

 ステップS601で、指定された元検索キーから 、上記の符号化方法によって、検索キーを作 成する。ステップS601の詳細は、図7を参照し� ��後述する。例えば、図5の(b)には、5ビット� �元検索キー“10100”から作成された10ビット� ��検索キー270が例示されている。
 続いて、ステップS602で、検索対象のカップ ルドノードツリーのルートノードを検索開始 ノードに設定する。

 次にステップS603で、カップルドノードツ リーのノードを格納する配列を、検索キーに より、検索開始ノードより検索し、検索結果 としてのインデックスキーを得る。ステップ S603の処理の詳細は図8とあわせて後述する。� ��のステップS606で参照するために、ステップ S603では、図5の(c)に例示したように探索経路� ��タック310に配列番号が格納される。

 次のステップS604では、検索キーと、ステッ プS603で得られたインデックスキーとの差分� �ット位置を求める。差分ビット位置の定義� �びステップS604の詳細は図9及び図10とあわせ� ��後述する。
 続くステップS606では、検索キーとステップ S603で得られたインデックスキーとに基づい� �、探索経路スタックを遡り、最長一致キー� �得る。ステップS606の処理の詳細は、図11と� �わせて後述する。
 ステップS606で最長一致キーが得られれば検 索は成功し、図6の処理が終了する。ステッ� �S606で最長一致キーが得られなければ検索は� ��敗して、図6の処理が終了する。

 次に図7のフローチャートを参照して、入 力ビット列として与えられた元ビット列を符 号化して符号化ビット列を出力する符号化処 理について説明する。図7の符号化処理は、� �6のステップS601に相当する。また、後述する ように、挿入処理及び削除処理においても図 7の符号化処理が実行される。

 ステップS701において、入力ビット列の有意 ビットの部分の長さである有意ビット長を、 ビット長として記憶する。
 また、ステップS702において、入力ビット列 のうち次に処理すべきビットの位置を示すビ ット位置を初期化する。本実施形態では0ビ� �ト目から順に処理するために、ステップS702� ��は、ビット位置を0に初期化する。
 そして、ステップS703において、出力ビット 列を、初期化して空ビット列とする。ビット 位置と出力ビット列の値は、後述のステップ S704~ステップS708のループにおいて更新される 。

 続いて、ステップS704において、ステップS70 1で記憶したビット長よりも現在のビット位� �が小さいか否かを判定し、現在のビット位� �の方が小さければステップS705へ進み、それ� ��外の場合はステップS709へ進む。
 ステップS705では、入力ビット列から、現在 のビット位置の指すビット値を取り出す。
 続いて、ステップS706では出力ビット列の末 尾にビット値1を連結する。そして、ステッ� �S707で出力ビット列の末尾に、ステップS705で 得たビット値を連結する。
 その後ステップS708でビット位置を次の位置 に更新してから、ステップS704に戻る。なお� �本実施形態では左から順に0、1、2……ビッ� �目と数えるので、「次の位置」とは現在の� �ット位置の右隣の位置のことである。
 ステップS709では、出力ビット列の末尾に、 入力ビット列中のドントケアビットの数のぶ ん、“00”なるビット対を連結し、処理を終� ��する。

 以上の処理により、例えば元ビット列“101* *”から、符号化ビット列“1110110000”が得ら� ��る。
 なお、本実施形態においては、元ビット列� ��の有意ビットの数とドントケアビットの数� ��、入力ビット列そのものとは別に指定され� ��ものとする。ただし、固定長のビット列の� ��を扱う場合は、有意ビットの数からドント� ��アビットの数を求めることも、その逆も可� ��なので、一方のみが指定されてもよい。

 次に図8のフローチャートを参照して、初期 検索を行う図6のステップS603の処理の詳細を� ��明する。
 ステップS801において、探索経路スタックの スタックポインタの値を初期値に設定する。 この初期値は、探索経路スタックに何も格納 されていないときの値であり、後述の図11の� ��理においても使われる。本実施形態の図8の 処理におけるスタックポインタは、次に配列 番号をステップS813においてプッシュすべき� �探索経路スタック上の位置を示すものとし� �以下では説明する。

 続いてステップS802で、検索開始ノードの配 列番号を取得する。図8の処理が実行される� �は、図6のステップS602が実行された後なので 、ステップS802では具体的にはルートノード� �配列番号を得る。
 次に、ステップS803で、カップルドノードツ リーのノードを格納する配列から、ステップ S801で取得した配列番号の指す配列要素をノ� �ドとして読み出す。
 そして、ステップS804で、ステップS803で読� �出したノードからノード種別を取り出し、� �テップS805で、ノード種別がブランチノード� ��あるか否かを判定する。

 ステップS805の判定において、読み出したノ ードがブランチノードである場合は、ステッ プS806に進み、ノードから弁別ビット位置に� �いての情報を取り出し、更に、ステップS807� ��、取り出した弁別ビット位置に対応するビ� ��ト値を検索キーから取り出す。そして、ス� ��ップS808で、ノードから代表ノード番号を取 り出す。
 続いてステップS811で、ステップS806で取り� �した弁別ビット位置が偶数か否かを判定す� �。

 本実施形態の符号化によれば、符号化ビッ� ��列における偶数のビット位置にあるビット� ��識別ビットであり、奇数のビット位置にあ� ��ビットはデータビットである。よって、ス� ��ップS811の判定が偶数の場合、有意ビットを 符号化したビットが後続するか否かの判定の ためにステップS812に進み、ステップS807で取� ��出したビット値が1か否かを判定する。
 ステップS812の判定が1の場合、本実施形態� �おける符号化では、元検索キーの有意ビッ� �の値を有するデータビットがまだ検索キー� �残っている。そのため、ステップS813に進ん� ��、ステップS803でノードを読み出した配列番 号を探索経路スタックに格納する。

 続いてステップS814で、ステップS808で取り� �した代表ノード番号に1を加えて、ステップS 803で読み出したノードの子ノードにあたるノ ード[1]の配列番号を取得し、新たな配列番号 として設定する。
 そして、ステップS815で、ステップS814で得� �子ノードの配列番号を探索経路スタックに� �納し、スタックポインタの値を1つ増やして� ��ら、ステップS803に戻る。
 なおここで「1つ増やす」という表現は、図 5の(c)のように探索経路スタック310を2列に分� ��て図示する説明に合わせた表現であり、具� ��的な探索経路スタック310およびスタックポ� ��ンタの実装方法を限定する趣旨のものでは� ��い。

 図5の(c)の探索経路スタック310では、ステッ プS813で格納される配列番号を左列に、ステ� �プS815で格納される配列番号を右列に、それ� ��れ図示している。ステップS815で行われるス タックポインタの値の更新は、図5の(c)にお� �てスタックポインタが指す行を次の行に移� �ことに相当する。
 一方、ステップS811の判定が奇数の場合は、 弁別ビット位置がデータビットの位置である ことを表す。また、ステップS812の判定が0の� ��合は、本実施形態における符号化では、識� ��ビットが0であること、すなわち元検索キー におけるドントケアビットを符号化したビッ ト位置まで達したことを表す。
 ステップS811で奇数と判定された場合とステ ップS812で0と判定された場合は、いずれもス� ��ップS809に進む。

 ステップS809では、検索キーからステップS80 7で取り出したビット値を、ステップS808で取� ��出した代表ノード番号に加算し、その加算� ��結果を新たな配列番号として設定する。ス� ��ップS809の実行後、処理はステップS803に戻� �。
 以降、ステップS805の判定においてリーフノ ードと判定されてステップS810に進むまで、� �テップS803からステップS815までの処理を繰り 返す。繰り返しにおいては、ステップS809ま� �はステップS814で設定された配列番号がステ� ��プS803で使われる。
 ステップS810では、リーフノードからインデ ックスキーを取り出して、処理を終了する。

 なお、ドントケアビット“*”は“00”と符� ��化されるので、jを0以上の整数とすると、� �号化ビット列の2jビット目が“0”ならば、� �号化ビット列の(2j+1)ビット目は必ず“0”で� ��る。
 そして、弁別ビット位置が2jのブランチノ� �ドの子ノードのうちノード[0]は、必ず、jビ� ��ト目以降がすべてドントケアビットである� ��インデックスキーを符号化したインデック� ��キーを格納するリーフノードである。

 したがって、ステップS811からステップS812� �S809、S803、S804、S805と処理が進む場合は、ス� ��ップS805において必ずリーフノードだと判定 され、必ずステップS810へ分岐する。
 このノード[0]であるリーフノードを、(有意 ビットの終端に達したという意味で)親のブ� �ンチノードから見て「終端側ノード」と呼� �、終端側ノードと対になるノード[1]を「非� �端側ノード」と呼ぶことにする。後述の図11 のステップS1107とステップS1108は、非終端側� �ードから終端側ノードを求める処理である� �

 次に図9のフローチャートを参照して、差分 ビット位置を求める図6のステップS604の処理� ��詳細を説明する。
 ステップS901で、比較ビット長を設定する。 比較ビット長に設定する値は、検索キー中の 、元検索キーの最上位のドントケアビットを 符号化したビット対の位置と、図6のステッ� �S603で得られたインデックスキー中の、元イ� ��デックスキーの最下位の有意ビットを符号� ��したビット対の位置のうち、より上位の位� ��までの、最上位である0ビット目からの長さ である。より正確には、比較ビット長を次の (1)~(3)のように定める。
(1) 元検索キーに有意ビットが含まれない場� ��、すなわち元検索キーの0ビット目がドント ケアビットの場合は、元検索キーの0ビット� �のドントケアビットを符号化したビット対� �検索キーの0~1ビット目である。よって、比� �ビット長を2に設定する。
(2) 元検索キーに有意ビットが含まれるが、� ��インデックスキーに有意ビットが含まれな� ��場合は、比較ビット長を0に設定する。
(3) 元検索キーと元インデックスキーの双方� ��有意ビットを含む場合は、比較ビット長を� ��のように定める。

 元検索キーの最上位のドントケアビットの� ��置をa(a≧1)とすると、aビット目のドントケ� ��ビットを符号化したビット対は、検索キー� ��2a~(2a+1)ビット目に位置する。なお、元検索� ��ーが有意ビットのみからなる場合は、元検� ��キーの長さをnとして、便宜的にa=nと見なす ものとする。
 また、元インデックスキーの最下位の有意� ��ットの位置をb(b≧0)とすると、bビット目の� ��意ビットを符号化したビット対は、インデ� ��クスキーの2b~(2b+1)ビット目に位置する。
 よって、(2a+1)≦(2b+1)の場合、すなわちa≦b� �場合、比較ビット長は、0ビット目から(2a+1)� ��ット目までの長さ、すなわち(2a+2)に設定さ� ��る。一方、(2a+1)>(2b+1)の場合、すなわちa&g t;bの場合、比較ビット長は0ビット目から(2b+1 )ビット目までの長さ、すなわち(2b+2)に設定� �れる。
 上記(1)~(3)のとおり、ステップS901で設定さ� �る比較ビット長は偶数なので、以下では説� �の便宜上、比較ビット長を2c(c≧0)と表記す� �。

 ステップS902で、検索キーとインデックスキ ーを、比較ビット長の指すビット列で比較し て、比較ビット長の差分ビット列を得る。す なわち、検索キーとインデックスキーを、0~( 2c-1)ビット目までの範囲で比較して、長さ2c� �差分ビット列を得る。
 差分ビット列は、検索キーとインデックス� ��ーで値が一致する位置のビットは値が0で、 一致しない位置のビットは値が1となるビッ� �列であり、例えば排他的論理和を求めるビ� �ト演算によって得ることができる。

 続いてステップS903で、差分ビット列を最上 位の位置すなわち0ビット目から見て、最初� �不一致ビットすなわち値が1のビットのビッ� ��位置を、差分ビット位置に設定し、処理を� ��了する。
 不一致ビットが存在しない場合は、後に差� ��ビット位置を参照することはないので、ス� ��ップS903において便宜的に差分ビット位置を 例えば2cと設定してもよい。また、比較ビッ� ��長が0のときは、便宜的に差分ビット位置を 負数に設定する。

 次に、図10を参照して、差分ビット位置の� �体例を説明する。
 図10の例では、検索キーは、元検索キー“10 100”を符号化した符号化ビット列“1110111010� �である。この元検索キーは有意ビットのみ� �らなるので、上記(3)の説明より便宜的にa=5� �見なされる。
 一方、この検索キーによるステップS603の検 索で得られるインデックスキーは、ドントケ アビットを含む元インデックスキー“1011*”� ��符号化したインデックスキー251e“1110111100� �である。この元インデックスキーにおける� �下位の有意ビットの位置はb=3である。
 よって、a>bなので、図9のステップS901で� �、8(=2b+2)が比較ビット長に設定される。
 そして、ステップS902で8ビットの差分ビッ� �列が得られ、ステップS903で7が差分ビット位 置に設定される。以上により、図9の処理、� �なわち図6のステップS604が終了する。

 次に、図11のフローチャートを参照して、� �長一致キーを取得する図6のステップS606の処 理の詳細を説明する。
 ステップS1101で、検索キーと図6のステップS 603で得られたインデックスキーを、比較ビッ ト長2cの指すビット列で比較して、すなわち� ��上位の0ビット目から(2c-1)ビット目までの範 囲で比較して、両者が等しいか否かを判断す る。
 ステップS1101で等しいと判断された場合、� �理はステップS1111に進み、ステップS603で得� �れたインデックスキーを最長一致キーに設� �して処理を終了する。
 ステップS1101で等しくないと判断された場� �、処理はステップS1102に進む。
 ステップS1102では、探索経路スタックのス� �ックポインタの値が初期値か否かを判断し� �初期値であれば最長一致キーを設定せずに� �11の処理を終了し、そうでなければステップ S1103に進む。

 図8のステップS801の説明から分かるとおり� �本実施形態においてスタックポインタが初� �値となるのは、探索経路スタックに最初に� �ッシュした配列番号をスタックポインタが� �しているか、探索経路スタックが空である� �きである。
 ステップS1103では、探索経路スタックのス� �ックポインタを1つ戻して、探索経路スタッ� ��から配列番号を取り出す。すなわち、ステ� ��プS1103の処理はポップ動作である。
 なお、図5の(c)における探索経路スタック310 の図示に合わせて説明すると、ステップS1103� ��処理は、1行上にスタックポインタを動かし て、変更後のスタックポインタが指す行の左 列から配列番号を取り出す処理である。

 続いてステップS1104では、カップルドノー� �ツリーのノードを格納する配列から、ステ� �プS1103で取り出した配列番号の指す配列要素 をノードとして読み出す。
 そして、ステップS1105では、ステップS1104で 読み出したノードから、弁別ビット位置を取 り出す。
 ここで、ステップS1103で取り出される配列� �号は、必ず図8のステップS813において探索経 路スタックにプッシュされた配列番号であっ て、図8のステップS815で探索経路スタックに� ��ッシュされた配列番号ではない。
 次にステップS1106で、ステップS1105で取り出 した弁別ビット位置は、図9のステップS903で� ��た差分ビット位置よりも上位の位置関係に� ��るか否かを判断する。
 弁別ビット位置が差分ビット位置よりも上� ��の場合はステップS1107に進み、そうでない� �合はステップS1102に戻る。
 ステップS1107では、探索経路スタックから� �探索経路スタックのスタックポインタの指� �子ノードの配列番号を読み出す。

 例えば、図5の(c)のようにスタックを図示す ることにすると、スタックポインタは行の位 置を表し、左列は偶数の弁別ビット位置を含 むノードの配列番号を表し、右列は同じ行の 左列に書かれた配列番号のノードの子ノード のうち、非終端側ノードであるノード[1]の配 列番号を表している。
 よって、図5の(c)の図示にしたがって動作を 説明するなら、ステップS1107では、スタック� ��インタの表す行の右列にある配列番号が読� ��出される。
 続いて、ステップS1108で、ステップS1107で読 み出された子ノードの配列番号と対をなす配 列番号を得る。

 本実施形態では、ノード対を構成する2つの ノードは隣接する配列番号の配列要素に格納 されるので、ノード対を構成する2つのノー� �の配列番号同士も対をなす。例えば、ノー� �[0]は偶数の配列番号の配列要素に格納され� �そのノード[0]と対になるノード[1]はその直� �の奇数の配列番号の配列要素に格納される� �よって、偶数と奇数の配列番号同士も対を� �す。
 この例の場合、ステップS1108では、ステッ� �S1107で読み出したノード[1]の配列番号から1� �引くことにより、そのノード[1]とノード対� �構成するノード[0]の配列番号が取得される� �つまり、ステップS1108では非終端側ノードの 配列番号から、リーフノードである終端側ノ ードの配列番号が取得される。

 次に、ステップS1109で、配列から、ステッ� �S1108で得た配列番号の指す配列要素、すなわ ち終端側ノードでありリーフノードである上 記のノード[0]を、ノードとして読み出す。
 続いて、ステップS1110では、ステップS1109で 読み出したリーフノードからインデックスキ ーを取り出し、次のステップS1111において、� ��り出したインデックスキーを最長一致キー� ��設定して、図11の処理を終了する。

 次に、図5のカップルドノードツリーを使っ た図6~図9及び図11の処理の具体例をいくつか� ��明する。
 元検索キーが、図5の(b)と図10に示した“1010 0”のとき、図6のステップS603では、図5に「� �期検索」と示したノード211eのインデックス� ��ー251eが得られる。
 この場合、図10を参照して説明したように8� ��ットが比較ビット長に設定され、差分ビッ� ��位置は7である。よって、図11のステップS110 2からステップS1106が実行され、配列番号221c� �ノード210dから弁別ビット位置230dが取り出さ れる。
 弁別ビット位置230dの値は6であり、7より上� ��なので、ステップS1107からステップS1111が実 行されて、図5に「最長一致」と示したノー� �210eのインデックスキー250eが最長一致キーに 設定される。これは、最長一致キーの定義の (b)に該当する場合である。

 元検索キーが“1100*”のとき、図6のステッ� ��S603ではインデックスキー250fが得られる。� �の場合、元検索キーの最上位のドントケア� �ットの位置は4、元インデックスキーの最下� ��の有意ビットの位置は3なので、比較ビット 長は8である。
 そして、図11のステップS1101では検索キーと インデックスキーが等しいと判定され、ステ ップS1111に進み、インデックスキー250fが最長 一致キーに設定される。この例は、最長一致 キーの定義の(a)に該当する例である。

 元検索キーが“11001”のとき、図6のステッ� ��S603では、元インデックスキー“1100*”を符� ��化したインデックスキー250fが得られる。
 この場合、元検索キーの最上位のドントケ� ��ビットの位置は便宜的に5と見なされ、元イ ンデックスキーの最下位の有意ビットの位置 が3なので、図9のステップS901では、8が比較� �ット長に設定される。
 よって、図11のステップS1101では検索キーと インデックスキーが等しいと判定され、ステ ップS1111に進み、インデックスキー250fが最長 一致キーに設定される。この例も、最長一致 キーの定義の(b)に該当する例である。

 元検索キーが“11***”のとき、図6のステッ� ��S603では元インデックスキー“1100*”を符号� ��したインデックスキー250fが得られる。
 この場合、元検索キーの最上位のドントケ� ��ビットの位置は2、元インデックスキーの最 下位の有意ビットの位置は3なので、図9のス� ��ップS901では6が比較ビット長に設定される� �差分ビット位置は4である。
 よって図11ではステップS1101からステップS11 02に進む。そして、ステップS1102からステッ� �S1106が実行されて、配列番号(220a+1)のノード2 11bから弁別ビット位置231bが取り出される。� �別ビット位置231bの値は2であり、4よりも上� �である。
 よって、ステップS1107からステップS1111が実 行され、ノード210cの、“1****”を符号化した インデックスキー250cが最長一致キーに設定� �れる。この例も、最長一致キーの定義の(b)� �該当する例である。

 元検索キーが“0****”のとき、図6のステッ� ��S603では“1****”を符号化したインデックス� ��ー250cが得られる。この場合、元検索キーの 最上位のドントケアビットの位置は1であり� �元インデックスキーの最下位の有意ビット� �位置は0なので、図9のステップS901では2が比� ��ビット長に設定され、差分ビット位置は1で ある。
 よって、図11のステップS1102からステップS11 06が実行されて、配列番号220のルートノード2 10aから弁別ビット位置230aが取り出される。� �別ビット位置230aの値は0であり、1よりも上� �である。
 よって、ステップS1107からステップS1111が実 行され、ノード210bの、“*****”を符号化した インデックスキー250bが最長一致キーに設定� �れる。この例も、最長一致キーの定義の(b)� �該当する例である。

 以上説明したとおり、上記の検索方法に� ��れば、元検索キーと元インデックスキーの� ��方にドントケアビットがあっても検索を行� ��ことができ、また、検索と選択という2段階 の処理を行うことなく、一意に定まる最長一 致キーを取得することができる。

 次に、図12~図13Cのフローチャートを参照� ��て、符号化ビット列を用いた検索用のカッ� ��ルドノードツリーに、元挿入キーの指定に� ��たがって、リーフノードを挿入する処理に� ��いて説明する。なお、ルートノードの挿入� ��理と、ルートノード以外のノードを既存の� ��ップルドノードツリーに挿入する通常の挿� ��処理によりカップルドノードツリーが生成� ��れることから、ノードの挿入処理の説明は� ��ップルドノードツリーの生成処理の説明で� ��ある。

 図12のステップS1201で、指定された元挿入キ ーから図7の符号化処理により挿入キーを作� �する。
 続いて、ステップS1202において、取得する� �とを求められたカップルドノードツリーの� �ートノードの配列番号が登録済みであるか� �かが判定される。ステップS1202での判定が登 録済みであればステップS1203へ進む。

 ステップS1203ではルートノードを検索開始� �ードに設定する。
 続いてステップS1204で、検索開始ノードよ� �開始して、挿入キーにより、カップルドノ� �ドツリーのノードを格納する配列を検索し� �挿入キーをインデックスキーとして挿入し� �(すなわち、挿入キーをインデックスキーと� ��て含むリーフノードをカップルドノードツ� ��ーに挿入して)、図12の処理を終了する。ス� ��ップS1204の処理の詳細は、図13A~図13Cを参照� ��て後述する。

 一方、ステップS1202での判定が登録済みで� �ければ、まったく新しいカップルドノード� �リーの登録、生成が始まることになる。
 この場合、処理はステップS1205に進む。ス� �ップS1205において、配列から空きのノード対 を求め、そのノード対のうち代表ノードとな るべき配列要素の配列番号を取得する。
 次にステップS1206において、ステップS1205で 得た配列番号に0を加えた配列番号を求める(� ��実施形態では、ステップS1205で取得した配� �番号に等しい配列番号がここで得られるの� �、ステップS1206は省略可能である)。
 さらにステップS1207において、挿入するル� �トノード用にステップS1206で得た配列番号の 配列要素の、ノード種別に1(リーフノード)を 書き込むとともにインデックスキーに挿入キ ーを書き込む。
 そして、ステップS1208で、ステップS1206で取 得した配列番号をルートノードの配列番号と して登録して、図12の処理を終了する。

 次に、図13A~図13Cを参照して、図12のステ� ��プS1204の処理の詳細を説明する。図13Aは挿� �処理の前段である検索処理の処理フローを� �す図であり、図4に示した検索処理において� ��入キーを検索キーとしたものにほぼ相当す� ��。

 ステップS1301は図4のステップS401で検索開 始ノードをルートノードとしたものに相当す る。また、ステップS1302~ステップS1310の処理� ��、図4のステップS402~ステップS410に完全に対 応する。よって、これらのステップの説明は 省略する。

 図4と図13Aの比較から分かるように、インデ ックスキーや挿入キーが符号化されているか 否かに関わらず、同様の処理によって検索開 始ノードからリーフノードに至る検索が行わ れる。
 なお、図13Aにおいては、探索経路スタック� ��使い方が図4と同様であり、図8や図11とは異 なることに注意されたい。本実施形態におけ る図13Aの処理では、スタックポインタは、ス テップS1302のプッシュ動作によりプッシュさ� ��た配列番号を格納する、探索経路スタック� ��の場所を指している。

 図13AのステップS1311において挿入キーと� �ンデックスキーを比較し、等しければ挿入� �ーは既にカップルドノードツリーに存在す� �のであるから、挿入は失敗となり、処理を� �了する。等しくなければ次の処理、すなわ� �図13BのステップS1312以下の処理に進む。

 図13Bは、挿入するノード対のための配列要� ��を準備する処理を説明する処理フロー図で� ��る。
 ステップS1312において、配列から空きのノ� �ド対を求め、そのノード対のうち代表ノー� �となるべき配列要素の配列番号を取得する� �
 ステップS1313に進み、挿入キーとステップS1 310で得たインデックスキーの大小を比較し、 挿入キーが大きいときは値1、小さいときは� �0のブール値を得る。
 ステップS1314に進み、ステップS1312で得た代 表ノードの配列番号にステップS1313で得たブ� ��ル値を加算した配列番号を得る。
 ステップS1315に進み、ステップS1312で得た代 表ノードの配列番号にステップS1313で得たブ� ��ル値の論理否定値を加算した配列番号を得� ��。

 ステップS1314で得た配列番号は、挿入キー� �インデックスキーとして持つリーフノード� �格納される配列要素の配列番号であり、ス� �ップS1315で得た配列番号は、そのリーフノー ドと対を成すノードが格納される配列要素の ものである。
 つまり、図13Aに示した前段の検索処理で得� ��れたリーフノードに格納されたインデック� ��キーと挿入キーの大小により、挿入される� ��ード対のうちどちらのノードに挿入キーを� ��持するリーフノードが格納されるかが、図1 3Bの処理により決定される。

 例えば、図5の(a)のカップルドノードツリー に、元挿入キー“1101*”を符号化した挿入キ� ��“1111101100”をインデックスキーとして含む リーフノードを挿入する場合、図13Aの処理に よって探索経路スタックには、配列番号220、 (220a+1)、(221b+1)、(221c+1)、221dが格納される。� �た、ステップS1310では配列番号221dのノード21 0fの“1111101000”というインデックスキー250f� �取り出されている。
 よって、ステップS1313で挿入キーとインデ� �クスキーが比較され、挿入キーの方が大き� �のでブール値1が得られ、挿入されるノード� ��の代表ノード番号に1を加えた配列要素に、 挿入キーを保持するリーフノードが格納され る。

 一方、図5の(a)のカップルドノードツリーに 、元挿入キー“0****”を符号化した挿入キー� ��1000000000”をインデックスキーとして含むリ ーフノードを挿入する場合、図13Aの処理によ って探索経路スタックには、配列番号220、(22 0a+1)、221bが格納される。また、ステップS1310� ��はノード210cの“1100000000”というインデッ� �スキー250cが取り出されている。
 よって、ステップS1313で挿入キーとインデ� �クスキーが比較され、挿入キーの方が小さ� �のでブール値0が得られ、挿入されるノード� ��の代表ノード番号に0を加えた配列要素に、 挿入キーを保持するリーフノードが格納され る。

 フローチャートの説明に戻ると、図13Bのス� ��ップS1315に続いて、図13Cの処理が実行され� �。図13Cは、図13Bで準備された配列要素にノ� �ドを格納するとともにその挿入位置を求め� �既存のノードの内容を変更して挿入処理を� �成させる処理フローを示す図である。
 ステップS1316~ステップS1323までの処理は、� �入するノード対のカップルドノードツリー� �の位置を求める処理であり、ステップS1324以 下の処理は各ノードにデータを設定して挿入 処理を完成させる処理である。

 ステップS1316で、挿入キーとステップS1310で 得たインデックスキーのビット列比較を例え ば排他的論理和で行い、差分ビット列を得る 。
 ステップS1317に進み、ステップS1316で得た差 分ビット列から、上位0ビット目から見た最� �の不一致ビットのビット位置を得る。この� �理は、例えばプライオリティエンコーダを� �するCPUではそこに差分ビット列を入力し、� �一致のビット位置を得ることができる。ま� �、ソフト的にプライオリティエンコーダと� �等の処理を行い最初の不一致ビットのビッ� �位置を得ることも可能である。

 次にステップS1318に進み、探索経路スタッ� �のスタックポインタがルートノードの配列� �号を指しているか判定する。指していれば� �テップS1324に移行し、指していなければステ ップS1319に進む。
 ステップS1319において、探索経路スタック� �スタックポインタを1つ戻してそこにスタッ� ��されている配列番号を取り出す。
 ステップS1320に進み、ステップS1319で取り出 した配列番号の配列要素を配列からノードと して読み出す。
 ステップS1321に進み、ステップS1320で読み出 したノードから、弁別ビット位置を取り出す 。
 次にステップS1322に進み、ステップS1321で取 り出した弁別ビット位置がステップS1317で得� ��ビット位置より上位の位置関係か判定する� ��ここで上位の位置関係とは、ビット列のよ� ��左側の位置、すなわちビット位置の値が小� ��い位置であることとする。

 ステップS1322の判定結果が否定であれば、� �テップS1318に戻り、ステップS1318での判定が� ��定になるかステップS1322での判定が肯定に� �るまで繰り返す。ステップS1322での判定が肯 定になると、ステップS1323で探索経路スタッ� ��のスタックポインタを1つ進め、ステップS13 24以下の処理に移行する。
 上記ステップS1316~ステップS1323で説明した� �理は、挿入するノード対の挿入位置を決定� �るために、挿入キーと図13Aの検索により取� �されたインデックスキーの間でビット列比� �を行い、ビット列比較で異なるビット値と� �る先頭の(最上位の)ビット位置と探索経路ス タックに格納されているブランチノードの弁 別ビット位置との相対的位置関係を調べ、弁 別ビット位置が上位となるブランチノードの 次のブランチノードのリンク先を挿入するノ ード対の挿入位置とするものである。

 例えば、元挿入キーが“1101*”である上記� �例の場合、インデックスキー“1111101000”と� ��入キー“1111101100”とは7ビット目で異なる� �また、1回目のステップS1319の実行により取� �出された配列番号(221c+1)が指すノード211dの� �別ビット位置231dは5であり7より上位である� �
 よって、ステップS1323によりスタックポイ� �タが1つ進められ、スタックポインタは、ノ� ��ド210fの配列番号221dを格納した探索経路ス� �ック上の場所を指すこととなる。

 また、元挿入キーが“0****”である上記の� �の場合、インデックスキー“1100000000”と挿� ��キー“1000000000”は1ビット目で異なる。
 よって、この例では、ステップS1318~ステッ� ��S1322の繰り返しにより、探索経路スタック� �積まれた配列番号の配列要素に格納された� �ランチノードの弁別ビット位置と、1という� ��ット位置との位置関係をチェックしながら� ��弁別ビット位置が上位になるまで順次探索� ��路スタックを逆にたどる。
 その結果、ステップS1322で、弁別ビット位� �230aの値が0であるルートノード210aの配列番� �220を指した状態となる。そして、ステップS1 323でスタックポインタが1つ進められ、スタ� �クポインタは、ノード211bの配列番号(220a+1)� �格納した探索経路スタック上の場所を指す� �ととなる。

 また、探索経路スタックを逆にたどりルー� ��ノードに至っても、ルートノードの弁別ビ� ��ト位置が、先に求めたビット列比較で異な� ��ビット値となる最上位のビット位置より上� ��のビット位置でないということは、そのカ� ��プルドノードツリーのインデックスキーの� ��位ビットで、ルートノードの弁別ビット位� ��より上位のビットの値は全て等しい場合で� ��る。そして、挿入キーにおいて、初めてル� ��トノードの弁別ビット位置より上位のビッ� ��の値に異なるビット値のものがあるという� ��とである。
 したがって、そのような場合には、挿入す� ��ノード対はルートノードの直接のリンク先� ��なり、ルートノードの弁別ビット位置は、� ��存のインデックスキーと異なる値である挿� ��キーの最上位ビットの位置に変わる。

 次に、ステップS1324以下の各ノードにデー� �を設定して挿入処理を完成させる処理につ� �て説明する。
 ステップS1324では探索経路スタックからス� �ックポインタの指す配列番号を取り出す。
 ステップS1325において、ステップS1314で得た 配列番号の指す配列要素のノード種別に1(リ� ��フノード)を、インデックスキーに挿入キー を書き込む。
 ステップS1326に進み、配列からステップS1324 で得た配列番号の配列要素を読み出す。
 次にステップS1327において、ステップS1315で 得た配列番号の配列要素にステップS1326で読� ��出した内容を書き込む。
 最後にステップS1328において、ステップS1324 で得た配列番号の指す配列要素のノード種別 に0(ブランチノード)を、弁別ビット位置にス テップS1317で得たビット位置を、代表ノード� ��号にステップS1312で得た配列番号を書き込� �、処理を終了する。

 元挿入キーが“1101*”である上記の例の場� �、ステップS1325で、取得された空ノード対の ノード[1]を、挿入キーを保持するリーフノー ドとする。
 一方、ノード[0]にはステップS1327でノード21 0fの内容を書き込む。そして、ステップS1328� �、ノード210fの弁別ビット位置に7を格納し、 代表ノード番号には取得されたノード対の代 表ノードが格納される配列要素の配列番号を 格納する。
 また、元挿入キーが“0****”である上記の� �の場合、ステップS1325で、取得された空ノー ド対のノード[0]を、挿入キーを保持するリー フノードとする。
 一方、ノード[1]にはステップS1327でノード21 1bの内容を書き込む。そして、ステップS1328� �、ノード211bの弁別ビット位置231bに1を格納� �、代表ノード番号には取得されたノード対� �代表ノードが格納される配列要素の配列番� �を格納する。
 先にも述べたように、インデックスキーの� ��合があるとき、そこから順次インデックス� ��ーを取り出し、図12~図13Cの処理を繰り返す� ��とにより、インデックスキーの集合に対応� ��た本発明のカップルドノードツリーを構築� ��ることができることは明らかである。

 次に、図14~図15Bを参照して、符号化ビット� ��を用いた検索用のカップルドノードツリー� ��ら、元削除キーの指定にしたがって、リー� ��ノードを削除する処理について説明する。
 図14のステップS1401で、指定された元削除キ ーから、図7の符号化処理により、削除キー� �作成する。続いて、ステップS1402で、カップ ルドノードツリーのルートノードを検索開始 ノードに設定する。そして、ステップS1403で� ��削除キーにより、検索開始ノードより開始� ��て、カップルドノードツリーのノードを格� ��する配列を検索し、削除キーと等しいイン� ��ックスキーを含むリーフノードをカップル� ��ノードツリーから削除する。

 次に、図15Aと図15Bを参照して、図14のステ� �プS1403の処理の詳細を説明する。
 図15Aは、削除処理の前段である検索処理の� ��理フローを示す図であり、図4に示した検索 処理において削除キーを検索キーとしたもの にほぼ相当する。
 ステップS1501は図4のステップS401で検索開始 ノードをルートノードとしたものに相当する 。また、ステップS1502~ステップS1510の処理は� ��図4のステップS402~ステップS410に完全に対応 する。よって、これらのステップの説明は省 略する。

 図15AのステップS1511において削除キーと� �ンデックスキーを比較し、等しくなければ� �れば削除すべきインデックスキーはカップ� �ドノードツリーに存在しないのであるから� �削除は失敗となり、処理を終了する。等し� �れば次の処理、つまり図15BのステップS1512以 下の処理に進む。

 図15Bは、削除処理の後段の処理フローを説� ��する図である。
 まず、ステップS1512で探索経路スタックに2� ��以上の配列番号が格納されているか判定す� ��。2つ以上の配列番号が格納されていないと いうことは、言い換えれば1つだけで、その� �列番号はルートノードの格納された配列要� �のものである。
 その場合はステップS1518に移行し、ステッ� �S1501で得たルートノードの配列番号に係るノ ード対を削除する。次にステップS1519に進み� ��登録されていたルートノードの配列番号を� ��除して処理を終了する。

 ステップS1512において探索経路スタックに2� ��以上の配列番号が格納されていると判定さ� ��たときはステップS1513に進み、ステップS1508 で得た代表ノード番号にステップS1507で得た� ��ット値を反転した値を加算した配列番号を� ��る。この処理は、削除対象のインデックス� ��ーが格納されたリーフノードと対をなすノ� ��ドの配置された配列番号を求めるものであ� ��。
 次にステップS1514において、ステップS1513で 得た配列番号の配列要素の内容を配列から読 み出し、ステップS1515において探索経路スタ� ��クのスタックポインタを1つ戻して配列番号 を取り出す。

 次にステップS1516に進み、ステップS1514で読 み出した配列要素の内容をステップS1515で得� ��配列番号の配列要素に上書きする。この処� ��は、削除対象のインデックスキーが格納さ� ��たリーフノードへのリンク元であるブラン� ��ノードを上記リーフノードと対をなすノー� ��に置き換えるものである。
 最後にステップS1517においてステップS1508で 得た代表ノード番号に係るノード対を削除し て処理を終了する。

 以上のとおり、削除処理は挿入処理の場� ��と同様に、インデックスキーや削除キーが� ��号化されているか否かに関わらず、図4と同 様の処理によって検索開始ノードからリーフ ノードに至る検索が行われる。また、削除処 理における探索経路スタックの使い方も、図 4と同様であり、図8や図11とは異なる。この� �において、図14~図15Bの削除処理は、図12~図13 Cの挿入処理と類似である。

 以下に、図5の(a)のカップルドノードツリー に対して、元削除キー“1011*”を指定して削� ��処理を行う場合を例に説明する。
 まず、図14のステップS1401で元削除キー“101 1*”から削除キー“1110111100”が作成され、ス テップS1403で、この削除キーを使って図15Aと� ��15Bの処理が行われる。

 図15Aの処理では最初にステップS1501でルー� �ノードの配列番号220を得る。
 続いて、図15Aの処理により探索経路スタッ� ��には、配列番号220、(220a+1)、(221b+1)、221c、(2 20d+1)がこの順にプッシュされる。そして、図 15AのステップS1511で、配列番号(220d+1)に格納� �れたノード211eのインデックスキー251eと削除 キーが比較され、両者が等しいことから図15B に進む。
 図15BのステップS1513では配列番号220dが得ら� ��、ステップS1514で配列番号220dに格納された� ��ード210eの内容が読み出される。
 続いて、ステップS1515で配列番号221cが取り� ��され、ステップS1516で配列番号221cに格納さ� ��たノード210dにノード210eの内容が書き込ま� �、ステップS1517で配列番号220dにより示され� �ノード対201eが削除され、削除処理が終了す� ��。

 以上説明したとおり、上記の挿入処理と� ��除処理において影響を受ける既存のノード� ��範囲は最小限であり、挿入や削除による保� ��コストが低いというカップルドノードツリ� ��の長所は保たれている。また、上記のよう� ��符号化方法を採用することにより、この長� ��を保ちつつ、ドントケアビットを考慮した� ��速な最長一致検索が可能となる。そして、� ��ントケアビットを考慮した高速な最長一致� ��索のために必要なコストという観点から見� ��、上記の符号化方法を、例えば特許文献3や 特許文献4で行われる煩雑な前処理と比較す� �と、上記の符号化方法のコストは格段に低� �。

 以上、本発明を実施するための最良の形態� ��ついて詳細に説明したが、本発明の実施の� ��態はそれに限ることなく種々の変形が可能� ��ある。
 上記の実施形態では、ビット値0に対応して リンクされるノード[0]を代表ノードとし、ビ ット値1に対応してリンクされるノード[1]を� �表ノードと対になる非代表ノードとしてい� �。しかし、ノード[1]を代表ノードとし、ノ� �ド[0]を非代表ノードとしてもよい。なお、� �ートノードを代表ノードの位置に配置する� �非代表ノードの位置に配置するかが任意で� �ることは、図2Bなどに関する説明から明らか であろう。

 上記の実施形態では、リーフノードのイン� ��ックスキーに、符号化ビット列が格納され� ��いる。しかし、それ以外の形式のビット列� ��リーフノードのインデックスキーとして格� ��するように上記の実施形態を変形すること� ��可能である。
 元ビット列においてドントケアビットが有� ��ビットよりも前に存在していないという前� ��条件があるため、例えば、元ビット列のう� ��有意ビットの部分のみを符号化しない形で� ��ンデックスキーとして格納することも可能� ��ある。元ビット列が固定長の場合は、この� ��うな形式のインデックスキーから、ドント� ��アビットのビット数を求めることも可能で� ��る。
 また、このような形式のインデックスキー� ��場合、元ビット列の長さは符号化ビット列� ��半分以下であるため、リーフノードに必要� ��記憶容量を半分以下に削減することが可能� ��ある。換言すれば、同じリーフノードの記� ��容量で2倍以上の長さのビット列を扱うこと が可能となる。いずれにしろ、記憶領域の利 用効率が上がる。

 なお、このような形式のインデックスキー� ��利用する実施形態では、例えば、図6のステ ップS604でインデックスキーを符号化してか� �元検索キーと比較するなど、上記の実施形� �を適宜変更する必要があることは明らかで� �る。
 あるいは、ドントケアビットに任意のビッ� ��値を設定したビット列と、有意ビットの範� ��を示すビット列(例えば、マスクビット列や 、数値を表すビット列など)との組み合わせ� �よって元ビット列を表し、その組み合わせ� �リーフノードのインデックスキーとして格� �してもよい。

 また、上記の実施形態では、符号化されて� ��ない元検索キーが入力として与えられ、検� ��処理は符号化処理を含んでいる。しかし、� ��め符号化された検索キーを入力として与え� ��れた場合には、符号化処理は不要である。� ��入処理と削除処理においても同様のことが� ��える。
 なお、符号化処理は、図7に示した方法以外 の方法によって実現することも可能である。 例えば、入力ビット列をシフトレジスタ等に よって1ビットずつシフトさせながら、1ビッ� ��ずつ入力ビット列から取り出し、取り出し� ��1ビットと識別ビットを連結する方法を採用 してもよい。

 また、上記の実施形態で採用した符号化方� ��以外の符号化方法を採用することも可能で� ��る。上記実施形態の符号化方法では、元ビ� ��ト列における1ビットを符号化ビット列にお ける2ビットに符号化しているが、このよう� �1:2の対応関係を有する符号化方法以外の符� �化方法を採用することも可能である。
 例えば、元ビット列における1ビットを符号 化ビット列における3ビットに符号化しても� �い。また、上記実施形態の符号化方法の識� �ビットは、値が0のときドントケアビットを� ��し、値が1のとき有意ビットを示すが、逆で もよい。

 なお、検索処理は、符号化方法に合わせ� ��適宜変更する必要がある。例えば、識別ビ� ��トの0と1の意味が上記実施形態と逆の符号� �方法を採用した場合は、図8のステップS812で 、ビット値が0のときステップS813に進み、ビ� ��ト値が1のときステップS809に進むように変� �し、ステップS814で代表ノード番号に加える� ��を1から0に変更する必要がある。一方、挿� �処理と削除処理は符号化方法によらず、上� �実施形態の方法を採用することが可能であ� �。

 また、上記の図5において“0****”を元検索� ��ーとしたときの最長一致キーは、“*****”� �符号化した“0000000000”だが、この場合、最� ��一致キーの元ビット列“*****”が表す集合� �、“1”から始まるビット列を包含する。し� ��し、“1”から始まるビット列と元検索キー “0****”は、最上位の0ビット目が異なってい る。検索の目的によっては、このような場合 を検索失敗として扱いたいことがある。
 そこで、最長一致キーの元ビット列は少な� ��とも0ビット目が有意ビットであり、最長一 致キーの元ビット列と元検索キーとは、少な くとも0ビット目の値が一致していなくては� �らないという制約を課すことも考えられる� �この制約を課すために、図6の処理を次のよ� ��に変形してもよい。

 すなわち、ステップS604とステップS606の間� �、求めた差分ビット位置が0ビット目か否か� ��判定する新たなステップS605を追加する。
 差分ビット位置が0ビット目のとき、上記の 制約を満たす最長一致キーはカップルドノー ドツリーに存在しないので、検索は失敗し、 図6の処理は終了する。一方、ステップS605で� ��分ビット位置が0ビット目でないときは、処 理がステップS606へ進む。

 あるいは、この変形例をさらに変形し、� ��テップS605で差分ビット位置が1以下なら処� �を終了し、差分ビット位置が2以上ならステ� ��プS606へ処理が進むようにしてもよい。

 また、常に検索キーの方がインデックス� ��ーよりも有意ビット長が長いことが保証さ� ��ているような応用分野において本発明の検� ��方法を利用する場合は、図8のステップS812� �省略し、ステップS811で弁別ビット位置が偶� ��のときステップS813に進むようにしてもよい 。

 上記の検索処理は用途に応じて他にも様々� ��変形することが可能である。例えば、図6で はステップS602でルートノードを検索開始ノ� �ドに設定しているが、任意の部分木のルー� �ノードを検索開始ノードとしてもよい。
 また、上記の各処理において探索経路スタ� ��クを利用しているが、探索経路スタックの� ��現方法は任意である。図5では、理解を容易 にするために、探索経路スタックを2列に分� �て表示しているが、この図示は探索経路ス� �ックの実現方法を限定するものではない。

 さらに、図8の処理では、処理の効率化のた めに、弁別ビット位置が偶数のブランチノー ドとその子ノードであるノード[1]の配列番号 を探索経路スタックに格納している。しかし 、挿入処理や削除処理と同様に検索開始ノー ドからリーフノードへ至る経路上のすべての ノードの配列番号を探索経路スタックに格納 してもよい。
 その場合、図11のステップS1107とステップS11 08のかわりに、探索経路スタックからブラン� ��ノードの配列番号を読み出し、その配列番� ��のブランチノードを配列から読み出して、� ��表ノード番号を取り出してもよい。取り出� ��れた代表ノード番号は、このブランチノー� ��の子ノードのうち代表ノードであるノード[ 0]の配列番号であるから、ステップS1109以降� �図11と同様に実行することが可能である。

 あるいは、図8ではステップS814で得た非終� �側ノードであるノード[1]の配列番号をステ� �プS815で探索経路スタックに格納しているが� ��ステップS815では終端側ノードであるノード [0]の配列番号を探索経路スタックに格納する ように、上記の実施形態を変形してもよい。
 ただし、その場合でも、ステップS814で配列 番号を得たノード[1]が、ステップS815の直後� �ステップS803で読み出される点は図8と同様で ある。このような変形を行う場合は、図11の� ��テップS1107とステップS1108のかわりに、ノー ド[0]の配列番号を直接探索経路スタックから 読み出すようにすればよい。

 なお、本発明の検索方法、挿入方法、ま� ��は削除方法を実行する装置が、カップルド� ��ードツリーを格納する記憶手段と、各フロ� ��チャートに示した処理をコンピュータに実� ��させるプログラムによりコンピュータ上に� ��築可能なことは明らかである。したがって� ��上記プログラム、及びプログラムを記憶し� ��コンピュータ読み取り可能な記憶媒体は、� ��発明の実施の形態に含まれる。