【手続補正書】
【提出日】平成24年12月11日(2012.12.11)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１３
【補正方法】変更
【補正の内容】
【請求項１３】
ビット列からなる検索キーにより、検索対象であるビット列からなるインデックスキーあるいは該インデックスキーにアクセスするための情報が格納されたツリーのデータ構造に基づいて、前記インデックスキーを検索するビット列検索装置において、
前記インデックスキーは、本来のインデックスキーのある特定のビット位置に特定のビット値を挿入したものであり、
前記検索キーは、本来の検索キーの、前記本来のインデックスキーと同一の特定のビット位置に前記特定のビット値を挿入したものであり、
前記ツリーは配列に記憶され、ｎ段目（ｎは正整数）までのツリーの構成要素を有するものであり、該ツリーの始点であって、前記配列の配列番号１の配列要素に配置されるルートノードと、前記配列の隣接した配列要素に配置される代表ノードと非代表ノードである２つのノードを有する、ツリーの構成要素としてのノード対を有し、前記ノードはブランチノードかリーフノードであって、前記ブランチノードは、前記検索キーの弁別ビット位置を格納する領域を含むが、ブランチノードとリーフノードを識別するノード種別を格納する領域、リンク先である直近下位のノード対の代表ノードの配置された配列要素の配列番号を格納する領域、及び前記インデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含まないものであり、前記リーフノードは、前記インデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含むが、前記ノード種別を格納する領域、及び前記検索キーの弁別ビット位置を格納する領域を含まないものであって、前記代表ノードは該代表ノードの直近上位のブランチノードの配置された配列要素の配列番号の２倍の値の配列番号の配列要素に配置され、前記リーフノードはｎ段目にのみ位置する、カップルドノードツリーと、
検索を開始するルートノードの配置された配列要素の配列番号１をリンク先ノードの配列番号として設定する検索開始位置設定手段と、
第１〜第ｎ−１のノード読出手段と、
第１〜第ｎ−１のリンク手段と、
インデックスキー読出手段と、
を備え、
前記第１のノード読出手段は、前記検索開始位置設定手段によりリンク先ノードの配列番号として設定された配列番号１の配列要素から該配列要素に配置されたルートノードを読み出し、
前記第１のリンク手段は、前記第１のノード読出手段により読み出されたルートノードの弁別ビット位置の前記検索キーのビット値と前記ルートノードの配置された配列要素の配列番号の２倍の値との和を前記リンク先ノードの配列番号として設定し、
前記第２〜第ｎ−１のノード読出手段は、それぞれ前記第１〜第ｎ−２のリンク手段が設定したリンク先ノードの配列番号が指す配列要素をブランチノードとして読み出し、
前記第２〜第ｎ−１のリンク手段は、それぞれ前記第２〜第ｎ−１のノード読出手段により読み出されたブランチノードの弁別ビット位置の前記検索キーのビット値と前記ブランチノードの配置された配列要素の配列番号の２倍の値との和を前記リンク先ノードの配列番号として設定するものであり、
前記インデックスキー読出手段は、前記第ｎ−１リンク手段が設定したリンク先ノードの配列番号が指す配列要素をリーフノードとして読み出し、該読み出したリーフノードのインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域から直接当該インデックスキーを読み出す、あるいは該インデックスキーにアクセスするための情報に基づき当該インデックスキーを読み出す、
ことを特徴とするビット列検索装置。
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１４
【補正方法】変更
【補正の内容】
【請求項１４】
請求項１３記載のビット列検索装置が実行するビット列検索方法において、
検索を開始するルートノードの配置された配列要素の配列番号１をリンク先ノードの配列番号として設定する検索開始位置設定ステップと、
第１〜第ｎ−１のノード読出ステップと、
第１〜第ｎ−１のリンクステップと、
インデックスキー読出ステップと、
を備え、
前記第１のノード読出ステップにおいて、前記検索開始位置設定ステップでリンク先ノードの配列番号として設定された配列番号１の配列要素から該配列要素に配置されたルートノードを読み出し、
前記第１のリンクステップにおいて、前記第１のノード読出ステップで読み出されたルートノードの弁別ビット位置の前記検索キーのビット値と前記ルートノードの配置された配列要素の配列番号の２倍の値との和を前記リンク先ノードの配列番号として設定し、
前記第２〜第ｎ−１のノード読出ステップにおいて、それぞれ前記第１〜第ｎ−２のリンクステップで設定したリンク先ノードの配列番号が指す配列要素をブランチノードとして読み出し、
前記第２〜第ｎ−１のリンクステップは、それぞれ前記第２〜第ｎ−１のノード読出ステップで読み出されたブランチノードの弁別ビット位置の前記検索キーのビット値と前記ブランチノードの配置された配列要素の配列番号の２倍の値との和を前記リンク先ノードの配列番号として設定するものであり、
前記インデックスキー読出ステップにおいて、前記第ｎ−１リンクステップで設定したリンク先ノードの配列番号が指す配列要素をリーフノードとして読み出し、該読み出したリーフノードのインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域から直接当該インデックスキーを読み出す、あるいは該インデックスキーにアクセスするための情報に基づき当該インデックスキーを読み出す、
ことを特徴とするビット列検索方法。
【手続補正３】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１７
【補正方法】変更
【補正の内容】
【請求項１７】
ビット列からなる検索キーによるビット列検索に用いられる、検索対象であるビット列からなるインデックスキーあるいは該インデックスキーにアクセスするための情報が格納されたツリーのデータ構造において、
前記インデックスキーは、本来のインデックスキーのある特定のビット位置に特定のビット値を挿入したものであり、
前記検索キーは、本来の検索キーの、前記本来のインデックスキーと同一の特定のビット位置に前記特定のビット値を挿入したものであり、
前記ツリーは配列に記憶され、ｎ段目（ｎは正整数）までのツリーの構成要素を有するものであり、該ツリーの始点であって、前記配列の配列番号１の配列要素に配置されるルートノードと、前記配列の隣接した配列要素に配置される代表ノードと非代表ノードである２つのノードを有する、ツリーの構成要素としてのノード対を有し、前記ノードはブランチノードかリーフノードであって、前記ブランチノードは、前記検索キーの弁別ビット位置を格納する領域を含むが、ブランチノードとリーフノードを識別するノード種別を格納する領域、リンク先である直近下位のノード対の代表ノードの配置された配列要素の配列番号を格納する領域、及び前記インデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含まないものであり、前記リーフノードは、前記インデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含むが、前記ノード種別を格納する領域、及び前記検索キーの弁別ビット位置を格納する領域を含まないものであって、前記代表ノードは該代表ノードの直近上位のブランチノードの配置された配列要素の配列番号の２倍の値の配列番号の配列要素に配置され、前記リーフノードはｎ段目にのみ位置するものであり、
前記ツリーの記憶手段を備えたビット列検索装置により、
検索を開始するルートノードの配置された配列要素の配列番号１をリンク先ノードの配列番号として設定する検索開始位置設定ステップと、
第１〜第ｎ−１のノード読出ステップと、
第１〜第ｎ−１のリンクステップと、
インデックスキー読出ステップと、
を備え、
前記第１のノード読出ステップにおいて、前記検索開始位置設定ステップでリンク先ノードの配列番号として設定された配列番号１の配列要素から該配列要素に配置されたルートノードを読み出し、
前記第１のリンクステップにおいて、前記第１のノード読出ステップで読み出されたルートノードの弁別ビット位置の前記検索キーのビット値と前記ルートノードの配置された配列要素の配列番号の２倍の値との和を前記リンク先ノードの配列番号として設定し、
前記第２〜第ｎ−１のノード読出ステップにおいて、それぞれ前記第１〜第ｎ−２のリンクステップで設定したリンク先ノードの配列番号が指す配列要素をブランチノードとして読み出し、
前記第２〜第ｎ−１のリンクステップは、それぞれ前記第２〜第ｎ−１のノード読出ステップで読み出されたブランチノードの弁別ビット位置の前記検索キーのビット値と前記ブランチノードの配置された配列要素の配列番号の２倍の値との和を前記リンク先ノードの配列番号として設定するものであり、
前記インデックスキー読出ステップにおいて、前記第ｎ−１リンクステップで設定したリンク先ノードの配列番号が指す配列要素をリーフノードとして読み出し、該読み出したリーフノードのインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域から直接当該インデックスキーを読み出す、あるいは該インデックスキーにアクセスするための情報に基づき当該インデックスキーを読み出す検索方法の実行を可能とすることを特徴とするデータ構造。
【手続補正４】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１９
【補正方法】変更
【補正の内容】
【請求項１９】
ビット列からなる検索キーにより、検索対象であるビット列からなるインデックスキーあるいは該インデックスキーにアクセスするための情報が格納されたツリーのデータ構造に基づいて、前記インデックスキーを検索するビット列検索装置において、
前記インデックスキーは、本来のインデックスキーのある特定のビット位置に特定のビット値を挿入したものであり、
前記検索キーは、本来の検索キーの、前記本来のインデックスキーと同一の特定のビット位置に前記特定のビット値を挿入したものであり、
前記ツリーは配列に記憶され、ｎ段目（ｎは正整数）までのツリーの構成要素を有するものであり、該ツリーの始点であるルートノードであって、ノード参照番号１に、該ルートノードの位置を定める配列番号であるベース番号と前記ツリーの各段のノードの開始位置を定める番号であるオフセット番号を加えた値の配列番号の配列要素に配置されるルートノードと、前記配列の隣接した配列要素に配置される代表ノードと非代表ノードである２つのノードを有する、ツリーの構成要素としてのノード対を有し、前記ノードはブランチノードかリーフノードであって、前記ブランチノードは、前記検索キーの弁別ビット位置を格納する領域を含むが、ブランチノードとリーフノードを識別するノード種別を格納する領域、リンク先である直近下位のノード対の代表ノードの配置された配列要素の配列番号を格納する領域、及び前記インデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含まないものであり、前記リーフノードは、前記インデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含むが、前記ノード種別を格納する領域、及び前記検索キーの弁別ビット位置を格納する領域を含まないものであって、前記代表ノードは該代表ノードの直近上位のブランチノードのノード参照番号の２倍の値のノード参照番号に、前記ベース番号と該直近上位のブランチノードの次の段のオフセット番号を加えた値の配列番号の配列要素に配置され、前記リーフノードはｎ段目にのみ位置する、カップルドノードツリーと、
検索を開始するルートノードのノード参照番号１と該ノードについての前記オフセット番号と前記ベース番号に基づいて該ルートノードの配置された配列要素の配列番号を取得し、該取得した配列番号をリンク先ノードの配列番号として設定する検索開始位置設定手段と、
第１〜第ｎ−１のノード読出手段と、
第１〜第ｎ−１のリンク手段と、
インデックスキー読出手段と、
を備え、
前記第１のノード読出手段は、前記検索開始位置設定手段によりリンク先ノードの配列番号として設定された配列番号の配列要素から該配列要素に配置されたルートノードを読み出し、
前記第１のリンク手段は、前記第１のノード読出手段により読み出されたルートノードの弁別ビット位置の前記検索キーのビット値と前記ルートノードのノード参照番号１の２倍の値との和を前記リンク先ノードのノード参照番号とし、該ノード参照番号と前記ベース番号と前記ルートノードの次の段のオフセット番号の和をリンク先ノードの配列番号として設定し、
前記第２〜第ｎ−１のノード読出手段は、それぞれ前記第１〜第ｎ−２のリンク手段が設定したリンク先ノードの配列番号が指す配列要素をブランチノードとして読み出し、
前記第２〜第ｎ−１のリンク手段は、それぞれ前記第２〜第ｎ−１のノード読出手段により読み出されたブランチノードの弁別ビット位置の前記検索キーのビット値と前記ブランチノードのノード参照番号の２倍の値との和を前記リンク先ノードのノード参照番号とし、該ノード参照番号と前記ベース番号と前記ブランチノードの次の段のオフセット番号の和をリンク先ノードの配列番号として設定するものであり、
前記インデックスキー読出手段は、前記第ｎ−１リンク手段が設定したリンク先ノードの配列番号が指す配列要素をリーフノードとして読み出し、該読み出したリーフノードのインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域から直接当該インデックスキーを読み出す、あるいは該インデックスキーにアクセスするための情報に基づき当該インデックスキーを読み出す、
ことを特徴とするビット列検索装置。
【手続補正５】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項２０
【補正方法】変更
【補正の内容】
【請求項２０】
請求項１９記載のビット列検索装置が実行するビット列検索方法において、
検索を開始するルートノードのノード参照番号１と該ルートノードについての前記オフセット番号と前記ベース番号に基づいて該ルートノードの配置された配列要素の配列番号を取得し、該取得した配列番号をリンク先ノードの配列番号として設定する検索開始位置設定ステップと、
第１〜第ｎ−１のノード読出ステップと、
第１〜第ｎ−１のリンクステップと、
インデックスキー読出ステップと、
を備え、
前記第１のノード読出ステップにおいて、前記検索開始位置設定ステップでリンク先ノードの配列番号として設定された配列番号の配列要素から該配列要素に配置されたルートノードを読み出し、
前記第１のリンクステップにおいて、前記第１のノード読出ステップで読み出されたルートノードの弁別ビット位置の前記検索キーのビット値と前記ルートノードのノード参照番号１の２倍の値との和を前記リンク先ノードのノード参照番号とし、該ノード参照番号と前記ベース番号と前記ルートノードの次の段のオフセット番号の和をリンク先ノードの配列番号として設定し、
前記第２〜第ｎ−１のノード読出ステップにおいて、それぞれ前記第１〜第ｎ−２のリンクステップで設定したリンク先ノードの配列番号が指す配列要素をブランチノードとして読み出し、
前記第２〜第ｎ−１のリンクステップは、それぞれ前記第２〜第ｎ−１のノード読出ステップで読み出されたブランチノードの弁別ビット位置の前記検索キーのビット値と前記ブランチノードのノード参照番号の２倍の値との和を前記リンク先ノードのノード参照番号とし、該ノード参照番号と前記ベース番号と前記ブランチノードの次の段のオフセット番号の和をリンク先ノードの配列番号として設定するものであり、
前記インデックスキー読出ステップにおいて、前記第ｎ−１リンクステップで設定したリンク先ノードの配列番号が指す配列要素をリーフノードとして読み出し、該読み出した前記リーフノードのインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域から直接当該インデックスキーを読み出す、あるいは該インデックスキーにアクセスするための情報に基づき当該インデックスキーを読み出す、
ことを特徴とするビット列検索方法。
【手続補正６】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項２３
【補正方法】変更
【補正の内容】
【請求項２３】
ビット列からなる検索キーによるビット列検索に用いられる、検索対象であるビット列からなるインデックスキーあるいは該インデックスキーにアクセスするための情報が格納されたツリーのデータ構造において、
前記インデックスキーは、本来のインデックスキーのある特定のビット位置に特定のビット値を挿入したものであり、
前記検索キーは、本来の検索キーの、前記本来のインデックスキーと同一の特定のビット位置に前記特定のビット値を挿入したものであり、
前記ツリーは配列に記憶され、ｎ段目（ｎは正整数）までのツリーの構成要素を有するものであり、該ツリーの始点であるルートノードであって、ノード参照番号１に、該ルートノードの位置を定める配列番号であるベース番号と前記ツリーの各段のノードの開始位置を定める番号であるオフセット番号を加えた値の配列番号の配列要素に配置されるルートノードと、前記配列の隣接した配列要素に配置される代表ノードと非代表ノードである２つのノードを有する、ツリーの構成要素としてのノード対を有し、前記ノードはブランチノードかリーフノードであって、前記ブランチノードは、前記検索キーの弁別ビット位置を格納する領域を含むが、ブランチノードとリーフノードを識別するノード種別を格納する領域、リンク先である直近下位のノード対の代表ノードの配置された配列要素の配列番号を格納する領域、及び前記インデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含まないものであり、前記リーフノードは、前記インデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含むが、前記ノード種別を格納する領域、及び前記検索キーの弁別ビット位置を格納する領域を含まないものであって、前記代表ノードは該代表ノードの直近上位のブランチノードのノード参照番号の２倍の値のノード参照番号に、前記ベース番号と該直近上位のブランチノードの次の段のオフセット番号を加えた値の配列番号の配列要素に配置され、前記リーフノードはｎ段目にのみ位置するものであり、
前記ツリーの記憶手段を備えたビット列検索装置により、
検索を開始するルートノードのノード参照番号１と該ルートノードについての前記オフセット番号と前記ベース番号に基づいて該ルートノードの配置された配列要素の配列番号を取得し、該取得した配列番号をリンク先ノードの配列番号として設定する検索開始位置設定ステップと、
第１〜第ｎ−１のノード読出ステップと、
第１〜第ｎ−１のリンクステップと、
インデックスキー読出ステップと、
を備え、
前記第１のノード読出ステップにおいて、前記検索開始位置設定ステップでリンク先ノードの配列番号として設定された配列番号の配列要素から該配列要素に配置されたルートノードを読み出し、
前記第１のリンクステップにおいて、前記第１のノード読出ステップで読み出されたルートノードの弁別ビット位置の前記検索キーのビット値と前記ルートノードのノード参照番号１の２倍の値との和を前記リンク先ノードのノード参照番号とし、該ノード参照番号と前記ベース番号と前記ルートノードの次の段のオフセット番号の和をリンク先ノードの配列番号として設定し、
前記第２〜第ｎ−１のノード読出ステップにおいて、それぞれ前記第１〜第ｎ−２のリンクステップで設定したリンク先ノードの配列番号が指す配列要素をブランチノードとして読み出し、
前記第２〜第ｎ−１のリンクステップは、それぞれ前記第２〜第ｎ−１のノード読出ステップで読み出されたブランチノードの弁別ビット位置の前記検索キーのビット値と前記ブランチノードのノード参照番号の２倍の値との和を前記リンク先ノードのノード参照番号とし、該ノード参照番号と前記ベース番号と前記ブランチノードの次の段のオフセット番号の和をリンク先ノードの配列番号として設定するものであり、
前記インデックスキー読出ステップにおいて、前記第ｎ−１リンクステップで設定したリンク先ノードの配列番号が指す配列要素をリーフノードとして読み出し、該読み出した前記リーフノードのインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域から直接当該インデックスキーを読み出す、あるいは該インデックスキーにアクセスするための情報に基づき当該インデックスキーを読み出す検索方法の実行を可能とすることを特徴とするデータ構造。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００１９
【補正方法】変更
【補正の内容】
【００１９】
検索開始ノードがルートノードであるので、ビット列“１０００１０”を検索キーとしてルートノード２１０ａから処理をスタートする。ルートノード２１０ａの弁別ビット位置２３０ａは０であるので、検索キー“１０００１０”の弁別ビット位置が０のビット値をみると１である。そこで代表ノード番号として格納された配列番号２２０ａに１を加えた配列番号の配列要素に格納されたノード２１１ｂにリンクする。ノード２１１ｂの弁別ビット位置２３１ｂには２が格納されているので、検索キー“１０００１０”の弁別ビット位置が２のビット値をみると０であるから、代表ノード番号として格納された配列番号２２１ｂの配列要素に格納されたノード２１０ｆにリンクする。
ノード２１０ｆの弁別ビット位置２３０ｆには５が格納されているので、検索キー“１０００１０”の弁別ビット位置が５のビット値をみると０であるから、代表ノード番号として格納された配列番号２２０ｆの配列要素に格納されたノード２１０ｇにリンクする。
ノード２１０ｇのノード種別２６０ｇは１でありリーフノードであることを示しているので、インデックスキー２５０ｇを検索結果キーとして読み出す。このようにしてカップルドノードツリーを用いた検索が行われる。なお、検索結果キーを検索キーと比較すると両方とも“１０００１０”であって一致している。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００６６
【補正方法】変更
【補正の内容】
【００６６】
また、図４Ｂに示すツリー構造における段数は５段であるので、図８Ｂに示すツリー構造においては、５段目にのみリーフノードが位置している。そして、図４Ｂに示すツリー構造において５段目より上位の階層に位置するリーフノードは、弁別ビット位置が０のダミーのブランチノードとなっている。そして、ダミーのブランチノードの直近下位のノードが５段目のノードとなるまで、ダミーのブランチノードが挿入されている。
直近下位のノード対の代表ノードが配置された配列要素の配列番号である代表ノード番号の算出方法は、第１の実施形態のものと同じである。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００８９
【補正方法】変更
【補正の内容】
【００８９】
ベース番号は、後述の１段目のオフセット番号と組み合わせてツリーのルートノードの位置を定める番号である。ベース番号を用いることにより、ルートノードの配列番号が、図４Ａ及び図４Ｂの例示のように１に制約される必要をなくすことができる。
オフセット番号は、ツリーの各段のノードの格納される開始位置を定める番号である。オフセット番号を用いることにより、ツリーのノードを、そのノードが位置するツリー上の段数毎に配置することができる。オフセット番号は、段数毎にオフセット番号表に設定しておく。
ノード参照番号は、ノードの順番を定める番号であり、図４Ａ及び図４Ｂに例示する配列番号に相当する。
配列番号は、ベース番号、オフセット番号及びノード参照番号の和により求めることができる。
本変形例において、ベース番号を０、各段のオフセット番号を０とすると、ノード参照番号は図４Ａ及び図４Ｂに例示する配列番号と一致し、本変形例のカップルドノードツリーは、図４Ａ及び図４Ｂに例示する第１の実施形態のカップルドノードツリーと一致する。
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】０１０１
【補正方法】変更
【補正の内容】
【０１０１】
ステップＳ１４０５の判定において、読み出したノードがブランチノードである場合はステップＳ１４０６に進み、ノードから弁別ビット位置についての情報を取り出し、更に、ステップＳ１４０７で、取り出した弁別ビット位置に対応するビット値を検索キーから取り出す。そして、ステップＳ１４０８で、ノード参照番号に、ノード参照番号を２倍した値にステップＳ１４０７で得た値を設定する。さらにステップＳ１４０９で、段数カウンタに１を加えて、ステップＳ１４０２ａに戻る。
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】０１３１
【補正方法】変更
【補正の内容】
【０１３１】
ステップＳ１９０７では、段数カウンタに値１を加え、ステップＳ１９０８に進み、ノード参照番号を２倍にする。さらにステップＳ１９０９において、ステップＳ１９０３で読み出したノードから、代表ノード番号を取り出し、ステップＳ１９１０で、該取り出した代表ノード番号に値０を加えた値を配列番号に設定し、ステップＳ１９０２に戻る。
【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】０１５８
【補正方法】変更
【補正の内容】
【０１５８】
上述のステップＳ２２０６において、ノード種別がリーフノードを示すものと判定されると、ステップＳ２２１１に進み、段数カウンタの値は最大段数カウンタに設定された値より大きいか判定し、大きくなければそのまま処理を終了し、大きければ、ステップＳ２２１２で、最大段数カウンタに段数カウンタの値を設定して処理を終了する。
【手続補正１３】
【補正対象書類名】図面
【補正対象項目名】図２２
【補正方法】変更
【補正の内容】
【図２２】
2011134289.tif 000001