(57)【要約】【課題】より記憶容量の小さい記憶手段に収容可能なカップルドノードツリーのツリー構造を提供する。【解決手段】ブランチノードから、代表ノード番号を格納する領域を削除する。ルートノードは配列の配列番号１の配列要素に配置し、ブランチノードのリンク先のノード対の代表ノードは、ブランチノードの配置された配列要素の配列番号の２倍の配列番号の配列要素に配置する。リンク先のノードの配置された配列要素の配列番号は、リンク元のブランチノードの配列番号を２倍し、検索キーの弁別ビット位置のビット値と加算して求める。【選択図】図４Ａ
2011134289.tif 000002
【特許請求の範囲】
【請求項１】
ビット列からなる検索キーにより、検索対象であるビット列からなるインデックスキーあるいは該インデックスキーにアクセスするための情報が格納されたツリーのデータ構造に基づいて、前記インデックスキーを検索するビット列検索装置において、
前記ツリーは配列に記憶されたものであり、該ツリーの始点であって、前記配列の配列番号１の配列要素に配置されるルートノードと、前記配列の隣接した配列要素に配置される代表ノードと非代表ノードである２つのノードを有する、ツリーの構成要素としてのノード対を有し、前記ノードは該ノードがブランチノードであるかリーフノードであるかを示すノード種別を格納する領域を有し、前記ブランチノードは、前記ノード種別に加えて、前記検索キーの弁別ビット位置を格納する領域を含むが、リンク先である直近下位のノード対の代表ノードの配置された配列要素の配列番号を格納する領域及び前記検索対象のビット列からなるインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含まないものであり、前記リーフノードは、前記ノード種別に加えて、前記検索対象のビット列からなるインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含むが、前記検索キーの弁別ビット位置を格納する領域を含まないものであって、前記代表ノードは該代表ノードの直近上位のブランチノードの配置された配列要素の配列番号の２倍の値の配列番号の配列要素に配置される、カップルドノードツリーと、
検索を開始するノードの配置された配列要素の配列番号を取得し、該取得した配列番号をリンク先ノードの配列番号として設定する検索開始位置設定手段と、
前記検索開始位置設定手段あるいは後記リンク手段によりリンク先ノードの配列番号として設定された配列番号の配列要素から該配列要素に配置されたノードを読み出すノード読出手段と、
前記ノード読出手段により読み出されたノードのノード種別を格納する領域から当該ノード種別を読み出し、該ノード種別が前記リーフノードを示すものであるかブランチノードを示すものであるかを判定するノード種別判定手段と、
前記リーフノードのインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域から直接当該インデックスキーを読み出す、あるいは該インデックスキーにアクセスするための情報に基づき当該インデックスキーを読み出すインデックスキー読出手段と、
前記ノード種別判定手段で判定されたノード種別がブランチノードを示すものであるとき、該ブランチノードの弁別ビット位置を格納する領域から当該弁別ビット位置を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記ブランチノードの配置された配列要素の配列番号の２倍の値との和を前記リンク先ノードの配列番号として設定するリンク手段と、
を備え、
前記ノード読出手段で読み出したノードのノード種別を前記ノード種別判定手段で判定し、該ノード種別がリーフノードを示すものであれば、前記インデックスキー読出手段によりインデックスキーを読み出し、該ノード種別がブランチノードを示すものであれば、前記リンク手段により前記リンク先ノードの配列番号を設定し、該設定されたリンク先ノードの配列番号の配列要素に配置されたノードを前記ノード読出手段で読み出し、該読み出したノードのノード種別を前記ノード種別判定手段で判定することを該ノード種別がリーフノードを示すものとなるまで繰り返し、該ノード種別がリーフノードを示すときに前記インデックスキー読出手段によりインデックスキーを読み出すことを特徴とするビット列検索装置。
【請求項２】
請求項１記載のビット列検索装置が実行するビット列検索方法において、
検索を開始するノードの配置された配列要素の配列番号を取得し、該取得した配列番号をリンク先ノードの配列番号として設定する検索開始位置設定ステップと、
前記検索開始位置設定ステップあるいは後記リンクステップにおいてリンク先ノードの配列番号として設定された配列番号の配列要素から該配列要素に配置されたノードを読み出すノード読出ステップと、
前記ノード読出ステップで読み出されたノードのノード種別を格納する領域から当該ノード種別を読み出し、該ノード種別が前記リーフノードを示すものであるかブランチノードを示すものであるかを判定するノード種別判定ステップと、
前記リーフノードのインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域から直接当該インデックスキーを読み出す、あるいは該インデックスキーにアクセスするための情報に基づき当該インデックスキーを読み出すインデックスキー読出ステップと、
前記ノード種別判定ステップで判定されたノード種別がブランチノードを示すものであるとき、該ブランチノードの弁別ビット位置を格納する領域から当該弁別ビット位置を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記ブランチノードの配置された配列要素の配列番号の２倍の値との和を前記リンク先ノードの配列番号として設定するリンクステップと、
を備え、
前記ノード読出ステップで読み出したノードのノード種別を前記ノード種別判定ステップで判定し、該ノード種別がリーフノードを示すものであれば、前記インデックスキー読出ステップにおいてインデックスキーを読み出し、該ノード種別がブランチノードを示すものであれば、前記リンクステップにおいて前記リンク先ノードの配列番号を設定し、該設定されたリンク先ノードの配列番号の配列要素に配置されたノードを前記ノード読出ステップで読み出し、該読み出したノードのノード種別を前記ノード種別判定ステップで判定することを該ノード種別がリーフノードを示すものとなるまで繰り返し、該ノード種別がリーフノードを示すときに前記インデックスキー読出ステップにおいてインデックスキーを読み出すことを特徴とするビット列検索方法。
【請求項３】
請求項２記載のビット列検索方法をコンピュータに実行させることを特徴とするプログラム。
【請求項４】
請求項２記載のビット列検索方法をコンピュータに実行させるプログラムを記憶したことを特徴とするコンピュータ読み取り可能な記憶媒体。
【請求項５】
ビット列からなる検索キーによるビット列検索に用いられる、検索対象であるビット列からなるインデックスキーあるいは該インデックスキーにアクセスするための情報が格納されたツリーのデータ構造において、
前記ツリーは配列に記憶されたものであり、該ツリーの始点であって、前記配列の配列番号１の配列要素に配置されるルートノードと、前記配列の隣接した配列要素に配置される代表ノードと非代表ノードである２つのノードを有する、ツリーの構成要素としてのノード対を有し、前記ノードは該ノードがブランチノードであるかリーフノードであるかを示すノード種別を格納する領域を有し、前記ブランチノードは、前記ノード種別に加えて、前記検索キーの弁別ビット位置を格納する領域を含むが、リンク先である直近下位のノード対の代表ノードの配置された配列要素の配列番号を格納する領域及び前記検索対象のビット列からなるインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含まないものであり、前記リーフノードは、前記ノード種別に加えて、前記検索対象のビット列からなるインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含むが、前記検索キーの弁別ビット位置を格納する領域を含まないものであって、前記代表ノードは該代表ノードの直近上位のブランチノードの配置された配列要素の配列番号の２倍の値の配列番号の配列要素に配置されるものであり、
前記ツリーの記憶手段を備えたビット列検索装置により、
検索を開始するノードの配置された配列要素の配列番号を取得し、該取得した配列番号をリンク先ノードの配列番号として設定する検索開始位置設定ステップと、
前記検索開始位置設定ステップあるいは後記リンクステップにおいてリンク先ノードの配列番号として設定された配列番号の配列要素から該配列要素に配置されたノードを読み出すノード読出ステップと、
前記ノード読出ステップで読み出されたノードのノード種別を格納する領域から当該ノード種別を読み出し、該ノード種別が前記リーフノードを示すものであるかブランチノードを示すものであるかを判定するノード種別判定ステップと、
前記リーフノードのインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域から直接当該インデックスキーを読み出す、あるいは該インデックスキーにアクセスするための情報に基づき当該インデックスキーを読み出すインデックスキー読出ステップと、
前記ノード種別判定ステップで判定されたノード種別がブランチノードを示すものであるとき、該ブランチノードの弁別ビット位置を格納する領域から当該弁別ビット位置を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記ブランチノードの配置された配列要素の配列番号の２倍の値との和を前記リンク先ノードの配列番号として設定するリンクステップと、
を備え、
前記ノード読出ステップで読み出したノードのノード種別を前記ノード種別判定ステップで判定し、該ノード種別がリーフノードを示すものであれば、前記インデックスキー読出ステップにおいてインデックスキーを読み出し、該ノード種別がブランチノードを示すものであれば、前記リンクステップにおいて前記リンク先ノードの配列番号を設定し、該設定されたリンク先ノードの配列番号の配列要素に配置されたノードを前記ノード読出ステップで読み出し、該読み出したノードのノード種別を前記ノード種別判定ステップで判定することを該ノード種別がリーフノードを示すものとなるまで繰り返し、該ノード種別がリーフノードを示すときに前記インデックスキー読出ステップにおいてインデックスキーを読み出す検索方法の実行を可能とすることを特徴とするデータ構造。
【請求項６】
請求項５記載のデータ構造を記憶したことを特徴とするコンピュータ読み取り可能な記憶媒体。
【請求項７】
ビット列からなる検索キーにより、検索対象であるビット列からなるインデックスキーあるいは該インデックスキーにアクセスするための情報が格納されたツリーのデータ構造に基づいて、前記インデックスキーを検索するビット列検索装置において、
前記ツリーは配列に記憶されたものであり、該ツリーの始点であるルートノードであって、ノード参照番号１に、該ルートノードの位置を定める配列番号であるベース番号と前記ツリーの各段のノードの開始位置を定める番号であるオフセット番号を加えた値の配列番号の配列要素に配置されるルートノードと、前記配列の隣接した配列要素に配置される代表ノードと非代表ノードである２つのノードを有する、ツリーの構成要素としてのノード対を有し、前記ノードは該ノードがブランチノードであるかリーフノードであるかを示すノード種別を格納する領域を有し、前記ブランチノードは、前記ノード種別に加えて、前記検索キーの弁別ビット位置を格納する領域を含むが、リンク先である直近下位のノード対の代表ノードの配置された配列要素の配列番号を格納する領域及び前記検索対象のビット列からなるインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含まないものであり、前記リーフノードは、前記ノード種別に加えて、前記検索対象のビット列からなるインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含むが、前記検索キーの弁別ビット位置を格納する領域を含まないものであって、前記代表ノードは該代表ノードの直近上位のブランチノードのノード参照番号の２倍の値のノード参照番号に、前記ベース番号と該直近上位のブランチノードの次の段のオフセット番号を加えた値の配列番号の配列要素に配置される、カップルドノードツリーと、
検索を開始するノードのノード参照番号と該ノードについての前記オフセット番号と前記ベース番号に基づいて該ノードの配置された配列要素の配列番号を取得し、該取得した配列番号をリンク先ノードの配列番号として設定する検索開始位置設定手段と、
前記検索開始位置設定手段あるいは後記リンク手段によりリンク先ノードの配列番号として設定された配列番号の配列要素から該配列要素に配置されたノードを読み出すノード読出手段と、
前記ノード読出手段により読み出されたノードのノード種別を格納する領域から当該ノード種別を読み出し、該ノード種別が前記リーフノードを示すものであるかブランチノードを示すものであるかを判定するノード種別判定手段と、
前記リーフノードのインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域から直接当該インデックスキーを読み出す、あるいは該インデックスキーにアクセスするための情報に基づき当該インデックスキーを読み出すインデックスキー読出手段と、
前記ノード種別判定手段で判定されたノード種別がブランチノードを示すものであるとき、該ブランチノードの弁別ビット位置を格納する領域から当該弁別ビット位置を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記ブランチノードのノード参照番号の２倍の値との和を前記リンク先ノードのノード参照番号とし、該ノード参照番号と前記ベース番号と前記ブランチノードの次の段のオフセット番号の和をリンク先ノードの配列番号として設定するリンク手段と、
を備え、
前記ノード読出手段で読み出したノードのノード種別を前記ノード種別判定手段で判定し、該ノード種別がリーフノードを示すものであれば、前記インデックスキー読出手段によりインデックスキーを読み出し、該ノード種別がブランチノードを示すものであれば、前記リンク手段により前記リンク先ノードの配列番号を設定し、該設定されたリンク先ノードの配列番号の配列要素に配置されたノードを前記ノード読出手段で読み出し、該読み出したノードのノード種別を前記ノード種別判定手段で判定することを該ノード種別がリーフノードを示すものとなるまで繰り返し、該ノード種別がリーフノードを示すときに前記インデックスキー読出手段によりインデックスキーを読み出すことを特徴とするビット列検索装置。
【請求項８】
請求項１記載のビット列検索装置が実行するビット列検索方法において、
検索を開始するノードのノード参照番号と該ノードについての前記オフセット番号と前記ベース番号に基づいて該ノードの配置された配列要素の配列番号を取得し、該取得した配列番号をリンク先ノードの配列番号として設定する検索開始位置設定ステップと、
前記検索開始位置設定ステップあるいは後記リンクステップにおいてリンク先ノードの配列番号として設定された配列番号の配列要素から該配列要素に配置されたノードを読み出すノード読出ステップと、
前記ノード読出ステップで読み出されたノードのノード種別を格納する領域から当該ノード種別を読み出し、該ノード種別が前記リーフノードを示すものであるかブランチノードを示すものであるかを判定するノード種別判定ステップと、
前記リーフノードのインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域から直接当該インデックスキーを読み出す、あるいは該インデックスキーにアクセスするための情報に基づき当該インデックスキーを読み出すインデックスキー読出ステップと、
前記ノード種別判定ステップで判定されたノード種別がブランチノードを示すものであるとき、該ブランチノードの弁別ビット位置を格納する領域から当該弁別ビット位置を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記ブランチノードのノード参照番号の２倍の値との和を前記リンク先ノードのノード参照番号とし、該ノード参照番号と前記ベース番号と前記ブランチノードの次の段のオフセット番号の和をリンク先ノードの配列番号として設定するリンクステップと、
を備え、
前記ノード読出ステップで読み出したノードのノード種別を前記ノード種別判定ステップで判定し、該ノード種別がリーフノードを示すものであれば、前記インデックスキー読出ステップにおいてインデックスキーを読み出し、該ノード種別がブランチノードを示すものであれば、前記リンクステップにおいて前記リンク先ノードの配列番号を設定し、該設定されたリンク先ノードの配列番号の配列要素に配置されたノードを前記ノード読出ステップで読み出し、該読み出したノードのノード種別を前記ノード種別判定ステップで判定することを該ノード種別がリーフノードを示すものとなるまで繰り返し、該ノード種別がリーフノードを示すときに前記インデックスキー読出ステップにおいてインデックスキーを読み出すことを特徴とするビット列検索方法。
【請求項９】
請求項８記載のビット列検索方法をコンピュータに実行させることを特徴とするプログラム。
【請求項１０】
請求項８記載のビット列検索方法をコンピュータに実行させることを特徴とするプログラムを記憶したことを特徴とするコンピュータ読み取り可能な記憶媒体。
【請求項１１】
ビット列からなる検索キーによるビット列検索に用いられる、検索対象であるビット列からなるインデックスキーあるいは該インデックスキーにアクセスするための情報が格納されたツリーのデータ構造において、
前記ツリーは配列に記憶されたものであり、該ツリーの始点であるルートノードであって、ノード参照番号１に、該ルートノードの位置を定める配列番号であるベース番号と前記ツリーの各段のノードの開始位置を定める番号であるオフセット番号を加えた値の配列番号の配列要素に配置されるルートノードと、前記配列の隣接した配列要素に配置される代表ノードと非代表ノードである２つのノードを有する、ツリーの構成要素としてのノード対を有し、前記ノードは該ノードがブランチノードであるかリーフノードであるかを示すノード種別を格納する領域を有し、前記ブランチノードは、前記ノード種別に加えて、前記検索キーの弁別ビット位置を格納する領域を含むが、リンク先である直近下位のノード対の代表ノードの配置された配列要素の配列番号を格納する領域及び前記検索対象のビット列からなるインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含まないものであり、前記リーフノードは、前記ノード種別に加えて、前記検索対象のビット列からなるインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含むが、前記検索キーの弁別ビット位置を格納する領域を含まないものであって、前記代表ノードは該代表ノードの直近上位のブランチノードのノード参照番号の２倍の値のノード参照番号に、前記ベース番号と該直近上位のブランチノードの次の段のオフセット番号を加えた値の配列番号の配列要素に配置されるものであり、
前記ツリーの記憶手段を備えたビット列検索装置により、
検索を開始するノードのノード参照番号と該ノードについての前記オフセット番号と前記ベース番号に基づいて該ノードの配置された配列要素の配列番号を取得し、該取得した配列番号をリンク先ノードの配列番号として設定する検索開始位置設定ステップと、
前記検索開始位置設定ステップあるいは後記リンクステップにおいてリンク先ノードの配列番号として設定された配列番号の配列要素から該配列要素に配置されたノードを読み出すノード読出ステップと、
前記ノード読出ステップで読み出されたノードのノード種別を格納する領域から当該ノード種別を読み出し、該ノード種別が前記リーフノードを示すものであるかブランチノードを示すものであるかを判定するノード種別判定ステップと、
前記リーフノードのインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域から直接当該インデックスキーを読み出す、あるいは該インデックスキーにアクセスするための情報に基づき当該インデックスキーを読み出すインデックスキー読出ステップと、
前記ノード種別判定ステップで判定されたノード種別がブランチノードを示すものであるとき、該ブランチノードの弁別ビット位置を格納する領域から当該弁別ビット位置を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記ブランチノードのノード参照番号の２倍の値との和を前記リンク先ノードのノード参照番号とし、該ノード参照番号と前記ベース番号と前記ブランチノードの次の段のオフセット番号の和をリンク先ノードの配列番号として設定するリンクステップと、
を備え、
前記ノード読出ステップで読み出したノードのノード種別を前記ノード種別判定ステップで判定し、該ノード種別がリーフノードを示すものであれば、前記インデックスキー読出ステップにおいてインデックスキーを読み出し、該ノード種別がブランチノードを示すものであれば、前記リンクステップにおいて前記リンク先ノードの配列番号を設定し、該設定されたリンク先ノードの配列番号の配列要素に配置されたノードを前記ノード読出ステップで読み出し、該読み出したノードのノード種別を前記ノード種別判定ステップで判定することを該ノード種別がリーフノードを示すものとなるまで繰り返し、該ノード種別がリーフノードを示すときに前記インデックスキー読出ステップにおいてインデックスキーを読み出す検索方法の実行を可能とすることを特徴とするデータ構造。
【請求項１２】
請求項１１記載のデータ構造を記憶したことを特徴とするコンピュータ読み取り可能な記憶媒体。
【請求項１３】
ビット列からなる検索キーにより、検索対象であるビット列からなるインデックスキーあるいは該インデックスキーにアクセスするための情報が格納されたツリーのデータ構造に基づいて、前記インデックスキーを検索するビット列検索装置において、
前記インデックスキーは、本来のインデックスキーのある特定のビット位置に特定のビット値を挿入したものであり、
前記検索キーは、本来の検索キーの、前記本来のインデックスキーと同一の特定のビット位置に前記特定のビット値を挿入したものであり、
前記ツリーは配列に記憶され、ｎ段目（ｎは正整数）までのツリーの構成要素を有するものであり、該ツリーの始点であって、前記配列の配列番号１の配列要素に配置されるルートノードと、前記配列の隣接した配列要素に配置される代表ノードと非代表ノードである２つのノードを有する、ツリーの構成要素としてのノード対を有し、前記ブランチノードは、前記検索キーの弁別ビット位置を格納する領域を含むが、ブランチノードとリーフノードを識別するノード種別を格納する領域、リンク先である直近下位のノード対の代表ノードの配置された配列要素の配列番号を格納する領域、及び前記インデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含まないものであり、前記リーフノードは、前記インデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含むが、前記ノード種別を格納する領域、及び前記検索キーの弁別ビット位置を格納する領域を含まないものであって、前記代表ノードは該代表ノードの直近上位のブランチノードの配置された配列要素の配列番号の２倍の値の配列番号の配列要素に配置され、前記リーフノードはｎ段目にのみ位置する、カップルドノードツリーと、
検索を開始するルートノードの配置された配列要素の配列番号１をリンク先ノードの配列番号として設定する検索開始位置設定手段と、
第１〜第ｎのノード読出手段と、
第１〜第ｎ−１のリンク手段と、
インデックスキー読出手段と、
を備え、
前記第１のノード読出手段は、前記検索開始位置設定手段によりリンク先ノードの配列番号として設定された配列番号１の配列要素から該配列要素に配置されたルートノードを読み出し、
前記第１のリンク手段は、前記第１のノード読出手段により読み出されたルートノードの弁別ビット位置を格納する領域から当該弁別ビット位置を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記ルートノードの配置された配列要素の配列番号の２倍の値との和を前記リンク先ノードの配列番号として設定し、
前記第２〜第ｎ−１のノード読出手段は、それぞれ前記第１〜第ｎ−２のリンク手段が設定したリンク先ノードの配列番号が指す配列要素をブランチノードとして読み出し、
前記第２〜第ｎ−１のリンク手段は、それぞれ前記第２〜第ｎ−１のノード読出手段により読み出されたブランチノードの弁別ビット位置を格納する領域から当該弁別ビット位置を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記ブランチノードの配置された配列要素の配列番号の２倍の値との和を前記リンク先ノードの配列番号として設定するものであり、
前記第ｎのノード読出手段は、前記第ｎ−１リンク手段が設定したリンク先ノードの配列番号が指す配列要素をリーフノードとして読み出し、
インデックスキー読出手段は、前記第ｎのノード読出手段が読みだした前記リーフノードのインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域から直接当該インデックスキーを読み出す、あるいは該インデックスキーにアクセスするための情報に基づき当該インデックスキーを読み出す、
ことを特徴とするビット列検索装置。
【請求項１４】
請求項１３記載のビット列検索装置が実行するビット列検索方法において、
検索を開始するルートノードの配置された配列要素の配列番号１をリンク先ノードの配列番号として設定する検索開始位置設定ステップと、
第１〜第ｎのノード読出ステップと、
第１〜第ｎ−１のリンクステップと、
インデックスキー読出ステップと、
を備え、
前記第１のノード読出ステップにおいて、前記検索開始位置設定ステップでリンク先ノードの配列番号として設定された配列番号１の配列要素から該配列要素に配置されたルートノードを読み出し、
前記第１のリンクステップにおいて、前記第１のノード読出ステップで読み出されたルートノードの弁別ビット位置を格納する領域から当該弁別ビット位置を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記ルートノードの配置された配列要素の配列番号の２倍の値との和を前記リンク先ノードの配列番号として設定し、
前記第２〜第ｎ−１のノード読出ステップにおいて、それぞれ前記第１〜第ｎ−２のリンクステップで設定したリンク先ノードの配列番号が指す配列要素をブランチノードとして読み出し、
前記第２〜第ｎ−１のリンクステップは、それぞれ前記第２〜第ｎ−１のノード読出ステップで読み出されたブランチノードの弁別ビット位置を格納する領域から当該弁別ビット位置を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記ブランチノードの配置された配列要素の配列番号の２倍の値との和を前記リンク先ノードの配列番号として設定するものであり、
前記第ｎのノード読出ステップにおいて、前記第ｎ−１リンクステップで設定したリンク先ノードの配列番号が指す配列要素をリーフノードとして読み出し、
前記インデックスキー読出ステップにおいて、前記第ｎのノード読出ステップで読みだした前記リーフノードのインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域から直接当該インデックスキーを読み出す、あるいは該インデックスキーにアクセスするための情報に基づき当該インデックスキーを読み出す、
ことを特徴とするビット列検索方法。
【請求項１５】
請求項１４記載のビット列検索方法をコンピュータに実行させることを特徴とするプログラム。
【請求項１６】
請求項１４記載のビット列検索方法をコンピュータに実行させるプログラムを記憶したことを特徴とするコンピュータ読み取り可能な記憶媒体。
【請求項１７】
ビット列からなる検索キーによるビット列検索に用いられる、検索対象であるビット列からなるインデックスキーあるいは該インデックスキーにアクセスするための情報が格納されたツリーのデータ構造において、
前記インデックスキーは、本来のインデックスキーのある特定のビット位置に特定のビット値を挿入したものであり、
前記検索キーは、本来の検索キーの、前記本来のインデックスキーと同一の特定のビット位置に前記特定のビット値を挿入したものであり、
前記ツリーは配列に記憶され、ｎ段目（ｎは正整数）までのツリーの構成要素を有するものであり、該ツリーの始点であって、前記配列の配列番号１の配列要素に配置されるルートノードと、前記配列の隣接した配列要素に配置される代表ノードと非代表ノードである２つのノードを有する、ツリーの構成要素としてのノード対を有し、前記ブランチノードは、前記検索キーの弁別ビット位置を格納する領域を含むが、ブランチノードとリーフノードを識別するノード種別を格納する領域、リンク先である直近下位のノード対の代表ノードの配置された配列要素の配列番号を格納する領域、及び前記インデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含まないものであり、前記リーフノードは、前記インデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含むが、前記ノード種別を格納する領域、及び前記検索キーの弁別ビット位置を格納する領域を含まないものであって、前記代表ノードは該代表ノードの直近上位のブランチノードの配置された配列要素の配列番号の２倍の値の配列番号の配列要素に配置され、前記リーフノードはｎ段目にのみ位置するものであり、
前記ツリーの記憶手段を備えたビット列検索装置により、
検索を開始するルートノードの配置された配列要素の配列番号１をリンク先ノードの配列番号として設定する検索開始位置設定ステップと、
第１〜第ｎのノード読出ステップと、
第１〜第ｎ−１のリンクステップと、
インデックスキー読出ステップと、
を備え、
前記第１のノード読出ステップにおいて、前記検索開始位置設定ステップでリンク先ノードの配列番号として設定された配列番号１の配列要素から該配列要素に配置されたルートノードを読み出し、
前記第１のリンクステップにおいて、前記第１のノード読出ステップで読み出されたルートノードの弁別ビット位置を格納する領域から当該弁別ビット位置を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記ルートノードの配置された配列要素の配列番号の２倍の値との和を前記リンク先ノードの配列番号として設定し、
前記第２〜第ｎ−１のノード読出ステップにおいて、それぞれ前記第１〜第ｎ−２のリンクステップで設定したリンク先ノードの配列番号が指す配列要素をブランチノードとして読み出し、
前記第２〜第ｎ−１のリンクステップは、それぞれ前記第２〜第ｎ−１のノード読出ステップで読み出されたブランチノードの弁別ビット位置を格納する領域から当該弁別ビット位置を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記ブランチノードの配置された配列要素の配列番号の２倍の値との和を前記リンク先ノードの配列番号として設定するものであり、
前記第ｎのノード読出ステップにおいて、前記第ｎ−１リンクステップで設定したリンク先ノードの配列番号が指す配列要素をリーフノードとして読み出し、
前記インデックスキー読出ステップにおいて、前記第ｎのノード読出ステップで読みだした前記リーフノードのインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域から直接当該インデックスキーを読み出す、あるいは該インデックスキーにアクセスするための情報に基づき当該インデックスキーを読み出す検索方法の実行を可能とすることを特徴とするデータ構造。
【請求項１８】
請求項１７記載のデータ構造を記憶したことを特徴とするコンピュータ読み取り可能な記憶媒体。
【請求項１９】
ビット列からなる検索キーにより、検索対象であるビット列からなるインデックスキーあるいは該インデックスキーにアクセスするための情報が格納されたツリーのデータ構造に基づいて、前記インデックスキーを検索するビット列検索装置において、
前記インデックスキーは、本来のインデックスキーのある特定のビット位置に特定のビット値を挿入したものであり、
前記検索キーは、本来の検索キーの、前記本来のインデックスキーと同一の特定のビット位置に前記特定のビット値を挿入したものであり、
前記ツリーは配列に記憶され、ｎ段目（ｎは正整数）までのツリーの構成要素を有するものであり、該ツリーの始点であるルートノードであって、ノード参照番号１に、該ルートノードの位置を定める配列番号であるベース番号と前記ツリーの各段のノードの開始位置を定める番号であるオフセット番号を加えた値の配列番号の配列要素に配置されるルートノードと、前記配列の隣接した配列要素に配置される代表ノードと非代表ノードである２つのノードを有する、ツリーの構成要素としてのノード対を有し、前記ブランチノードは、前記検索キーの弁別ビット位置を格納する領域を含むが、ブランチノードとリーフノードを識別するノード種別を格納する領域、リンク先である直近下位のノード対の代表ノードの配置された配列要素の配列番号を格納する領域、及び前記インデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含まないものであり、前記リーフノードは、前記インデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含むが、前記ノード種別を格納する領域、及び前記検索キーの弁別ビット位置を格納する領域を含まないものであって、前記代表ノードは該代表ノードの直近上位のブランチノードのノード参照番号の２倍の値のノード参照番号に、前記ベース番号と該直近上位のブランチノードの次の段のオフセット番号を加えた値の配列番号の配列要素に配置され、前記リーフノードはｎ段目にのみ位置する、カップルドノードツリーと、
検索を開始するルートノードのノード参照番号１と該ノードについての前記オフセット番号と前記ベース番号に基づいて該ルートノードの配置された配列要素の配列番号を取得し、該取得した配列番号をリンク先ノードの配列番号として設定する検索開始位置設定手段と、
第１〜第ｎのノード読出手段と、
第１〜第ｎ−１のリンク手段と、
インデックスキー読出手段と、
を備え、
前記第１のノード読出手段は、前記検索開始位置設定手段によりリンク先ノードの配列番号として設定された配列番号の配列要素から該配列要素に配置されたルートノードを読み出し、
前記第１のリンク手段は、前記第１のノード読出手段により読み出されたルートノードの弁別ビット位置を格納する領域から当該弁別ビット位置を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記ルートノードのノード参照番号１の２倍の値との和を前記リンク先ノードのノード参照番号とし、該ノード参照番号と前記ベース番号と前記ルートノードの次の段のオフセット番号の和をリンク先ノードの配列番号として設定し、
前記第２〜第ｎ−１のノード読出手段は、それぞれ前記第１〜第ｎ−２のリンク手段が設定したリンク先ノードの配列番号が指す配列要素をブランチノードとして読み出し、
前記第２〜第ｎ−１のリンク手段は、それぞれ前記第２〜第ｎ−１のノード読出手段により読み出されたブランチノードの弁別ビット位置を格納する領域から当該弁別ビット位置を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記ブランチノードのノード参照番号の２倍の値との和を前記リンク先ノードのノード参照番号とし、該ノード参照番号と前記ベース番号と前記ブランチノードの次の段のオフセット番号の和をリンク先ノードの配列番号として設定するものであり、
前記第ｎのノード読出手段は、前記第ｎ−１リンク手段が設定したリンク先ノードの配列番号が指す配列要素をリーフノードとして読み出し、
インデックスキー読出手段は、前記第ｎのノード読出手段が読みだした前記リーフノードのインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域から直接当該インデックスキーを読み出す、あるいは該インデックスキーにアクセスするための情報に基づき当該インデックスキーを読み出す、
ことを特徴とするビット列検索装置。
【請求項２０】
請求項１９記載のビット列検索装置が実行するビット列検索方法において、
検索を開始するルートノードのノード参照番号１と該ルートノードについての前記オフセット番号と前記ベース番号に基づいて該ルートノードの配置された配列要素の配列番号を取得し、該取得した配列番号をリンク先ノードの配列番号として設定する検索開始位置設定ステップと、
第１〜第ｎのノード読出ステップと、
第１〜第ｎ−１のリンクステップと、
インデックスキー読出ステップと、
を備え、
前記第１のノード読出ステップにおいて、前記検索開始位置設定ステップでリンク先ノードの配列番号として設定された配列番号の配列要素から該配列要素に配置されたルートノードを読み出し、
前記第１のリンクステップにおいて、前記第１のノード読出ステップで読み出されたルートノードの弁別ビット位置を格納する領域から当該弁別ビット位置を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記ルートノードのノード参照番号１の２倍の値との和を前記リンク先ノードのノード参照番号とし、該ノード参照番号と前記ベース番号と前記ルートノードの次の段のオフセット番号の和をリンク先ノードの配列番号として設定し、
前記第２〜第ｎ−１のノード読出ステップにおいて、それぞれ前記第１〜第ｎ−２のリンクステップで設定したリンク先ノードの配列番号が指す配列要素をブランチノードとして読み出し、
前記第２〜第ｎ−１のリンクステップは、それぞれ前記第２〜第ｎ−１のノード読出ステップで読み出されたブランチノードの弁別ビット位置を格納する領域から当該弁別ビット位置を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記ブランチノードのノード参照番号の２倍の値との和を前記リンク先ノードのノード参照番号とし、該ノード参照番号と前記ベース番号と前記ブランチノードの次の段のオフセット番号の和をリンク先ノードの配列番号として設定するものであり、
前記第ｎのノード読出ステップにおいて、前記第ｎ−１リンクステップで設定したリンク先ノードの配列番号が指す配列要素をリーフノードとして読み出し、
前記インデックスキー読出ステップにおいて、前記第ｎのノード読出ステップで読みだした前記リーフノードのインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域から直接当該インデックスキーを読み出す、あるいは該インデックスキーにアクセスするための情報に基づき当該インデックスキーを読み出す、
ことを特徴とするビット列検索方法。
【請求項２１】
請求項２０記載のビット列検索方法をコンピュータに実行させることを特徴とするプログラム。
【請求項２２】
請求項２０記載のビット列検索方法をコンピュータに実行させるプログラムを記憶したことを特徴とするコンピュータ読み取り可能な記憶媒体。
【請求項２３】
ビット列からなる検索キーによるビット列検索に用いられる、検索対象であるビット列からなるインデックスキーあるいは該インデックスキーにアクセスするための情報が格納されたツリーのデータ構造において、
前記インデックスキーは、本来のインデックスキーのある特定のビット位置に特定のビット値を挿入したものであり、
前記検索キーは、本来の検索キーの、前記本来のインデックスキーと同一の特定のビット位置に前記特定のビット値を挿入したものであり、
前記ツリーは配列に記憶され、ｎ段目（ｎは正整数）までのツリーの構成要素を有するものであり、該ツリーの始点であるルートノードであって、ノード参照番号１に、該ルートノードの位置を定める配列番号であるベース番号と前記ツリーの各段のノードの開始位置を定める番号であるオフセット番号を加えた値の配列番号の配列要素に配置されるルートノードと、前記配列の隣接した配列要素に配置される代表ノードと非代表ノードである２つのノードを有する、ツリーの構成要素としてのノード対を有し、前記ブランチノードは、前記検索キーの弁別ビット位置を格納する領域を含むが、ブランチノードとリーフノードを識別するノード種別を格納する領域、リンク先である直近下位のノード対の代表ノードの配置された配列要素の配列番号を格納する領域、及び前記インデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含まないものであり、前記リーフノードは、前記インデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域を含むが、前記ノード種別を格納する領域、及び前記検索キーの弁別ビット位置を格納する領域を含まないものであって、前記代表ノードは該代表ノードの直近上位のブランチノードのノード参照番号の２倍の値のノード参照番号に、前記ベース番号と該直近上位のブランチノードの次の段のオフセット番号を加えた値の配列番号の配列要素に配置され、前記リーフノードはｎ段目にのみ位置するものであり、
前記ツリーの記憶手段を備えたビット列検索装置により、
検索を開始するルートノードのノード参照番号１と該ルートノードについての前記オフセット番号と前記ベース番号に基づいて該ルートノードの配置された配列要素の配列番号を取得し、該取得した配列番号をリンク先ノードの配列番号として設定する検索開始位置設定ステップと、
第１〜第ｎのノード読出ステップと、
第１〜第ｎ−１のリンクステップと、
インデックスキー読出ステップと、
を備え、
前記第１のノード読出ステップにおいて、前記検索開始位置設定ステップでリンク先ノードの配列番号として設定された配列番号の配列要素から該配列要素に配置されたルートノードを読み出し、
前記第１のリンクステップにおいて、前記第１のノード読出ステップで読み出されたルートノードの弁別ビット位置を格納する領域から当該弁別ビット位置を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記ルートノードのノード参照番号１の２倍の値との和を前記リンク先ノードのノード参照番号とし、該ノード参照番号と前記ベース番号と前記ルートノードの次の段のオフセット番号の和をリンク先ノードの配列番号として設定し、
前記第２〜第ｎ−１のノード読出ステップにおいて、それぞれ前記第１〜第ｎ−２のリンクステップで設定したリンク先ノードの配列番号が指す配列要素をブランチノードとして読み出し、
前記第２〜第ｎ−１のリンクステップは、それぞれ前記第２〜第ｎ−１のノード読出ステップで読み出されたブランチノードの弁別ビット位置を格納する領域から当該弁別ビット位置を読み出し、該読み出した弁別ビット位置の前記検索キーのビット値と前記ブランチノードのノード参照番号の２倍の値との和を前記リンク先ノードのノード参照番号とし、該ノード参照番号と前記ベース番号と前記ブランチノードの次の段のオフセット番号の和をリンク先ノードの配列番号として設定するものであり、
前記第ｎのノード読出ステップにおいて、前記第ｎ−１リンクステップで設定したリンク先ノードの配列番号が指す配列要素をリーフノードとして読み出し、
前記インデックスキー読出ステップにおいて、前記第ｎのノード読出ステップで読みだした前記リーフノードのインデックスキーあるいは該インデックスキーにアクセスするための情報を格納する領域から直接当該インデックスキーを読み出す、あるいは該インデックスキーにアクセスするための情報に基づき当該インデックスキーを読み出す検索方法の実行を可能とすることを特徴とするデータ構造。
【請求項２４】
請求項２３記載のデータ構造を記憶したことを特徴とするコンピュータ読み取り可能な記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ビット列検索の技術に関し、特にカップルドノードツリーを用いたビット列検索に関する。
【背景技術】
【０００２】
近年、社会の情報化が進展し、大規模なデータベースが各所で利用されるようになってきている。このような大規模なデータベースからレコードを検索するには、各レコードの記憶されたアドレスと対応づけられたレコード内の項目をインデックスキーとして検索をし、所望のレコードを探し出すことが通例である。また、全文検索における文字列も、文書のインデックスキーと見なすことができる。
【０００３】
そして、それらのインデックスキーはビット列で表現されることから、データベースの検索はビット列データの検索に帰着されるということができる。
ビット列データを検索するビット列検索に関するものとして、下記特許文献１、特許文献２及び特許文献３等に開示されたカップルドノードツリーを用いた検索技術がある。
【０００４】
図１Ａに示すのは、従来の、配列に配置されたカップルドノードツリーの構成例を説明する図である。
図１Ａを参照すると、ノード１０１が配列１００の配列番号１０の配列要素に配置されている。ノード１０１はノード種別１０２、弁別ビット位置１０３及び代表ノード番号１０４で構成されている。ノード種別１０２は０であり、ノード１０１がブランチノードであることを示している。弁別ビット位置１０３には１が格納されている。代表ノード番号１０４にはリンク先のノード対の代表ノードの配列番号２０が格納されている。なお、以下では表記の簡略化のため、代表ノード番号に格納された配列番号を代表ノード番号ということもある。また、代表ノード番号に格納された配列番号をそのノードに付した符号あるいはノード対に付した符号で表すこともある。
【０００５】
配列番号２０の配列要素には、ノード対１１１の代表ノードであるノード［０］１１２が格納されている。そして隣接する次の配列要素（配列番号２０＋１）に代表ノードと対になるノード［１］１１３が格納されている。ノード［０］１１２のノード種別１１４には０が、弁別ビット位置１１５には３が、代表ノード番号１１６には３０が格納されている。またノード［１］１１３のノード種別１１７には１が格納されており、ノード［１］１１３がリーフノードであることを示している。インデックスキー１１８には、“０００１”が格納されている。
【０００６】
なお、代表ノードをノード［０］で表し、それと対になるノードをノード［１］で表すことがある。また、ある配列番号の配列要素に格納されたノードを、その配列番号のノードということがあり、ノードの格納された配列要素の配列番号を、ノードの配列番号ということもある。
配列番号３０及び３１の配列要素に格納されたノード１２２とノード１２３からなるノード対１２１の内容は省略されている。
【０００７】
ノード［０］１１２、ノード［１］１１３、ノード１２２、及びノード１２３の格納された配列要素にそれぞれ付された０あるいは１は、検索キーで検索を行う場合にノード対のどちらのノードにリンクするかを示すものである。前段のブランチノードの弁別ビット位置にある検索キーのビット値である０か１を代表ノード番号に加えた配列番号のノードにリンクする。
したがって、前段のブランチノードの代表ノード番号に、検索キーの弁別ビット位置のビット値を加えることにより、リンク先のノードが格納された配列要素の配列番号を求めることができる。
なお、上記の例では代表ノード番号をノード対の配置された配列番号のうち小さい方を採用しているが、大きいほうを採用することも可能であることは明らかである。
【０００８】
図１Ｂは、従来のカップルドノードツリーのツリー構造を概念的に示す図である。
符号２１０ａで示すのが図１Ｂに例示するカップルドノードツリー２００のルートノードである。図示の例では、ルートノード２１０ａは配列番号２２０に配置されたノード対２０１ａの代表ノードとしている。
【０００９】
ツリー構造としては、ルートノード２１０ａの下にノート対２０１ｂが、その下層にノード対２０１ｃとノード対２０１ｆが配置され、ノード対２０１ｆの下層にはノード対２０１ｈとノード対２０１ｇが配置されている。ノード対２０１ｃの下にはノード対２０１ｄが、さらにその下にはノード対２０１ｅが配置されている。
【００１０】
各ノードの前に付された０あるいは１の符号は、図１において説明した配列要素の前に付された符号と同じである。検索キーの弁別ビット位置のビット値に応じてツリーをたどり、検索対象のリーフノードを見つけることになる。
【００１１】
図示された例では、ルートノード２１０ａのノード種別２６０ａは０でブランチノードであることを示し、弁別ビット位置２３０ａは０を示している。代表ノード番号は２２０ａであり、それはノード対２０１ｂの代表ノード２１０ｂの格納された配列要素の配列番号である。
ノード対２０１ｂはノード２１０ｂと２１１ｂで構成され、それらのノード種別２６０ｂ、２６１ｂはともに０であり、ブランチノードであることを示している。ノード２１０ｂの弁別ビット位置２３０ｂには１が格納され、リンク先の代表ノード番号にはノード対２０１ｃの代表ノード２１０ｃの格納された配列要素の配列番号２２０ｂが格納されている。
【００１２】
ノード２１０ｃのノード種別２６０ｃには１が格納されているので、このノードはリーフノードであり、したがって、インデックスキーを含んでいる。インデックスキー２５０ｃには“０００１１１”が格納されている。一方ノード２１１ｃのノード種別２６１ｃは０、弁別ビット位置２３１ｃは２であり、代表ノード番号にはノード対２０１ｄの代表ノード２１０ｄの格納された配列要素の配列番号２２１ｃが格納されている。
ノード２１０ｄのノード種別２６０ｄは０、弁別ビット位置２３０ｄは５であり、代表ノード番号にはノード対２０１ｅの代表ノード２１０ｅの格納された配列要素の配列番号２２０ｄが格納されている。ノード２１０ｄと対になるノード２１１ｄのノード種別２６１ｄは１であり、インデックスキー２５１ｄには“０１１０１０”が格納されている。
ノード対２０１ｅのノード２１０ｅ、２１１ｅのノード種別２６０ｅ、２６１ｅはともに１であり双方ともリーフノードであることを示し、それぞれのインデックスキー２５０ｅ、２５１ｅにはインデックスキーとして“０１００１０”と“０１００１１”が格納されている。
【００１３】
ノード対２０１ｂのもう一方のノードであるノード２１１ｂの弁別ビット位置２３１ｂには２が格納され、リンク先の代表ノード番号にはノード対２０１ｆの代表ノード２１０ｆの格納された配列要素の配列番号２２１ｂが格納されている。
ノード対２０１ｆのノード２１０ｆ、２１１ｆのノード種別２６０ｆ、２６１ｆはともに０であり双方ともブランチノードである。それぞれの弁別ビット位置２３０ｆ、２３１ｆには５、３が格納されている。ノード２１０ｆの代表ノード番号にはノード対２０１ｇの代表ノード２１０ｇの格納された配列要素の配列番号２２０ｆが格納され、ノード２１１ｆの代表ノード番号にはノード対２０１ｈの代表ノードであるノード［０］２１０ｈの格納された配列要素の配列番号２２１ｆが格納されている。
ノード対２０１ｇのノード２１０ｇ、２１１ｇのノード種別２６０ｇ、２６１ｇはともに１であり双方ともリーフノードであることを示し、それぞれのインデックスキー２５０ｇ、２５１ｇには“１０００１０”と“１０００１１”が格納されている。
また同じくノード対２０１ｈの代表ノードであるノード［０］２１０ｈとそれと対をなすノード［１］２１１ｈのノード種別２６０ｈ、２６１ｈはともに１であり双方ともリーフノードであることを示し、それぞれのインデックスキー２５０ｈ、２５１ｈには“１０１０１１”と“１０１１００“が格納されている。
【００１４】
次に、上述のカップルドノードツリーを用いた基本的な検索処理について説明する。以下の説明においては、特に図示されてはいないが、処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶領域が用いられる。また、あるデータ格納領域に格納されるデータ自体にデータ格納領域の符号を付して説明する場合があるし、データ自体の名前をそのデータを格納する一時記憶領域の名前として用いることもある。
【００１５】
図２は、従来のカップルドノードツリーを用いたビット列検索の処理フロー例を説明する図である。
まず、ステップＳ２０１で、検索開始ノードの配列番号を取得する。取得された配列番号に対応する配列は、カップルドノードツリーを構成する任意のノードを格納したものである。検索開始ノードの指定は、オペレータからの入力によってもよいし、図２に例示する処理を利用するアプリケーションプログラムによるものでもよい。
取得された検索開始ノードの配列番号は、図示しない検索開始ノード設定エリアに設定されるが、この検索開始ノード設定エリアは、先に述べた「処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶領域」の一つである。以下の説明では、「図示しない検索開始ノード設定エリアに設定する」のような表現に変えて、「検索開始ノードの配列番号を得る。」、「検索開始ノードとして設定する」あるいは単に「検索開始ノードに設定する」のように記述することもある。
【００１６】
次に、ステップＳ２０２で、探索経路スタックに取得された配列番号を格納し、ステップＳ２０３で、その配列番号に対応する配列要素を参照すべきノードとして読み出す。そして、ステップＳ２０４で、読み出したノードから、ノード種別を取り出し、ステップＳ２０５で、ノード種別がブランチノードであるか否かを判定する。
ステップＳ２０５の判定において、読み出したノードがブランチノードである場合は、ステップＳ２０６に進み、ノードから弁別ビット位置についての情報を取り出し、更に、ステップＳ２０７で、取り出した弁別ビット位置に対応するビット値を検索キーから取り出す。そして、ステップＳ２０８で、ノードから代表ノード番号を取り出して、ステップＳ２０９で、検索キーから取り出したビット値と代表ノード番号とを加算し、新たな配列番号として、ステップＳ２０２に戻る。
【００１７】
以降、ステップＳ２０５の判定においてリーフノードと判定されてステップＳ２１０に進むまで、ステップＳ２０２からステップＳ２０９までの処理を繰り返す。ステップＳ２１０で、リーフノードからインデックスキーを検索結果キーとして取り出して、処理を終了する。
【００１８】
ルートノードを検索開始ノードとして図１Ｂに例示するカップルドノードツリー２００からインデックスキー“１０００１０”を検索する処理を簡単に説明する。弁別ビット位置は、最上位ビットの位置から０、１、２、・・・とする。
【００１９】
検索開始ノードがルートノードであるので、ビット列“１０００１０”を検索キーとしてルートノード２１０ａから処理をスタートする。ルートノード２１０ａの弁別ビット位置２３０ａは０であるので、検索キー“１０００１０”の弁別ビット位置が０のビット値をみると１である。そこで代表ノード番号の格納された配列番号２２０ａに１を加えた配列番号の配列要素に格納されたノード２１１ｂにリンクする。ノード２１１ｂの弁別ビット位置２３１ｂには２が格納されているので、検索キー“１０００１０”の弁別ビット位置が２のビット値をみると０であるから、代表ノード番号の格納された配列番号２２１ｂの配列要素に格納されたノード２１０ｆにリンクする。
ノード２１０ｆの弁別ビット位置２３０ｆには５が格納されているので、検索キー“１０００１０”の弁別ビット位置が５のビット値をみると０であるから、代表ノード番号の格納された配列番号２２０ｆの配列要素に格納されたノード２１０ｇにリンクする。
ノード２１０ｇのノード種別２６０ｇは１でありリーフノードであることを示しているので、インデックスキー２５０ｇを検索結果キーとして読み出す。このようにしてカップルドノードツリーを用いた検索が行われる。なお、検索結果キーを検索キーと比較すると両方とも“１０００１０”であって一致している。
【００２０】
上述の図２に示すフローチャート例では、検索処理をノードからインデックスキーを検索結果キーとして取り出すことで終了しているが、さらに検索結果キーと検索キーの一致判定を行い、一致すれば検索成功とし、一致しなければ検索失敗とすることもできる。
【００２１】
図１Ａ及び図１Ｂに示すカップルドノードツリーのリーフノードは、リーフノードインデックスキーを直接含むものであり、図２に示す検索処理は、リーフノードからインデックスキーを取り出すものである。このリーフノードの構成と検索処理におけるインデックスキーの取り出しは、特許文献１及び特許文献２に開示されたものと同様である。
【００２２】
一方、特許文献３に開示されたカップルドノードツリーのリーフノードには、インデックスキーに替えて、インデックスキーの記憶された記憶領域の位置を示すポインタである参照ポインタが格納されている。そして、検索処理におけるインデックスキーの取り出しは、リーフノードから参照ポインタを取り出し、参照ポインタの指す記憶領域にアクセスすることにより行われる。
また、特許文献４には、カップルドノードツリーのノードを順次巡回して退避することが記載されている。
【先行技術文献】
【特許文献】
【００２３】
【特許文献１】特開２００８−０１５８７２号公報
【特許文献２】特開２００８−１１２２４０号公報
【特許文献３】特開２００８−２６９５０３号公報
【特許文献４】特開２００８−２６９１９７号公報
【発明の概要】
【発明が解決しようとする課題】
【００２４】
カップルドノードツリーは、それ以前に検索処理に用いられていたツリーと比べてツリーを記憶する記憶容量が少ないという特徴を有する。しかしながら、検索対象のデータサイズが非常に大きくなると、より小さい容量の記憶手段に配置可能なツリー構造であることが望ましい。
そこで、本発明が解決しようとする課題は、より小さい容量の記憶手段に配置可能なカップルドノードツリーのツリー構造を提供することである。
【課題を解決するための手段】
【００２５】
本発明によれば、カップルドノードツリーの各ノードは、ツリー上の位置に応じた配列の配列要素に配置される。ルートノードの配置される配列要素の配列番号は１とされ、ブランチノードのリンク先のノード対の代表ノードの配置された配列要素の配列番号は、ブランチノードが配置された配列要素の配列番号を２倍することにより求められる。したがって、本発明によるブランチノードは、代表ノード番号を含む必要がない。
【００２６】
本発明の第１の態様によれば、ブランチノードはノード種別と弁別ビット位置を含むが、代表ノード番号は含まない。また、リーフノードは、ノード種別とインデックスキーあるいはインデックスキーにアクセスするための情報を含む。インデックスキーにアクセスするための情報は、上述の特許文献３に記載されたインデックスキーの記憶された記憶領域の位置を示す参照ポインタであってもよいし、それに限らず、インデックスキーの記憶された記憶領域の位置を求める索引のインデックスであってもよい。
【００２７】
また、本発明の第２の態様によれば、検索対象のインデックスキーのある特定のビット位置に特定のビット値“０”あるいは“１”を挿入したものによりカップルドノードツリーを構成し、同様に検索キーの、検索対象のインデックスキーと同一の特定のビット位置に同一の特定のビット値“０”あるいは“１”を挿入したものにより検索を行う。そして、ブランチノードとリーフノードはノード種別を含まず、ブランチノードは弁別ビット位置を含むが代表ノード番号は含まず、リーフノードはインデックスキーあるいはインデックスキーにアクセスするための情報を含む。
【００２８】
そして、リーフノードは、カップルドノードツリーの最大段数をＮとしたとき、Ｎ段目にのみ存在し、かつＮ段目にはリーフノードしか存在しないようにツリーを構成することにより、ノードの種別の判別を可能としている。したがって、検索処理は、ルートノードから最終段であるＮ段目のノードまでのリンク動作を繰り返すことで行われる。
【発明の効果】
【００２９】
本発明によれば、ブランチノードは少なくともリンク先を識別する代表ノード番号を含まないので、ノードのサイズを小さくすることができる。例えばインデックキーの数が１６とすると、リーフノードのサイズを規定するインデックスキーを表現するためのビット数は４である。一方、従来のブランチノードのサイズを規定する弁別ビット位置に必要なビット数は２、代表ノード番号に必要なビット数は、ルートノードを含めたリンク先となるノード対の数が１＋１＋２＋４＋８＝１６であることから４であるので、必要なビット数は合計で６となる。
【００３０】
したがって、従来のブランチノードは、リーフノードと比べて大きな記憶容量を必要としていた。この記憶容量の差は、インデックスキーの数が大きくなるとさらに拡大する。しかし、本発明によれば、代表ノード番号を格納する記憶領域が必要なくなることから、カップルドノードツリーを配置する配列のサイズを小さくすることができる。
【００３１】
さらに、本発明の第２の実施形態によれば、カップルドノードツリーを配置する配列のサイズを小さくすることに加えて、検索処理におけるノード種別の判定による分岐動作が削除されるので、処理速度を向上させることができる。
【図面の簡単な説明】
【００３２】
【図１Ａ】従来の、配列に配置されたカップルドノードツリーの構成例を説明する図である。
【図１Ｂ】従来のカップルドノードツリーのツリー構造を概念的に示す図である。
【図２】従来のカップルドノードツリーを用いたビット列検索の処理フロー例を説明する図である。
【図３】本発明を実施するためのハードウェア構成例を説明する図である。
【図４Ａ】本発明の第１の実施形態における配列に配置されたカップルドノードツリーの構成例を説明する図である。
【図４Ｂ】本発明の第１の実施形態に係るカップルドノードツリーのツリー構造を概念的に示す図である。
【図５】本発明の第１の実施形態におけるビット列検索装置の機能ブロック構成例を説明する図である。
【図６】本発明の第１の実施形態におけるビット列検索の処理フロー例を説明する図である。
【図７】本発明の第１の実施形態におけるカップルドノードツリーを用いた検索例を示す図である。
【図８Ａ】本発明の第２の実施形態における配列に配置されたカップルドノードツリーの構成例を説明する図である。
【図８Ｂ】本発明の第２の実施形態に係るカップルドノードツリーのツリー構造を概念的に示す図である。
【図９】本発明の第２の実施形態におけるビット列検索装置の機能ブロック構成例を説明する図である。
【図１０】本発明の第２の実施形態におけるビット列検索の処理フロー例を説明する図である。
【図１１】本発明の第２の実施形態におけるリンク先の配列番号を求める処理フロー例を説明する図である。
【図１２】本発明の第２の実施形態におけるカップルドノードツリーを用いた検索例を示す図である。
【図１３】本発明の第１の実施形態の変形例における配列に配置されたカップルドノードツリーの構成例を説明する図である。
【図１４】本発明の第１の実施形態の変形例におけるビット列検索の処理フロー例を説明する図である。
【図１５】本発明の第２の実施形態の変形例における配列に配置されたカップルドノードツリーの構成例を説明する図である。
【図１６】本発明の第２の実施形態の変形例におけるビット列検索の処理フロー例を説明する図である。
【図１７】リンク先の配列番号を求める処理フロー例を説明する図である。
【図１８Ａ】本発明の第１及び第２の実施形態におけるポインタレスツリーを生成する処理の前段の処理フロー例を説明する図である。
【図１８Ｂ】本発明の第１及び第２の実施形態におけるポインタレスツリーを生成する処理の後段の処理フロー例を説明する図である。
【図１９】巡回開始ノードよりツリーを巡回し、ノードをポインタレスツリーに格納する処理フロー例を説明する図である。
【図２０Ａ】本発明の第１の実施形態におけるノードを生成する処理の処理フロー例を説明する図である。
【図２０Ｂ】本発明の第２の実施形態におけるノードを生成する処理の処理フロー例を説明する図である。
【図２１】変換前のツリーの最大段数を求める処理フロー例を説明する図である。
【図２２】巡回開始ノードよりツリーを巡回し、ノードの段数をカウントして巡回済みノードの最大段数を求める処理フロー例を示す図である。
【発明を実施するための形態】
【００３３】
図３は、本発明を実施するためのハードウェア構成例を説明する図である。本発明の検索装置による検索処理は中央処理装置３０２及びキャッシュメモリ３０３を少なくとも備えたデータ処理装置３０１によりデータ格納装置３０８を用いて実施することができる。カップルドノードツリーが配置される配列３０９と検索中にたどるノードが格納された配列要素の配列番号を記憶する探索経路スタック３１０を有するデータ格納装置３０８は、主記憶装置３０５または外部記憶装置３０６で実現することができ、あるいは通信装置３０７を介して接続された遠方に配置された装置を用いることも可能である。
なお、リーフノードにインデックスキーではなくインデックスキーにアクセスするための情報を格納する場合には、データ格納装置には、インデックスキーを記憶する記憶領域が設けられる。
【００３４】
図３の例示では、主記憶装置３０５、外部記憶装置３０６及び通信装置３０７が一本のバス３０４によりデータ処理装置３０１に接続されているが、接続方法はこれに限るものではない。また、主記憶装置３０５をデータ処理装置３０１内のものとすることもできるし、探索経路スタック３１０を中央処理装置３０２内のハードウェアとして実現することも可能である。あるいは、配列３０９は外部記憶装置３０６に、探索経路スタック３１０を主記憶装置３０５に持つなど、使用可能なハードウェア環境、インデックスキー集合の大きさ等に応じて適宜ハードウェア構成を選択できることは明らかである。
また、特に図示されてはいないが、処理の途中で得られた各種の値を後の処理で用いるためにそれぞれの処理に応じた一時記憶装置が用いられることは当然である。
【００３５】
次に図４Ａ〜図７を参照して、本発明の第１の実施形態について説明する。
図４Ａは、本発明の第１の実施形態における配列に配置されたカップルドノードツリーの構成例を説明する図である。図１Ａに示す構成例と比べると、ブランチノードから代表ノード番号を格納する領域がなくなっている。また、配列番号は、１から１５への連続した番号のものが記載されている。
【００３６】
図４Ａを参照すると、ルートノード４０１が配列４００の配列番号１の配列要素に配置されている。ルートノード４０１はノード種別４０２及び弁別ビット位置４０３で構成されている。ノード種別４０２は０であり、ルートノード４０１がブランチノードであることを示している。弁別ビット位置４０３には１が格納されている。
【００３７】
配列番号が１であるルートノード４０１からの点線の矢印４１０で示すリンク先ノード対４１１の代表ノードであるノード［０］４１２は、ツリー上で直近上位に位置する親ノードであるルートノード４０１の配列番号１の２倍の値を持つ配列番号２の配列要素に配置されている。そして隣接する次の配列要素（配列番号３）に代表ノードと対になるノード［１］４１３が配置されている。ノード［０］４１２のノード種別には１が格納されており、ノード［０］４１２がリーフノードであることを示している。インデックスキー４１８には、“０００１”が格納されている。一方、ノード［１］４１３のノード種別には０が格納されており、ノード［１］４１３がブランチノードであることを示している。ブランチノード４１３の弁別ビット位置には３が格納されている。
【００３８】
配列番号が３であるブランチノード４１３からの点線の矢印４２０で示すリンク先ノード対４２１の代表ノードであるノード４２２は、親ノードであるノード４１３の配列番号３の２倍の値を持つ配列番号６の配列要素に配置されている。そして隣接する次の配列要素（配列番号７）に代表ノードと対になるノード４２３が配置されている。ノード４２２のノード種別には０が格納されており、ノード４２２がブランチノードであることを示している。ブランチノード４２２の弁別ビット位置には４が格納されている。また、ノード４２３のノード種別にも０が格納されており、ノード４２３がブランチノードであることを示している。ブランチノード４２２の弁別ビット位置には５が格納されている。
【００３９】
そして、配列番号４及び配列番号５の配列要素には、ノードは配置されていない。
上述の例示から明らかなとおり、リンク先のノード対の代表ノードの配列番号は、親ノードの配列番号の２倍となる。
【００４０】
そこで、配列番号が６であるブランチノード４２２からの点線の矢印４３０で示すリンク先ノード対４３１の代表ノードであるノード４３２は、配列番号１２の配列要素に配置されている。そして隣接する次の配列要素（配列番号１３）に代表ノードと対になるノード４３３が配置されている。ノード４３２及びノード４３３の内容の記載は省略されている。
【００４１】
同様に、配列番号が７であるブランチノード４２３からの点線の矢印４４０で示すリンク先ノード対４４１の代表ノードであるノード４４２は、配列番号１４の配列要素に配置されている。そして隣接する次の配列要素（配列番号１５）に代表ノードと対になるノード４４３が配置されている。ノード４４２及びノード４４３の内容の記載は省略されている。
また、配列番号８から配列番号１１の配列要素には、ノードは配置されていない。
【００４２】
図４Ｂは、本発明の第１の実施形態におけるカップルドノードツリーのツリー構造を概念的に示す図である。図１Ｂに示すカップルドノードツリー２００のツリー構造と比べると、図４Ｂに示すカップルドノードツリー２００ａのリーフノードについては同一であり、ブランチノードの弁別ビット位置の値も図１Ｂに示すものと同一なので、ツリー自体の分岐パターンも同一である。しかし、ブランチノードは、リンク先のノード対の代表ノードの配列番号である代表ノード番号を含まない。代表ノード番号はブランチノードの配列番号を２倍することにより得られるので、代表ノード番号によるリンク先への結合を、代表ノード番号の符号を付した点線の矢印により表している。また、各ノードを示す符号の近傍に、各ノードが配置される配列要素の配列番号を、ルートノード２１０ａに対して［１］のように表示している。代表ノード番号と配列番号の表記以外は図１Ｂに記載したものと同じなので、これ以上の説明は省略する。
【００４３】
図５は、本発明の第１の実施形態におけるビット列検索装置の機能ブロック構成例を説明する図である。
図５に例示する本実施態様に係るビット列検索装置５００は、検索ツリー記憶手段５１０、検索開始位置設定手段５２０、ノード読出手段５３０、ノード種別判定手段５４０、検索キー設定手段５５０、ノードリンク手段５６０及び検索結果出力手段５７０を備えている。
【００４４】
検索ツリー記憶手段５１０の記憶領域には配列が確保され、その配列にカップルドノードツリーが配置される。検索開始位置設定手段５２０には、検索開始ノードの配列番号が設定される。ルートノードを検索開始ノードとする場合は、配列番号として１が設定される。検索開始位置の設定は、検索処理の結果を利用するユーザにより設定することができる。
【００４５】
ノード読出手段５３０は、検索開始位置設定手段５２０に設定された配列番号の検索開始ノード、あるいはノードリンク手段５６０により設定された配列番号のリンク先のノードを読み出す。ノード種別識別手段５４０は、ノード読出手段５３０が読みだしたノードの種別を判定し、リーフノードであればそのリーフノードを検索結果出力手段５７０に渡し、ブランチノードであればそのブランチノードをノードリンク手段５６０に渡す。
【００４６】
検索キー設定手段５５０には、検索キーが設定される。検索キーの設定は、検索処理の結果を利用するユーザにより設定することができる。ノードリンク手段５６０は、ノード種別判定手段５４０から渡されたブランチノードの弁別ビット位置にある、検索キー設定手段５５０に設定された検索キーのビットの値とブランチノードの配置されている配列要素の配列番号を２倍した値を加算した値を、次に読み出すノードの配置された配列要素の配列番号として設定する。
【００４７】
検索結果出力手段５７０は、ノード種別判定手段５４０から渡されたリーフノードからインデックスキーあるいはインデックスキーにアクセスするための情報を取り出す。リーフノードから取り出すものがインデックスキーであるときは、そのインデックスキーを検索結果キーとして出力する。リーフノードから取り出すものがインデックスキーにアクセスするための情報であるときは、取り出したインデックスキーにアクセスするための情報に基づき、インデックスキーを読み出して検索結果キーとして出力する。
なお、検索結果キーと検索キーを比較し、一致すれば検索成功とし、一致しなければ検索失敗とする検索結果を出力することも可能である。
上記図５を参照して説明した機能ブロック構成はあくまで１つの例であり、種々の変形が可能であることは明らかである。
【００４８】
以下、本発明の第１の実施形態における検索処理について、図６を参照して説明する。図６は、本発明の第１の実施形態におけるビット列検索の処理フロー例を説明する図である。
【００４９】
まず、ステップＳ６０１で、リンク先配列番号に１を設定する。ここでいうリンク先配列番号は、先に述べた図示しない一時的記憶領域の１つの例である。リンク先配列番号には、検索開始ノードの配列番号と、リンク先のノード対の代表ノードの配列番号が設定される。図６に示す例では、検索開始ノードをルートノードとしたものである。検索開始ノードをルートノード以外のものとした場合でも、以下の処理フローは同様である。
【００５０】
次にステップＳ６０３で、配列からリンク先配列番号に設定された配列番号の配列要素を参照すべきノードとして読み出す。そして、ステップＳ６０４で、読み出したノードから、ノード種別を取り出し、ステップＳ６０５で、ノード種別がブランチノードであるか否かを判定する。
【００５１】
ステップＳ６０５の判定において、読み出したノードがブランチノードである場合はステップＳ６０６に進み、ノードから弁別ビット位置についての情報を取り出し、更に、ステップＳ６０７で、取り出した弁別ビット位置に対応するビット値を検索キーから取り出す。そして、ステップＳ６０８で、リンク先配列番号に設定された配列番号を２倍にしてリンク先配列番号に設定する。さらにステップＳ６０９で、ステップＳ６０７で検索キーから取り出したビット値をステップＳ６０８でリンク先配列番号に設定した配列番号に加算し、新たな配列番号としてリンク先配列番号に設定して、ステップＳ６０３に戻る。
【００５２】
以降、ステップＳ６０５の判定においてリーフノードと判定されてステップＳ６１０に進むまで、ステップＳ６０３からステップＳ６０９までの処理を繰り返す。ステップＳ６１０では、リーフノードからインデックスキーを取り出して、処理を終了する。
なお、上述の例では、リーフノードにインデックスキーが直接含まれているものとしたが、リーフノードにインデックスキーにアクセスするための情報が含まれている場合には、ステップＳ６１０においてリーフノードからインデックスキーにアクセスするための情報を取り出し、さらに追加ステップにおいて、取り出されたインデックスキーにアクセスするための情報を用いてインデックスキーを取り出す。
また、インデックスキーを取り出したのち、そのインデックスキーを検索結果キーとして他のアプリケーションで用いることもできるし、検索キーとの一致判定を行い、検索成功あるいは検索失敗とすることもできる。
【００５３】
次に、図７を参照して、本発明の第１の実施形態に係るカップルドノードツリーを用いた検索例を説明する。図７には、図４Ｂに例示したカップルドノードツリーのうち、説明に必要な部分のみ記載しており、ノード２１１ｂより下位の部分は省略されている。
図７に示す例では、検索キー設定エリア２７０には検索キーとしてビット列“０１１０１０”（以下、検索キー２７０と表記する。）が設定され、検索開始ノードはルートノード２１０ａとされている。また、リンク先の配列番号が、リンク元のブランチノードの配列番号を２倍した代表ノード番号と検索キーの弁別ビット位置のビット値の和で求められることも記載されている。
【００５４】
以下、図７の記載に沿って、検索処理の流れを説明する。
検索開始ノードがルートノードであることから、検索の開始時には、リンク先配列番号には１が設定されるので、ノード２１０ａが読み出される。そして、ノード２１０ａのノード種別２２０ａは０であり、ブランチノードであることを示しているので弁別ビット位置２３０ａからその値０が取り出される。検索キー２７０のビット位置０の値は０であるので、リンク先配列番号は、配列番号１を２倍した代表ノード番号２２０ａに０を加えた２となり、配列番号２の配列要素に配置されたノード２１０ｂが次に読み出される。
【００５５】
ノード２１０ｂのノード種別２２０ｂは０であり、ブランチノードであることを示しているので弁別ビット位置２３０ｂからその値１が取り出される。検索キー２７０のビット位置１の値は１であるので、リンク先配列番号は、配列番号２を２倍した代表ノード番号２２０ｂに１を加えた５となり、配列番号５の配列要素に配置されたノード２１１ｃが次に読み出される。
【００５６】
ノード２１１ｃのノード種別２２１ｃは０であり、ブランチノードであることを示しているので弁別ビット位置２３１ｃからその値２が取り出される。検索キー２７０のビット位置２の値は１であるので、リンク先配列番号は、配列番号５を２倍した代表ノード番号２２１ｃに１を加えた１１となり、配列番号１１の配列要素に配置されたノード２１１ｄが次に読み出される。
【００５７】
ノード２１１ｄのノード種別２２１ｄは１であり、リーフノードであることを示しているのでインデックスキー２５１ｄからインデックスキー“０１１０１０”が取り出され、検索処理が終了する。
【００５８】
次に図８Ａ〜図１２を参照して、本発明の第２の実施形態について説明する。
図８Ａは、本発明の第２の実施形態における配列に配置されたカップルドノードツリーの構成例を説明する図である。本実施形態は、リーフノード、ブランチノードからノード種別を削除し、リーフノードをツリーの最下段にのみに配置している。さらに、インデックスキー、検索キーは、本来のインデックスキー、検索キーに対して、ある特定のビット位置である最上位ビットに０を挿入したものとしている。リンク先の配列番号の求め方は、第１の実施形態と同様である。なお、最上位ビットとして付加するビット値は、０ではなく１とすることもできる。要するに、同一のビット値を最上位ビットとして付加すればよい。また、特定のビット値を挿入するある特定のビット位置も、最上位のビット位置に限ることなく、任意のビット位置とすることができる。同一のビット値を挿入したビット位置は、カップルドノードツリーの本来のブランチノードの弁別ビット位置に現れることはない。そこで、後に説明するダミーのブランチノードの弁別ビット位置として用い、ダミーのブランチノードを挿入することにより、リーフノードをツリーの最下段にのみに配置することを可能としている。
【００５９】
図８Ａを参照すると、ルートノード８０１が配列８００の配列番号１の配列要素に配置されている。ルートノード８０１は弁別ビット位置８０３で構成されている。弁別ビット位置８０３には２が格納されている。
【００６０】
配列番号が１であるルートノード８０１からの点線の矢印８１０で示すリンク先ノード対８１１の代表ノードであるノード［０］８１２は、ツリー上で直近上位に位置する親ノードであるルートノード８０１の配列番号１の２倍の値を持つ配列番号２の配列要素に配置されている。そして隣接する次の配列要素（配列番号３）に代表ノードと対になるノード［１］８１３が配置されている。
【００６１】
ノード［０］８１２の弁別ビット位置には０が格納されており、そのリンク先は、点線の矢印８４０で示すように、ノード［０］８１２の配列番号２の２倍の配列番号４の配列要素に格納されたノード８４２である。また、ノード８４２の弁別ビット位置には０が格納されており、そのリンク先は、点線の矢印８５０で示すように、ノード８４２の配列番号４の２倍の配列番号８の配列要素に格納されたノード８５２である。
【００６２】
ノード８５２は、図８Ａに例示するカップルドノードツリーの最下段に位置するので、リーフノードであり、インデックスキー８１８には最上位ビットに０が挿入されたインデックスキー“００００１”が格納されている。
図８Ａに示す例では、インデックスキー“００００１”は、ルートノード８０１の弁別ビット位置８０３のビット位置２におけるビット値０によりすでに他の配列要素に格納されたインデックスキーとは弁別されている。したがって、図４Ａに示す第１の実施形態のように、ルートノードの直近下位の配列番号２の配列要素に格納されたノードが本来のリーフノードの位置であるが、本実施形態においてはリーフノードであることを識別するノード種別を用いないので、弁別ビット位置が最上位ビット位置の０であるダミーのブランチノード８１２、８４２を挿入して最下段に位置するようにしている。なお、図８Ａに示す配列番号５の配列要素が空きとなっているように、２段目のダミーのブランチノード８４２と対をなすノードは実質的に存在しない空きノードとなる。
【００６３】
一方、ノード［１］８１３の弁別ビット位置には４が格納されている。配列番号が３であるブランチノード８１３からの点線の矢印８２０で示すリンク先ノード対８２１の代表ノードであるノード８２２は、親ノードであるノード８１３の配列番号３の２倍の値を持つ配列番号６の配列要素に配置されている。そして隣接する次の配列要素（配列番号７）に代表ノードと対になるノード８２３が配置されている。ノード８２２の弁別ビット位置には５が格納されている。また、ノード８２３の弁別ビット位置には６が格納されている。
【００６４】
配列番号が６であるブランチノード８２２からの点線の矢印８３０で示すリンク先ノード対８３１の代表ノードであるノード８３２は、配列番号１２の配列要素に配置されている。そして隣接する次の配列要素（配列番号１３）に代表ノードと対になるノード８３３が配置されている。ノード８３２及びノード８３３の内容の記載は省略されている。また、ブランチノード８２３のリンク先の記載も省略されている。
【００６５】
図８Ｂは、本発明の第２の実施形態におけるカップルドノードツリーのツリー構造を概念的に示す図である。図８Ｂに示すツリー構造においては、図４Ｂに示すツリー構造に格納されている各インデックスキーの最上位のビット位置に０が追加され、ビット長が６ビットから７ビットになっている。それに伴い、図４Ｂに示すブランチノードと同一の符号を付したブランチノードの弁別ビット位置は１つシフトされ、値が１つ大きくなっている。
【００６６】
また、図４Ｂに示すツリー構造における段数は５段であるので、図８Ｂに示すツリー構造においては、５段目にのみリーフノードが位置している。そして、図４Ａに示すツリー構造において５段目より上位の階層に位置するリーフノードは、弁別ビット位置が０のダミーのブランチノードとなっている。そして、ダミーのブランチノードの直近下位のノードが５段目のノードとなるまで、ダミーのブランチノードが挿入されている。
直近下位のノード対の代表ノードが配置された配列要素の配列番号である代表ノード番号の算出方法は、第１の実施形態のものと同じである。
【００６７】
図４Ｂに示す例示では、最上位ビットとして０を付加しているため、例えば本来的なインデックスキー“０００１１１”はリーフノード２１０ｊに格納されているが、最上位ビットとして１を付加した場合はリーフノード２１１ｊに格納することは明らかである。
【００６８】
図９は、本発明の第２の実施形態におけるビット列検索装置の機能ブロック構成例を説明する図である。
図９に例示する本実施態様に係るビット列検索装置９００は、検索ツリー記憶手段９１０、検索開始位置設定手段９２０、ノード読出手段９３０１〜９３０ｎ、検索キー設定手段９５０、ノードリンク手段９６０１〜９６０ｎ−１及び検索結果出力手段９７０を備えている。ただし、ｎはカップルドノードツリーの段数である。
【００６９】
先に説明した第１の実施形態と同様に、検索ツリー記憶手段９１０の記憶領域には配列が確保され、その配列に本発明の第２の実施形態に係るカップルドノードツリーが配置される。また、検索開始位置設定手段９２０には、検索開始ノードの配列番号として、ルートノードの配列番号である１が設定される。
【００７０】
ノード読出手段９３０１は、検索開始位置設定手段に設定された配列番号１のルートノードを読み出す。
検索キー設定手段９５０には、検索キーが設定される。検索キーの設定は、検索処理の結果を利用するユーザにより設定することができる。ノードリンク手段９６０１は、ノード読出手段９６０１が読み出したブランチノードの弁別ビット位置にある、検索キー設定手段９５０に設定された検索キーのビットの値とルートノードの配列番号１を２倍した値とを加算した値を、次に読み出すノードの配置された配列要素の配列番号として設定する。
【００７１】
以下同様に、ノードリンク手段９６０２〜９６０ｎ−１は、ノード読出手段９３０２〜９３０ｎ−１が読み出したブランチノードの弁別ビット位置にある、検索キー設定手段９５０に設定された検索キーのビットの値と、前段のノードリンク手段９６０１〜９６０ｎ−２により設定された配列番号を２倍した値とを加算した値を、それぞれ次に読み出すノードの配置された配列要素の配列番号として設定する。
【００７２】
ノード読出手段９３０２〜９３０ｎ−１は、前段のノードリンク手段９６０１〜９６０ｎ−２が設定した配列番号のブランチノードを読み出し、ノード読出手段９３０ｎは、ノードリンク手段９６０ｎ−１が設定した配列番号のリーフノードを読み出して、検索結果出力手段９７０に渡す。
【００７３】
検索結果出力手段９７０は、ノード読出手段９３０ｎから渡されたリーフノードから、第１の実施形態の場合と同様に、インデックスキーあるいはインデックスキーにアクセスするための情報を取り出す。リーフノードから取り出すものがインデックスキーであるときは、そのインデックスキーを検索結果キーとして出力する。リーフノードから取り出すものがインデックスキーにアクセスするための情報であるときは、取り出したインデックスキーにアクセスするための情報に基づき、インデックスキーを読み出して検索結果キーとして出力する。
また、検索結果キーと検索キーを比較し、一致すれば検索成功とし、一致しなければ検索失敗とする検索結果を出力することが可能であることも、第１の実施形態の場合と同様である。
【００７４】
次に、本発明の第２の実施形態における検索処理について、図１０及び図１１を参照して説明する。
図１０は、本発明の第２の実施形態におけるビット列検索の処理フロー例を説明する図である。図１０に示す例では、カップルドノードツリーの段数はｎとする。
【００７５】
まず、ステップＳ１００１で、リンク先配列番号に１を設定する。
次にステップＳ１００２において、リンク先配列番号（ルートノードの配列番号）の指す配列に格納された弁別ビット位置と検索キーにより、２段目のノードの配列番号を求める。
【００７６】
続いてステップＳ１００３において、２段目のノードの配列番号の指す配列に格納された弁別ビット位置と検索キーにより、３段目のノードの配列番号を求める。
以下同様に、ステップＳ１００４〜ステップＳ１００ｎにおいて、３段目〜ｎ−１段目のノードの配列番号の指す配列に格納された弁別ビット位置と検索キーにより、それぞれ４段目〜ｎ段目のノードの配列番号を求める。ステップＳ１００２〜ステップＳ１００ｎの処理の詳細は、後に図１１を参照して説明する。
【００７７】
最後に、ｎ段目のノードの配列番号の指す配列に格納されたビット列をインデックスキーとして取り出し、処理を終了する。
なお、図１０に例示する処理フロー例は、特定の段数ｎを有する本実施形態のカップルドノードツリーを用いたものであるが、段数ｎをパラメータとしたアセンブラマクロにより、本実施形態の任意の段数のカップルドノードツリーを用いた検索処理を実現するための処理フローを生成することが可能である。
【００７８】
図１１は、本発明の第２の実施形態におけるリンク先の配列番号を求める処理フロー例を説明する図であり、図１０に示すステップＳ１００２〜ステップＳ１００ｎの処理の詳細を示すものである。
【００７９】
まず、ステップＳ１１０１において、配列から、リンク先配列番号の指す配列要素に格納された内容を弁別ビット位置として読み出し、ステップＳ１１０２において、検索キーから、該読み出した弁別ビット位置の指すビット値を取り出す。
【００８０】
次にステップＳ１１０３において、リンク先配列番号に設定された配列番号を２倍にしてリンク先配列番号に設定する。さらにステップＳ１１０４で、ステップＳ１１０３でリンク先配列番号に設定された配列番号に、ステップＳ１１０２で取り出したビット値を加算してリンク先配列番号に設定して処理を終了する。
【００８１】
次に、図１２を参照して、本発明の第２の実施形態に係るカップルドノードツリーを用いた検索例を説明する。図１２には、図８Ｂに例示したカップルドノードツリーのうち、説明に必要な部分のみ記載しており、ノード２１１ｂより下位の部分は省略されている。
図１２に示す例では、検索キー設定エリア２８０には検索キーとしてビット列“００１１０１０”（以下、検索キー２８０と表記する。）が設定されている。検索キー２８０は、図４Ｂに示す本発明の第１の実施形態に係るカップルドノードツリーを用いた検索例における検索キー２７０に最上位ビットとして０を付加したものである。検索開始ノードはルートノード２１０ａである。図４Ｂに示す検索例と同様に、リンク先の配列番号が、リンク元のブランチノードの配列番号を２倍した代表ノード番号と検索キーの弁別ビット位置のビット値の和で求められることも記載されている。
【００８２】
以下、図１２の記載に沿って、検索処理の流れを説明する。
検索開始ノードがルートノードであることから、検索の開始時には、リンク先配列番号には１が設定されるので、ノード２１０ａが読み出される。そして、ノード２１０ａの弁別ビット位置２３０ａからその値１が取り出される。検索キー２８０のビット位置１の値は０であるので、リンク先配列番号は、配列番号１を２倍した代表ノード番号２２０ａに０を加えた２となり、配列番号２の配列要素に配置されたノード２１０ｂが次に読み出される。
【００８３】
そして、ノード２１０ｂの弁別ビット位置２３０ｂからその値２が取り出される。検索キー２８０のビット位置２の値は１であるので、リンク先配列番号は、配列番号２を２倍した代表ノード番号２２０ｂに１を加えた５となり、配列番号５の配列要素に配置されたノード２１１ｃが次に読み出される。
【００８４】
そして、ノード２１１ｃの弁別ビット位置２３１ｃからその値３が取り出される。検索キー２８０のビット位置３の値は１であるので、リンク先配列番号は、配列番号５を２倍した代表ノード番号２２１ｃに１を加えた１１となり、配列番号１１の配列要素に配置されたノード２１１ｄが次に読み出される。
【００８５】
そして、ノード２１１ｄの弁別ビット位置２３１ｄからその値０が取り出される。検索キー２８０のビット位置０の値は０であるので、リンク先配列番号は、配列番号１１を２倍した代表ノード番号２２１ｉに０を加えた２２となり、配列番号２２の配列要素に配置されたノード２１０ｌが次に読み出される。
【００８６】
ノード２１０ｌはカップルドノードツリーの最下位段に位置するので、インデックスキー２５０ｌから検索結果のインデックスキー“００１１０１０”が取り出され、検索処理が終了する。
【００８７】
次に、上述の第１の実施形態及び第２の実施形態の変形例について説明する。これらの変形例は、ツリーを格納する配列を記憶装置の領域に柔軟に配置可能とする、あるいは記憶装置の任意の領域に存在する配列にツリーを配置可能とするためのものである。
【００８８】
図１３は、本発明の第１の実施形態の変形例における配列に格納されたカップルドノードツリーの構成例を説明する図である。図４Ａに示す構成例と比較すると、ベース番号６００とオフセット番号６１０が追加されている。また、図４Ａの配列番号１〜１５に替えて、ノード参照番号６２０の値１〜１５が記載されている。図１３においては、配列番号６３０については、その番号の値として、１００、１１１、１２２、１２３、１３４〜１３７、１４８〜１５５が記載されている。
また、図１３には、ベース番号６００の値として１００が、オフセット番号６１０の値として１０、２０、３０、４０が例示されている。
その他の符号については、図４Ａに示された対応する符号にａを付加したものが使用されている。
【００８９】
ベース番号は、後述の１段目のオフセット番号と組み合わせてツリーのルートノードの位置を定める番号である。ベース番号を用いることにより、ルートノードの配列番号が、図４Ａ及び図４Ｂの例示のように１に制約される必要をなくすことができる。
オフセット番号は、ツリーの各段のノードの格納される開始位置を定める番号である。オフセット番号を用いることにより、ツリーのノードを、そのノードが位置するツリー上の段数毎に配置することができる。オフセット番号は、段数毎にオフセット番号表に設定しておく。
ノード参照番号は、ノードの順番を定める番号であり、図４に例示する配列番号に相当する。
配列番号は、ベース番号、オフセット番号及びノード参照番号の和により求めることができる。
本変形例において、ベース番号を０、各段のオフセット番号を０とすると、ノード参照番号は図４Ａ及び図４Ｂに例示する配列番号と一致し、本変形例のカップルドノードツリーは、図４Ａ及び図４Ｂに例示する第１の実施形態のカップルドノードツリーと一致する。
【００９０】
図１３を参照すると、ベース番号６００が１００（以下、ベース番号１００という。）、オフセット番号６１０（１段目）が１０（以下、オフセット番号１０、のようにいう。）であって、ノード参照番号６２０は１（以下、ノード参照番号１、のようにいう。）であるから、ルートノード４０１ａは配列４００ａの配列番号６３０が１１１（以下、配列番号１１１、のようにいう。）の配列要素に配置されている。ルートノード４０１ａはノード種別４０２ａ及び弁別ビット位置４０３ａで構成されている。ノード種別４０２ａは０であり、ルートノード４０１ａがブランチノードであることを示している。弁別ビット位置４０３ａには１が格納されている。
【００９１】
ノード参照番号１のルートノード４０１ａからの点線の矢印４１０ａで示すリンク先ノード対４１１ａの代表ノードであるノード［０］４１２ａは、ツリー上で直近上位に位置する親ノードであるルートノード４０１ａのノード参照番号１の２倍の値を持つノード参照番号２に、ベース番号１００とオフセット番号２０の和を加えた配列番号１２２の配列要素に配置されている。そして隣接する次の配列要素（ノード参照番号３、配列番号１２３）に代表ノードと対になるノード［１］４１３ａが配置されている。ノード［０］４１２ａのノード種別には１が格納されており、ノード［０］４１２ａがリーフノードであることを示している。インデックスキー４１８ａには、“０００１”が格納されている。一方、ノード［１］４１３ａのノード種別には０が格納されており、ノード［１］４１３ａがブランチノードであることを示している。ブランチノード４１３ａの弁別ビット位置には３が格納されている。
【００９２】
ノード参照番号が３であるブランチノード４１３ａからの点線の矢印４２０ａで示すリンク先ノード対４２１ａの代表ノードであるノード４２２ａは、親ノードであるノード４１３ａのノード参照番号３の２倍の値を持つノード参照番号６に、ベース番号１００とオフセット番号３０の和を加えた配列番号１３６の配列要素に配置されている。そして隣接する次の配列要素（ノード参照番号７、配列番号１３７）に代表ノードと対になるノード４２３ａが配置されている。ノード４２２ａのノード種別には０が格納されており、ノード４２２ａがブランチノードであることを示している。ブランチノード４２２ａの弁別ビット位置には４が格納されている。また、ノード４２３ａのノード種別にも０が格納されており、ノード４２３ａがブランチノードであることを示している。ブランチノード４２２ａの弁別ビット位置には５が格納されている。
【００９３】
そして、配列番号１３４及び配列番号１３５の配列要素には、ノードは配置されていない。
上述の例示から明らかなとおり、リンク先のノード対の代表ノードのノード参照番号は、親ノードのノード参照番号の２倍となる。
【００９４】
そこで、ノード参照番号が６であるブランチノード４２２ａからの点線の矢印４３０ａで示すリンク先ノード対４３１ａの代表ノードであるノード４３２ａは、ノード参照番号１２に、ベース番号１００とオフセット番号４０の和を加えた配列番号１５２の配列要素に配置されている。そして隣接する次の配列要素（ノード参照番号１３、配列番号１５３）に代表ノードと対になるノード４３３ａが配置されている。ノード４３２ａ及びノード４３３ａの内容の記載は省略されている。
【００９５】
同様に、ノード参照番号が７であるブランチノード４２３ａからの点線の矢印４４０ａで示すリンク先ノード対４４１ａの代表ノードであるノード４４２ａは、ノード参照番号１４に、ベース番号１００とオフセット番号４０の和を加えた配列番号１５４の配列要素に配置されている。そして隣接する次の配列要素（ノード参照番号１５、配列番号１５５）に代表ノードと対になるノード４４３ａが配置されている。ノード４４２ａ及びノード４４３ａの内容の記載は省略されている。
また、配列番号１４８から配列番号１５１の配列要素には、ノードは配置されていない。
【００９６】
本変形例においても、カップルドノードツリーのツリー構造自体は、図４Ｂに示すものと同じである。違う点は、図４Ａ及び図４Ｂに示すものにおいては、ノードのツリー上の位置が配列に結びついた配列番号で規定されるのに対して、本変形例においては、配列とは独立のノード参照番号で規定される点である。
そして、ノード参照番号とベース番号及びオフセット番号を組み合わせることにより、ノードにアクセスすることが可能である。
【００９７】
したがって、オフセット番号を適宜選択することにより、例えばツリーのうち上位ｎ段を主記憶装置に配置し、ｎ段目より下位のノードを外部記憶装置に配置するようなことが可能である。
【００９８】
次に、本発明の第１の実施形態の変形例における検索処理について、図１４を参照して説明する。図１４は、本発明の第１の実施形態の変形例におけるビット列検索の処理フロー例を説明する図である。図６に示す処理フロー例と比較すると、ノード参照番号、ベース番号及びオフセット番号の取り扱いが加わったことと、これらの番号により配列番号を求めることが異なる。
【００９９】
まず、ステップＳ１４０１ａで、ベース番号を設定し、ステップＳ１４０１ｂで、オフセット番号表を設定する。さらに、ステップＳ１４０１ｃで、段数カウンタに値１を設定し、ステップＳ１４０１ｄで、ノード参照番号に値１を設定する。図１４に示す例では、検索開始ノードをルートノードとするものであるが、段数カウンタとノード参照番号に１以外の番号が指定され、検索開始ノードをルートノード以外のものとした場合でも、以下の処理フローは同様である。
【０１００】
次にステップＳ１４０２ａで、オフセット番号表より、段数カウンタの指すオフセット番号を取り出し、ステップＳ１４０２ｂで、リンク先配列番号に、ノード参照番号にベース番号とオフセット番号を加えた値を設定する。
次にステップＳ１４０３で、配列からリンク先配列番号に設定された配列番号の配列要素を参照すべきノードとして読み出す。そして、ステップＳ１４０４で、読み出したノードから、ノード種別を取り出し、ステップＳ１４０５で、ノード種別がブランチノードであるか否かを判定する。
【０１０１】
ステップＳ１４０５の判定において、読み出したノードがブランチノードである場合はステップＳ１４０６に進み、ノードから弁別ビット位置についての情報を取り出し、更に、ステップＳ１４０７で、取り出した弁別ビット位置に対応するビット値を検索キーから取り出す。そして、ステップＳ１４０８で、ノード参照番号に、ノード参照番号を２倍した値にステップＳ１４０７で得た値を設定する。さらにステップＳ１４０９で、段数カウンタに１を加えて、ステップＳ１４０３に戻る。
【０１０２】
以降、ステップＳ１４０５の判定においてリーフノードと判定されてステップＳ１４１０に進むまで、ステップＳ１４０２ａからステップＳ１４０９までの処理を繰り返す。  ステップＳ１４１０では、リーフノードからインデックスキーを取り出して、処理を終了する。
なお、上述の例では、リーフノードにインデックスキーが直接含まれているものとしたが、リーフノードにインデックスキーにアクセスするための情報が含まれている場合には、ステップＳ１４１０においてリーフノードからインデックスキーにアクセスするための情報を取り出し、さらに追加ステップにおいて、取り出されたインデックスキーにアクセスするための情報を用いてインデックスキーを取り出す。
また、インデックスキーを取り出したのち、そのインデックスキーを検索結果キーとして他のアプリケーションで用いることもできるし、検索キーとの一致判定を行い、検索成功あるいは検索失敗とすることもできる。
【０１０３】
次に、本発明の第２の実施形態の変形例について説明する。ベース番号、オフセット番号及びノード参照番号の技術的意義、及び配列番号との関係は、第１の実施態様の変形例と同じである。
図１５は、本発明の第２の実施形態の変形例における配列に格納されたカップルドノードツリーの構成例を説明する図である。図８Ａに示す構成例と比較すると、ベース番号７００とオフセット番号７１０が追加されている。また、図８Ａの配列番号１〜１５に替えて、ノード参照番号７２０の値１〜１５が記載されている。図１５においては、配列番号７３０については、その番号の値として、１００、１１１、１２２、１２３、１３４〜１３７、１４８〜１５５が記載されている。
また、図１５には、ベース番号７００の値として１００が、オフセット番号７１０の値として１０、２０、３０、４０が例示されている。
その他の符号については、図８Ａに示された対応する符号にａを付加したものが使用されている。
本変形例において、第１の実施形態の変形例と同様に、ベース番号を０、各段のオフセット番号を０とすると、ノード参照番号は図８Ａ及び図８Ｂに例示する配列番号と一致し、本変形例のカップルドノードツリーは、図８Ａ及び図８Ｂに例示する第２の実施形態のカップルドノードツリーと一致する。
【０１０４】
図１５を参照すると、ベース番号が１００、オフセット番号が１０であって、ノード参照番号は１であるから、ルートノード８０１ａは配列８００ａの配列番号１１１の配列要素に配置されている。ルートノード８０１ａは弁別ビット位置８０３ａで構成されている。弁別ビット位置８０３ａには２が格納されている。
【０１０５】
ノード参照番号が１であるルートノード８０１ａからの点線の矢印８１０ａで示すリンク先ノード対８１１ａの代表ノードであるノード［０］８１２ａは、ツリー上で直近上位に位置する親ノードであるルートノード８０１ａのノード参照番号１の２倍の値を持つノード参照番号２に、ベース番号１００とオフセット番号２０の和を加えた配列番号１２２の配列要素に配置されている。そして隣接する次の配列要素（ノード参照番号３、配列番号１２３）に代表ノードと対になるノード［１］８１３ａが配置されている。
【０１０６】
ノード［０］８１２ａの弁別ビット位置には０が格納されており、そのリンク先は、点線の矢印８４０ａで示すように、ノード［０］８１２ａのノード参照番号２の２倍の値を持つノード参照番号４に、ベース番号１００とオフセット番号３０の和を加えた配列番号１３４の配列要素に格納されたノード８４２ａである。また、ノード８４２の弁別ビット位置には０が格納されており、そのリンク先は、点線の矢印８５０ａで示すように、ノード８４２ａのノード参照番号４の２倍の値を持つノード参照番号８に、ベース番号１００とオフセット番号４０の和を加えた配列番号１４８の配列要素に格納されたノード８５２ａである。
【０１０７】
ノード８５２ａは、図１５に例示するカップルドノードツリーの最下段に位置するので、リーフノードであり、インデックスキー８１８ａには最上位ビットに０が挿入されたインデックスキー“００００１”が格納されている。
【０１０８】
一方、ノード［１］８１３ａの弁別ビット位置には４が格納されている。ノード参照番号が３であるブランチノード８１３ａからの点線の矢印８２０ａで示すリンク先ノード対８２１ａの代表ノードであるノード８２２ａは、親ノードであるノード８１３ａのノード参照番号３の２倍の値を持つノード参照番号６に、ベース番号１００とオフセット番号３０の和を加えた配列番号１３６の配列要素に配置されている。そして隣接する次の配列要素（ノード参照番号７、配列番号１３７）に代表ノードと対になるノード８２３ａが配置されている。ノード８２２ａの弁別ビット位置には５が格納されている。また、ノード８２３ａの弁別ビット位置には６が格納されている。
【０１０９】
ノード参照番号が６であるブランチノード８２２ａからの点線の矢印８３０ａで示すリンク先ノード対８３１ａの代表ノードであるノード８３２ａは、ノード参照番号６の２倍の値を持つノード参照番号１２に、ベース番号１００とオフセット番号４０の和を加えた配列番号１５２の配列要素に配置されている。そして隣接する次の配列要素（ノード参照番号１３、配列番号１５３）に代表ノードと対になるノード８３３ａが配置されている。ノード８３２及びノード８３３の内容の記載は省略されている。また、ブランチノード８２３ａのリンク先の記載も省略されている。
【０１１０】
本変形例においても、カップルドノードツリーのツリー構造自体は、図８Ｂに示すものと同じである。違う点は、図８Ａ及び図８Ｂに示すものにおいては、ノードのツリー上の位置が配列に結びついた配列番号で規定されるのに対して、第１の実施形態の変形例と同様に、本変形例においても、配列とは独立のノード参照番号で規定される点である。
そして、ノード参照番号とベース番号及びオフセット番号を組み合わせることにより、ノードにアクセスすることが可能である。
【０１１１】
したがって、オフセット番号を適宜選択することにより、例えばツリーのうち上位ｎ段を主記憶装置に配置し、ｎ段目より下位のノードを外部記憶装置に配置するようなことが可能である。
【０１１２】
次に、本発明の第２の実施形態の変形例における検索処理について、図１６を参照して説明する。図１６は、本発明の第２の実施形態の変形例におけるビット列検索の処理フロー例を説明する図である。図１０に示す処理フロー例と比較すると、ノード参照番号、ベース番号及びオフセット番号の取り扱いが加わったことと、これらの番号により配列番号を求めることが異なる。
【０１１３】
まず、ステップＳ１６０１ａで、ベース番号を設定し、ステップＳ１６０１ｂで、オフセット番号表を設定する。さらに、ステップＳ１６０１ｃで、ノード参照番号に値１を設定する。さらにステップＳ１６０１ｄにおいて、リンク先配列番号に、ノード参照番号にベース番号とオフセット番号を加えた値を設定する。ステップＳ１６０１ｄの処理により、リンク先配列番号には、ルートノードの配列番号が設定される。
【０１１４】
次にステップＳ１６０２において、ルートノードの配列番号（リンク先配列番号）の指す配列に格納された弁別ビット位置と検索キーにより、２段目のノードの配列番号を求める。
続いてステップＳ１６０３において、２段目のノードの配列番号の指す配列に格納された弁別ビット位置と検索キーにより、３段目のノードの配列番号を求める。
以下同様に、ステップＳ１６０４〜ステップＳ１６０ｎにおいて、３段目〜ｎ−１段目のノードの配列番号の指す配列に格納された弁別ビット位置と検索キーにより、それぞれ４段目〜ｎ段目のノードの配列番号を求める。ステップＳ１６０２〜ステップＳ１６０ｎの処理の詳細は、後に図１７を参照して説明する。
【０１１５】
最後に、ｎ段目のノードの配列番号の指す配列に格納されたビット列をインデックスキーとして取り出し、処理を終了する。
なお、図１０に例示する処理フロー例と同様に、図１６に例示する処理フロー例は、特定の段数ｎを有する本実施形態のカップルドノードツリーを用いたものであるが、段数ｎをパラメータとしたアセンブラマクロにより、本実施形態の任意の段数のカップルドノードツリーを用いた検索処理を実現するための処理フローを生成することが可能である。
【０１１６】
図１７は、本発明の第２の実施形態の変形例におけるリンク先の配列番号を求める処理フロー例を説明する図であり、図１６に示すステップＳ１６０２〜ステップＳ１６０ｎの処理の詳細を示すものである。
【０１１７】
まず、ステップＳ１７０１において、配列から、リンク先配列番号の指す配列要素に格納された内容を弁別ビット位置として読み出し、ステップＳ１７０２において、検索キーから、該読み出した弁別ビット位置の指すビット値を取り出す。
【０１１８】
次にステップＳ１７０３ａにおいて、オフセット番号表より、次段のオフセット番号を取り出し、ステップＳ１７０３ｂにおいて、ノード参照番号に、ノード参照番号を２倍した値にステップＳ１７０２で得た値を加えた値を設定する。さらにステップＳ１７０４で、リンク先配列番号に、ノード参照番号にベース番号とオフセット番号を加えた値を設定して処理を終了する。
【０１１９】
次に、本発明の第１の実施形態及び第２の実施形態のカップルドノードツリーの生成について説明する。なお、以下の説明において、本発明の第１の実施形態及び第２の実施形態のツリーをポインタレスツリーといい、従来のカップルドノードツリーを単にツリー、あるいは変換前のツリーということがある。
本発明のポインタレスツリーの生成は、例えば次のようにして実現することができる。すなわち、ポインタレスツリーを生成する際には、ポインタレスツリーに格納されるインデックスキーにより、図１Ａ及び図１Ｂに例示する形態のツリーが生成されているものとする。そして、ポインタレスツリーの生成は、ツリーのノードをルートノードから順次巡回し、本発明の第１の実施形態あるいは第２の実施形態のノードに変換することにより、実現される。このノードの巡回は、以下において詳細に説明するが、前記特許文献４として引用した特開２００８−２６９１９７号公報の図１０Ａ〜図１２及びそれに関連した明細書の記載に開示されたノードの退避処理で用いられるものと類似するものである。
ツリーの生成は、前記特許文献１として引用した特開２００８−１５８７２号公報の図５〜図８及びそれに関連した明細書の記載に開示され、詳細に説明されているので、ここでの説明は省略する。
【０１２０】
図１８Ａは、本発明の第１及び第２の実施形態におけるポインタレスツリーを生成する処理の前段の処理フロー例を示す図である。図１８Ａに示すように、まずステップＳ１８０１において、ポインタレスツリーを生成するための配列を取得し、ステップＳ１８０２おいて、配列要素を初期化する。このステップＳ１８０２の処理は、ダミーのブランチノードを用いる第２の実施形態における処理例において必要となるものであり、第１の実施形態では省略可能である。
次にステップＳ１８０２ａにおいて変換前のツリーの最大段数を求め、ステップＳ１８０２ｂにおいて該最大段数を段数カウンタの上限値に設定する。段数カウンタの上限値は、第２の実施形態においてリーフノードをポインタレスツリーの最下段に配置するために用いられるものである。したがって、ステップＳ１８０２の処理と同様に、第１の実施形態では省略可能である。
ステップＳ１８０２ａの処理の詳細については、後に図２１及び図２２を参照して説明する。
【０１２１】
次にステップＳ１８０３において、ベース番号を設定し、ステップＳ１８０４において、オフセット番号表を設定する。
さらに、ステップＳ１８０５において、段数カウンタに１を設定し、ステップＳ１８０６において、ノード参照番号に１を設定し、ステップＳ１８０７において、巡回開始ノードの配列番号に、ツリーのルートノードの配列番号を設定して図１８Ｂに示すステップＳ１８１２に進む。
【０１２２】
なお、上述の図１８Ａ及び以下の図面に例示するフローは、図１３あるいは図１５に示す変形例に対応するものである。しかし、変形例においてベース番号を０、各段におけるオフセット番号を０、ノード参照番号を配列番号とすれば、図４Ａあるいは図８Ａに示す形態のツリーの生成処理を示すものである。したがって、図１８Ａ及び以下の図面に例示するフローは、変形例を含む第１の実施形態及び第２の実施形態のポインタレスツリーの生成処理を説明するものである。
【０１２３】
図１８Ｂは、本発明の第１及び第２の実施形態におけるポインタレスツリーを生成する処理の後段の処理フロー例を示す図である。図１８Ｂに示すように、ステップＳ１８１２において、巡回開始ノードよりツリーを巡回し、巡回先のノードを変換してポインタレスツリーに格納する。ステップＳ１８１２の処理の詳細は、後に図１９を参照して説明する。
【０１２４】
次にステップＳ１８１３において、探索経路スタックのスタックポインタはツリーのルートノードの配列番号を指しているか判定する。配列番号の探索経路スタックへの格納は、ステップＳ１８１２の処理で行われる。
探索経路スタックのスタックポインタはツリーのルートノードの配列番号を指していれば、ツリーの全てのノードの処理は完了しているので処理を終了する。そうでなければ、ステップＳ１８１４に進む。
【０１２５】
ステップＳ１８１４では、探索経路スタックから配列番号を取り出し、探索経路スタックのスタックポインタを１つ減らす。次にステップＳ１８１５において、ステップＳ１８１４で取り出した配列番号からノード位置を求め、そのノード位置がノード［０］であるかを、ステップＳ１８１６において判定する。ノード位置がノード［０］でなければ、ステップＳ１８１７で段数カウンタから値１を減じてステップＳ１８１３に戻る。ノード位置がノード［０］であれば、ステップＳ１８１８に進む。
【０１２６】
ステップＳ１８１８では、ステップＳ１８１４で取り出した配列番号に値１を加えて、ノード［１］の配列番号を得る。そして、ステップＳ１８１９で巡回開始ノードの配列番号に、ステップＳ１８１８で得たノード［１］の配列番号を設定し、ステップＳ１８２０で、ノード参照番号に１を加えてステップＳ１８１２に戻る。
上述のステップＳ１８１２〜ステップＳ１８２０のループ処理を、ステップＳ１８１３において探索経路スタックのスタックポインタがツリーのルートノードの配列番号を指していると判定されるまで繰り返すことにより、ツリー上のすべてのノードの巡回が行われ、各ノードがポインタレスツリーのノードに変換されてポインタレスツリーが生成される。
【０１２７】
図１９は、巡回開始ノードよりツリーを巡回し、ノードをポインタレスツリーに格納する処理フロー例を説明する図であり、図１８ＢのステップＳ１８１２の処理の詳細を説明する図である。
図に示すように、まずステップＳ１９０１において、巡回開始ノードの配列番号を配列番号に設定する。巡回開始ノードの配列番号は、図１８Ｂに示すステップＳ１８１２〜ステップＳ１８２０のループ処理の初回の処理においては、図１８ＡのステップＳ１８０７で設定されており、それ以降の処理においては、図１８Ｂに示すステップＳ１８１９で設定される。
【０１２８】
次にステップＳ１９０２において、探索経路スタックに配列番号を格納する。この配列番号は、ステップＳ１９０１あるいは後記ステップＳ１９１０で設定されているものである。
【０１２９】
次にステップＳ１９０３において、変換前のツリーが格納された配列から、配列番号の指す配列要素をノードとして読み出し、ステップＳ１９０４において、ノード参照番号をもとに、図１８ＡのステップＳ１８０１で取得した配列の配列要素にノードを書き込むことでポインタレスツリーのノードを生成する。ステップＳ１９０４の処理の詳細は、後に図２０Ａ及び図２０Ｂを参照して説明する。図２０Ａは第１の実施形態のためのもの、図２０Ｂは第２の実施形態のためのものである。
【０１３０】
次にステップＳ１９０５において、ステップＳ１９０３で読み出したノードからノード種別を取り出し、ステップＳ１９０６で、該取り出したノード種別はブランチノードを示すものか判定する。ステップＳ１９０６の判定が、ノード種別はブランチノードを示すものではなくリーフノードを示すものであれば処理を終了し、ブランチノードを示すものであれば、ステップＳ１９０７に進む。
【０１３１】
ステップＳ１９０７では、段数カウンタに値１を加え、ステップＳ１９０８に進み、ノード参照番号を２倍にする。さらにステップＳ１９０９において、ステップＳ１９０３で読み出したノードから、代表番号を取り出し、ステップＳ１９１０で、該取り出した代表ノード番号に値０を加えた値を配列番号に設定し、ステップＳ１９０２に戻る。
【０１３２】
上述のステップＳ１９０２〜ステップＳ１９１０のループ処理を、ステップＳ１９０６においてノード種別がリーフノードを示すまで繰り返す。つまり、ひとまとまりの処理として、巡回開始ノードから最初のリーフノードまでノードを巡回してノードを読み出し、それを変換してポインタレスツリーのノードを書き込む。図１９に示す処理フロー例では、ステップＳ１９１０において、代表ノード番号に値０を加えて配列番号に設定していることから、ノード［０］側を優先してノードを巡回しているが、ノード［１］側を優先してノードを巡回することも可能であることは、以上の説明から当業者に明らかである。
【０１３３】
図２０Ａは、本発明の第１の実施形態におけるノードを生成する処理の処理フロー例を説明する図であり、図１９に示すステップＳ１９０４の第１の実施形態における処理の詳細を説明する図である。
【０１３４】
図に示すように、まずステップＳ２００１において、オフセット番号表より、段数カウンタの指すオフセット番号を取り出し、ステップＳ２００２において、配列番号に、ノード参照番号にベース番号とオフセット番号を加えた値を設定する。ここでの配列番号は、ポインタレスツリーを格納する配列の配列要素の配列番号を設定する一時記憶領域であり、図１９ＡのステップＳ１９０１やステップＳ１９１０で設定される変換前のツリーを格納する配列の配列要素の配列番号を設定する一時記憶領域とは異なる。
【０１３５】
次にステップＳ２００３において、図１９のステップＳ１９０３で読み出しているノードから、ノード種別を取り出し、ステップＳ２００４において、該取り出したノード種別はブランチノードのものか判定する。判定結果が肯定的なものであれば、ステップＳ２００５に進み、否定的なものであれば、ステップＳ２００７に進む。
【０１３６】
ステップＳ２００５では、ノードから弁別ビット位置を取り出し、ステップＳ２００６において、ステップＳ２００２で設定した配列番号の指す配列要素にノード種別と弁別ビット位置を書き込み、ブランチノードを生成して処理を終了する。
ステップＳ２００７では、ノードからインデックスキーを取り出し、ステップＳ２００８において、ステップＳ２００２で設定した配列番号の指す配列要素にノード種別とインデックスキーを書き込み、ブランチノードを生成して処理を終了する。
【０１３７】
図２０Ｂは、本発明の第２の実施形態におけるノードを生成する処理の処理フロー例を説明する図であり、図１９に示すステップＳ１９０４の第２の実施形態における処理の詳細を説明する図である。
【０１３８】
図に示すように、まずステップＳ２０２１において、オフセット番号表より、段数カウンタの指すオフセット番号を取り出し、ステップＳ２０２３において、図１９のステップＳ１９０３で読み出しているノードから、ノード種別を取り出し、ステップＳ２０２４に進む。
【０１３９】
ステップＳ２０２４では、ステップＳ２０２３で取り出したノード種別はブランチノードのものか判定する。判定結果が肯定的なものであれば、ステップＳ２０２５に進み、否定的なものであれば、ステップＳ２０２９に進む。
【０１４０】
ステップＳ２０２５では、配列番号に、ノード参照番号にベース番号とオフセット番号を加えた値を設定する。そしてステップＳ２０２６で、ノードから弁別ビット位置を取り出し、ステップＳ２０２７で、該弁別ビット位置に値１を加え、ステップＳ２０２８において、ステップＳ２０２５で設定した配列番号の指す配列要素に弁別ビット位置を書き込み、ブランチノードを生成して処理を終了する。
【０１４１】
一方、ステップＳ２０２４の判定が否定的なものであって、ステップＳ２０２３で取り出したノード種別がリーフノードのものであるときは、ステップＳ２０２９に進み、ノード参照番号と段数カウンタを退避し、ステップＳ２０３０に進む。
【０１４２】
ステップＳ２０３０では、段数カウンタは上限値か判定し、上限値でなければ、ステップＳ２０３１でノード参照番号を２倍し、ステップＳ２０３２で段数カウンタに値１を加え、ステップＳ２０３３で、オフセット番号表より、段数カウンタの指すオフセット番号を取り出してステップＳ２０３０に戻る。
【０１４３】
上述のステップＳ２０３０〜Ｓ２０３３のループ処理は、第２の実施形態におけるリーフノードをポインタレスツリーの最下段のレベルに配置するためのものである。図１Ｂ、図８Ｂの例示では、例えば図１Ｂの変換前のツリーでは３段目にあるリーフノード２１０ｃは、図８Ｂでは５段目のノード２１０ｊに変換されている。そして、図８Ｂにおけるノード２１０ｃの位置情報は、図２０ＢのステップＳ２０２９の処理により、退避される。
【０１４４】
なお、段数カウンタの上限値については、図１８Ａに示すステップＳ１８０２ｂで設定されているが、それに替えて、変換前のツリーを生成するときに、リーフノードを挿入するごとにそのリーフノードの段数をカウントし、その最大値をツリーの属性として記憶しておき、第２の実施形態のポインタレスツリーを生成するときに、その最大値を段数カウンタの上限値とすることができる。
【０１４５】
上述のステップＳ２０３０で、段数カウンタは上限値であると判定されると、ステップＳ２０３４に進み、配列番号に、ノード参照番号にベース番号とオフセット番号を加えた値を設定する。そしてステップＳ２０３５で、ノードからインデックスキーを取り出し、ステップＳ２０３６で、該インデックスキーの最上位のビット位置にビット値“０”を挿入し、ステップＳ２０３７において、ステップＳ２０３４で設定した配列番号の指す配列要素にインデックスキーを書き込み、リーフノードを生成してステップＳ２０３８に進む。
ステップＳ２０３８では、ノード参照番号と段数カウンタに、ステップＳ２０２９で退避したノード参照番号と段数カウンタをそれぞれ設定して処理を終了する。
【０１４６】
次に、変換前のツリーの最大段数を求める処理について説明する。
図２１は、変換前のツリーの最大段数を求める処理フロー例を説明する図であり、図１８ＡのステップＳ１８０２ａの処理の詳細を説明するものである。
【０１４７】
図２１に示すように、まずステップＳ２１０１において、段数カウンタに値１を設定し、ステップＳ２１０２において、最大段数カウンタに、段数カウンタに設定された値を設定する。すなわち、段数カウンタ及び最大段数カウンタには、初期値として値１が設定される。
【０１４８】
次にステップＳ２１１２において、巡回開始ノードよりツリーを巡回し、巡回先のノードの段数をカウントして巡回済みノードの最大段数を求める。ステップＳ２１１２の処理の詳細は、後に図２２を参照して説明する。
【０１４９】
次にステップＳ２１１３において、探索経路スタックのスタックポインタはツリーのルートノードの配列番号を指しているか判定する。配列番号の探索経路スタックへの格納は、ステップＳ２１１２の処理で行われる。
探索経路スタックのスタックポインタはツリーのルートノードの配列番号を指していれば、ツリーの全てのノードの巡回は完了しているので処理を終了する。そうでなければ、ステップＳ２１１４に進む。
【０１５０】
ステップＳ２１１４では、探索経路スタックから配列番号を取り出し、探索経路スタックのスタックポインタを１つ減らす。次にステップＳ２１１５において、ステップＳ２１１４で取り出した配列番号からノード位置を求め、そのノード位置がノード［０］であるかを、ステップＳ２１１６において判定する。ノード位置がノード［０］でなければ、ステップＳ２１１７で段数カウンタから値１を減じてステップＳ２１１３に戻る。ノード位置がノード［０］であれば、ステップＳ２１１８に進む。
【０１５１】
ステップＳ２１１８では、ステップＳ２１１４で取り出した配列番号に値１を加えて、ノード［１］の配列番号を得る。そして、ステップＳ２１１９で巡回開始ノードの配列番号に、ステップＳ２１１８で得たノード［１］の配列番号を設定してステップＳ２１１２に戻る。
上述のステップＳ２１１２〜ステップＳ２１１９のループ処理を、ステップＳ２１１３において探索経路スタックのスタックポインタがツリーのルートノードの配列番号を指していると判定されるまで繰り返すことにより、ツリー上のすべてのノードの巡回が行われ、巡回済みノードの最大段数、すなわち、変換前ツリーの最大段数が求められる。
【０１５２】
図２２は、巡回開始ノードよりツリーを巡回し、ノードの段数をカウントして巡回済みノードの最大段数を求める処理フロー例を示す図であり、図２１のステップＳ２１１２の処理の詳細を説明する図である。
図に示すように、まずステップＳ２２０１において、巡回開始ノードの配列番号を配列番号に設定する。巡回開始ノードの配列番号は、図２１に示すステップＳ２１１２〜ステップＳ２１１９のループ処理の初回の処理においては、図２１のステップＳ２１０７で設定されており、それ以降の処理においては、図２１に示すステップＳ２１１９で設定される。
【０１５３】
次にステップＳ２２０２において、探索経路スタックに配列番号を格納する。この配列番号は、ステップＳ２２０１あるいは後記ステップＳ２２１０で設定されているものである。
【０１５４】
次にステップＳ２２０３において、変換前のツリーが格納された配列から、配列番号の指す配列要素をノードとして読み出し、次にステップＳ２２０５において、該読み出したノードからノード種別を取り出す。
【０１５５】
次にステップＳ２２０６で、該取り出したノード種別はブランチノードを示すものか判定する。ステップＳ２２０６において、ノード種別はブランチノードを示すものであると判定されれば、ステップＳ２２０７に進み、ノード種別はブランチノードを示すものではなくリーフノードを示すものとであると判定されると、ステップＳ２２１０に進む。
【０１５６】
ステップＳ２２０７では、段数カウンタに値１を加え、ステップＳ２２０９において、ステップＳ２２０３で読み出したノードから、代表番号を取り出し、ステップＳ２２１０で、該取り出した代表ノード番号に値０を加えた値を配列番号に設定し、ステップＳ２２０２に戻る。
【０１５７】
上述のステップＳ２２０２〜ステップＳ２２１０のループ処理を、ステップＳ２２０６においてノード種別がリーフノードを示すまで繰り返す。なお、図２２に示す処理フロー例では、ステップＳ２２１０において、代表ノード番号に値０を加えて配列番号に設定していることから、ノード［０］側を優先してノードを巡回しているが、先に説明した図１９の処理と同様に、ノード［１］側を優先してノードを巡回することも可能であることは、当業者に明らかである。
【０１５８】
上述のステップＳ２２０６において、ノード種別がリーフノードを示すものと判定されると、ステップＳ２２１０に進み、段数カウンタの値は最大段数カウンタに設定された値より大きいか判定し、大きくなければそのまま処理を終了し、大きければ、ステップＳ２２１１で、最大段数カウンタに段数カウンタの値を設定して処理を終了する。
【０１５９】
以上本発明を実施するための形態について詳細に説明したが、本発明の実施の形態はそれに限ることなく種々の変形が可能であることは当業者に明らかである。
また、本発明の第１の実施形態及び第２の実施形態に係るビット列検索装置が、図６、図１０及び図１１、あるいは図１４、図１６及び図１７に例示した処理をコンピュータに実行させるプログラムによりコンピュータ上に構築可能なことは明らかである。
したがって、上記プログラム、及びプログラムを記憶したコンピュータ読み取り可能な記憶媒体は、本発明の実施の形態に含まれる。さらに、本発明のカップルドノードツリーのデータ構造も、本発明の実施の形態に含まれる。
【符号の説明】
【０１６０】
１００、４００、８００          配列
１０１                          ノード
１０２、４０２                  ノード種別
１０３、４０３、８０３          弁別ビット位置
１０４                          代表ノード番号
１１８、４１８、８１８          インデックスキー
２００、２００ａ、２００ｂ      カップルドノードツリー
２１０ａ、４０１、８０１        ルートノード
２７０、２８０                  検索キー
３０１                          データ処理装置
３０２                          中央処理装置
３０３                          キャッシュメモリ
３０４                          バス
３０５                          主記憶装置
３０６                          外部記憶装置
３０７                          通信装置
３０８                          データ格納装置
３０９                          配列
３１０                          探索経路スタック
５００、９００                  ビット列検索装置
５１０、９１０                  検索ツリー記憶手段
５２０、９２０                  検索開始位置設定手段
５３０                          ノード読出手段
５４０                          ノード種別判定手段
５５０、９５０                  検索キー設定手段
５６０                          ノードリンク手段
５７０、９７０                  検索結果出力手段
９３０１、・・・、９３０ｎ      ノード読出手段
９６０１、・・・、９６０ｎ−１  ノードリンク手段
６００、７００                  ベース番号
６１０、７１０                  オフセット番号
６２０、７２０                  ノード参照番号
６３０、７３０                  配列番号
【図１Ａ】
2011134289.tif 000003
【図１Ｂ】
2011134289.tif 000004
【図２】
2011134289.tif 000005
【図３】
2011134289.tif 000006
【図４Ａ】
2011134289.tif 000007
【図４Ｂ】
2011134289.tif 000008
【図５】
2011134289.tif 000009
【図６】
2011134289.tif 000010
【図７】
2011134289.tif 000011
【図８Ａ】
2011134289.tif 000012
【図８Ｂ】
2011134289.tif 000013
【図９】
2011134289.tif 000014
【図１０】
2011134289.tif 000015
【図１１】
2011134289.tif 000016
【図１２】
2011134289.tif 000017
【図１３】
2011134289.tif 000018
【図１４】
2011134289.tif 000019
【図１５】
2011134289.tif 000020
【図１６】
2011134289.tif 000021
【図１７】
2011134289.tif 000022
【図１８Ａ】
2011134289.tif 000023
【図１８Ｂ】
2011134289.tif 000024
【図１９】
2011134289.tif 000025
【図２０Ａ】
2011134289.tif 000026
【図２０Ｂ】
2011134289.tif 000027
【図２１】
2011134289.tif 000028
【図２２】
2011134289.tif 000029