【手続補正書】
【提出日】平成20年11月11日(2008.11.11)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対、からなるビット列検索に用いるツリーであって、
前記ルートノードは、前記ツリーの始点を表すノードであって、該ツリーのノードが１つのときは前記リーフノード、該ツリーのノードが２つ以上のときは前記ブランチノードであり、
前記ブランチノードは、ビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードの位置を示す情報を含み、前記リーフノードは検索対象のビット列からなるインデックスキーを含む、カップルドノードツリーを備え、
前記ルートノードを含む前記ブランチノードにおいて、該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード対のどちらかのノードにリンクすることを順次前記リーフノードに至るまで繰り返すことにより前記検索キーによる検索を実行し、前記リーフノードに含まれるインデックスキーと前記検索キーを比較し、一致すれば検索成功とし、一致しなければ検索失敗とすることを特徴とするビット列検索装置。
【請求項２】
前記カップルドノードツリーは、配列に記憶され、前記リンク先のノード対の一方のノードの位置を示す情報は、そのノードが格納された前記配列の配列要素の配列番号であることを特徴とする請求項１記載のビット列検索装置。
【請求項３】
前記配列番号と前記検索キーの弁別ビット位置のビット値との演算によりリンク先のノードの格納された配列要素の配列番号を求めることを特徴とする請求項２記載のビット列検索装置。
【請求項４】
前記ブランチノードとリーフノードは、それぞれのノードの種別を示すデータを含むことを特徴とする請求項１記載のビット列検索装置。
【請求項５】
配列の配列要素に記憶されるルートノードと、配列の隣接した配列要素に記憶されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対、からなるビット列検索に用いるツリーであって、前記ルートノードは、前記ツリーの始点を表すノードであって、該ツリーのノードが１つのときは前記リーフノード、該ツリーのノードが２つ以上のときは前記ブランチノードであり、前記ブランチノードは、ビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードが格納された前記配列の配列要素の配列番号を含み、前記リーフノードは検索対象のビット列からなるインデックスキーを含むカップルドノードツリーに、所望のビット列からなるインデックスキーを含むリーフノードを挿入するインデックスキー挿入方法において、
前記インデックスキーを前記検索キーとして、前記ルートノードを含む前記ブランチノードにおいて、該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード対のどちらかのノードにリンクすることを順次前記リーフノードに至るまで繰り返すことにより前記検索キーによる検索を実行するとともに、該リーフノードに至るまでたどったリンク経路のブランチノード及び該リーフノードが格納された配列要素の配列番号をスタックに順次格納し、
前記検索キーと前記該当するリーフノードに含まれるインデックスキーの間で大小比較とビット列比較を行い、
ビット列比較で異なるビット値となる先頭のビット位置と前記スタックに格納されているブランチノードの弁別ビット位置との相対的位置関係により挿入されるインデックスキーを含むリーフノードともう一方のノードからなるノード対の挿入位置を決定し、
前記大小関係により挿入するインデックスキーを含むリーフノードを前記挿入されるノード対のどちらのノードとするかを決定する、
ことを特徴とするインデックスキー挿入方法。
【請求項６】
配列の配列要素に記憶されるルートノードと、配列の隣接した配列要素に記憶されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対、からなるビット列検索に用いるツリーであって、前記ルートノードは、前記ツリーの始点を表すノードであって、該ツリーのノードが１つのときは前記リーフノード、該ツリーのノードが２つ以上のときは前記ブランチノードであり、前記ブランチノードは、ビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードが格納された前記配列の配列要素の配列番号を含み、前記リーフノードは検索対象のビット列からなるインデックスキーを含むカップルドノードツリーの生成方法において、
前記インデックスキーの集合から１つのインデックスキーを取り出し、該インデックスキーを含むリーフノードをルートノードとするカップルドノードツリーを生成し、
さらに前記インデックスキーの集合から順次インデックスキーを取り出して該インデックスキーを含むリーフノードを、請求項５記載のインデックスキー挿入方法により前記カップルドノードツリーに挿入することによりカップルドノードツリーを生成することを特徴とするカップルドノードツリーの生成方法。
【請求項７】
配列の配列要素に記憶されるルートノードと、配列の隣接した配列要素に記憶されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対、からなるビット列検索に用いるツリーであって、前記ルートノードは、前記ツリーの始点を表すノードであって、該ツリーのノードが１つのときは前記リーフノード、該ツリーのノードが２つ以上のときは前記ブランチノードであり、前記ブランチノードは、ビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードが格納された前記配列の配列要素の配列番号を含み、前記リーフノードは検索対象のビット列からなるインデックスキーを含むカップルドノードツリーから任意のインデックスキーを含むリーフノードを削除するインデックスキー削除方法において、
前記インデックスキーを前記検索キーとして、前記ルートノードを含む前記ブランチノードにおいて、該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード対のどちらかのノードにリンクすることを順次前記リーフノードに至るまで繰り返すことにより前記検索キーによる検索を実行し、
削除対象のインデックスキーを保持する前記リーフノードと同一ノード対を構成するノードの内容を当該ノード対のリンク元のブランチノードに書き込み、
当該ノード対を削除する、
ことを特徴とするインデックスキー削除方法。
【請求項８】
ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対、からなるビット列検索に用いるツリーであって、
前記ルートノードは、ツリーの始点を表すノードであって、該ツリーのノードが１つのときは前記リーフノード、ツリーのノードが２つ以上のときは前記ブランチノードであり、
前記ブランチノードは、ビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードの位置を示す情報を含み、前記リーフノードは検索対象のビット列からなるインデックスキーを含むカップルドノードツリーを用いたビット列検索方法において、
前記ルートノードを含む前記ブランチノードにおいて、該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード対のどちらかのノードにリンクすることを順次前記リーフノードに至るまで繰り返すことにより、
前記検索キーによる検索を実行し、前記リーフノードに含まれるインデックスキーと前記検索キーを比較し、一致すれば検索成功とし、一致しなければ検索失敗とすることを特徴とするビット列検索方法。
【請求項９】
前記カップルドノードツリーは、配列に記憶され、前記リンク先のノード対の一方のノードの位置を示す情報は、そのノードが格納された前記配列の配列要素の配列番号であることを特徴とする請求項８記載のビット列検索方法。
【請求項１０】
前記配列番号と前記検索キーの弁別ビット位置のビット値との演算によりリンク先のノードの格納された配列要素の配列番号を求めることを特徴とする請求項９記載のビット列検索方法。
【請求項１１】
請求項８〜１０記載のビット列検索方法をコンピュータに実行させるためのプログラム。
【請求項１２】
請求項５記載のインデックスキー挿入方法をコンピュータに実行させるためのプログラム。
【請求項１３】
請求項６記載のカップルドノードツリー生成方法をコンピュータに実行させるためのプログラム。
【請求項１４】
請求項７記載のインデックスキー削除方法をコンピュータに実行させるためのプログラム。
【請求項１５】
ビット列検索に用いるツリー状のデータ構造であって、
ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対、からなり、
前記ルートノードは、前記ツリーの始点を表すノードであって、該ツリーのノードが１つのときは前記リーフノード、該ツリーのノードが２つ以上のときは前記ブランチノードであり、
前記ブランチノードは、ビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードの位置を示す情報を含み、
前記リーフノードは検索対象のビット列からなるインデックスキーを含み、
前記ルートノードを含む前記ブランチノードにおいて、該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード対のどちらかのノードにリンクすることを順次前記リーフノードに至るまで繰り返すことにより前記検索キーによる検索の実行を可能とすることを特徴とするデータ構造。
【請求項１６】
前記データ構造は、配列に記憶され、前記リンク先のノード対の一方のノードの位置を示す情報は、そのノードが格納された前記配列の配列要素の配列番号であることを特徴とする請求項１５記載のデータ構造。