(57)【特許請求の範囲】
【請求項１】
ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対、からなるビット列検索に用いるツリーであって、
前記ルートノードは、ツリーの始点を表すノードであって、該ツリーのノードが１つのときは前記リーフノード、ツリーのノードが２つ以上のときは前記ブランチノードであり、
前記ブランチノードは、ビット列検索を行うための検索キーの弁別ビット位置と、リンク先のノード対の一方のノードである代表ノードの位置を示す位置情報を含み、
前記リーフノードは、検索対象のビット列からなるインデックスキーを含む、カップルドノードツリーのデータ構造に基づいてコンピュータが前記インデックスキーを検索するビット列検索方法において、
前記インデックスキーは、有意ビットのみからなるビット列、ビットの値を問わないドントケアビットのみからなるビット列、または１ビット以上の有意ビットに１ビット以上のドントケアビットが連なるビット列のいずれかである、前方有意ビット列を符号化した符号化ビット列からなり、
前記検索キーは、前方有意ビット列を符号化した符号化ビット列からなり、
前記符号化ビット列は、前記前方有意ビット列を構成する各ビットに対応するビット対であって、該ビットがドントケアビットであるか有意ビットであるかを示す識別ビットと、該ビットがドントケアビットの場合は予め決められた値であり、該ビットが有意ビットの場合は該ビットの値を示すデータビットとのビット対からなるビット列であり、
前記ビット列検索方法が、
前記カップルドノードツリーの任意の部分木のルートノードを検索開始ノードとして、前記ブランチノードにおいて該ブランチノードに含まれる弁別ビット位置の前記検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいは該代表ノードと対になる非代表ノードにリンクすることを、弁別ビット位置が、前記符号化ビット列を構成するいずれかのビット対の識別ビットであって識別対象のビットが有意ビットであることを示す識別ビットが存在する位置に一致するブランチノードのアドレス情報を少なくとも記憶することにより、リンクしてたどった経路を記憶しながら、前記リーフノードに至るまで順次繰り返す初期検索ステップと、
前記初期検索ステップで到達した前記リーフノードからインデックスキーを取得するインデックスキー取得ステップと、
前記取得した前記インデックスキーと前記検索キーとの間で、ビット列の先頭から、前記取得した前記インデックスキーにおける、末尾の有意ビットを符号化したビット対の位置と、前記検索キーにおける、先頭のドントケアビットを符号化したビット対の位置のうち、いずれか前記符号化ビット列の先頭に近いビット位置までの範囲でビット列比較し、異なるビット値となる先頭のビット位置を差分ビット位置として取得する差分ビット位置取得ステップと、
前記取得した前記インデックスキーと前記検索キーとが、前記範囲において一致するならば、前記取得した前記インデックスキーを、最長一致キーとして取得する第１の最長一致キー取得ステップと、
前記比較の結果、前記取得した前記インデックスキーと前記検索キーとが一致しないならば、弁別ビット位置が、前記符号化ビット列を構成するいずれかのビット対の識別ビットが存在する位置に一致するとともに該弁別ビット位置が前記差分ビット位置よりも前記符号化ビット列の先頭に近いビット位置である前記経路上のブランチノードのうち、前記弁別ビット位置が前記符号化ビット列の末尾に最も近いビット位置であるブランチノードを選択するブランチノード選択ステップと、
前記選択した前記ブランチノードからリンクされるノード対のうち、前記ドントケアビットを示す前記識別ビットの値に対応してリンクされるリーフノードである終端側ノードに含まれるインデックスキーを最長一致キーとして取得する第２の最長一致キー取得ステップと、
を備えることを特徴とするビット列検索方法。
【請求項２】
前記リーフノードの前記インデックスキーが、前記符号化ビット列のかわりに符号化前の前記前方有意ビット列からなり、
前記差分ビット位置取得ステップ及び前記第１の最長一致キー取得ステップでは、前記取得した前記インデックスキーのかわりに、前記取得した前記インデックスキーを符号化した符号化ビット列を前記検索キーと比較する、
ことを特徴とする請求項１記載のビット列検索方法。
【請求項３】
前記初期検索ステップにおいて前記経路を記憶する際、前記ブランチノードの前記位置情報に加えて、該ブランチノードからリンクされるノード対のうち、前記有意ビットを示す前記識別ビットの値に対応してリンクされるノードである非終端側ノードの位置を示す位置情報も記憶することを特徴とする請求項１記載のビット列検索方法。
【請求項４】
前記第２の最長一致キー取得ステップにおいて、記憶された前記非終端側ノードの前記位置情報から、該非終端側ノードとノード対をなす前記終端側ノードの位置情報を求めることを特徴とする請求項３記載のビット列検索方法。
【請求項５】
前記経路はスタックに記憶されることを特徴とする請求項１記載のビット列検索方法。
【請求項６】
前記カップルドノードツリーは配列に記憶され、前記ブランチノードに含まれる前記位置情報は、該位置情報に対応する前記代表ノードが格納された前記配列の配列要素の配列番号であることを特徴とする請求項１記載のビット列検索方法。
【請求項７】
ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対、からなるビット列検索に用いるツリーであって、
前記ルートノードは、ツリーの始点を表すノードであって、該ツリーのノードが１つのときは前記リーフノード、ツリーのノードが２つ以上のときは前記ブランチノードであり、
前記ブランチノードは、ビット列検索を行うための検索キーの弁別ビット位置と、リンク先のノード対の一方のノードである代表ノードの位置を示す位置情報を含み、
前記リーフノードは、検索対象のビット列からなるインデックスキーを含む、カップルドノードツリーに、
所望のビット列からなるインデックスキーを含むリーフノードをコンピュータが挿入する挿入方法において、
前記インデックスキーは、有意ビットのみからなるビット列、ビットの値を問わないドントケアビットのみからなるビット列、または１ビット以上の有意ビットに１ビット以上のドントケアビットが連なるビット列のいずれかである、前方有意ビット列を符号化した符号化ビット列からなり、
前記検索キーは、前方有意ビット列を符号化した符号化ビット列からなり、
前記符号化ビット列は、前記前方有意ビット列を構成する各ビットに対応するビット対であって、該ビットがドントケアビットであるか有意ビットであるかを示す識別ビットと、該ビットがドントケアビットの場合は予め決められた値であり、該ビットが有意ビットの場合は該ビットの値を示すデータビットとのビット対からなるビット列であり、
符号化ビット列である前記所望のビット列は、符号化ビット列または符号化される前の前方有意ビット列の形式で指定され、
前記挿入方法が、
前記符号化ビット列によって前記所望のビット列が指定された場合は、指定された該符号化ビット列を検索キーとし、
前記前方有意ビット列によって前記所望のビット列が指定された場合は、指定された前記前方有意ビット列を符号化して符号化ビット列を取得し、取得した該符号化ビット列を検索キーとし、
前記ブランチノードにおいて該ブランチノードに含まれる弁別ビット位置の前記検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいは該代表ノードと対になる非代表ノードにリンクすることを、前記ルートノードから順次前記リーフノードに至るまで経路を記憶しながら繰り返し、
前記リーフノードのインデックスキーと前記検索キーとの間で、大小比較とビット列比較を行い、
前記ビット列比較で異なるビット値となる先頭のビット位置である差分ビット位置と、前記経路上のブランチノードの弁別ビット位置との相対的位置関係により、挿入される前記リーフノードともう一方のノードからなるノード対の挿入位置を決定し、
前記所望のビット列からなるインデックスキーを含む前記リーフノードを、挿入される前記ノード対のどちらのノードとするかを、前記大小関係により決定する、
ことを含む方法であることを特徴とする挿入方法。
【請求項８】
前記リーフノードの前記インデックスキーが、前記符号化ビット列のかわりに前記前方有意ビット列からなり、
前記大小比較と前記ビット列比較の前に前記インデックスキーを符号化して符号化ビット列を取得し、前記リーフノードのインデックスキーと前記検索キーとの間で前記大小比較と前記ビット列比較を行うかわりに、取得した前記符号化ビット列と前記検索キーとの間で前記大小比較と前記ビット列比較を行う、
ことを特徴とする請求項７記載の挿入方法。
【請求項９】
前記カップルドノードツリーは配列に記憶され、前記ブランチノードに含まれる前記位置情報は、該位置情報に対応する前記代表ノードが格納された前記配列の配列要素の配列番号であることを特徴とする請求項７記載の挿入方法。
【請求項１０】
ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対、からなるビット列検索に用いるツリーであって、
前記ルートノードは、ツリーの始点を表すノードであって、該ツリーのノードが１つのときは前記リーフノード、ツリーのノードが２つ以上のときは前記ブランチノードであり、
前記ブランチノードは、ビット列検索を行うための検索キーの弁別ビット位置と、リンク先のノード対の一方のノードである代表ノードの位置を示す位置情報を含み、
前記リーフノードは、検索対象のビット列からなるインデックスキーを含む、カップルドノードツリーから、
所望のビット列からなるインデックスキーを含むリーフノードをコンピュータが削除する削除方法において、
前記インデックスキーは、有意ビットのみからなるビット列、ビットの値を問わないドントケアビットのみからなるビット列、または１ビット以上の有意ビットに１ビット以上のドントケアビットが連なるビット列のいずれかである、前方有意ビット列を符号化した符号化ビット列からなり、
前記検索キーは、前方有意ビット列を符号化した符号化ビット列からなり、
前記符号化ビット列は、前記前方有意ビット列を構成する各ビットに対応するビット対であって、該ビットがドントケアビットであるか有意ビットであるかを示す識別ビットと、該ビットがドントケアビットの場合は予め決められた値であり、該ビットが有意ビットの場合は該ビットの値を示すデータビットとのビット対からなるビット列であり、
符号化ビット列である前記所望のビット列は、符号化ビット列または符号化される前の前方有意ビット列の形式で指定され、
前記削除方法が、
前記符号化ビット列によって前記所望のビット列が指定された場合は、指定された該符号化ビット列を検索キーとし、
前記前方有意ビット列によって前記所望のビット列が指定された場合は、指定された前記前方有意ビット列を符号化して符号化ビット列を取得し、取得した該符号化ビット列を検索キーとし、
前記ブランチノードにおいて該ブランチノードに含まれる弁別ビット位置の前記検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいは該代表ノードと対になる非代表ノードにリンクすることを、前記ルートノードから順次前記リーフノードに至るまで繰り返し、
前記リーフノードとノード対をなすノードの内容を、当該ノード対のリンク元のブランチノードに格納し、
当該ノード対を削除する、
ことを含む方法であることを特徴とする削除方法。
【請求項１１】
前記リーフノードの前記インデックスキーが、前記符号化ビット列のかわりに前記前方有意ビット列からなることを特徴とする請求項１０記載の削除方法。
【請求項１２】
前記カップルドノードツリーは配列に記憶され、前記ブランチノードに含まれる前記位置情報は、該位置情報に対応する前記代表ノードが格納された前記配列の配列要素の配列番号であることを特徴とする請求項１０記載の削除方法。
【請求項１３】
請求項１〜６いずれか１項記載のビット列検索方法をコンピュータに実行させるためのプログラム。
【請求項１４】
請求項７〜９いずれか１項記載の挿入方法をコンピュータに実行させるためのプログラム。
【請求項１５】
請求項１０〜１２いずれか１項記載の削除方法をコンピュータに実行させるためのプログラム。
【請求項１６】
請求項１３〜１５いずれか１項記載のプログラムを記憶したことを特徴とするコンピュータ読み取り可能な記憶媒体。
【請求項１７】
ビット列検索に用いるツリー状のデータ構造であって、
ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対、からなるビット列検索に用いるツリーであって、
前記ルートノードは、ツリーの始点を表すノードであって、該ツリーのノードが１つのときは前記リーフノード、ツリーのノードが２つ以上のときは前記ブランチノードであり、
前記ブランチノードは、ビット列検索を行うための検索キーの弁別ビット位置と、リンク先のノード対の一方のノードである代表ノードの位置を示す位置情報を含み、
前記リーフノードは、検索対象のビット列からなるインデックスキーを含み、
前記インデックスキーは、有意ビットのみからなるビット列、ビットの値を問わないドントケアビットのみからなるビット列、もしくは１ビット以上の有意ビットに１ビット以上のドントケアビットが連なるビット列のいずれかである、前方有意ビット列、または該前方有意ビット列を符号化した符号化ビット列からなり、
前記検索キーは、前方有意ビット列を符号化した符号化ビット列からなり、
前記符号化ビット列は、前記前方有意ビット列を構成する各ビットに対応するビット対であって、該ビットがドントケアビットであるか有意ビットであるかを示す識別ビットと、該ビットがドントケアビットの場合は予め決められた値であり、該ビットが有意ビットの場合は該ビットの値を示すデータビットとのビット対からなるビット列であり、
コンピュータが、
前記カップルドノードツリーの任意の部分木のルートノードを検索開始ノードとして、前記ブランチノードにおいて該ブランチノードに含まれる弁別ビット位置の前記検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいは該代表ノードと対になる非代表ノードにリンクすることを、弁別ビット位置が、前記符号化ビット列を構成するいずれかのビット対の識別ビットであって識別対象のビットが有意ビットであることを示す識別ビットが存在する位置に一致するブランチノードのアドレス情報を少なくとも記憶することにより、リンクしてたどった経路を記憶しながら、前記リーフノードに至るまで順次繰り返す初期検索ステップと、
前記初期検索ステップで到達した前記リーフノードからインデックスキーを取得するインデックスキー取得ステップと、
前記取得した前記インデックスキーと前記検索キーとの間で、ビット列の先頭から、前記取得した前記インデックスキーにおける、末尾の有意ビットを符号化したビット対の位置と、前記検索キーにおける、先頭のドントケアビットを符号化したビット対の位置のうち、いずれか前記符号化ビット列の先頭に近いビット位置までの範囲でビット列比較し、異なるビット値となる先頭のビット位置を差分ビット位置として取得する差分ビット位置取得ステップと、
前記取得した前記インデックスキーと前記検索キーとが、前記範囲において一致するならば、前記取得した前記インデックスキーを、最長一致キーとして取得する第１の最長一致キー取得ステップと、
前記比較の結果、前記取得した前記インデックスキーと前記検索キーとが一致しないならば、弁別ビット位置が、前記符号化ビット列を構成するいずれかのビット対の識別ビットが存在する位置に一致するとともに該弁別ビット位置が前記差分ビット位置よりも前記符号化ビット列の先頭に近いビット位置である前記経路上のブランチノードのうち、前記弁別ビット位置が前記符号化ビット列の末尾に最も近いビット位置であるブランチノードを選択するブランチノード選択ステップと、
前記選択した前記ブランチノードからリンクされるノード対のうち、前記ドントケアビットを示す前記識別ビットの値に対応してリンクされるリーフノードである終端側ノードに含まれるインデックスキーを最長一致キーとして取得する第２の最長一致キー取得ステップとを備えるビット列検索方法を実行すること、
を可能とするデータ構造。
【請求項１８】
前記データ構造は配列に記憶され、前記ブランチノードが含む前記位置情報は、該位置情報に対応する前記代表ノードが格納された前記配列の配列要素の配列番号であることを特徴とする請求項１７記載のデータ構造。
【請求項１９】
請求項１７又は請求項１８記載のデータ構造を記憶したことを特徴とするコンピュータ読み取り可能な記憶媒体。
【請求項２０】
ビット列検索装置において、
ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対、からなるビット列検索に用いるツリーであって、前記ルートノードは、ツリーの始点を表すノードであって、該ツリーのノードが１つのときは前記リーフノード、ツリーのノードが２つ以上のときは前記ブランチノードであり、前記ブランチノードは、ビット列検索を行うための検索キーの弁別ビット位置と、リンク先のノード対の一方のノードである代表ノードの位置を示す位置情報を含み、前記リーフノードは、検索対象のビット列からなるインデックスキーを含む、カップルドノードツリーであって、
前記インデックスキーは、有意ビットのみからなるビット列、ビットの値を問わないドントケアビットのみからなるビット列、または１ビット以上の有意ビットに１ビット以上のドントケアビットが連なるビット列のいずれかである、前方有意ビット列を符号化した符号化ビット列からなり、
前記符号化ビット列は、前記前方有意ビット列を構成する各ビットに対応するビット対であって、該ビットがドントケアビットであるか有意ビットであるかを示す識別ビットと、該ビットがドントケアビットの場合は予め決められた値であり、該ビットが有意ビットの場合は該ビットの値を示すデータビットとのビット対からなるビット列であるカップルドノードツリーと、
前記カップルドノードツリーの任意の部分木のルートノードを検索開始ノードとして、前記ブランチノードにおいて、前方有意ビット列を符号化した符号化ビット列からなる前記検索キーの該ブランチノードに含まれる弁別ビット位置のビット値に応じてリンク先のノード対の代表ノードかあるいは該代表ノードと対になる非代表ノードにリンクすることを、弁別ビット位置が、前記符号化ビット列を構成するいずれかのビット対の識別ビットであって識別対象のビットが有意ビットであることを示す識別ビットが存在する位置に一致するブランチノードのアドレス情報を少なくとも記憶することにより、リンクしてたどった経路を記憶しながら、前記リーフノードに至るまで順次繰り返す初期検索手段と、
前記初期検索手段により到達した前記リーフノードからインデックスキーを取得するインデックスキー取得手段と、
前記取得した前記インデックスキーと前記検索キーとの間で、ビット列の先頭から、前記取得した前記インデックスキーにおける、末尾の有意ビットを符号化したビット対の位置と、前記検索キーにおける、先頭のドントケアビットを符号化したビット対の位置のうち、いずれか前記符号化ビット列の先頭に近いビット位置までの範囲でビット列比較し、異なるビット値となる先頭のビット位置を差分ビット位置として取得する差分ビット位置取得手段と、
前記取得した前記インデックスキーと前記検索キーとが、前記範囲において一致するならば、前記取得した前記インデックスキーを、最長一致キーとして取得する第１の最長一致キー取得手段と、
前記比較の結果、前記取得した前記インデックスキーと前記検索キーとが一致しないならば、弁別ビット位置が、前記符号化ビット列を構成するいずれかのビット対の識別ビットが存在する位置に一致するとともに該弁別ビット位置が前記差分ビット位置よりも前記符号化ビット列の先頭に近いビット位置である前記経路上のブランチノードのうち、前記弁別ビット位置が前記符号化ビット列の末尾に最も近いビット位置であるブランチノードを選択するブランチノード選択手段と、
前記選択した前記ブランチノードからリンクされるノード対のうち、前記ドントケアビットを示す前記識別ビットの値に対応してリンクされるリーフノードである終端側ノードに含まれるインデックスキーを最長一致キーとして取得する第２の最長一致キー取得手段と、
を備えることを特徴とするビット列検索装置。
【請求項２１】
前記リーフノードの前記インデックスキーが、前記符号化ビット列のかわりに符号化前の前記前方有意ビット列からなり、
前記差分ビット位置取得手段及び前記第１の最長一致キー取得手段は、前記取得した前記インデックスキーのかわりに、前記取得した前記インデックスキーを符号化した符号化ビット列を前記検索キーと比較する、
ことを特徴とする請求項２０記載のビット列検索装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ビット列を記憶するツリー状のデータ構造を用いてビット列の集合から所望のビット列を検索する技術に関するものである。
【背景技術】
【０００２】
近年、社会の情報化が進展し、大規模なデータベースが各所で利用されるようになってきている。このような大規模なデータベースからレコードを検索するには、各レコードの記憶されたアドレスと対応づけられたレコード内の項目をインデックスキーとして検索をし、所望のレコードを探し出すことが通例である。また、全文検索における文字列も、文書のインデックスキーと見なすことができる。
【０００３】
そして、それらのインデックスキーはビット列で表現されることから、データベースの検索はビット列の検索に帰着されるということができる。
上記ビット列の検索を高速に行うために、ビット列を記憶するデータ構造を種々に工夫することが従来から行われている。このようなものの一つとして、パトリシアツリーという木構造が知られている。
【０００４】
図１６は、上述の従来の検索処理に用いられているパトリシアツリーの一例を示すものである。パトリシアツリーのノードは、インデックスキー、検索キーの検査ビット位置、左右のリンクポインタを含んで構成される。明示はされていないが、ノードにはインデックスキーに対応するレコードにアクセスするための情報が含まれていることは勿論である。
【０００５】
図１６の例では、インデックスキー“１０００１０”を保持するノード１７５０ａがルートノードとなっており、その検査ビット位置１７３０ａは０である。ノード１７５０ａの左リンク１７４０ａにはノード１７５０ｂが接続され、右リンク１７４１ａにはノード１７５０ｆが接続されている。
【０００６】
ノード１７５０ｂの保持するインデックスキーは“０１００１１”であり、検査ビット位置１７３０ｂは１である。ノード１７５０ｂの左リンク１７４０ｂにはノード１７５０ｃが、右リンク１７４１ｂにはノード１７５０ｄが接続されている。ノード１７５０ｃが保持するインデックスキーは“０００１１１”、検査ビット位置１７３０ｃは３である。ノード１７５０ｄが保持するインデックスキーは“０１１０１０”、検査ビット位置１７３０ｄは２である。
【０００７】
ノード１７５０ｃから実線で接続された部分はノード１７５０ｃの左右のリンクポインタを示すものであり、点線の接続されていない左ポインタ１７４０ｃは、その欄が空欄であることを示している。点線の接続された右ポインタ１７４１ｃの点線の接続先は、ポインタの示すアドレスを表しており、今の場合ノード１７５０ｃを右ポインタ１７４１ｃが指定していることを表している。
【０００８】
ノード１７５０ｄの右ポインタ１７４１ｄはノード１７５０ｄ自身を指しており、左リンク１７４０ｄにはノード１７５０ｅが接続されている。ノード１７５０ｅの保持するインデックスキーは“０１００１０”、検査ビット位置１７３０ｅは５である。ノード１７５０ｅの左ポインタ１７４０ｅはノード１７５０ｂを、右ポインタ１７４１ｅはノード１７５０ｅを指している。
【０００９】
また、ノード１７５０ｆの保持するインデックスキーは“１０１０１１”であり、検査ビット位置１７３０ｆは２である。ノード１７５０ｆの左リンク１７４０ｆにはノード１７５０ｇが、右リンク１７４１ｆにはノード１７５０ｈが接続されている。
【００１０】
ノード１７５０ｇの保持するインデックスキーは“１０００１１”であり、検査ビット位置１７３０ｇは５である。ノード１７５０ｇの左ポインタ１７４０ｇはノード１７５０ａを、右ポインタ１７４１ｇはノード１７５０ｇを指している。
【００１１】
ノード１７５０ｈの保持するインデックスキーは“１０１１００”であり、検査ビット位置１７３０ｈは３である。ノード１７５０ｈの左ポインタ１７４０ｈはノード１７５０ｆを、右ポインタ１７４１ｈはノード１７５０ｈを指している。
【００１２】
図１６の例では、ルートノード１７５０ａからツリーを降りるにしたがって、各ノードの検査ビット位置が大きくなるように構成されている。
ある検索キーで検索を行うとき、ルートノードから順次各ノードに保持される検索キーの検査ビット位置を検査していき、検査ビット位置のビット値が１であるか０であるか判定を行い、１であれば右リンクをたどり、０であれば左リンクをたどる。そして、リンク先のノードの検査ビット位置がリンク元のノードの検査ビット位置より大きくなければ、すなわち、リンク先が下方でなく上方に戻れば（図１６において点線で示されたこの逆戻りのリンクをバックリンクという）、リンク先のノードのインデックスキーと検索キーの比較を行う。比較の結果、等しければ検索成功であり、等しくなければ検索失敗であることが保証されている。
【００１３】
上記のように、パトリシアツリーを用いた検索処理では、必要なビットの検査だけで検索できること、キー全体の比較は１回ですむことなどのメリットがあるが、各ノードからの２つのリンクが必ずあることにより記憶容量が増大することや、バックリンクの存在による判定処理の複雑化、バックリンクにより戻ることで初めてインデックスキーと比較することによる検索処理の遅延及び追加削除等データメンテナンスの困難性などの欠点がある。
【００１４】
これらのパトリシアツリーの欠点を解消しようとするものとして、例えば下記特許文献１に開示された技術がある。下記特許文献１に記載されたパトリシアツリーにおいては、下位の左右のノードは連続した領域に記憶することによりポインタの記憶容量を削減するとともに、次のリンクがバックリンクであるか否かを示すビットを各ノードに設けることにより、バックリンクの判定処理を軽減している。
【００１５】
しかしながら、下記特許文献１に開示されたものにおいても、１つのノードは必ずインデックスキーの領域とポインタの領域を占めること、下位の左右のノードを連続した領域に記憶するようにしてポインタを１つとしたため、例えば図１６に示したパトリシアツリーの最下段の部分である左ポインタ１７４０ｃ、右ポインタ１７４１ｈ等の部分にもノードと同じ容量の記憶領域を割り当てる必要があるなど、記憶容量の削減効果はあまり大きいものではない。また、バックリンクによる検索処理の遅延の問題や追加削除等の処理が困難であることも改善されていない。
【００１６】
上述の従来の検索手法における問題点を解決するものとして、本出願人は、特願２００６−１８７８２７において、ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対からなるビット列検索に用いるツリーであって、ルートノードはツリーの始点を表すノードであって、該ツリーのノードが１つのときはリーフノード、ツリーのノードが２つ以上のときは前記ブランチノードであり、前記ブランチノードは、ビット列検索を行う検索キーの弁
別ビット位置とリンク先のノード対の一方のノードである代表ノードの位置を示す位置情報を含み、前記リーフノードは検索対象のビット列からなるインデックスキーを含むカップルドノードツリーを用いたビット列検索を提案した。
【００１７】
上記出願においては、与えられたインデックスキーの集合からカップルドノードツリーを生成する方法と、カップルドノードツリーから単一のインデックスキーを検索する手法等の、カップルドノードツリーを用いた基本的な検索手法が示されている。また、カップルドノードツリーの構成が、インデックスキーの集合により一意に規定されることと、カップルドノードツリー上に、インデックスキーがソートされて配置されていることも説明されている。
【００１８】
また、ビット列の検索には、最小値、最大値を求める、ある範囲の値のものを求める等の各種の検索要求が存在する。そこで、本出願人は、特願２００６−２９３６１９において、カップルドノードツリーの任意の部分木に含まれるインデックスキーの最大値／最小値を求める手法及びカップルドノードツリーに格納されたインデックスキーを昇順または降順に取り出す手法等を提案した。
【００１９】
さらに、検索キーとして与えられたビット列と完全に一致するインデックスキーが存在しなくても、検索キーと一部が一致するインデックスキーが存在するならそのインデックスキーを検索結果として取得したいという検索要求も存在する。そこで、本出願人は、特願２００７−１３２２８９において、カップルドノードツリーを用いた最長一致検索と最短一致検索の手法を提案した。
【００２０】
また、上記各出願において、カップルドノードツリーを配列に配置すること、上記提案した各検索処理における検索開始ノードからのツリー上の探索経路のノードの配列番号を探索経路スタックに順次スタックし、探索経路スタックにスタックされた配列番号を用いた処理も開示した。
【００２１】
一方で、ビット列を扱う処理によっては、一部のビットを、有意なものとして扱わないドントケアビットとして扱いたい場合がある。例えば、ルータにおけるルーティングテーブルの検索では、ＩＰ（Internet Protocol）アドレスを表すビット列のうち、ネットワークアドレスの部分を有意ビットとして扱い、ホストアドレスの部分をドントケアビットとして扱うことが望まれる。
【００２２】
特許文献２には、パトリシアツリーを用いた最長一致検索を高速化する最長一致検索回路について記載されており、パトリシアツリーのノードとドントケアビットを含むビット列との対応関係を図示している。また、その最長一致検索回路がルーティングテーブル検索システムに適していることも特許文献２には記載されている。
【００２３】
一方で、ＩＰアドレスだけではなく、各種の分類コードなどにおいても、ビット列の値とビット列が表す内容の階層的な分類とが対応し、より上位のビットがより上位の分類を表すことがある。このようなビット列を使った検索においては、下位の一部のビットがドントケアビットであるビット列を検索キーとして検索を行いたい場合がある。
【００２４】
なぜなら、検索キーとして指定されたビット列に相当する分類がインデックスキーとして存在するか否か、存在しない場合は、検索キーとして指定されたビット列に相当する分類を包含する上位の分類のうちで最下位の分類、すなわち検索キーが表す分類に最も近い分類は何か、ということを知りたいことがあるためである。
【００２５】
このように、ドントケアビットを考慮しつつ、最長一致検索を行うことが望まれる。ま
た、一般の文字列検索などにおいても、検索キーとして用いるビット列と、検索の対象であるインデックスキーの双方がドントケアビットを含むことを許す検索によって、より柔軟な検索を実現することが求められる。
【００２６】
一方で、最長一致検索を高速に行うための既存の手法は、煩雑な前処理を必要とし、データの保守にかかるコストが大きい。ドントケアビットを考慮した最長一致検索が可能であり、検索が高速で、保守にかかるコストが低いというすべての条件を満たす手法は知られていない。
【００２７】
例えば、特許文献３に記載のＩＰアドレス検索テーブル作成方法では、第１のエントリのＩＰアドレスの範囲が第２のエントリのＩＰアドレスの範囲を含む場合に、第１のエントリを、第１のエントリに包含される第３と第４のエントリに分解し、第１のエントリを消去する。そして、第３と第４のエントリをそれぞれ第２のエントリと比較して、一致した分解エントリを消去する。
【００２８】
分解は、サブネットマスクで値が“１”となる範囲を１ビットずつ増やしながら、分解エントリが第２のエントリと一致するまで繰り返し行われる。分解によって、２つのエントリ間の包含関係が解消されるので、ハードウェアによる高速検索装置において、常に正しく最長一致検索を実行することが可能となる。しかし、エントリの追加や削除のたびに、包含関係が変動するため、データの保守にかかるコストが高い。
【００２９】
また、特許文献４には、自然言語処理における単語辞書等の最長一致検索を高速化する方法が記載されている。この方法では、まずレコード群をキー項目（辞書に登録する単語）で昇順にソートする。そして、各レコードに対し、当該レコードよりも前のレコードで、当該レコードのキー項目と最長一致するキー項目を持つレコードの番号を「次ポインタ」として設定する。
【００３０】
このように次ポインタが設定された辞書を使うと、検索キーワードを使ってバイナリ・サーチを行い、その検索結果のレコード中のキー項目と検索キーワードを比較し、不一致ならば次ポインタを順次たどっていくことにより、最長一致検索を行うことが可能である。これにより、バイナリ・サーチの高速性を活かしつつ、最長一致検索を可能としている。しかし、レコードの追加や削除のたびに、レコード番号や次ポインタを設定しなおす必要がある。
【特許文献１】特開２００１−３５７０７０号公報
【特許文献２】特開２００３−２２４５８１号公報
【特許文献３】特開平１１−１０３３１８号公報
【特許文献４】特開平１０−１７７５８２号公報
【発明の開示】
【発明が解決しようとする課題】
【００３１】
そこで本発明の目的は、高速な検索が可能でありデータの保守にかかるコストが低いというカップルドノードツリーの長所を活かしつつ、ドントケアビットが有意ビットよりも上位の位置に存在しないという前提のもとで、ドントケアビットを含むビット列を使って、ドントケアビットを含むビット列を表すインデックスキーを含むカップルドノードツリーを検索することを可能とすることである。
【課題を解決するための手段】
【００３２】
本発明によれば、以下のデータ構造を持つカップルドノードツリーが提供され、そのカップルドノードツリーを用いて検索が行われる。また、本発明によれば、指定されたビット列に対応するリーフノードの挿入や削除をそのカップルドノードツリーに対して行う方
法が提供される。
【００３３】
本発明のカップルドノードツリーは、ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対、からなるビット列検索に用いるツリーである。
【００３４】
前記ルートノードは、ツリーの始点を表すノードであって、該ツリーのノードが１つのときは前記リーフノード、ツリーのノードが２つ以上のときは前記ブランチノードである。
【００３５】
前記ブランチノードは、ビット列検索を行うための検索キーの弁別ビット位置と、リンク先のノード対の一方のノードである代表ノードの位置を示す位置情報を含み、前記リーフノードは、検索対象のビット列からなるインデックスキーを含む。
【００３６】
また、前記インデックスキーは、有意ビットのみからなるビット列、ビットの値を問わないドントケアビットのみからなるビット列、または１ビット以上の有意ビットに１ビット以上のドントケアビットが連なるビット列のいずれかである、前方有意ビット列を符号化した符号化ビット列からなる。
【００３７】
前記検索キーは、前方有意ビット列を符号化した符号化ビット列からなる。
前記符号化ビット列は、前記前方有意ビット列を構成する各ビットに対応するビット対であって、該ビットがドントケアビットであるか有意ビットであるかを示す識別ビットと、該ビットがドントケアビットの場合は予め決められた値であり、該ビットが有意ビットの場合は該ビットの値を示すデータビットとのビット対からなるビット列である。
【００３８】
符号化前の前方有意ビット列を元ビット列という場合もあり、符号化ビット列であるインデックスキーや検索キーに対応する、符号化される前の前方有意ビット列を、それぞれ元インデックスキーや元検索キーという場合もある。
【００３９】
このようなカップルドノードツリーの検索は、次のようにして行われる。
まず、初期検索ステップにおいて、前記カップルドノードツリーの任意の部分木のルートノードを検索開始ノードとして、前記ブランチノードにおいて該ブランチノードに含まれる弁別ビット位置の前記検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいは該代表ノードと対になる非代表ノードにリンクすることを、前記符号化ビット列において識別ビットが存在する位置に前記弁別ビット位置が相当するブランチノードのアドレス情報を少なくとも記憶することにより、リンクしてたどった経路を記憶しながら、前記リーフノードに至るまで順次繰り返す。
【００４０】
そして、インデックスキー取得ステップにおいて、前記初期検索ステップで到達した前記リーフノードからインデックスキーを取得する。
続いて差分ビット位置取得ステップにおいて、前記取得した前記インデックスキーと前記検索キーとの間で、ビット列の先頭から、前記取得した前記インデックスキーにおける、末尾の有意ビットを符号化したビット対の位置と、前記検索キーにおける、先頭のドントケアビットを符号化したビット対の位置のうち、いずれか前記符号化ビット列の先頭に近いビット位置までの範囲でビット列比較し、異なるビット値となる先頭のビット位置を差分ビット位置として取得する。
【００４１】
そして、第１の最長一致キー取得ステップにおいて、前記取得した前記インデックスキーと前記検索キーとが、前記範囲において一致するならば、前記取得した前記インデックスキーを、最長一致キーとして取得する。
【００４２】
前記比較の結果、前記取得した前記インデックスキーと前記検索キーとが一致しないならば、ブランチノード選択ステップで、前記符号化ビット列において識別ビットが存在する位置に弁別ビット位置が相当するとともに該弁別ビット位置が前記差分ビット位置よりも前記符号化ビット列の先頭に近いビット位置の、前記経路上のブランチノードのうち、前記弁別ビット位置が前記符号化ビット列の末尾に最も近いビット位置であるブランチノードを選択する。そして、第２の最長一致キー取得ステップで、前記選択した前記ブランチノードからリンクされるノード対のうち、前記ドントケアビットを示す前記識別ビットの値に対応してリンクされるリーフノードである終端側ノードに含まれるインデックスキーを最長一致キーとして取得する。
【００４３】
なお、前記リーフノードの前記インデックスキーが、前記符号化ビット列のかわりに符号化前の前記前方有意ビット列からなっていてもよい。
その場合、前記差分ビット位置取得ステップ及び前記第１の最長一致キー取得ステップでは、前記取得した前記インデックスキーのかわりに、前記取得した前記インデックスキーを符号化した符号化ビット列を前記検索キーと比較する。
【００４４】
また、符号化ビット列または符号化される前の前方有意ビット列の形式で指定された、符号化ビット列である所望のビット列からなるインデックスキーを含むリーフノードを前記カップルドノードツリーに挿入するには、次の処理を行う。
【００４５】
まず、前記符号化ビット列によって前記所望のビット列が指定された場合は、指定された該符号化ビット列を検索キーとし、前記前方有意ビット列によって前記所望のビット列が指定された場合は、指定された前記前方有意ビット列を符号化して符号化ビット列を取得し、取得した該符号化ビット列を検索キーとする。
【００４６】
そして、前記ブランチノードにおいて該ブランチノードに含まれる弁別ビット位置の前記検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいは該代表ノードと対になる非代表ノードにリンクすることを、前記ルートノードから順次前記リーフノードに至るまで経路を記憶しながら繰り返す。
【００４７】
続いて、前記リーフノードのインデックスキーと前記検索キーとの間で、大小比較とビット列比較を行う。
さらに、前記ビット列比較で異なるビット値となる先頭のビット位置である差分ビット位置と、前記経路上のブランチノードの弁別ビット位置との相対的位置関係により、挿入される前記リーフノードともう一方のノードからなるノード対の挿入位置を決定する。
【００４８】
その後、前記所望のビット列からなるインデックスキーを含む前記リーフノードを、挿入される前記ノード対のどちらのノードとするかを、前記大小関係により決定する。
なお、前記リーフノードの前記インデックスキーが、前記符号化ビット列のかわりに前記前方有意ビット列からなっていてもよい。
【００４９】
その場合、前記大小比較と前記ビット列比較の前に前記インデックスキーを符号化して符号化ビット列を取得し、前記リーフノードのインデックスキーと前記検索キーとの間で前記大小比較と前記ビット列比較を行うかわりに、取得した前記符号化ビット列と前記検索キーとの間で前記大小比較と前記ビット列比較を行う。
【００５０】
また、符号化ビット列または符号化される前の前方有意ビット列の形式で指定された、符号化ビット列である所望のビット列を表すインデックスキーを含むリーフノードを前記カップルドノードツリーから削除するには、次の処理を実行する。
【００５１】
まず、前記符号化ビット列によって前記所望のビット列が指定された場合は、指定された該符号化ビット列を検索キーとし、前記前方有意ビット列によって前記所望のビット列が指定された場合は、指定された前記前方有意ビット列を符号化して符号化ビット列を取得し、取得した該符号化ビット列を検索キーとする。
【００５２】
そして、前記ブランチノードにおいて該ブランチノードに含まれる弁別ビット位置の前記検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいは該代表ノードと対になる非代表ノードにリンクすることを、前記ルートノードから順次前記リーフノードに至るまで繰り返す。
【００５３】
続いて、前記リーフノードとノード対をなすノードの内容を、当該ノード対のリンク元のブランチノードに格納する。そして、当該ノード対を削除する。
また、本発明によれば、上記の検索方法、挿入方法、及び削除方法をコンピュータに実行させるプログラムも提供される。
【発明の効果】
【００５４】
ドントケアビットの値は一意に決められず、一意に値が決められないビットに基づいてブランチノードでリンク先を一意に決めることはできない。そこで本発明では、上記のように符号化された検索キーを利用している。
【００５５】
本発明によれば、符号化される前の前方有意ビット列におけるドントケアビットも、符号化ビット列である検索キーにおいては一意な値を持つビットに符号化されている。また、リーフノードに含まれるインデックスキーが、符号化ビット列であるか符号化される前の前方有意ビット列であるかによらず、本発明では、ブランチノードの弁別ビット位置は、符号化された状態におけるビットの位置を表している。
【００５６】
よって、検索キーの元となった符号化前の前方有意ビット列がドントケアビットを含むとしても、本発明によれば、ブランチノードにおいてリンク先を一意に決め、検索を行うことが可能である。
【００５７】
また、本発明の検索方法によって最長一致キーとして取得されるインデックスキーは、検索キーの元となった符号化前の前方有意ビット列のドントケアビットが具体的にどのような値を取ろうとも、ドントケアビットに値が設定されたそのビット列を常に包含するビット列の集合を表す。
【００５８】
よって、本発明のカップルドノードツリーは、ドントケアビットを含むビット列を使う検索に好適である。
また、上記の挿入方法により本発明のカップルドノードツリーを生成することができ、上記の挿入方法と削除方法により本発明のカップルドノードツリーを保守することができる。
【００５９】
さらに、本発明によるカップルドノードツリーは、ノード対から構成され、ブランチノードが弁別ビット位置と位置情報を含み、リーフノードがインデックスキーを含むという点で、先の出願のカップルドノードツリーと構成が類似している。先の出願のカップルドノードツリーと類似しているこれらの構成は、高速な検索を可能とし、挿入や削除を低コストで行うことができるという、カップルドノードツリーの特徴の要因となる構成でもある。
【００６０】
したがって、本発明によれば、検索が高速であり、ノードの挿入や削除にかかる計算コ
ストが低いという長所を受け継ぎつつ、ドントケアビットを含むビット列を使った検索に好適なカップルドノードツリーが提供される。
【発明を実施するための最良の形態】
【００６１】
最初に、本出願人により先の上記出願において提案された、本発明の前提となるカップルドノードツリーについて、カップルドノードツリーを配列に格納する例を説明する。ブランチノードが保持するリンク先の位置を示すデータとして、記憶装置のアドレス情報とすることもできるが、ブランチノードあるいはリーフノードのうち占有する領域の記憶容量の大きい方を格納可能な配列要素からなる配列を用いることにより、ノードの位置を配列番号で表すことができ、位置情報の情報量を削減することができる。
【００６２】
図１は、配列に格納されたカップルドノードツリーの構成例を説明する図である。
図１を参照すると、ノード１０１が配列１００の配列番号１０の配列要素に配置されている。ノード１０１はノード種別１０２、弁別ビット位置１０３及び代表ノード番号１０４で構成されている。ノード種別１０２は０であり、ノード１０１がブランチノードであることを示している。弁別ビット位置１０３には１が格納されている。代表ノード番号１０４にはリンク先のノード対の代表ノードの配列番号２０が格納されている。なお、以下では表記の簡略化のため、代表ノード番号に格納された配列番号を代表ノード番号ということもある。また、代表ノード番号に格納された配列番号をそのノードに付した符号あるいはノード対に付した符号で表すこともある。
【００６３】
配列番号２０の配列要素には、ノード対１１１の代表ノードであるノード［０］１１２が格納されている。そして隣接する次の配列要素（配列番号２０＋１）に代表ノードと対になるノード［１］１１３が格納されている。ノード［０］１１２のノード種別１１４には０が、弁別ビット位置１１５には３が、代表ノード番号１１６には３０が格納されている。またノード［１］１１３のノード種別１１７には１が格納されており、ノード［１］１１３がリーフノードであることを示している。インデックスキー１１８には、“０００１”が格納されている。パトリシアツリーについて先に述べたと同様に、リーフノードにインデックスキーと対応するレコードにアクセスする情報が含まれることは当然であるが、表記は省略している。
【００６４】
なお、代表ノードをノード［０］で表し、それと対になるノードをノード［１］で表すことがある。また、ある配列番号の配列要素に格納されたノードを、その配列番号のノードということがあり、ノードの格納された配列要素の配列番号を、ノードの配列番号ということもある。
【００６５】
配列番号３０及び３１の配列要素に格納されたノード１２２とノード１２３からなるノード対１２１の内容は省略されている。
ノード［０］１１２、ノード［１］１１３、ノード１２２、及びノード１２３の格納された配列要素にそれぞれ付された０あるいは１は、検索キーで検索を行う場合にノード対のどちらのノードにリンクするかを示すものである。前段のブランチノードの弁別ビット位置にある検索キーのビット値である０か１を代表ノード番号に加えた配列番号のノードにリンクする。
【００６６】
したがって、前段のブランチノードの代表ノード番号に、検索キーの弁別ビット位置のビット値を加えることにより、リンク先のノードが格納された配列要素の配列番号を求めることができる。
【００６７】
なお、上記の例では代表ノード番号をノード対の配置された配列番号のうち小さい方を採用しているが、大きいほうを採用することも可能であることは明らかである。
図２は、カップルドノードツリーのツリー構造を概念的に示す図である。図示の６ビットのインデックスキーは、図１６に例示されたパトリシアツリーのものと同じである。
【００６８】
符号２１０ａで示すのがルートノードである。図示の例では、ルートノード２１０ａは配列番号２２０に配置されたノード対２０１ａの代表ノードとしている。
ツリー構造としては、ルートノード２１０ａの下にノート対２０１ｂが、その下層にノード対２０１ｃとノード対２０１ｆが配置され、ノード対２０１ｆの下層にはノード対２０１ｈとノード対２０１ｇが配置されている。ノード対２０１ｃの下にはノード対２０１ｄが、さらにその下にはノード対２０１ｅが配置されている。
【００６９】
各ノードの前に付された０あるいは１の符号は、図１において説明した配列要素の前に付された符号と同じである。検索キーの弁別ビット位置のビット値に応じてツリーをたどり、検索対象のリーフノードを見つけることになる。
【００７０】
図示された例では、ルートノード２１０ａのノード種別２６０ａは０でブランチノードであることを示し、弁別ビット位置２３０ａは０を示している。代表ノード番号は２２０ａであり、それはノード対２０１ｂの代表ノード２１０ｂの格納された配列要素の配列番号である。
【００７１】
ノード対２０１ｂはノード２１０ｂと２１１ｂで構成され、それらのノード種別２６０ｂ、２６１ｂはともに０であり、ブランチノードであることを示している。ノード２１０ｂの弁別ビット位置２３０ｂには１が格納され、リンク先の代表ノード番号にはノード対２０１ｃの代表ノード２１０ｃの格納された配列要素の配列番号２２０ｂが格納されている。
【００７２】
ノード２１０ｃのノード種別２６０ｃには１が格納されているので、このノードはリーフノードであり、したがって、インデックスキー２５０ｃを含んでいる。インデックスキー２５０ｃには“０００１１１”が格納されている。一方ノード２１１ｃのノード種別２６１ｃは０、弁別ビット位置２３１ｃは２であり、代表ノード番号にはノード対２０１ｄの代表ノード２１０ｄの格納された配列要素の配列番号２２１ｃが格納されている。
【００７３】
ノード２１０ｄのノード種別２６０ｄは０、弁別ビット位置２３０ｄは５であり、代表ノード番号にはノード対２０１ｅの代表ノード２１０ｅの格納された配列要素の配列番号２２０ｄが格納されている。ノード２１０ｄと対になるノード２１１ｄのノード種別２６１ｄは１であり、インデックスキー２５１ｄには“０１１０１０”が格納されている。
【００７４】
ノード対２０１ｅのノード２１０ｅ、２１１ｅのノード種別２６０ｅ、２６１ｅはともに１であり双方ともリーフノードであることを示し、それぞれのインデックスキー２５０ｅ、２５１ｅにはインデックスキーとして“０１００１０”と“０１００１１”が格納されている。
【００７５】
ノード対２０１ｂのもう一方のノードであるノード２１１ｂの弁別ビット位置２３１ｂには２が格納され、リンク先の代表ノード番号にはノード対２０１ｆの代表ノード２１０ｆの格納された配列要素の配列番号２２１ｂが格納されている。
【００７６】
ノード対２０１ｆのノード２１０ｆ、２１１ｆのノード種別２６０ｆ、２６１ｆはともに０であり双方ともブランチノードである。それぞれの弁別ビット位置２３０ｆ、２３１ｆには５、３が格納されている。ノード２１０ｆの代表ノード番号にはノード対２０１ｇの代表ノード２１０ｇの格納された配列要素の配列番号２２０ｆが格納され、ノード２１１ｆの代表ノード番号にはノード対２０１ｈの代表ノードであるノード［０］２１０ｈの
格納された配列要素の配列番号２２１ｆが格納されている。
【００７７】
ノード対２０１ｇのノード２１０ｇ、２１１ｇのノード種別２６０ｇ、２６１ｇはともに１であり双方ともリーフノードであることを示し、それぞれのインデックスキー２５０ｇ、２５１ｇには“１０００１０”と“１０００１１”が格納されている。
【００７８】
また同じくノード対２０１ｈの代表ノードであるノード［０］２１０ｈとそれと対をなすノード［１］２１１ｈのノード種別２６０ｈ、２６１ｈはともに１であり双方ともリーフノードであることを示し、それぞれのインデックスキー２５０ｈ、２５１ｈには“１０１０１１”と“１０１１００”が格納されている。
【００７９】
以下、上述のツリーからインデックスキー“１０００１０”を検索する処理の流れを簡単に説明する。弁別ビット位置は、左から０、１、２、・・・とする。
まず、ビット列“１０００１０”を検索キーとしてルートノード２１０ａから処理をスタートする。ルートノード２１０ａの弁別ビット位置２３０ａは０であるので、検索キー“１０００１０”の弁別ビット位置が０のビット値をみると１である。そこで代表ノード番号の格納された配列番号２２０ａに１を加えた配列番号の配列要素に格納されたノード２１１ｂにリンクする。ノード２１１ｂの弁別ビット位置２３１ｂには２が格納されているので、検索キー“１０００１０”の弁別ビット位置が２のビット値をみると０であるから、代表ノード番号の格納された配列番号２２１ｂの配列要素に格納されたノード２１０ｆにリンクする。
【００８０】
ノード２１０ｆの弁別ビット位置２３０ｆには５が格納されているので、検索キー“１０００１０”の弁別ビット位置が５のビット値をみると０であるから、代表ノード番号の格納された配列番号２２０ｆの配列要素に格納されたノード２１０ｇにリンクする。
【００８１】
ノード２１０ｇのノード種別２６０ｇは１でありリーフノードであることを示しているので、インデックスキー２５０ｇを読み出して検索キーと比較すると両方とも“１０００１０”であって一致している。このようにしてカップルドノードツリーを用いた検索が行われる。
【００８２】
次に、図２を参照してカップルドノードツリーの構成の意味について説明する。
カップルドノードツリーの構成はインデックスキーの集合により規定される。図２の例で、ルートノード２１０ａの弁別ビット位置が０であるのは、図２に例示されたインデックスキーに０ビット目が０のものと１のものがあるからである。０ビット目が０のインデックスキーのグループはノード２１０ｂの下に分類され、０ビット目が１のインデックスキーのグループはノード２１１ｂの下に分類されている。
【００８３】
ノード２１１ｂの弁別ビット位置が２であるのは、ノード２１１ｈ、２１０ｈ、２１１ｇ、２１０ｇに格納された０ビット目が１のインデックスキーの１ビット目がすべて０で等しく、２ビット目で初めて異なるものがあるという、インデックスキーの集合の性質を反映している。
【００８４】
以下０ビット目の場合と同様に、２ビット目が１であるものはノード２１１ｆ側に分類され、２ビット目が０であるものはノード２１０ｆ側に分類される。
そして２ビット目が１であるインデックスキーは３ビット目の異なるものがあるのでノード２１１ｆの弁別ビット位置には３が格納され、２ビット目が０であるインデックスキーでは３ビット目も４ビット目も等しく５ビット目で異なるのでノード２１０ｆの弁別ビット位置には５が格納される。
【００８５】
ノード２１１ｆのリンク先においては、３ビット目が１のものと０のものがそれぞれ１つしかないことから、ノード２１０ｈ、２１１ｈはリーフノードとなり、それぞれインデックスキー２５０ｈと２５１ｈに“１０１０１１”と“１０１１００”が格納されている。
【００８６】
仮にインデックスキーの集合に“１０１１００”の代わりに“１０１１０１”か“１０１１１０”が含まれていたとしても、３ビット目までは“１０１１００”と等しいので、ノード２１１ｈに格納されるインデックスキーが変わるだけで、ツリー構造自体は変わることはない。しかし、“１０１１００”に加えて“１０１１０１”が含まれていると、ノード２１１ｈはブランチノードとなり、その弁別ビット位置は５になる。追加されるインデックスキーが“１０１１１０”であれば、弁別ビット位置は４となる。
【００８７】
以上説明したように、カップルドノードツリーの構造は、インデックスキーの集合に含まれる各インデックスキーの各ビット位置のビット値により決定される。
そしてさらにいえば、異なるビット値となるビット位置ごとにビット値が“１”のノードとビット値が“０”のノードとに分岐していることから、ノード［１］側とツリーの深さ方向を優先させてリーフノードをたどると、それらに格納されたインデックスキーは、ノード２１１ｈのインデックスキー２５１ｈの“１０１１００”、ノード２１０ｈのインデックスキー２５０ｈの“１０１０１１”、・・・、ノード２１０ｃのインデックスキー２５０ｃの“０００１１１”となり降順にソートされている。
【００８８】
すなわち、カップルドノードツリーにおいては、インデックスキーはソートされてツリー上に配置されている。
検索キーで検索するときはインデックスキーがカップルドノードツリー上に配置されたルートをたどることになり、例えば検索キーが“１０１１００”であればノード２１１ｈに到達することができる。また、上記説明からも想像がつくように、“１０１１０１”か“１０１１１０”を検索キーとした場合でもノード２１１ｈにたどり着き、インデックスキー２５１ｈと比較することにより検索が失敗したことが分かる。
【００８９】
また、例えば“１００１００”で検索した場合でも、ノード２１０ａ、２１１ｂ、２１０ｆのリンク経路では検索キーの３ビット目と４ビット目は使われることがなく、“１００１００”の５ビット目が０なので、“１０００１０”で検索した場合と同様にノード２１０ｇに到達することになる。このように、カップルドノードツリーに格納されたインデックスキーのビット構成に応じた弁別ビット位置を用いて分岐が行われる。
【００９０】
図３は、本発明を実施するためのハードウェア構成例を説明する図である。
本発明の検索装置による検索処理及びデータメンテナンスは中央処理装置３０２及びキャッシュメモリ３０３を少なくとも備えたデータ処理装置３０１によりデータ格納装置３０８を用いて実施される。カップルドノードツリーが配置される配列３０９と検索中にたどるノードが格納された配列要素の配列番号を記憶する探索経路スタック３１０を有するデータ格納装置３０８は、主記憶装置３０５または外部記憶装置３０６で実現することができ、あるいは通信装置３０７を介して接続された遠方に配置された装置を用いることも可能である。図１の配列１００は、配列３０９の一例である。
【００９１】
図３の例示では、主記憶装置３０５、外部記憶装置３０６及び通信装置３０７が一本のバス３０４によりデータ処理装置３０１に接続されているが、接続方法はこれに限るものではない。また、主記憶装置３０５をデータ処理装置３０１内のものとすることもできるし、探索経路スタック３１０を中央処理装置３０２内のハードウェアとして実現することも可能である。あるいは、配列３０９は外部記憶装置３０６に、探索経路スタック３１０を主記憶装置３０５に持つなど、使用可能なハードウェア環境、インデックスキー集合の
大きさ等に応じて適宜ハードウェア構成を選択できることは明らかである。
【００９２】
また、特に図示されてはいないが、処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶装置が用いられることは当然である。
次に、上述の出願において、本出願人により提案されたカップルドノードツリーを用いた基本的な検索処理について、本発明を理解するために必要な範囲で紹介する。
【００９３】
図４は、本出願人による出願である上記特願２００６−２９３６１９で提案されたビット列検索の基本動作を示したフローチャートである。
まず、ステップＳ４０１で、検索開始ノードの配列番号を取得する。取得された配列番号に対応する配列要素は、カップルドノードツリーを構成する任意のノードを格納したものである。検索開始ノードの指定は、後述の各種応用検索において行われる。
【００９４】
次に、ステップＳ４０２で、探索経路スタック３１０に取得された配列番号を格納し、ステップＳ４０３で、その配列番号に対応する配列要素を参照すべきノードとして読み出す。そして、ステップＳ４０４で、読み出したノードから、ノード種別を取り出し、ステップＳ４０５で、ノード種別がブランチノードであるか否かを判定する。
【００９５】
ステップＳ４０５の判定において、読み出したノードがブランチノードである場合は、ステップＳ４０６に進み、ノードから弁別ビット位置についての情報を取り出し、更に、ステップＳ４０７で、取り出した弁別ビット位置に対応するビット値を検索キーから取り出す。そして、ステップＳ４０８で、ノードから代表ノード番号を取り出して、ステップＳ４０９で、検索キーから取り出したビット値と代表ノード番号とを加算し、新たな配列番号として、ステップＳ４０２に戻る。
【００９６】
以降、ステップＳ４０５の判定においてリーフノードと判定されてステップＳ４１０に進むまで、ステップＳ４０２からステップＳ４０９までの処理を繰り返す。ステップＳ４１０で、リーフノードからインデックスキーを取り出して、処理を終了する。
【００９７】
なお、カップルドノードツリーは、リーフノードを挿入する処理を繰り返すことにより生成することが可能である。上記特願２００６−１８７８２７によれば、その挿入処理ではまず、指定された挿入キーを検索キーとしてカップルドノードツリーから該当するリーフノードを検索する。その際、そのリーフノードに至るまでたどった経路上のブランチノード及び当該リーフノードが格納された配列要素の配列番号をスタックに順次格納する。そして、検索キーと、リーフノードに含まれるインデックスキーの間で大小比較とビット列比較を行う。続いて、ビット列比較で異なるビット値となる先頭のビット位置と、スタックに格納されているブランチノードの弁別ビット位置との相対的位置関係により、挿入キーを含むリーフノードともう一方のノードからなる新たなノード対の挿入位置を決定する。そして、大小関係により、挿入キーを含むリーフノードを、挿入されるノード対のどちらのノードとするかを決定し、ノード対を挿入する。
【００９８】
また、指定されたインデックスキーを含むリーフノードをカップルドノードツリーから削除する方法も、上記特願２００６−１８７８２７に記載されている。それによれば、削除キーを検索キーとしてカップルドノードツリーから該当するリーフノードを検索し、そのリーフノードとノード対を構成するノードの内容を、当該ノード対のリンク元のブランチノードに書き込み、当該ノード対を削除することで、指定されたインデックスキーを含むリーフノードを削除することができる。
【００９９】
また、特願２００６−２９３６１９には、０〜ｎ（ｎ≧０）ビット目までの値が指定された前方一致キーと、０〜ｎビット目が完全に一致するインデックスキーをすべて取り出
す前方一致検索の方法も記載されている。例えば、前方一致キーとして“１０＊＊＊＊”が指定された場合、ｎ＝１であり、０〜１ビット目が前方一致キーと一致するインデックスキーがすべて取り出される。
【０１００】
その具体的な方法は、次のとおりである。まず、前方一致キーのすべての“＊”を“０”で置き換えた下限キーと、前方一致キーのすべての“＊”を“１”で置き換えた上限キーを取得する。そして、下限キーと上限キーで指定される検索範囲のインデックスキーを昇順でカップルドノードツリーから取り出す。
【０１０１】
指定された検索範囲のインデックスキーを昇順でカップルドノードツリーから取り出す処理は、次のように行われる。まず、下限キー以上のインデックスキーの最小値である下限値を下限キーから取得し、上限キー以下のインデックスキーの最大値である上限値を上限キーから取得する。
【０１０２】
下限値の取得は、ノード［０］側及び深さ方向を優先させた深さ優先探索順にカップルドノードツリーのリーフノードを探索しながら、リーフノードのインデックスキーと下限キーを比較することにより行われる。上限値の取得方法は、探索順をノード［１］側及び深さ方向を優先させた深さ優先探索順とする以外は、下限値の取得と同様の方法である。
【０１０３】
そして、下限値のインデックスキーを格納したリーフノードから開始して、上限値のインデックスキーが見つかるまで、ノード［０］側及び深さ方向を優先させた深さ優先探索順にカップルドノードツリーのリーフノードを探索し、順次リーフノードからインデックスキーを取り出す。
【０１０４】
以上の処理により、前方一致キーと０〜ｎビット目が完全に一致するインデックスキーをすべて取り出すことができる。
また、特願２００７−１３２２８９には、指定された最長一致検索キーと部分一致するインデックスキーのうち、差分ビット位置が最も下位となるインデックスキーを検索する最長一致検索の方法が記載されている。なお、ここで差分ビット位置とは、２つのビット列を比較したときにビット値が一致しない不一致ビットのうち、最も上位の位置である。
【０１０５】
その具体的な方法は、次のとおりである。まず、最長一致検索キーを検索キーとし、ルートノードを検索開始ノードとして図４の検索を行い、その結果得られたインデックスキーと最長一致検索キーとを比較し、差分ビット位置を求める。
【０１０６】
そして、図４の検索において記憶された探索経路スタックを遡り、弁別ビット位置が差分ビット位置よりも上位にあるブランチノードのうち、弁別ビット位置が最下位のブランチノードの配列番号の次に探索経路スタックに記憶された配列番号のノードを最長一致ノードとして取得する。
【０１０７】
カップルドノードツリーの構造から、以上のようにして取得された最長一致ノードをルートノードとする部分木に含まれるすべてのインデックスキーは、最長一致検索キーと部分一致するインデックスキーのうち差分ビット位置が最も下位であるという上記の条件を満たす。よって、必要に応じて、この部分木の中から適宜インデックスキーを取り出せばよい。
【０１０８】
以上、本発明の前提となる技術を説明したが、必要とあれば、上述の特許出願の明細書及び図面の記載を参照されたい。
なお、上記特願２００６−２９３６１９による前方一致検索及び特願２００７−１３２２８９による最長一致検索と、本発明による検索との関連性を説明すれば、下記のごとくである。
【０１０９】
上記の前方一致検索における前方一致キーはドントケアビットを含む。また、上記の最長一致検索は、最長一致検索キーと部分的にしか一致しないインデックスキーが結果として得られることがあるという点で、不一致の範囲をドントケアビットとして扱っていると見ることもできる。
【０１１０】
しかし、上記の前方一致検索と最長一致検索はいずれも、一意に定まる１つのインデックスキーを取得する処理ではない。
すなわち、上記の前方一致検索で取り出されるインデックスキーの数は、２以上のことがある。また、上記の最長一致検索において、最長一致ノードをルートノードとする部分木は複数のリーフノードを有することがあり、この部分木の中からどのインデックスキーを取り出すかは任意である。
【０１１１】
つまり、上記の前方一致検索と最長一致検索では、検索の条件を満たすという点で互いに対等な複数のインデックスキーが存在することがある。よって、検索の目的によっては、それら複数のインデックスキーの中から、何らかの基準によって１つを選択することが必要である。
【０１１２】
一方で、ルータにおけるルーティングテーブルの検索など、非常に高速な処理が求められる分野では、上記のような検索と選択という２段階の処理を行うことは好ましくない。そのため、前方一致検索や最長一致検索のように部分的な一致に基づく検索の場合でも、最適な１つのインデックスキーが一意に定まり、２段階目の選択処理を必要とせずに、その一意なインデックスキーを取得する方法が望まれる。
【０１１３】
以下に説明するとおり、本発明によるドントケアビットを考慮した検索は、そのような要望を満たすものである。上記の前方一致検索、最長一致検索、及び、以下に述べるドントケアビットを考慮した検索は、検索の目的に応じて使い分けるべきものである。
【０１１４】
次に、本発明の実施形態について詳しく説明する。以下では、ビット列の符号化方法の例と、カップルドノードツリーの例を説明してから、検索、挿入、削除の各処理について説明する。
【０１１５】
以下の説明では、符号化の前と後のビット列をそれぞれ「元ビット列」、「符号化ビット列」という。「インデックスキー」や「検索キー」という語は、特に断らない限り符号化ビット列の状態であることを示し、元ビット列の状態を示す場合には「元インデックスキー」や「元検索キー」のように表記する。
【０１１６】
また、値が“０”または“１”に定まっているビットを「有意ビット」と呼び、値が“０”と“１”のいずれでもよく、一意に定まらないビットを「ドントケアビット」と呼ぶ。なお、ドントケアビットは、“０”または“１”により表される有意ビットと区別して、符号“＊”により表記する。
【０１１７】
また、以下では、ドントケアビットが有意ビットよりも前に存在していないことを前提とする。つまり、元ビット列は、ドントケアビットのみからなるか、有意ビットのみからなるか、１ビット以上の有意ビットに１ビット以上のドントケアビットが後続するかのいずれかである。
【０１１８】
このようにドントケアビットを含む可能性のある元ビット列を符号化するために、各ビットを２ビットに符号化する符号化方法を採用する。
符号化ビット列は、２ビットからなるビット対を単位とする。各ビット対の０ビット目
は、ドントケアビットであるか有意ビットであるかを示す識別ビットである。各ビット対の１ビット目は、データビットと呼ぶ。
【０１１９】
識別ビットは、値が“０”のときドントケアビットを示し、値が“１”のとき有意ビットを示す。
識別ビットの値が“０”のとき、対となるデータビットの値は必ず、予め決められた値であり、以下の実施形態では、予め決められたその値として“０”を採用する。識別ビットの値が“１”のとき、データビットは元ビット列のビットの値を表す。
【０１２０】
つまり、元ビット列の各ビットは、“０”なる値の有意ビットのとき“１０”なるビット対に符号化され、“１”なる値の有意ビットのとき“１１”なるビット対に符号化され、ドントケアビットのとき“００”なるビット対に符号化される。
【０１２１】
この符号化方法によれば、元ビット列において後続の有意ビットがあるか否かを、符号化ビット列から簡単に判断することができる。なぜなら、符号化ビット列中の任意のビットは、そのビットの位置が偶数であるか奇数であるかによって、そのビットが識別ビットであるかデータビットであるかを簡単に区別することができ、上記の前提からドントケアビットが有意ビットよりも前に存在することはないからである。
【０１２２】
次に図５を参照して、符号化ビット列を利用したカップルドノードツリーの例を説明する。図５の（ａ）は、６つの符号化されていない元インデックスキー“＊＊＊＊＊”、“１＊＊＊＊”、“１０１＊＊”、“１０１１＊”、“１１００＊”、“１１１＊＊”の集合に対応するカップルドノードツリーの概念的な構造を示す。
【０１２３】
なお、図５は、後述の検索処理のための説明に関する部分（ｂ）と（ｃ）も含むが、ここでは先にカップルドノードツリーの構造についてのみ説明する。
図５の（ａ）のカップルドノードツリーの各リーフノードは、インデックスキーとして、上記６つの元インデックスキーをそれぞれ符号化した符号化ビット列を格納している。図５では、理解の助けとするために、元インデックスキーの値が、各インデックスキーの近傍の括弧内に示されている。
【０１２４】
インデックスキーに格納されるのが符号化ビット列であるという点以外は、図５は図２と同様なので、図５においても図２と同様の符号を用いる。
すなわち、ルートノード２１０ａは、配列番号２２０に配置され、ノード対２０１ａの代表ノードである。ツリー構造としては、ルートノード２１０ａの下にノード対２０１ｂが、その下層にノード対２０１ｃが、さらにその下層にノード対２０１ｄが配置されている。そして、ノード対２０１ｄの下層には、ノード対２０１ｅとノード対２０１ｆが配置されている。
【０１２５】
ルートノード２１０ａのノード種別２６０ａは０でブランチノードであることを示し、弁別ビット位置２３０ａは０であり、代表ノード番号には、ノード対２０１ｂの代表ノードであるノード２１０ｂの格納された配列要素の配列番号２２０ａが格納されている。
【０１２６】
ノード対２０１ｂは、ノード種別２６０ｂが１であってリーフノードであるノード２１０ｂと、ノード種別２６１ｂが０であってブランチノードであるノード２１１ｂで構成される。
【０１２７】
ノード２１０ｂのインデックスキー２５０ｂには、元インデックスキー“＊＊＊＊＊”を符号化した“００００００００００”が格納されている。
一方、ノード２１１ｂの弁別ビット位置２３１ｂには２が格納され、代表ノード番号に
は、ノード対２０１ｃの代表ノード２１０ｃの格納された配列要素の配列番号２２１ｂが格納されている。
【０１２８】
ノード対２０１ｃは、ノード種別２６０ｃが１であってリーフノードであるノード２１０ｃと、ノード種別２６１ｃが０であってブランチノードであるノード２１１ｃで構成される。
【０１２９】
ノード２１０ｃのインデックスキー２５０ｃには、元インデックスキー“１＊＊＊＊”を符号化した“１１００００００００”が格納されている。
一方、ノード２１１ｃの弁別ビット位置２３１ｃには３が格納され、代表ノード番号には、ノード対２０１ｄの代表ノード２１０ｄの格納された配列要素の配列番号２２１ｃが格納されている。
【０１３０】
ノード対２０１ｄは、ノード２１０ｄと２１１ｄで構成され、それぞれのノード種別２６０ｄと２６１ｄはブランチノードであることを示す０である。
ノード２１０ｄの弁別ビット位置２３０ｄには６が格納され、代表ノード番号には、ノード対２０１ｅの代表ノード２１０ｅの格納された配列要素の配列番号２２０ｄが格納されている。
【０１３１】
一方、ノード２１１ｄの弁別ビット位置２３１ｄには５が格納され、代表ノード番号には、ノード対２０１ｆの代表ノード２１０ｆの格納された配列要素の配列番号２２１ｄが格納されている。
【０１３２】
ノード対２０１ｅは、ノード２１０ｅと２１１ｅで構成され、それぞれのノード種別２６０ｅと２６１ｅはリーフノードであることを示す１である。
ノード２１０ｅのインデックスキー２５０ｅには、元インデックスキー“１０１＊＊”を符号化した“１１１０１１００００”が格納されている。
【０１３３】
一方、ノード２１１ｅのインデックスキー２５１ｅには、元インデックスキー“１０１１＊”を符号化した“１１１０１１１１００”が格納されている。
ノード対２０１ｆは、ノード２１０ｆと２１１ｆで構成され、それぞれのノード種別２６０ｆと２６１ｆはリーフノードであることを示す１である。
【０１３４】
ノード２１０ｆのインデックスキー２５０ｆには、元インデックスキー“１１００＊”を符号化した“１１１１１０１０００”が格納されている。
一方、ノード２１１ｆのインデックスキー２５１ｆには、元インデックスキー“１１１＊＊”を符号化した“１１１１１１００００”が格納されている。
【０１３５】
検索キーとして使われる符号化ビット列が、カップルドノードツリーに含まれるインデックスキーのうちの１つと完全に一致する場合は、図４と同様の処理により、検索キーと等しいインデックスキーが検索結果として得られる。
【０１３６】
しかし、ドントケアビットを考慮すると、検索キーと部分的に一致するインデックスキーを検索結果として得るべき場合がある。そのような部分的な一致に基づく検索の詳細は、図６〜図１１を参照して後述する。
【０１３７】
次に、図５の（ａ）のカップルドノードツリーの構成の意味について説明する。図５の（ａ）のように、符号化ビット列を用いる場合でも、図２と同様に、カップルドノードツリーの構成はインデックスキーの集合により規定される。
【０１３８】
図５の（ａ）の例で、ルートノード２１０ａの弁別ビット位置が０であるのは、図５中のインデックスキーに０ビット目が０のものと１のものがあるからである。０ビット目が０のインデックスキーは１つしかないためノード２１０ｂに分類され、０ビット目が１のインデックスキーはノード２１１ｂの下層に分類されている。
【０１３９】
ノード２１１ｂの弁別ビット位置２３１ｂが２であるのは、ノード２１１ｂの下層の各ノードに格納された０ビット目が１のインデックスキーの１ビット目がすべて１で等しく、２ビット目で初めて異なるものがあるという、インデックスキーの集合の性質を反映している。
【０１４０】
以下同様に、０〜１ビット目が“１１”であるインデックスキーのうちで、２ビット目が０のインデックスキーは１つしかないのでノード２１０ｃに分類され、２ビット目が１のインデックスキーはノード２１１ｃの下層に分類される。ノード２１１ｃの弁別ビット位置２３１が３であるのは、ノード２１１ｃの下層の各ノードに格納されたインデックスキーには、３ビット目が０のものと１のものがあることを反映している。
【０１４１】
ノード２１０ｄの弁別ビット位置２３０ｄが６である理由は、ノード２１０ｄの下層の各ノードに格納された０〜３ビット目が“１１１０”であるインデックスキーは、４〜５ビット目がいずれも“１１”で等しく、６ビット目で初めて異なるという、インデックスキーの性質を反映しているからである。
【０１４２】
ノード２１０ｄのリンク先においては、６ビット目が０のインデックスキーと１のインデックスキーがそれぞれ１つしかない。よって、ノード２１０ｅと２１１ｅはリーフノードであり、ノード２１０ｅと２１１ｅのインデックスキー２５０ｅと２５１ｅにはそれぞれ、“１０１＊＊”の符号化ビット列である“１１１０１１００００”と“１０１１＊”の符号化ビット列である“１１１０１１１１００”が格納されている。
【０１４３】
一方、ノード２１１ｄの弁別ビット位置２３１ｄが５である理由は、ノード２１１ｄの下層の各ノードに格納された０〜３ビット目が“１１１１”であるインデックスキーは、４ビット目がいずれも１で等しく、５ビット目で初めて異なるという、インデックスキーの性質を反映しているからである。
【０１４４】
ノード２１１ｄのリンク先においては、５ビット目が０のインデックスキーと１のインデックスキーがそれぞれ１つしかない。よって、ノード２１０ｆと２１１ｆはリーフノードであり、ノード２１０ｆと２１１ｆのインデックスキー２５０ｆと２５１ｆにはそれぞれ、“１１００＊”の符号化ビット列である“１１１１１０１０００”と“１１１＊＊”の符号化ビット列である“１１１１１１００００”が格納されている。
【０１４５】
このように、図５の（ａ）においては符号化ビット列であるインデックスキーの集合がカップルドノードツリーのツリー構造と対応している。
また、本実施形態における符号化方法では、２つの元ビット列の０〜ｍ（０≦ｍ）ビット目が一致することと、その２つの元ビット列を符号化した２つの符号化ビット列の０〜（２ｍ＋１）ビット目が一致することは同値である。したがって、カップルドノードツリーのツリー構造は、符号化する前の元インデックスキーの集合により規定されるということもでき、ツリー構造と元インデックスキーの集合との間に対応関係がある。
【０１４６】
すなわち、元インデックスキーのうち０ビット目がドントケアビットのものは“＊＊＊＊＊”のみなので、“＊＊＊＊＊”がルートノード２１０ａの直下のノード２１０ｂに分類され、０ビット目が有意ビットである元インデックスキーはノード２１０ｂと対をなすノード２１１ｂの下層に分類される。
【０１４７】
ノード２１１ｂの下層に分類された元インデックスキーは、すべて０ビット目が“１”で等しい。よって、０ビット目が“０”と“１”のいずれであるかという分類は不要である。
【０１４８】
一方、これらの元インデックスキーのうち、１ビット目がドントケアビットのものは“１＊＊＊＊”という元インデックスキーだけなので、これがノード２１０ｃに分類され、１ビット目が有意ビットの元インデックスキーはノード２１０ｃと対になるノード２１１ｃの下層に分類される。
【０１４９】
ノード２１１ｃの下層に分類される、少なくとも０〜１ビット目が有意ビットである元インデックスキーには、１ビット目が“０”のものと“１”のものがある。そこで、０〜１ビット目が“１０”のものはノード２１０ｄの下層に分類され、０〜１ビット目が“１１”のものはノード２１１ｄの下層に分類される。
【０１５０】
ノード２１０ｄの下層に分類される元インデックスキーは“１０１＊＊”と“１０１１＊”の２つである。この２つの元インデックスキーは、０〜２ビット目までが完全に一致するが、３ビット目がドントケアビットであるか有意ビットであるかが異なる。
【０１５１】
本実施形態ではドントケアビット“＊”を“００”と符号化している。よって、このようにｎビット目（ｎ≧１）以降がドントケアビットである元インデックスキーと、ｎビット目が有意ビットである元インデックスキーが、０〜（ｎ−１）ビット目の範囲において完全に一致する場合、前者がノード［０］側に分類される。
【０１５２】
したがって、元インデックスキー“１０１＊＊”がノード２１０ｅに、“１０１１＊”が２１１ｅに、それぞれ分類される。
一方、ノード２１１ｄの下層に分類される元インデックスキーは“１１００＊”と“１１１＊＊”の２つである。この２つの元インデックスキーは、０〜１ビット目が完全に一致するが、２ビット目の値が異なる。
【０１５３】
このように、先頭の０ビット目から順に比較して、いずれの元インデックスキーのドントケアビットにも達しないうちに値の異なる有意ビットが見つかる場合は、その有意ビットの値が“０”である元インデックスキーがノード［０］側に分類され、その有意ビットの値が“１”である元インデックスキーがノード［１］側に分類される。
【０１５４】
したがって、元インデックスキー“１１００＊”がノード２１０ｆに、元インデックスキー“１１１＊＊”がノード２１１ｆに、それぞれ分類される。
以上のとおり、符号化ビット列を分類して得られる階層構造と、元ビット列を分類して得られる階層構造は同値である。
【０１５５】
また、ドントケアビットの値は不定であることから、ドントケアビットと有意ビットの値のうちいずれが大きいかということは、本来は定まらない。しかし、便宜上、ドントケアビット“＊”が“０”なる値の有意ビットよりも小さいと定義すれば、カップルドノードツリーの構造は元インデックスキーの順序性を反映したものであると言うことができる。
【０１５６】
すなわち、図２と同様に、図５のカップルドノードツリーにおいても、ノード［１］側を優先させた深さ優先探索順にリーフノードをたどると、それらリーフノードに格納されたインデックスキーが表す元インデックスキーは降順にソートされている。換言すれば、元インデックスキーを降順にソートした順に対応して、各インデックスキーはカップルド
ノードツリー上に配置されている。
【０１５７】
なお、本実施形態において、ドントケアビットを示す識別ビットの値を“０”としているのは、“＊”が“０”よりも小さいという上記の定義と合わせるためである。
次に、本発明の一実施形態における検索処理について、図６のフローチャートを参照して説明する。図６の検索処理では、符号化されていない元ビット列である元検索キーが入力として指定され、例えば図５のように符号化ビット列を用いたカップルドノードツリーが検索される。
【０１５８】
図６の検索処理は、以下に述べる「最長一致キー」の条件を満たすインデックスキーがカップルドノードツリー内に存在すればその最長一致キーを得る処理である。もし、最長一致キーの条件を満たすインデックスキーがカップルドノードツリー内に含まれなければ、検索は失敗して終了する。
【０１５９】
本実施形態において最長一致キーとは、下記の（ａ）と（ｂ）のいずれかに相当するインデックスキーを示す。
（ａ）  元検索キーを符号化した符号化ビット列と全く同一のインデックスキー。
【０１６０】
（ｂ）  有意ビットが存在しないか、元検索キーよりも少ない数の有意ビットが存在するがすべての有意ビットの値が元検索キーのものと一致する元インデックスキーの中で、有意ビットの数が最大のものを符号化したインデックスキー。
【０１６１】
なお、上記の（ａ）は（ｂ）よりも優先度が高い。つまり、もし（ａ）に該当するインデックスキーが存在すればそのインデックスキーが最長一致キーであり、このとき、（ｂ）に該当するインデックスキーは、たとえ存在したとしても最長一致キーではない。
【０１６２】
図６の具体的な説明を始める前に、上記（ａ）と（ｂ）の定義についていくつか例を挙げて説明する。
上記（ａ）の例は、図５の（ａ）のカップルドノードツリーにおいて、元検索キーが“１１００＊”のときの、“１１００＊”を符号化した符号化ビット列である、ノード２１０ｆのインデックスキー２５０ｆである。
【０１６３】
また、図５の（ａ）のカップルドノードツリーにおいて、上記（ｂ）に該当する最長一致キーの例を３つ挙げると、次のとおりである。
１つ目の例は、元検索キーが“１１００１”のときの例である。この元検索キーの有意ビットの数は５である。
【０１６４】
図５の（ａ）には、有意ビットが存在しない元インデックスキー“＊＊＊＊＊”がある。また、５よりも少ない数の有意ビットが存在するが、すべての有意ビットの値が元検索キーのものと一致する元インデックスキーには、“１＊＊＊＊”と“１１００＊”がある。
【０１６５】
これらの３つの元インデックスキーのうち、有意ビットの数が最大の“１１００＊”を符号化した、ノード２１０ｆのインデックスキー２５０ｆが、最長一致キーである。
２つ目の例は、元検索キーが“１１＊＊＊”のときの例である。この元検索キーの有意ビットの数は２である。
【０１６６】
図５には、有意ビットが存在しない元インデックスキー“＊＊＊＊＊”がある。また、２よりも少ない数の有意ビットが存在するが、すべての有意ビットの値が元検索キーのものと一致する元インデックスキーには、“１＊＊＊＊”がある。
【０１６７】
これらの２つの元インデックスキーのうち、有意ビットの数が最大の“１＊＊＊＊”を符号化した、ノード２１０ｃのインデックスキー２５０ｃが、最長一致キーである。
なお、カップルドノードツリー内には、元インデックスキー“１１００＊”や“１１１＊＊”を符号化したインデックスキー２５０ｆ及び２５１ｆも存在する。“１１＊＊＊”と一致する範囲は、一見、“１＊＊＊＊”よりも“１１００＊”や“１１１＊＊”の方が広いように見える。
【０１６８】
しかし、インデックスキー２５０ｆ及び２５１ｆは、最長一致キーの定義から外れている。最長一致キーがこのように定義されている理由について補足すると下記のごとくである。
【０１６９】
ドントケアビットは任意の値を表すので、ドントケアビットを含む元ビット列は、ビット列の集合を表していると見なすことができる。例えば、“１１＊＊＊”が表す集合は“１１０１１”という元ビット列などを包含する。
【０１７０】
しかし、“１１０１１”は、“１１００＊”と３ビット目で異なり、“１１１＊＊”と２ビット目で異なる。つまり、“１１０１１”は、“１１００＊”や“１１１＊＊”に包含されない。よって、インデックスキー２５０ｆまたは２５１ｆを、元検索キー“１１＊＊＊”に対する最長一致キーとすることは不適切である。
【０１７１】
一方、元検索キー“１１＊＊＊”のドントケアビットがどのような値をとろうとも、ドントケアビットに値が設定されたそのビット列は、元インデックスキー“＊＊＊＊＊”が表す集合や、元インデックスキー“１＊＊＊＊”が表す集合には必ず包含される。
【０１７２】
そして、２つの元インデックスキーのうち、より多くの有意ビットを有する元インデックスキー“１＊＊＊＊”が表す集合の方がより小さく、元検索キー“１１＊＊＊”が表す集合により近い。よって、元検索キー“１１＊＊＊”に対する最長一致キーは元インデックスキー“１＊＊＊＊”である。
【０１７３】
３つ目の例は、元検索キーが“０＊＊＊＊”のときの例である。図５の（ａ）のカップルドノードツリーには、“０”から始まる元インデックスキーを符号化したインデックスキーは含まれない。
【０１７４】
しかし、このとき、上記（ｂ）の定義によれば、元インデックスキー“＊＊＊＊＊”を符号化した符号化ビット列である、ノード２１０ｂのインデックスキー２５０ｂが最長一致キーである。実際、元検索キー“０＊＊＊＊”のドントケアビットがどのような値をとろうとも、ドントケアビットに値が設定されたそのビット列は、元インデックスキー“＊＊＊＊＊”が表す集合に包含される。
【０１７５】
上記のように定義される最長一致キーを取得することは、例えばＩＰアドレスのように、ビット列の値と、ビット列が表す内容の階層的な分類とが対応するような場合において、最も適切な分類を選択するのに好適である。
【０１７６】
次に、図６フローチャートを参照して、図６の処理の詳細を説明する。図６に示す処理により、上記の（ａ）及び（ｂ）により定義される最長一致キーが存在すればそれを得ることができ、存在しなければ検索失敗という結果が得られる。
【０１７７】
ステップＳ６０１で、指定された元検索キーから、上記の符号化方法によって、検索キーを作成する。ステップＳ６０１の詳細は、図７を参照して後述する。例えば、図５の（
ｂ）には、５ビットの元検索キー“１０１００”から作成された１０ビットの検索キー２７０が例示されている。
【０１７８】
続いて、ステップＳ６０２で、検索対象のカップルドノードツリーのルートノードを検索開始ノードに設定する。
次にステップＳ６０３で、カップルドノードツリーのノードを格納する配列を、検索キーにより、検索開始ノードより検索し、検索結果としてのインデックスキーを得る。ステップＳ６０３の処理の詳細は図８とあわせて後述する。後のステップＳ６０６で参照するために、ステップＳ６０３では、図５の（ｃ）に例示したように探索経路スタック３１０に配列番号が格納される。
【０１７９】
次のステップＳ６０４では、検索キーと、ステップＳ６０３で得られたインデックスキーとの差分ビット位置を求める。差分ビット位置の定義及びステップＳ６０４の詳細は図９及び図１０とあわせて後述する。
【０１８０】
続くステップＳ６０６では、検索キーとステップＳ６０３で得られたインデックスキーとに基づいて、探索経路スタックを遡り、最長一致キーを得る。ステップＳ６０６の処理の詳細は、図１１とあわせて後述する。
【０１８１】
ステップＳ６０６で最長一致キーが得られれば検索は成功し、図６の処理が終了する。ステップＳ６０６で最長一致キーが得られなければ検索は失敗して、図６の処理が終了する。
【０１８２】
次に図７のフローチャートを参照して、入力ビット列として与えられた元ビット列を符号化して符号化ビット列を出力する符号化処理について説明する。図７の符号化処理は、図６のステップＳ６０１に相当する。また、後述するように、挿入処理及び削除処理においても図７の符号化処理が実行される。
【０１８３】
ステップＳ７０１において、入力ビット列の有意ビットの部分の長さである有意ビット長を、ビット長として記憶する。
また、ステップＳ７０２において、入力ビット列のうち次に処理すべきビットの位置を示すビット位置を初期化する。本実施形態では０ビット目から順に処理するために、ステップＳ７０２では、ビット位置を０に初期化する。
【０１８４】
そして、ステップＳ７０３において、出力ビット列を、初期化して空ビット列とする。ビット位置と出力ビット列の値は、後述のステップＳ７０４〜ステップＳ７０８のループにおいて更新される。
【０１８５】
続いて、ステップＳ７０４において、ステップＳ７０１で記憶したビット長よりも現在のビット位置が小さいか否かを判定し、現在のビット位置の方が小さければステップＳ７０５へ進み、それ以外の場合はステップＳ７０９へ進む。
【０１８６】
ステップＳ７０５では、入力ビット列から、現在のビット位置の指すビット値を取り出す。
続いて、ステップＳ７０６では出力ビット列の末尾にビット値１を連結する。そして、ステップＳ７０７で出力ビット列の末尾に、ステップＳ７０５で得たビット値を連結する。
【０１８７】
その後ステップＳ７０８でビット位置を次の位置に更新してから、ステップＳ７０４に戻る。なお、本実施形態では左から順に０、１、２……ビット目と数えるので、「次の位
置」とは現在のビット位置の右隣の位置のことである。
【０１８８】
ステップＳ７０９では、出力ビット列の末尾に、入力ビット列中のドントケアビットの数のぶん、“００”なるビット対を連結し、処理を終了する。
以上の処理により、例えば元ビット列“１０１＊＊”から、符号化ビット列“１１１０１１００００”が得られる。
【０１８９】
なお、本実施形態においては、元ビット列中の有意ビットの数とドントケアビットの数が、入力ビット列そのものとは別に指定されるものとする。ただし、固定長のビット列のみを扱う場合は、有意ビットの数からドントケアビットの数を求めることも、その逆も可能なので、一方のみが指定されてもよい。
【０１９０】
次に図８のフローチャートを参照して、初期検索を行う図６のステップＳ６０３の処理の詳細を説明する。
ステップＳ８０１において、探索経路スタックのスタックポインタの値を初期値に設定する。この初期値は、探索経路スタックに何も格納されていないときの値であり、後述の図１１の処理においても使われる。本実施形態の図８の処理におけるスタックポインタは、次に配列番号をステップＳ８１３においてプッシュすべき、探索経路スタック上の位置を示すものとして以下では説明する。
【０１９１】
続いてステップＳ８０２で、検索開始ノードの配列番号を取得する。図８の処理が実行されるのは、図６のステップＳ６０２が実行された後なので、ステップＳ８０２では具体的にはルートノードの配列番号を得る。
【０１９２】
次に、ステップＳ８０３で、カップルドノードツリーのノードを格納する配列から、ステップＳ８０１で取得した配列番号の指す配列要素をノードとして読み出す。
そして、ステップＳ８０４で、ステップＳ８０３で読み出したノードからノード種別を取り出し、ステップＳ８０５で、ノード種別がブランチノードであるか否かを判定する。
【０１９３】
ステップＳ８０５の判定において、読み出したノードがブランチノードである場合は、ステップＳ８０６に進み、ノードから弁別ビット位置についての情報を取り出し、更に、ステップＳ８０７で、取り出した弁別ビット位置に対応するビット値を検索キーから取り出す。そして、ステップＳ８０８で、ノードから代表ノード番号を取り出す。
【０１９４】
続いてステップＳ８１１で、ステップＳ８０６で取り出した弁別ビット位置が偶数か否かを判定する。
本実施形態の符号化によれば、符号化ビット列における偶数のビット位置にあるビットは識別ビットであり、奇数のビット位置にあるビットはデータビットである。よって、ステップＳ８１１の判定が偶数の場合、識別ビットが、該識別ビットを含むビット対が有意ビットを符号化して得られたか否かの判定のためにステップＳ８１２に進み、ステップＳ８０７で取り出したビット値が１か否かを判定する。
【０１９５】
ステップＳ８１２の判定が１の場合、本実施形態における符号化では、元検索キーの有意ビットの値を有するデータビットがまだ検索キーに残っている。そのため、ステップＳ８１３に進んで、ステップＳ８０３でノードを読み出した配列番号を探索経路スタックに格納する。
【０１９６】
続いてステップＳ８１４で、ステップＳ８０８で取り出した代表ノード番号に１を加えて、ステップＳ８０３で読み出したノードの子ノードにあたるノード［１］の配列番号を取得し、新たな配列番号として設定する。
【０１９７】
そして、ステップＳ８１５で、ステップＳ８１４で得た子ノードの配列番号を探索経路スタックに格納し、スタックポインタの値を１つ増やしてから、ステップＳ８０３に戻る。
【０１９８】
なおここで「１つ増やす」という表現は、図５の（ｃ）のように探索経路スタック３１０を２列に分けて図示する説明に合わせた表現であり、具体的な探索経路スタック３１０およびスタックポインタの実装方法を限定する趣旨のものではない。
【０１９９】
図５の（ｃ）の探索経路スタック３１０では、ステップＳ８１３で格納される配列番号を左列に、ステップＳ８１５で格納される配列番号を右列に、それぞれ図示している。ステップＳ８１５で行われるスタックポインタの値の更新は、図５の（ｃ）においてスタックポインタが指す行を次の行に移すことに相当する。
【０２００】
一方、ステップＳ８１１の判定が奇数の場合は、弁別ビット位置がデータビットの位置であることを表す。また、ステップＳ８１２の判定が０の場合は、本実施形態における符号化では、識別ビットが０であること、すなわち元検索キーにおけるドントケアビットを符号化したビット位置まで達したことを表す。
【０２０１】
ステップＳ８１１で奇数と判定された場合とステップＳ８１２で０と判定された場合は、いずれもステップＳ８０９に進む。
ステップＳ８０９では、検索キーからステップＳ８０７で取り出したビット値を、ステップＳ８０８で取り出した代表ノード番号に加算し、その加算の結果を新たな配列番号として設定する。ステップＳ８０９の実行後、処理はステップＳ８０３に戻る。
【０２０２】
以降、ステップＳ８０５の判定においてリーフノードと判定されてステップＳ８１０に進むまで、ステップＳ８０３からステップＳ８１５までの処理を繰り返す。繰り返しにおいては、ステップＳ８０９またはステップＳ８１４で設定された配列番号がステップＳ８０３で使われる。
【０２０３】
ステップＳ８１０では、リーフノードからインデックスキーを取り出して、処理を終了する。
なお、ドントケアビット“＊”は“００”と符号化されるので、ｊを０以上の整数とすると、符号化ビット列の２ｊビット目が“０”ならば、符号化ビット列の（２ｊ＋１）ビット目は必ず“０”である。
【０２０４】
そして、弁別ビット位置が２ｊのブランチノードの子ノードのうちノード［０］は、必ず、ｊビット目以降がすべてドントケアビットである元インデックスキーを符号化したインデックスキーを格納するリーフノードである。
【０２０５】
したがって、ステップＳ８１１からステップＳ８１２、Ｓ８０９、Ｓ８０３、Ｓ８０４、Ｓ８０５と処理が進む場合は、ステップＳ８０５において必ずリーフノードだと判定され、必ずステップＳ８１０へ分岐する。
【０２０６】
このノード［０］であるリーフノードを、（有意ビットの終端に達したという意味で）親のブランチノードから見て「終端側ノード」と呼び、終端側ノードと対になるノード［１］を「非終端側ノード」と呼ぶことにする。後述の図１１のステップＳ１１０７とステップＳ１１０８は、非終端側ノードから終端側ノードを求める処理である。
【０２０７】
次に図９のフローチャートを参照して、差分ビット位置を求める図６のステップＳ６０４の処理の詳細を説明する。
ステップＳ９０１で、比較ビット長を設定する。比較ビット長に設定する値は、検索キー中の、元検索キーの最上位のドントケアビットを符号化したビット対の位置と、図６のステップＳ６０３で得られたインデックスキー中の、元インデックスキーの最下位の有意ビットを符号化したビット対の位置のうち、より上位の位置までの、最上位である０ビット目からの長さである。別の言い方をすれば、比較ビット長は次の（１）〜（３）のように定められる。
（１）  元検索キーに有意ビットが含まれない場合、すなわち元検索キーの０ビット目がドントケアビットの場合は、元検索キーの０ビット目のドントケアビットを符号化したビット対は検索キーの０〜１ビット目である。よって、比較ビット長を２に設定する。
（２）  元検索キーに有意ビットが含まれるが、元インデックスキーに有意ビットが含まれない場合は、比較ビット長を０に設定する。
（３）  元検索キーと元インデックスキーの双方が有意ビットを含む場合は、比較ビット長を次のように定める。
【０２０８】
元検索キーの最上位のドントケアビットの位置をａ（ａ≧１）とすると、ａビット目のドントケアビットを符号化したビット対は、検索キーの２ａ〜（２ａ＋１）ビット目に位置する。なお、元検索キーが有意ビットのみからなる場合は、元検索キーの長さをｎとして、便宜的にａ＝ｎと見なすものとする。
【０２０９】
また、元インデックスキーの最下位の有意ビットの位置をｂ（ｂ≧０）とすると、ｂビット目の有意ビットを符号化したビット対は、インデックスキーの２ｂ〜（２ｂ＋１）ビット目に位置する。
【０２１０】
よって、（２ａ＋１）≦（２ｂ＋１）の場合、すなわちａ≦ｂの場合、比較ビット長は、０ビット目から（２ａ＋１）ビット目までの長さ、すなわち（２ａ＋２）に設定される。一方、（２ａ＋１）＞（２ｂ＋１）の場合、すなわちａ＞ｂの場合、比較ビット長は０ビット目から（２ｂ＋１）ビット目までの長さ、すなわち（２ｂ＋２）に設定される。
【０２１１】
上記（１）〜（３）のとおり、ステップＳ９０１で設定される比較ビット長は偶数なので、以下では説明の便宜上、比較ビット長を２ｃ（ｃ≧０）と表記する。
ステップＳ９０２で、検索キーとインデックスキーを、比較ビット長の指すビット列で比較して、比較ビット長の差分ビット列を得る。すなわち、検索キーとインデックスキーを、０〜（２ｃ−１）ビット目までの範囲で比較して、長さ２ｃの差分ビット列を得る。
【０２１２】
差分ビット列は、検索キーとインデックスキーで値が一致する位置のビットは値が０で、一致しない位置のビットは値が１となるビット列であり、例えば排他的論理和を求めるビット演算によって得ることができる。
【０２１３】
続いてステップＳ９０３で、差分ビット列を最上位の位置すなわち０ビット目から見て、最初の不一致ビットすなわち値が１のビットのビット位置を、差分ビット位置に設定し、処理を終了する。
【０２１４】
不一致ビットが存在しない場合は、後に差分ビット位置を参照することはないので、ステップＳ９０３において便宜的に差分ビット位置を例えば２ｃと設定してもよい。また、比較ビット長が０のときは、便宜的に差分ビット位置を負数に設定する。
【０２１５】
次に、図１０を参照して、差分ビット位置の具体例を説明する。
図１０の例では、検索キーは、元検索キー“１０１００”を符号化した符号化ビット列“１１１０１１１０１０”である。この元検索キーは有意ビットのみからなるので、上記
（３）の説明より便宜的にａ＝５と見なされる。
【０２１６】
一方、この検索キーによるステップＳ６０３の検索で得られるインデックスキーは、ドントケアビットを含む元インデックスキー“１０１１＊”を符号化したインデックスキー２５１ｅ“１１１０１１１１００”である。この元インデックスキーにおける最下位の有意ビットの位置はｂ＝３である。
【０２１７】
よって、ａ＞ｂなので、図９のステップＳ９０１では、８（＝２ｂ＋２）が比較ビット長に設定される。
そして、ステップＳ９０２で８ビットの差分ビット列が得られ、ステップＳ９０３で７が差分ビット位置に設定される。以上により、図９の処理、すなわち図６のステップＳ６０４が終了する。
【０２１８】
次に、図１１のフローチャートを参照して、最長一致キーを取得する図６のステップＳ６０６の処理の詳細を説明する。
ステップＳ１１０１で、検索キーと図６のステップＳ６０３で得られたインデックスキーを、比較ビット長２ｃの指すビット列で比較して、すなわち最上位の０ビット目から（２ｃ−１）ビット目までの範囲で比較して、両者が等しいか否かを判断する。
【０２１９】
ステップＳ１１０１で等しいと判断された場合、処理はステップＳ１１１１に進み、ステップＳ６０３で得られたインデックスキーを最長一致キーに設定して処理を終了する。
ステップＳ１１０１で等しくないと判断された場合、処理はステップＳ１１０２に進む。
【０２２０】
ステップＳ１１０２では、探索経路スタックのスタックポインタの値が初期値か否かを判断し、初期値であれば最長一致キーを設定せずに図１１の処理を終了し、そうでなければステップＳ１１０３に進む。
【０２２１】
図８のステップＳ８０１の説明から分かるとおり、本実施形態においてスタックポインタが初期値となるのは、探索経路スタックに最初にプッシュした配列番号をスタックポインタが指しているか、探索経路スタックが空であるときである。
【０２２２】
ステップＳ１１０３では、探索経路スタックのスタックポインタを１つ戻して、探索経路スタックから配列番号を取り出す。すなわち、ステップＳ１１０３の処理はポップ動作である。
【０２２３】
なお、図５の（ｃ）における探索経路スタック３１０の図示に合わせて説明すると、ステップＳ１１０３の処理は、１行上にスタックポインタを動かして、変更後のスタックポインタが指す行の左列から配列番号を取り出す処理である。
【０２２４】
続いてステップＳ１１０４では、カップルドノードツリーのノードを格納する配列から、ステップＳ１１０３で取り出した配列番号の指す配列要素をノードとして読み出す。
そして、ステップＳ１１０５では、ステップＳ１１０４で読み出したノードから、弁別ビット位置を取り出す。
【０２２５】
ここで、ステップＳ１１０３で取り出される配列番号は、必ず図８のステップＳ８１３において探索経路スタックにプッシュされた配列番号であって、図８のステップＳ８１５で探索経路スタックにプッシュされた配列番号ではない。
【０２２６】
次にステップＳ１１０６で、ステップＳ１１０５で取り出した弁別ビット位置は、図９
のステップＳ９０３で得た差分ビット位置よりも上位の位置関係にあるか否かを判断する。
【０２２７】
弁別ビット位置が差分ビット位置よりも上位の場合はステップＳ１１０７に進み、そうでない場合はステップＳ１１０２に戻る。
ステップＳ１１０７では、探索経路スタックから、探索経路スタックのスタックポインタの指す子ノードの配列番号を読み出す。
【０２２８】
例えば、図５の（ｃ）のようにスタックを図示することにすると、スタックポインタは行の位置を表し、左列は偶数の弁別ビット位置を含むノードの配列番号を表し、右列は同じ行の左列に書かれた配列番号のノードの子ノードのうち、非終端側ノードであるノード［１］の配列番号を表している。
【０２２９】
よって、図５の（ｃ）の図示にしたがって動作を説明するなら、ステップＳ１１０７では、スタックポインタの表す行の右列にある配列番号が読み出される。
続いて、ステップＳ１１０８で、ステップＳ１１０７で読み出された子ノードの配列番号と対をなす配列番号を得る。
【０２３０】
本実施形態では、ノード対を構成する２つのノードは隣接する配列番号の配列要素に格納されるので、ノード対を構成する２つのノードの配列番号同士も対をなす。例えば、ノード［０］は偶数の配列番号の配列要素に格納され、そのノード［０］と対になるノード［１］はその直後の奇数の配列番号の配列要素に格納される。よって、偶数と奇数の配列番号同士も対をなす。
【０２３１】
この例の場合、ステップＳ１１０８では、ステップＳ１１０７で読み出したノード［１］の配列番号から１を引くことにより、そのノード［１］とノード対を構成するノード［０］の配列番号が取得される。つまり、ステップＳ１１０８では非終端側ノードの配列番号から、リーフノードである終端側ノードの配列番号が取得される。
【０２３２】
次に、ステップＳ１１０９で、配列から、ステップＳ１１０８で得た配列番号の指す配列要素、すなわち終端側ノードでありリーフノードである上記のノード［０］を、ノードとして読み出す。
【０２３３】
続いて、ステップＳ１１１０では、ステップＳ１１０９で読み出したリーフノードからインデックスキーを取り出し、次のステップＳ１１１１において、取り出したインデックスキーを最長一致キーに設定して、図１１の処理を終了する。
【０２３４】
次に、図５のカップルドノードツリーを使った図６〜図９及び図１１の処理の具体例をいくつか説明する。
元検索キーが、図５の（ｂ）と図１０に示した“１０１００”のとき、図６のステップＳ６０３では、図５に「初期検索」と示したノード２１１ｅのインデックスキー２５１ｅが得られる。
【０２３５】
この場合、図１０を参照して説明したように８ビットが比較ビット長に設定され、差分ビット位置は７である。よって、図１１のステップＳ１１０２からステップＳ１１０６が実行され、配列番号２２１ｃのノード２１０ｄから弁別ビット位置２３０ｄが取り出される。
【０２３６】
弁別ビット位置２３０ｄの値は６であり、７より上位なので、ステップＳ１１０７からステップＳ１１１１が実行されて、図５に「最長一致」と示したノード２１０ｅのインデ
ックスキー２５０ｅが最長一致キーに設定される。これは、最長一致キーの定義の（ｂ）に該当する場合である。
【０２３７】
元検索キーが“１１００＊”のとき、図６のステップＳ６０３ではインデックスキー２５０ｆが得られる。この場合、元検索キーの最上位のドントケアビットの位置は４、元インデックスキーの最下位の有意ビットの位置は３なので、比較ビット長は８である。
【０２３８】
そして、図１１のステップＳ１１０１では検索キーとインデックスキーが等しいと判定され、ステップＳ１１１１に進み、インデックスキー２５０ｆが最長一致キーに設定される。この例は、最長一致キーの定義の（ａ）に該当する例である。
【０２３９】
元検索キーが“１１００１”のとき、図６のステップＳ６０３では、元インデックスキー“１１００＊”を符号化したインデックスキー２５０ｆが得られる。
この場合、元検索キーの最上位のドントケアビットの位置は便宜的に５と見なされ、元インデックスキーの最下位の有意ビットの位置が３なので、図９のステップＳ９０１では、８が比較ビット長に設定される。
【０２４０】
よって、図１１のステップＳ１１０１では検索キーとインデックスキーが等しいと判定され、ステップＳ１１１１に進み、インデックスキー２５０ｆが最長一致キーに設定される。この例も、最長一致キーの定義の（ｂ）に該当する例である。
【０２４１】
元検索キーが“１１＊＊＊”のとき、図６のステップＳ６０３では元インデックスキー“１１００＊”を符号化したインデックスキー２５０ｆが得られる。
この場合、元検索キーの最上位のドントケアビットの位置は２、元インデックスキーの最下位の有意ビットの位置は３なので、図９のステップＳ９０１では６が比較ビット長に設定される。差分ビット位置は４である。
【０２４２】
よって図１１ではステップＳ１１０１からステップＳ１１０２に進む。そして、ステップＳ１１０２からステップＳ１１０６が実行されて、配列番号（２２０ａ＋１）のノード２１１ｂから弁別ビット位置２３１ｂが取り出される。弁別ビット位置２３１ｂの値は２であり、４よりも上位である。
【０２４３】
よって、ステップＳ１１０７からステップＳ１１１１が実行され、ノード２１０ｃの、“１＊＊＊＊”を符号化したインデックスキー２５０ｃが最長一致キーに設定される。この例も、最長一致キーの定義の（ｂ）に該当する例である。
【０２４４】
元検索キーが“０＊＊＊＊”のとき、図６のステップＳ６０３では“１＊＊＊＊”を符号化したインデックスキー２５０ｃが得られる。この場合、元検索キーの最上位のドントケアビットの位置は１であり、元インデックスキーの最下位の有意ビットの位置は０なので、図９のステップＳ９０１では２が比較ビット長に設定され、差分ビット位置は１である。
【０２４５】
よって、図１１のステップＳ１１０２からステップＳ１１０６が実行されて、配列番号２２０のルートノード２１０ａから弁別ビット位置２３０ａが取り出される。弁別ビット位置２３０ａの値は０であり、１よりも上位である。
【０２４６】
よって、ステップＳ１１０７からステップＳ１１１１が実行され、ノード２１０ｂの、“＊＊＊＊＊”を符号化したインデックスキー２５０ｂが最長一致キーに設定される。この例も、最長一致キーの定義の（ｂ）に該当する例である。
【０２４７】
以上説明したとおり、上記の検索方法によれば、元検索キーと元インデックスキーの双方にドントケアビットがあっても検索を行うことができ、また、検索と選択という２段階の処理を行うことなく、一意に定まる最長一致キーを取得することができる。
【０２４８】
次に、図１２〜図１３Ｃのフローチャートを参照して、符号化ビット列を用いた検索用のカップルドノードツリーに、元挿入キーの指定にしたがって、リーフノードを挿入する処理について説明する。なお、ルートノードの挿入処理と、ルートノード以外のノードを既存のカップルドノードツリーに挿入する通常の挿入処理によりカップルドノードツリーが生成されることから、ノードの挿入処理の説明はカップルドノードツリーの生成処理の説明でもある。
【０２４９】
図１２のステップＳ１２０１で、指定された元挿入キーから図７の符号化処理により挿入キーを作成する。
続いて、ステップＳ１２０２において、取得することを求められたカップルドノードツリーのルートノードの配列番号が登録済みであるか否かが判定される。ステップＳ１２０２での判定が登録済みであればステップＳ１２０３へ進む。
【０２５０】
ステップＳ１２０３ではルートノードを検索開始ノードに設定する。
続いてステップＳ１２０４で、検索開始ノードより開始して、挿入キーにより、カップルドノードツリーのノードを格納する配列を検索し、挿入キーをインデックスキーとして挿入して（すなわち、挿入キーをインデックスキーとして含むリーフノードをカップルドノードツリーに挿入して）、図１２の処理を終了する。ステップＳ１２０４の処理の詳細は、図１３Ａ〜図１３Ｃを参照して後述する。
【０２５１】
一方、ステップＳ１２０２での判定が登録済みでなければ、まったく新しいカップルドノードツリーの登録、生成が始まることになる。
この場合、処理はステップＳ１２０５に進む。ステップＳ１２０５において、配列から空きのノード対を求め、そのノード対のうち代表ノードとなるべき配列要素の配列番号を取得する。
【０２５２】
次にステップＳ１２０６において、ステップＳ１２０５で得た配列番号に０を加えた配列番号を求める（本実施形態では、ステップＳ１２０５で取得した配列番号に等しい配列番号がここで得られるので、ステップＳ１２０６は省略可能である）。
【０２５３】
さらにステップＳ１２０７において、挿入するルートノード用にステップＳ１２０６で得た配列番号の配列要素の、ノード種別に１（リーフノード）を書き込むとともにインデックスキーに挿入キーを書き込む。
【０２５４】
そして、ステップＳ１２０８で、ステップＳ１２０６で取得した配列番号をルートノードの配列番号として登録して、図１２の処理を終了する。
次に、図１３Ａ〜図１３Ｃを参照して、図１２のステップＳ１２０４の処理の詳細を説明する。図１３Ａは挿入処理の前段である検索処理の処理フローを示す図であり、図４に示した検索処理において挿入キーを検索キーとしたものにほぼ相当する。
【０２５５】
ステップＳ１３０１は図４のステップＳ４０１で検索開始ノードをルートノードとしたものに相当する。また、ステップＳ１３０２〜ステップＳ１３１０の処理は、図４のステップＳ４０２〜ステップＳ４１０に完全に対応する。よって、これらのステップの説明は省略する。
【０２５６】
図４と図１３Ａの比較から分かるように、インデックスキーや挿入キーが符号化されて
いるか否かに関わらず、同様の処理によって検索開始ノードからリーフノードに至る検索が行われる。
【０２５７】
なお、図１３Ａにおいては、探索経路スタックの使い方が図４と同様であり、図８や図１１とは異なることに注意されたい。本実施形態における図１３Ａの処理では、スタックポインタは、ステップＳ１３０２のプッシュ動作によりプッシュされた配列番号を格納する、探索経路スタック上の場所を指している。
【０２５８】
図１３ＡのステップＳ１３１１において挿入キーとインデックスキーを比較し、等しければ挿入キーは既にカップルドノードツリーに存在するのであるから、挿入は失敗となり、処理を終了する。等しくなければ次の処理、すなわち図１３ＢのステップＳ１３１２以下の処理に進む。
【０２５９】
図１３Ｂは、挿入するノード対のための配列要素を準備する処理を説明する処理フロー図である。
ステップＳ１３１２において、配列から空きのノード対を求め、そのノード対のうち代表ノードとなるべき配列要素の配列番号を取得する。
【０２６０】
ステップＳ１３１３に進み、挿入キーとステップＳ１３１０で得たインデックスキーの大小を比較し、挿入キーが大きいときは値１、小さいときは値０のブール値を得る。
ステップＳ１３１４に進み、ステップＳ１３１２で得た代表ノードの配列番号にステップＳ１３１３で得たブール値を加算した配列番号を得る。
【０２６１】
ステップＳ１３１５に進み、ステップＳ１３１２で得た代表ノードの配列番号にステップＳ１３１３で得たブール値の論理否定値を加算した配列番号を得る。
ステップＳ１３１４で得た配列番号は、挿入キーをインデックスキーとして持つリーフノードが格納される配列要素の配列番号であり、ステップＳ１３１５で得た配列番号は、そのリーフノードと対を成すノードが格納される配列要素のものである。
【０２６２】
つまり、図１３Ａに示した前段の検索処理で得られたリーフノードに格納されたインデックスキーと挿入キーの大小により、挿入されるノード対のうちどちらのノードに挿入キーを保持するリーフノードが格納されるかが、図１３Ｂの処理により決定される。
【０２６３】
例えば、図５の（ａ）のカップルドノードツリーに、元挿入キー“１１０１＊”を符号化した挿入キー“１１１１１０１１００”をインデックスキーとして含むリーフノードを挿入する場合、図１３Ａの処理によって探索経路スタックには、配列番号２２０、（２２０ａ＋１）、（２２１ｂ＋１）、（２２１ｃ＋１）、２２１ｄが格納される。また、ステップＳ１３１０では配列番号２２１ｄのノード２１０ｆの“１１１１１０１０００”というインデックスキー２５０ｆが取り出されている。
【０２６４】
よって、ステップＳ１３１３で挿入キーとインデックスキーが比較され、挿入キーの方が大きいのでブール値１が得られ、挿入されるノード対の代表ノード番号に１を加えた配列要素に、挿入キーを保持するリーフノードが格納される。
【０２６５】
一方、図５の（ａ）のカップルドノードツリーに、元挿入キー“０＊＊＊＊”を符号化した挿入キー“１０００００００００”をインデックスキーとして含むリーフノードを挿入する場合、図１３Ａの処理によって探索経路スタックには、配列番号２２０、（２２０ａ＋１）、２２１ｂが格納される。また、ステップＳ１３１０ではノード２１０ｃの“１１００００００００”というインデックスキー２５０ｃが取り出されている。
【０２６６】
よって、ステップＳ１３１３で挿入キーとインデックスキーが比較され、挿入キーの方が小さいのでブール値０が得られ、挿入されるノード対の代表ノード番号に０を加えた配列要素に、挿入キーを保持するリーフノードが格納される。
【０２６７】
フローチャートの説明に戻ると、図１３ＢのステップＳ１３１５に続いて、図１３Ｃの処理が実行される。図１３Ｃは、図１３Ｂで準備された配列要素にノードを格納するとともにその挿入位置を求め、既存のノードの内容を変更して挿入処理を完成させる処理フローを示す図である。
【０２６８】
ステップＳ１３１６〜ステップＳ１３２３までの処理は、挿入するノード対のカップルドノードツリー上の位置を求める処理であり、ステップＳ１３２４以下の処理は各ノードにデータを設定して挿入処理を完成させる処理である。
【０２６９】
ステップＳ１３１６で、挿入キーとステップＳ１３１０で得たインデックスキーのビット列比較を例えば排他的論理和で行い、差分ビット列を得る。
ステップＳ１３１７に進み、ステップＳ１３１６で得た差分ビット列から、上位０ビット目から見た最初の不一致ビットのビット位置を得る。この処理は、例えばプライオリティエンコーダを有するＣＰＵではそこに差分ビット列を入力し、不一致のビット位置を得ることができる。また、ソフト的にプライオリティエンコーダと同等の処理を行い最初の不一致ビットのビット位置を得ることも可能である。
【０２７０】
次にステップＳ１３１８に進み、探索経路スタックのスタックポインタがルートノードの配列番号を指しているか判定する。指していればステップＳ１３２４に移行し、指していなければステップＳ１３１９に進む。
【０２７１】
ステップＳ１３１９において、探索経路スタックのスタックポインタを１つ戻してそこにスタックされている配列番号を取り出す。
ステップＳ１３２０に進み、ステップＳ１３１９で取り出した配列番号の配列要素を配列からノードとして読み出す。
【０２７２】
ステップＳ１３２１に進み、ステップＳ１３２０で読み出したノードから、弁別ビット位置を取り出す。
次にステップＳ１３２２に進み、ステップＳ１３２１で取り出した弁別ビット位置がステップＳ１３１７で得たビット位置より上位の位置関係か判定する。ここで上位の位置関係とは、ビット列のより左側の位置、すなわちビット位置の値が小さい位置であることとする。
【０２７３】
ステップＳ１３２２の判定結果が否定であれば、ステップＳ１３１８に戻り、ステップＳ１３１８での判定が肯定になるかステップＳ１３２２での判定が肯定になるまで繰り返す。ステップＳ１３２２での判定が肯定になると、ステップＳ１３２３で探索経路スタックのスタックポインタを１つ進め、ステップＳ１３２４以下の処理に移行する。
【０２７４】
上記ステップＳ１３１６〜ステップＳ１３２３で説明した処理は、挿入するノード対の挿入位置を決定するために、挿入キーと図１３Ａの検索により取得されたインデックスキーの間でビット列比較を行い、ビット列比較で異なるビット値となる先頭の（最上位の）ビット位置と探索経路スタックに格納されているブランチノードの弁別ビット位置との相対的位置関係を調べ、弁別ビット位置が上位となるブランチノードの次のブランチノードのリンク先を挿入するノード対の挿入位置とするものである。
【０２７５】
例えば、元挿入キーが“１１０１＊”である上記の例の場合、インデックスキー“１１
１１１０１０００”と挿入キー“１１１１１０１１００”とは７ビット目で異なる。また、１回目のステップＳ１３１９の実行により取り出された配列番号（２２１ｃ＋１）が指すノード２１１ｄの弁別ビット位置２３１ｄは５であり７より上位である。
【０２７６】
よって、ステップＳ１３２３によりスタックポインタが１つ進められ、スタックポインタは、ノード２１０ｆの配列番号２２１ｄを格納した探索経路スタック上の場所を指すこととなる。
【０２７７】
また、元挿入キーが“０＊＊＊＊”である上記の例の場合、インデックスキー“１１００００００００”と挿入キー“１０００００００００”は１ビット目で異なる。
よって、この例では、ステップＳ１３１８〜ステップＳ１３２２の繰り返しにより、探索経路スタックに積まれた配列番号の配列要素に格納されたブランチノードの弁別ビット位置と、１というビット位置との位置関係をチェックしながら、弁別ビット位置が上位になるまで順次探索経路スタックを逆にたどる。
【０２７８】
その結果、ステップＳ１３２２で、弁別ビット位置２３０ａの値が０であるルートノード２１０ａの配列番号２２０を指した状態となる。そして、ステップＳ１３２３でスタックポインタが１つ進められ、スタックポインタは、ノード２１１ｂの配列番号（２２０ａ＋１）を格納した探索経路スタック上の場所を指すこととなる。
【０２７９】
また、探索経路スタックを逆にたどりルートノードに至っても、ルートノードの弁別ビット位置が、先に求めたビット列比較で異なるビット値となる最上位のビット位置より上位のビット位置でないということは、そのカップルドノードツリーのインデックスキーの上位ビットで、ルートノードの弁別ビット位置より上位のビットの値は全て等しい場合である。そして、挿入キーにおいて、初めてルートノードの弁別ビット位置より上位のビットの値に異なるビット値のものがあるということである。
【０２８０】
したがって、そのような場合には、挿入するノード対はルートノードの直接のリンク先となり、ルートノードの弁別ビット位置は、既存のインデックスキーと異なる値である挿入キーの最上位ビットの位置に変わる。
【０２８１】
次に、ステップＳ１３２４以下の各ノードにデータを設定して挿入処理を完成させる処理について説明する。
ステップＳ１３２４では探索経路スタックからスタックポインタの指す配列番号を取り出す。
【０２８２】
ステップＳ１３２５において、ステップＳ１３１４で得た配列番号の指す配列要素のノード種別に１（リーフノード)を、インデックスキーに挿入キーを書き込む。
ステップＳ１３２６に進み、配列からステップＳ１３２４で得た配列番号の配列要素を読み出す。
【０２８３】
次にステップＳ１３２７において、ステップＳ１３１５で得た配列番号の配列要素にステップＳ１３２６で読み出した内容を書き込む。
最後にステップＳ１３２８において、ステップＳ１３２４で得た配列番号の指す配列要素のノード種別に０（ブランチノード）を、弁別ビット位置にステップＳ１３１７で得たビット位置を、代表ノード番号にステップＳ１３１２で得た配列番号を書き込み、処理を終了する。
【０２８４】
元挿入キーが“１１０１＊”である上記の例の場合、ステップＳ１３２５で、取得された空ノード対のノード［１］を、挿入キーを保持するリーフノードとする。
一方、ノード［０］にはステップＳ１３２７でノード２１０ｆの内容を書き込む。そして、ステップＳ１３２８で、ノード２１０ｆの弁別ビット位置に７を格納し、代表ノード番号には取得されたノード対の代表ノードが格納される配列要素の配列番号を格納する。
【０２８５】
また、元挿入キーが“０＊＊＊＊”である上記の例の場合、ステップＳ１３２５で、取得された空ノード対のノード［０］を、挿入キーを保持するリーフノードとする。
一方、ノード［１］にはステップＳ１３２７でノード２１１ｂの内容を書き込む。そして、ステップＳ１３２８で、ノード２１１ｂの弁別ビット位置２３１ｂに１を格納し、代表ノード番号には取得されたノード対の代表ノードが格納される配列要素の配列番号を格納する。
【０２８６】
先にも述べたように、インデックスキーの集合があるとき、そこから順次インデックスキーを取り出し、図１２〜図１３Ｃの処理を繰り返すことにより、インデックスキーの集合に対応した本発明のカップルドノードツリーを構築することができることは明らかである。
【０２８７】
次に、図１４〜図１５Ｂを参照して、符号化ビット列を用いた検索用のカップルドノードツリーから、元削除キーの指定にしたがって、リーフノードを削除する処理について説明する。
【０２８８】
図１４のステップＳ１４０１で、指定された元削除キーから、図７の符号化処理により、削除キーを作成する。続いて、ステップＳ１４０２で、カップルドノードツリーのルートノードを検索開始ノードに設定する。そして、ステップＳ１４０３で、削除キーにより、検索開始ノードより開始して、カップルドノードツリーのノードを格納する配列を検索し、削除キーと等しいインデックスキーを含むリーフノードをカップルドノードツリーから削除する。
【０２８９】
次に、図１５Ａと図１５Ｂを参照して、図１４のステップＳ１４０３の処理の詳細を説明する。
図１５Ａは、削除処理の前段である検索処理の処理フローを示す図であり、図４に示した検索処理において削除キーを検索キーとしたものにほぼ相当する。
【０２９０】
ステップＳ１５０１は図４のステップＳ４０１で検索開始ノードをルートノードとしたものに相当する。また、ステップＳ１５０２〜ステップＳ１５１０の処理は、図４のステップＳ４０２〜ステップＳ４１０に完全に対応する。よって、これらのステップの説明は省略する。
【０２９１】
図１５ＡのステップＳ１５１１において削除キーとインデックスキーを比較し、等しくなければければ削除すべきインデックスキーはカップルドノードツリーに存在しないのであるから、削除は失敗となり、処理を終了する。等しければ次の処理、つまり図１５ＢのステップＳ１５１２以下の処理に進む。
【０２９２】
図１５Ｂは、削除処理の後段の処理フローを説明する図である。
まず、ステップＳ１５１２で探索経路スタックに２つ以上の配列番号が格納されているか判定する。２つ以上の配列番号が格納されていないということは、言い換えれば１つだけで、その配列番号はルートノードの格納された配列要素のものである。
【０２９３】
その場合はステップＳ１５１８に移行し、ステップＳ１５０１で得たルートノードの配列番号に係るノード対を削除する。次にステップＳ１５１９に進み、登録されていたルートノードの配列番号を削除して処理を終了する。
【０２９４】
ステップＳ１５１２において探索経路スタックに２つ以上の配列番号が格納されていると判定されたときはステップＳ１５１３に進み、ステップＳ１５０８で得た代表ノード番号にステップＳ１５０７で得たビット値を反転した値を加算した配列番号を得る。この処理は、削除対象のインデックスキーが格納されたリーフノードと対をなすノードの配置された配列番号を求めるものである。
【０２９５】
次にステップＳ１５１４において、ステップＳ１５１３で得た配列番号の配列要素の内容を配列から読み出し、ステップＳ１５１５において探索経路スタックのスタックポインタを１つ戻して配列番号を取り出す。
【０２９６】
次にステップＳ１５１６に進み、ステップＳ１５１４で読み出した配列要素の内容をステップＳ１５１５で得た配列番号の配列要素に上書きする。この処理は、削除対象のインデックスキーが格納されたリーフノードへのリンク元であるブランチノードを上記リーフノードと対をなすノードに置き換えるものである。
【０２９７】
最後にステップＳ１５１７においてステップＳ１５０８で得た代表ノード番号に係るノード対を削除して処理を終了する。
以上のとおり、削除処理は挿入処理の場合と同様に、インデックスキーや削除キーが符号化されているか否かに関わらず、図４と同様の処理によって検索開始ノードからリーフノードに至る検索が行われる。また、削除処理における探索経路スタックの使い方も、図４と同様であり、図８や図１１とは異なる。この点において、図１４〜図１５Ｂの削除処理は、図１２〜図１３Ｃの挿入処理と類似である。
【０２９８】
以下に、図５の（ａ）のカップルドノードツリーに対して、元削除キー“１０１１＊”を指定して削除処理を行う場合を例に説明する。
まず、図１４のステップＳ１４０１で元削除キー“１０１１＊”から削除キー“１１１０１１１１００”が作成され、ステップＳ１４０３で、この削除キーを使って図１５Ａと図１５Ｂの処理が行われる。
【０２９９】
図１５Ａの処理では最初にステップＳ１５０１でルートノードの配列番号２２０を得る。
続いて、図１５Ａの処理により探索経路スタックには、配列番号２２０、（２２０ａ＋１）、（２２１ｂ＋１）、２２１ｃ、（２２０ｄ＋１）がこの順にプッシュされる。そして、図１５ＡのステップＳ１５１１で、配列番号（２２０ｄ＋１）に格納されたノード２１１ｅのインデックスキー２５１ｅと削除キーが比較され、両者が等しいことから図１５Ｂに進む。
【０３００】
図１５ＢのステップＳ１５１３では配列番号２２０ｄが得られ、ステップＳ１５１４で配列番号２２０ｄに格納されたノード２１０ｅの内容が読み出される。
続いて、ステップＳ１５１５で配列番号２２１ｃが取り出され、ステップＳ１５１６で配列番号２２１ｃに格納されたノード２１０ｄにノード２１０ｅの内容が書き込まれ、ステップＳ１５１７で配列番号２２０ｄにより示されるノード対２０１ｅが削除され、削除処理が終了する。
【０３０１】
以上説明したとおり、上記の挿入処理と削除処理において影響を受ける既存のノードの範囲は最小限であり、挿入や削除による保守コストが低いというカップルドノードツリーの長所は保たれている。また、上記のような符号化方法を採用することにより、この長所を保ちつつ、ドントケアビットを考慮した高速な最長一致検索が可能となる。そして、ドントケアビットを考慮した高速な最長一致検索のために必要なコストという観点から見て
、上記の符号化方法を、例えば特許文献３や特許文献４で行われる煩雑な前処理と比較すると、上記の符号化方法のコストは格段に低い。
【０３０２】
以上、本発明を実施するための最良の形態について詳細に説明したが、本発明の実施の形態はそれに限ることなく種々の変形が可能である。
上記の実施形態では、ビット値０に対応してリンクされるノード［０］を代表ノードとし、ビット値１に対応してリンクされるノード［１］を代表ノードと対になる非代表ノードとしていた。しかし、ノード［１］を代表ノードとし、ノード［０］を非代表ノードとしてもよい。なお、ルートノードを代表ノードの位置に配置するか非代表ノードの位置に配置するかが任意であることは、図２などに関する説明から明らかであろう。
【０３０３】
上記の実施形態では、リーフノードのインデックスキーに、符号化ビット列が格納されている。しかし、それ以外の形式のビット列をリーフノードのインデックスキーとして格納するように上記の実施形態を変形することも可能である。
【０３０４】
元ビット列においてドントケアビットが有意ビットよりも前に存在していないという前提条件があるため、例えば、元ビット列のうち有意ビットの部分のみを符号化しない形でインデックスキーとして格納することも可能である。元ビット列が固定長の場合は、このような形式のインデックスキーから、ドントケアビットのビット数を求めることも可能である。
【０３０５】
また、このような形式のインデックスキーの場合、元ビット列の長さは符号化ビット列の半分以下であるため、リーフノードに必要な記憶容量を半分以下に削減することが可能である。換言すれば、同じリーフノードの記憶容量で２倍以上の長さのビット列を扱うことが可能となる。いずれにしろ、記憶領域の利用効率が上がる。
【０３０６】
なお、このような形式のインデックスキーを利用する実施形態では、例えば、図６のステップＳ６０４でインデックスキーを符号化してから元検索キーと比較するなど、上記の実施形態を適宜変更する必要があることは明らかである。
【０３０７】
あるいは、ドントケアビットに任意のビット値を設定したビット列と、有意ビットの範囲を示すビット列（例えば、マスクビット列や、数値を表すビット列など）との組み合わせによって元ビット列を表し、その組み合わせをリーフノードのインデックスキーとして格納してもよい。
【０３０８】
また、上記の実施形態では、符号化されていない元検索キーが入力として与えられ、検索処理は符号化処理を含んでいる。しかし、予め符号化された検索キーを入力として与えられた場合には、符号化処理は不要である。挿入処理と削除処理においても同様のことが言える。
【０３０９】
なお、符号化処理は、図７に示した方法以外の方法によって実現することも可能である。例えば、入力ビット列をシフトレジスタ等によって１ビットずつシフトさせながら、１ビットずつ入力ビット列から取り出し、取り出した１ビットと識別ビットを連結する方法を採用してもよい。
【０３１０】
また、上記の実施形態で採用した符号化方法以外の符号化方法を採用することも可能である。上記実施形態の符号化方法では、元ビット列における１ビットを符号化ビット列における２ビットに符号化しているが、このような１：２の対応関係を有する符号化方法以外の符号化方法を採用することも可能である。
【０３１１】
例えば、元ビット列における１ビットを符号化ビット列における３ビットに符号化してもよい。また、上記実施形態の符号化方法の識別ビットは、値が０のときドントケアビットを示し、値が１のとき有意ビットを示すが、逆でもよい。
【０３１２】
なお、検索処理は、符号化方法に合わせて適宜変更する必要がある。例えば、識別ビットの０と１の意味が上記実施形態と逆の符号化方法を採用した場合は、図８のステップＳ８１２で、ビット値が０のときステップＳ８１３に進み、ビット値が１のときステップＳ８０９に進むように変更し、ステップＳ８１４で代表ノード番号に加える値を１から０に変更する必要がある。一方、挿入処理と削除処理は符号化方法によらず、上記実施形態の方法を採用することが可能である。
【０３１３】
また、上記の図５において“０＊＊＊＊”を元検索キーとしたときの最長一致キーは、“＊＊＊＊＊”を符号化した“００００００００００”だが、この場合、最長一致キーの元ビット列“＊＊＊＊＊”が表す集合は、“１”から始まるビット列を包含する。しかし、“１”から始まるビット列と元検索キー“０＊＊＊＊”は、最上位の０ビット目が異なっている。検索の目的によっては、このような場合を検索失敗として扱いたいことがある。
【０３１４】
そこで、最長一致キーの元ビット列は少なくとも０ビット目が有意ビットであり、最長一致キーの元ビット列と元検索キーとは、少なくとも０ビット目の値が一致していなくてはならないという制約を課すことも考えられる。この制約を課すために、図６の処理を次のように変形してもよい。
【０３１５】
すなわち、ステップＳ６０４とステップＳ６０６の間に、求めた差分ビット位置が０ビット目か否かを判定する新たなステップＳ６０５を追加する。
差分ビット位置が０ビット目のとき、上記の制約を満たす最長一致キーはカップルドノードツリーに存在しないので、検索は失敗し、図６の処理は終了する。一方、ステップＳ６０５で差分ビット位置が０ビット目でないときは、処理がステップＳ６０６へ進む。
【０３１６】
あるいは、この変形例をさらに変形し、ステップＳ６０５で差分ビット位置が１以下なら処理を終了し、差分ビット位置が２以上ならステップＳ６０６へ処理が進むようにしてもよい。
【０３１７】
また、常に検索キーの方がインデックスキーよりも有意ビット長が長いことが保証されているような応用分野において本発明の検索方法を利用する場合は、図８のステップＳ８１２を省略し、ステップＳ８１１で弁別ビット位置が偶数のときステップＳ８１３に進むようにしてもよい。
【０３１８】
上記の検索処理は用途に応じて他にも様々に変形することが可能である。例えば、図６ではステップＳ６０２でルートノードを検索開始ノードに設定しているが、任意の部分木のルートノードを検索開始ノードとしてもよい。
【０３１９】
また、上記の各処理において探索経路スタックを利用しているが、探索経路スタックの実現方法は任意である。図５では、理解を容易にするために、探索経路スタックを２列に分けて表示しているが、この図示は探索経路スタックの実現方法を限定するものではない。
【０３２０】
さらに、図８の処理では、処理の効率化のために、弁別ビット位置が偶数のブランチノードとその子ノードであるノード［１］の配列番号を探索経路スタックに格納している。しかし、挿入処理や削除処理と同様に検索開始ノードからリーフノードへ至る経路上のす
べてのノードの配列番号を探索経路スタックに格納してもよい。
【０３２１】
その場合、図１１のステップＳ１１０７とステップＳ１１０８のかわりに、探索経路スタックからブランチノードの配列番号を読み出し、その配列番号のブランチノードを配列から読み出して、代表ノード番号を取り出してもよい。取り出された代表ノード番号は、このブランチノードの子ノードのうち代表ノードであるノード［０］の配列番号であるから、ステップＳ１１０９以降は図１１と同様に実行することが可能である。
【０３２２】
あるいは、図８ではステップＳ８１４で得た非終端側ノードであるノード［１］の配列番号をステップＳ８１５で探索経路スタックに格納しているが、ステップＳ８１５では終端側ノードであるノード［０］の配列番号を探索経路スタックに格納するように、上記の実施形態を変形してもよい。
【０３２３】
ただし、その場合でも、ステップＳ８１４で配列番号を得たノード［１］が、ステップＳ８１５の直後のステップＳ８０３で読み出される点は図８と同様である。このような変形を行う場合は、図１１のステップＳ１１０７とステップＳ１１０８のかわりに、ノード［０］の配列番号を直接探索経路スタックから読み出すようにすればよい。
【０３２４】
なお、本発明の検索方法、挿入方法、または削除方法を実行する装置が、カップルドノードツリーを格納する記憶手段と、各フローチャートに示した処理をコンピュータに実行させるプログラムによりコンピュータ上に構築可能なことは明らかである。したがって、上記プログラム、及びプログラムを記憶したコンピュータ読み取り可能な記憶媒体は、本発明の実施の形態に含まれる。
【図面の簡単な説明】
【０３２５】
【図１】配列に格納されたカップルドノードツリーの構成例を説明する図である。
【図２】カップルドノードツリーのツリー構造を概念的に示す図である。
【図３】本発明を実施するためのハードウェア構成例を説明する図である。
【図４】一実施形態における検索処理を示すフローチャートである。
【図５】符号化ビット列を利用したカップルドノードツリーのツリー構造を概念的に示す図である。
【図６】一実施形態における検索処理を示すフローチャートである。
【図７】一実施形態における符号化処理を示すフローチャートである。
【図８】検索処理における初期検索のフローチャートである。
【図９】差分ビット位置を求める処理のフローチャートである。
【図１０】差分ビット位置の例を示す図である。
【図１１】検索処理において最長一致キーを求める処理のフローチャートである。
【図１２】一実施形態における挿入処理を示すフローチャートである。
【図１３Ａ】挿入処理の前段である検索処理のフローチャートである。
【図１３Ｂ】挿入するノード対のための配列要素を準備する処理を説明するフローチャートである。
【図１３Ｃ】ノード対を挿入する位置を求め、ノード対の各ノードの内容を書き込んで挿入処理を完成させるフローチャートである。
【図１４】一実施形態における削除処理を示すフローチャートである。
【図１５Ａ】削除処理の前段である検索処理のフローチャートである。
【図１５Ｂ】削除処理の後段を示すフローチャートである。
【図１６】従来の検索で用いられるパトリシアツリーの一例を示す図である。
【符号の説明】
【０３２６】
１０、２０、３０  配列番号
１００  配列
１０１  ノード
１０２、１１４、１１７、１２４、１２６、２６０ａ〜２６０ｈ、２６１ｂ〜２６１ｈ
ノード種別
１０３、１１５、２３０ａ〜２３０ｆ、２３１ｂ〜２３１ｆ  弁別ビット位置
１０４、１１６、２２０、２２０ａ〜２２０ｆ、２２１ｂ〜２２１ｆ  代表ノード番号
１１１、１２１、２０１ａ〜２０１ｈ  ノード対
１１２、１２２、２１０ａ〜２１０ｈ  ノード［０］、代表ノード
１１３、１２３、２１１ｂ〜２１１ｈ  ノード［１］、代表ノードと対をなす非代表ノード
１１８、２５０ｃ〜２５０ｈ、２５１ｄ〜２５１ｈ  インデックスキー
２７０  検索キー
３０１  データ処理装置
３０２  中央処理装置
３０３  キャッシュメモリ
３０４  バス
３０５  主記憶装置
３０６  外部記憶装置
３０７  通信装置
３０８  データ格納装置
３０９  配列
３１０  探索経路スタック
１７３０ａ〜１７３０ｈ  検査ビット位置
１７４０ａ〜１７４０ｈ  左リンク、左ポインタ
１７４１ａ〜１７４１ｈ  右リンク、右ポインタ
１７５０ａ〜１７５０ｈ  ノード
【図１】
0004527753.tif 000002
【図２】
0004527753.tif 000003
【図３】
0004527753.tif 000004
【図４】
0004527753.tif 000005
【図５】
0004527753.tif 000006
【図６】
0004527753.tif 000007
【図７】
0004527753.tif 000008
【図８】
0004527753.tif 000009
【図９】
0004527753.tif 000010
【図１０】
0004527753.tif 000011
【図１１】
0004527753.tif 000012
【図１２】
0004527753.tif 000013
【図１３Ａ】
0004527753.tif 000014
【図１３Ｂ】
0004527753.tif 000015
【図１３Ｃ】
0004527753.tif 000016
【図１４】
0004527753.tif 000017
【図１５Ａ】
0004527753.tif 000018
【図１５Ｂ】
0004527753.tif 000019
【図１６】
0004527753.tif 000020