【手続補正書】
【提出日】平成21年9月26日(2009.9.26)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ビット列からなる検索キーにより検索対象であるビット列からなるインデックスキーが格納されたツリーのデータ構造に基づいて前記インデックスキーを検索するビット列検索装置において、
前記ツリーの始点であるルートノードと、隣接した記憶領域に配置される代表ノードと非代表ノードである２つのノードを有する、ツリーの構成要素としてのノード対を有し、前記ノードは該ノードがブランチノードであるかリーフノードであるかを示すノード種別を格納する領域を有し、前記ブランチノードは、前記ノード種別に加えて、前記検索キーの弁別ビット位置を格納する領域とリンク先のノード対の代表ノードの位置を示す位置情報を格納する領域を含むが、前記検索対象のビット列からなるインデックスキーを格納する領域を含まないものであり、前記リーフノードは、前記ノード種別に加えて、前記検索対象のビット列からなるインデックスキーを格納する領域を含むが、前記検索キーの弁別ビット位置を格納する領域とリンク先のノード対の代表ノードの位置を示す位置情報を格納する領域を含まないものである、カップルドノードツリーと、
前記ノード対のどちらか一方のノードである検索開始ノードの位置を示す位置情報を取得し、該取得した検索開始ノードの位置を示す位置情報により検索開始ノードを読み出す検索開始ノード読出手段と、
前記ノードのノード種別を格納する領域から当該ノード種別を読み出し、該ノード種別が前記リーフノードを示すものであるかブランチノードを示すものであるかを判定するノード種別判定手段と、
前記リーフノードのインデックスキーを格納する領域から当該インデックスキーを読み出すインデックスキー読出手段と、
前記ブランチノードの弁別ビット位置を格納する領域とリンク先のノード対の代表ノードの位置を示す位置情報を格納する領域からそれぞれ当該弁別ビット位置とリンク先のノード対の代表ノードの位置を示す位置情報を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記読み出したリンク先のノード対の代表ノードの位置を示す位置情報との演算によりリンク先のノード対のどちらかのノードの位置を示す位置情報を求め、該求めたノードの位置を示す位置情報により示される記憶領域から、該記憶領域に配置されたノードをリンク先ノードとして読み出すリンク手段と、
を備え、
前記検索開始ノード読出手段で読み出した検索開始ノードのノード種別を前記ノード種別判定手段で判定し、該ノード種別がリーフノードを示すものであれば、該リーフノードから前記インデックスキー読出手段によりインデックスキーを読み出し、該ノード種別がブランチノードを示すものであれば、前記リンク手段によりリンク先ノードを読み出し、該読み出したリンク先ノードのノード種別を前記ノード種別判定手段で判定することを該ノード種別がリーフノードを示すものとなるまで繰り返し、該リーフノードから前記インデックスキー読出手段によりインデックスキーを読み出し、
前記インデックスキー読出手段により読み出されたインデックスキーを、前記検索開始ノードをそのルートノードとする前記カップルドノードツリーの部分木の前記検索キーによる検索結果である検索結果キーとするとともに、
前記検索開始ノードの配置された記憶領域のアドレス情報及び前記検索開始ノードから前記リーフノードに至るリンク先のノードの配置された記憶領域のアドレス情報と前記検索開始ノードから前記リーフノードに至るリンク経路のブランチノードの弁別ビット位置を順次スタックに格納することを特徴とするビット列検索装置。
【請求項２】
前記カップルドノードツリーは配列に記憶され、前記位置情報は、該位置情報に対応する前記代表ノードが配置された前記配列の配列要素の配列番号であり、
前記検索開始ノード及びリンク先のノードの配置された記憶領域のアドレス情報は、前記検索開始ノード及びリンク先のノードの配置された配列要素の配列番号であることを特徴とする請求項１記載のビット列検索装置。
【請求項３】
ビット列からなる検索キーにより検索対象であるビット列からなるインデックスキーが格納されたツリーのデータ構造に基づいて前記インデックスキーを検索するビット列検索装置が、前記ツリーに所望のビット列からなる挿入キーをインデックスキーとして格納するインデックスキー挿入方法において、
前記ツリーは、該ツリーの始点であるルートノードと、隣接した記憶領域に配置される代表ノードと非代表ノードである２つのノードを有する、ツリーの構成要素としてのノード対を有し、前記ノードは該ノードがブランチノードであるかリーフノードであるかを示すノード種別を格納する領域を有し、前記ブランチノードは、前記ノード種別に加えて、前記検索キーの弁別ビット位置を格納する領域とリンク先のノード対の代表ノードの位置を示す位置情報を格納する領域を含むが、前記検索対象のビット列からなるインデックスキーを格納する領域を含まないものであり、前記リーフノードは、前記ノード種別に加えて、前記検索対象のビット列からなるインデックスキーを格納する領域を含むが、前記検索キーの弁別ビット位置を格納する領域とリンク先のノード対の代表ノードの位置を示す位置情報を格納する領域を含まないものである、カップルドノードツリーであり、
前記ビット列検索装置は、
前記ノード対のどちらか一方のノードである検索開始ノードの位置を示す位置情報を取得し、該取得した検索開始ノードの位置を示す位置情報により検索開始ノードを読み出す検索開始ノード読出手段と、
前記ノードのノード種別を格納する領域から当該ノード種別を読み出し、該ノード種別が前記リーフノードを示すものであるかブランチノードを示すものであるかを判定するノード種別判定手段と、
前記リーフノードのインデックスキーを格納する領域から当該インデックスキーを読み出すインデックスキー読出手段と、
前記ブランチノードの弁別ビット位置を格納する領域とリンク先のノード対の代表ノードの位置を示す位置情報を格納する領域からそれぞれ当該弁別ビット位置とリンク先のノード対の代表ノードの位置を示す位置情報を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記読み出したリンク先のノード対の代表ノードの位置を示す位置情報との演算によりリンク先のノード対のどちらかのノードの位置を示す位置情報を求め、該求めたノードの位置を示す位置情報により示される記憶領域から、該記憶領域に配置されたノードをリンク先ノードとして読み出すリンク手段と、
を備え、
前記挿入キーを前記検索キーとして、
前記ルートノード読出手段でルートノードを読み出し、該読みだしたルートノードのノード種別を前記ノード種別判定手段で判定し、該ノード種別がリーフノードを示すものであれば、該リーフノードから前記インデックスキー読出手段によりインデックスキーを読み出し、該ノード種別がブランチノードを示すものであれば、前記リンク手段により前記リンク先ノードを読み出し、該読み出したリンク先ノードのノード種別を前記ノード種別判定手段で判定することを該ノード種別がリーフノードを示すものとなるまで繰り返し、該リーフノードから前記インデックスキー読出手段によりインデックスキーを読み出すとともに、該リーフノードに至るまでたどったリンク経路のブランチノード及び該リーフノードの位置を示す位置情報と該ブランチノードの弁別ビット位置をスタックに順次格納する検索ステップと、
前記検索ステップで読み出したインデックスキーと前記挿入キーの間で大小比較とビット列比較を行う比較ステップと、
ノード対を配置する空の隣接した記憶領域の組を取得し、代表ノードが配置される記憶領域の位置を示す位置情報を取得する空ノード対取得ステップと、
前記比較ステップにおける前記大小比較により挿入キーを含むリーフノードを前記空ノード対取得ステップで取得した空の隣接した記憶領域の組のどちらの空記憶領域に配置するかを決定するリーフノード格納位置決定ステップと、
前記比較ステップにおけるビット列比較で異なるビット値となる先頭のビット位置と、前記検索ステップで順次格納されたブランチノードの弁別ビット位置との相対的位置関係により、該ブランチノードの位置を示す位置情報を読み出し、該位置情報が示す記憶領域に配置されているノードを、前記空ノード対取得ステップで取得した空の隣接した記憶領域の組に配置されるノード対のリンク元として該ノード対の挿入位置を決定するノード対挿入位置決定ステップと、
前記リーフノード格納位置決定ステップで決定した空記憶領域に配置するリーフノードの、ノード種別を格納する領域にリーフノードであることを示すノード種別を、インデックスキーを格納する領域に前記挿入キーを書き込み、もう一方の空記憶領域に、前記ノード対挿入位置決定ステップで読み出したノードの位置を示す位置情報が示す記憶領域に配置されているノードの内容を読み出して書き込むことで挿入ノード対を生成する挿入ノード対生成ステップと、
前記ノード対挿入位置決定ステップで読み出したノードの位置を示す位置情報が示す記憶領域に配置されているノードをブランチノードとし、そのノード種別を格納する領域にブランチノードであることを示すノード種別を、弁別ビット位置を格納する領域に前記比較ステップにおけるビット列比較で異なるビット値となる先頭のビット位置を、リンク先のノード対の代表ノードの位置を示す前記位置情報を格納する領域に前記空ノード対取得ステップで取得した前記位置情報を、それぞれ書き込むブランチノード生成ステップと、
を備えたことを特徴とするインデックスキー挿入方法。
【請求項４】
前記カップルドノードツリーは配列に記憶され、前記位置情報は、該位置情報に対応する前記代表ノードが配置された前記配列の配列要素の配列番号であり、
前記検索開始ノード及びリンク先のノードの配置された記憶領域のアドレス情報は、前記検索開始ノード及びリンク先のノードの配置された配列要素の配列番号であることを特徴とする請求項３記載のインデックスキー挿入方法。
【請求項５】
ビット列検索装置が、ビット列からなる検索キーにより検索対象であるビット列からなるインデックスキーが格納されたツリーのデータ構造に基づいて前記インデックスキーを検索するビット列検索方法において、
前記ツリーは、該ツリーの始点であるルートノードと、隣接した記憶領域に配置される代表ノードと非代表ノードである２つのノードを有する、ツリーの構成要素としてのノード対を有し、前記ノードは該ノードがブランチノードであるかリーフノードであるかを示すノード種別を格納する領域を有し、前記ブランチノードは、前記ノード種別に加えて、前記検索キーの弁別ビット位置を格納する領域とリンク先のノード対の代表ノードの位置を示す位置情報を格納する領域を含むが、前記検索対象のビット列からなるインデックスキーを格納する領域を含まないものであり、前記リーフノードは、前記ノード種別に加えて、前記検索対象のビット列からなるインデックスキーを格納する領域を含むが、前記検索キーの弁別ビット位置を格納する領域とリンク先のノード対の代表ノードの位置を示す位置情報を格納する領域を含まないものである、カップルドノードツリーであって、
前記ノード対のどちらか一方のノードである検索開始ノードの位置を示す位置情報を取得し、該取得した検索開始ノードの位置を示す位置情報により検索開始ノードを読み出す検索開始ノード読出ステップと、
前記ノードのノード種別を格納する領域から当該ノード種別を読み出し、該ノード種別が前記リーフノードを示すものであるかブランチノードを示すものであるかを判定するノード種別判定ステップと、
前記リーフノードのインデックスキーを格納する領域から当該インデックスキーを読み出すインデックスキー読出ステップと、
前記ブランチノードの弁別ビット位置を格納する領域とリンク先のノード対の代表ノードの位置を示す位置情報を格納する領域からそれぞれ当該弁別ビット位置とリンク先のノード対の代表ノードの位置を示す位置情報を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記読み出したリンク先のノード対の代表ノードの位置を示す位置情報との演算によりリンク先のノード対のどちらかのノードの位置を示す位置情報を求め、該求めたノードの位置を示す位置情報により示される記憶領域から、該記憶領域に配置されたノードをリンク先ノードとして読み出すリンクステップと、
を備え、
前記検索開始ノード読出ステップで読み出した検索開始ノードのノード種別を前記ノード種別判定ステップで判定し、該ノード種別がリーフノードを示すものであれば、該リーフノードから前記インデックスキー読出ステップによりインデックスキーを読み出し、該ノード種別がブランチノードを示すものであれば、前記リンクステップにより前記リンク先ノードを読み出し、該読み出したリンク先ノードのノード種別を前記ノード種別判定ステップで判定することを該ノード種別がリーフノードを示すものとなるまで繰り返し、該リーフノードから前記インデックスキー読出ステップによりインデックスキーを読み出し、
前記インデックスキー読出ステップにより読み出されたインデックスキーを、前記検索開始ノードをそのルートノードとする前記カップルドノードツリーの部分木の前記検索キーによる検索結果である検索結果キーとするとともに、
前記検索開始ノードの配置された記憶領域のアドレス情報及び前記検索開始ノードから前記リーフノードに至るリンク先のノードの配置された記憶領域のアドレス情報と前記検索開始ノードから前記リーフノードに至るリンク経路のブランチノードの弁別ビット位置を順次スタックに格納することを特徴とするビット列検索方法。
【請求項６】
前記カップルドノードツリーは配列に記憶され、前記位置情報は、該位置情報に対応する前記代表ノードが配置された前記配列の配列要素の配列番号であり、
前記検索開始ノード及びリンク先のノードの配置された記憶領域のアドレス情報は、前記検索開始ノード及びリンク先のノードの配置された配列要素の配列番号であることを特徴とする請求項５記載のビット列検索方法。
【請求項７】
ビット列検索装置が、ビット列からなる検索キーにより検索対象であるビット列からなるインデックスキーが格納されたツリーのデータ構造に基づいて前記インデックスキーを検索するビット列検索方法において、
前記ツリーは、該ツリーの始点であるルートノードと、隣接した記憶領域に配置される代表ノードと非代表ノードである２つのノードを有する、ツリーの構成要素としてのノード対を有し、前記ノードは該ノードがブランチノードであるかリーフノードであるかを示すノード種別を格納する領域を有し、前記ブランチノードは、前記ノード種別に加えて、前記検索キーの弁別ビット位置を格納する領域とリンク先のノード対の代表ノードの位置を示す位置情報を格納する領域を含むが、前記検索対象のビット列からなるインデックスキーを格納する領域を含まないものであり、前記リーフノードは、前記ノード種別に加えて、前記検索対象のビット列からなるインデックスキーを格納する領域を含むが、前記検索キーの弁別ビット位置を格納する領域とリンク先のノード対の代表ノードの位置を示す位置情報を格納する領域を含まないものである、カップルドノードツリーであって、
前記ルートノード、あるいは、前記ノード対のどちらか一方のノード、である検索開始ノードの位置を示す位置情報を取得し、該取得した検索開始ノードの位置を示す位置情報により検索開始ノードを読み出す検索開始ノード読出ステップと、
前記ノードのノード種別を格納する領域から当該ノード種別を読み出し、該ノード種別が前記リーフノードを示すものであるかブランチノードを示すものであるかを判定するノード種別判定ステップと、
前記リーフノードのインデックスキーを格納する領域から当該インデックスキーを読み出すインデックスキー読出ステップと、
前記ブランチノードのリンク先のノード対の代表ノードの位置を示す位置情報を格納する領域からリンク先のノード対の代表ノードの位置を示す位置情報を読み出し、該読み出したリンク先のノード対の代表ノードの位置を示す位置情報により示される記憶領域に配置された代表ノードのみをリンク先ノードとして読み出す、あるいは該読み出したリンク先のノード対の代表ノードの位置を示す位置情報に基づいて演算により求める位置情報により示される記憶領域に配置された非代表ノードのみをリンク先ノードとして読み出すリンクステップと、
を備え、
前記検索開始ノード読出ステップで読み出した検索開始ノードのノード種別を前記ノード種別判定ステップで判定し、該ノード種別がリーフノードを示すものであれば、該リーフノードから前記インデックスキー読出ステップによりインデックスキーを読み出し、該ノード種別がブランチノードを示すものであれば、前記リンクステップにより前記リンク先ノードを読み出し、該読み出したリンク先ノードのノード種別を前記ノード種別判定ステップで判定することを該ノード種別がリーフノードを示すものとなるまで繰り返し、該リーフノードから前記インデックスキー読出ステップによりインデックスキーを読み出し、
前記インデックスキーステップにより読み出されたインデックスキーを、前記検索開始ノードをそのルートノードとする、前記カップルドノードツリーあるいは該カップルドノードツリーの部分木の、前記検索キーによる検索結果であるインデックスキーの最大値あるいは最小値として取得するとともに、
前記検索開始ノードの配置された記憶領域のアドレス情報及び前記検索開始ノードから前記リーフノードに至るリンク先のノードの配置された記憶領域のアドレス情報と前記検索開始ノードから前記リーフノードに至るリンク経路のブランチノードの弁別ビット位置を順次スタックに格納することを特徴とするビット列検索方法。
【請求項８】
前記カップルドノードツリーは配列に記憶され、前記位置情報は、該位置情報に対応する前記代表ノードが配置された前記配列の配列要素の配列番号であり、
前記検索開始ノード及びリンク先のノードの配置された記憶領域のアドレス情報は、前記検索開始ノード及びリンク先のノードの配置された配列要素の配列番号であることを特徴とする請求項７記載のビット列検索方法。
【請求項９】
請求項３又は請求項４記載のインデックスキー挿入方法、請求項５〜請求項８記載のビット列検索方法のいずれか１つの方法をコンピュータに実行させるためのプログラム。
【請求項１０】
請求項９記載のプログラムを記憶したコンピュータ読み取り可能な記憶媒体。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００７７
【補正方法】変更
【補正の内容】
【００７７】
ステップS５１５に進み、ステップS５１２で得た代表ノードの配列番号にステップS５１３で得たブール値の論理否定値を加算した配列番号を得る。
ステップS５１４で得た配列番号は、挿入キーをインデックスキーとして持つリーフノードが格納される配列要素の配列番号であり、ステップS５１５で得た配列番号は、そのリーフノードと対を成すノードが格納される配列要素のものである。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００８８
【補正方法】変更
【補正の内容】
【００８８】
ステップS５２２の判定結果が否定であれば、ステップS５１８に戻り、ステップS５１８での判定が肯定になるかステップS５２２での判定が肯定になるまで繰り返す。ステップS５２２での判定が肯定になると、ステップS５２３で探索経路スタックのスタックポインタを1つ進め、ステップS524以下の処理に移行する。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００９０
【補正方法】変更
【補正の内容】
【００９０】
例えば図２のカップルドノードツリーに”１１１０００”を挿入するとき、検索結果のインデックスキーはノード２１０ｈに格納された”１０１０１１ ”になる。挿入キー”１１１０００”とノード２１０ｈに格納されたインデックスキー”１０１０１１”のビット列比較により異なるビット値となる最上位のビット位置１が得られる。得られたビット位置１と探索経路スタックに積まれた配列番号の配列要素に格納されたブランチノードの弁別ビット位置との位置関係を弁別ビット位置が上位になるまで順次探索経路スタックを逆にたどると、ルートノード２１０ａに至る。そこで探索経路スタックのポインタを１つ進め、ノード２１１ｂの配列番号を得る。挿入キー”１１１０００”はノード２１１ｂのリンク先に挿入される。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００９１
【補正方法】変更
【補正の内容】
【００９１】
また、探索経路スタックを逆にたどりルートノードに至っても、ルートノードの弁別ビット位置が、先に求めたビット列比較で異なるビット値となる最上位のビット位置より上位のビット位置でないということは、そのカップルドノードツリーのインデックスキーの上位ビットで、ルートノードの弁別ビット位置より上位のビットの値は全て等しい場合である。そして、挿入するインデックスキーにおいて、初めてルートノードの弁別ビット位置より上位のビットの値に異なるビット値のものがあるということである。したがって、挿入するノード対はルートノードの直接のリンク先となり、ルートノードの弁別ビット位置は、既存のインデックスキーと異なる値である挿入キーの最上位ビットの位置に変わる。
【手続補正６】
【補正対象書類名】図面
【補正対象項目名】図７Ｂ
【補正方法】変更
【補正の内容】
【図７Ｂ】
2008181260.tif 000001