【手続補正書】
【提出日】平成24年12月11日(2012.12.11)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１
【補正方法】変更
【補正の内容】
【請求項１】
ビット列からなる検索キーにより、検索対象であるビット列からなるインデックスキーあるいは該インデックスキーにアクセスするための情報が格納されたツリーのデータ構造に基づいて、前記インデックスキーを検索するビット列検索装置において、
前記インデックスキーは、本来のインデックスキーのある特定のビット位置に特定のビット値を挿入したものであり、
前記検索キーは、本来の検索キーの、前記本来のインデックスキーと同一の特定のビット位置に前記特定のビット値を挿入したものであり、
前記ツリーは配列に記憶され、ｎ段目（ｎは正整数）までのツリーの構成要素を有するものであり、
該ツリーの始点であるルートノードであって、ノード参照番号１に、前記配列の先頭の配列要素の位置を定める番号であるベース番号を加えた値の配列番号の配列要素に配置されるルートノードと、前記配列の隣接した配列要素に配置される代表ノードと非代表ノードである２つのノードを有する、ツリーの構成要素としてのノード対を有し、前記ノードはブランチノードかリーフノードであって、前記ブランチノードは、前記検索キーの弁別ビット位置を格納する領域を含むが、ブランチノードとリーフノードを識別するノード種別を格納する領域、リンク先である直近下位のノード対の代表ノードの配置された配列要素の配列番号を格納する領域、及び前記インデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含まないものであり、前記リーフノードは、前記インデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含むが、前記ノード種別を格納する領域、及び前記検索キーの弁別ビット位置を格納する領域を含まないものであって、前記代表ノードは該代表ノードの直近上位のブランチノードのノード参照番号の２倍の値のノード参照番号に、前記ベース番号を加えた値の配列番号の配列要素に配置され、前記リーフノードはｎ段目にのみ位置する、カップルドノードツリーを記憶する検索ツリー記憶手段と、
前記検索キーの、各ブランチノードの前記弁別ビット位置と一致するビット位置のビット値を分岐先情報として前記ブランチノードに対応して格納する分岐先配列を記憶する分岐先情報記憶手段と、
前記検索ツリー記憶手段に記憶されたカップルドノードツリーからブランチノードをノード参照番号順に読み出し、該ブランチノードの弁別ビット位置と前記検索キーにより前記分岐先情報を抽出して前記分岐先配列の配列番号１の配列要素から順次各配列要素に設定する分岐先情報設定実行部と、
前記分岐先配列に設定された配列番号１の配列要素に格納された分岐先情報を前記カップルドノードツリーの第１段のノードの分岐先情報として読み出し、該読み出した分岐先情報に前記配列番号１を２倍した値を加えて得られる値を、前記カップルドノードツリーの第２段のノードの分岐先情報が格納された前記分岐先配列の配列要素の配列番号とし、以下、第２段のノードの分岐先情報に該第２段のノードの分岐先情報が格納された前記配列要素の配列番号を２倍した値を加えて得られる値を、前記カップルドノードツリーの第３段のノードの分岐先情報が格納された前記分岐先配列の配列要素の配列番号とするように、自段のノードの分岐先情報に該自段のノードの分岐先情報が格納された前記配列要素の配列番号を２倍した値を加えて得られる値を、前記カップルドノードツリーの次段のノードの分岐先情報が格納された前記分岐先配列の配列要素の配列番号とすることを前記カップルドノードツリーの第ｎ−２段のノードまで繰り返して前記カップルドノードツリーの第ｎ−１段のノードの分岐先情報の格納された前記分岐先配列の配列要素の配列番号を求める次段ノード分岐先情報格納位置計算実行部と、
前記次段ノード分岐先情報格納位置計算実行部が求めた配列番号により、前記分岐先配列から前記カップルドノードツリーの第ｎ−１段のノードの分岐先情報を読み出し、該読み出した分岐先情報と該配列番号に基づいてリーフノードの格納位置を求め、前記検索ツリー記憶手段に記憶されたカップルドノードツリーから該格納位置に格納されたリーフノードを読み出すリーフノード出力実行部と、
を備えることを特徴とするビット列検索装置
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００９９
【補正方法】変更
【補正の内容】
【００９９】
次にステップＳ９０２ａにおいて変換前のツリーの最大段数を求め、ステップＳ９０２ｂにおいて該最大段数を段数カウンタの上限値に設定する。
ステップＳ９０２ａの処理の詳細については、後に図１２Ａ及び図１２Ｂを参照して説明する。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０１０１
【補正方法】変更
【補正の内容】
【０１０１】
図９Ｂは、本発明の一実施形態におけるポインタレスツリーを生成する処理の後段の処理フロー例を示す図である。図９Ｂに示すように、ステップＳ９１３において、変換前のツリーが格納された配列から、配列番号の指す配列要素をノードとして読み出す。ステップＳ９１３の最初の処理においては、配列番号にはステップＳ９０７でルートノードの配列番号が設定されている。２回目以降の処理においては、後に説明するステップＳ９２０あるいはステップＳ９２８で設定される。以下の説明において、ステップＳ９１３で読み出されたノードを巡回開始ノードということがある。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０１１６
【補正方法】変更
【補正の内容】
【０１１６】
上述のステップＳ１１３０で、段数カウンタは上限値であると判定されると、ステップＳ１１３４に進む。ステップＳ１１３４では、段数カウンタの上限値から１を減じた値による２のべき乗の数値を求め、ノード参照番号から該数値を減じた値とリーフノード配列のベース番号との和を、リーフノード配列の配列番号に設定する。図２Ｂの例示では、段数カウンタの上限値は５であり、該上限値から１を減じた値による２のべき乗数は１６となる。この値から１を減じた値１５は、ブランチノード配列に配置されたブランチノードの数になる。ここでノード参照番号はブランチノード配列のノード参照番号であるから、このノード参照番号から１５を減じた値は図４の例示で説明したように、リーフノード配列のノード参照番号である。そして、ノード参照番号とベース番号の和により、配列番号が求められる。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】０１２０
【補正方法】変更
【補正の内容】
【０１２０】
図１２Ｂは、変換前のツリーの最大段数を求める処理の後段の処理フロー例を説明する図である。図１２Ｂに示すように、ステップＳ１２１３において、変換前のツリーが格納された配列から、配列番号の指す配列要素をノードとして読み出す。ステップＳ１２１３の最初の処理においては、配列番号にはステップＳ１２０７でルートノードの配列番号が設定されている。２回目以降の処理においては、後に説明するステップＳ１２２０あるいはステップＳ１２２８で設定される。図９Ｂにおける説明と同様に、以下の説明において、ステップＳ１２１３で読み出されたノードを巡回開始ノードということがある。
【手続補正６】
【補正対象書類名】図面
【補正対象項目名】図１１
【補正方法】変更
【補正の内容】
【図１１】
2011248626.tif 000001