【手続補正書】
【提出日】平成22年1月20日(2010.1.20)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ビット列からなる最長一致検索キーにより、検索対象であるビット列からなるインデックスキーが格納されたツリーのデータ構造に基づいて、前記インデックスキーのうち前記最長一致検索キーとの最長一致条件を満たすインデックスキーを検索する最長一致検索装置において、
ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対、からなるビット列検索に用いるツリーであって、
前記ルートノードは、ツリーの始点を表すノードであって、該ツリーのノードが１つのときは前記リーフノード、ツリーのノードが２つ以上のときは前記ブランチノードであり、前記ブランチノードは、ビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードである代表ノードの位置を示す位置情報を含み、前記リーフノードは検索対象のビット列からなるインデックスキーを含み、
前記ツリーの任意のノードを検索開始ノードとして、前記ブランチノードにおいて該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいはそれと隣接した記憶領域に配置されたノードにリンクすることを順次前記リーフノードに至るまで繰り返すことにより、前記リーフノードに格納されたインデックスキーを、前記検索開始ノードをルートノードとする前記ツリーの任意の部分木の前記検索キーによる検索の結果である検索結果キーとするように構成されたカップルドノードツリーと、
前記カップルドノードツリーの前記ルートノードを前記検索開始ノードとし、指定された最長一致検索キーを前記検索キーとして、前記ブランチノードにおいて該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいはそれと隣接した記憶領域に配置されたノードにリンクすることを順次リーフノードに至るまで繰り返し、前記ルートノードから該リーフノードまでの経路を記憶しながら該リーフノードに格納されたインデックスキーを前記検索結果キーとして取得する検索手段と、
前記最長一致検索キーと前記検索結果キーのビット列を比較して、ビット値が一致しない不一致ビットの位置のうち最も上位の位置である差分ビット位置を取得する差分ビット位置取得手段と、
前記差分ビット位置がビット列の最上位以外の位置のとき、記憶された前記経路を参照して最長一致ノードを設定する最長一致ノード設定手段であって、
前記ルートノードが前記リーフノードの場合または前記ルートノードが前記ブランチノードであり該ルートノードの前記弁別ビット位置が前記差分ビット位置よりも下位の位置の場合は、前記ルートノードを前記最長一致ノードとして設定し、
その他の場合は、前記経路上のノードであって前記弁別ビット位置が前記差分ビット位置よりも上位にある前記ブランチノードのうち前記弁別ビット位置が最下位の前記ブランチノードの次に前記検索手段によって記憶された前記ブランチノードまたは前記リーフノードを前記最長一致ノードとして設定する最長一致ノード設定手段と、
を備えることを特徴とする最長一致検索装置。
【請求項２】
前記最長一致ノードをルートノードとする前記カップルドノードツリーの部分木に含まれる前記リーフノードを選択し、選択した該リーフノードに含まれるインデックスキーを取得するインデックスキー取得手段をさらに備えることを特徴とする請求項１に記載の最長一致検索装置。
【請求項３】
ビット列からなる最長一致検索キーにより、検索対象であるビット列からなるインデックスキーが格納されたツリーのデータ構造に基づいて、前記インデックスキーのうち前記最長一致検索キーとの最長一致条件を満たすインデックスキーを検索する最長一致検索方法であって、
前記ツリーは、ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対、からなるビット列検索に用いるツリーであって、
前記ルートノードは、ツリーの始点を表すノードであって、該ツリーのノードが１つのときは前記リーフノード、ツリーのノードが２つ以上のときは前記ブランチノードであり、前記ブランチノードは、ビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードである代表ノードの位置を示す位置情報を含み、前記リーフノードは検索対象のビット列からなるインデックスキーを含み、
前記ツリーの任意のノードを検索開始ノードとして、前記ブランチノードにおいて該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいはそれと隣接した記憶領域に配置されたノードにリンクすることを順次前記リーフノードに至るまで繰り返すことにより、前記リーフノードに格納されたインデックスキーを、前記検索開始ノードをルートノードとする前記ツリーの任意の部分木の前記検索キーによる検索の結果である検索結果キーとするように構成されたカップルドノードツリーである最長一致検索方法において、
前記カップルドノードツリーの前記ルートノードを前記検索開始ノードとし、指定された最長一致検索キーを前記検索キーとして、前記ブランチノードにおいて該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいはそれと隣接した記憶領域に配置されたノードにリンクすることを順次リーフノードに至るまで繰り返し、前記ルートノードから該リーフノードまでの経路を記憶しながら該リーフノードに格納されたインデックスキーを前記検索結果キーとして取得する検索ステップと、
前記最長一致検索キーと前記検索結果キーのビット列を比較して、ビット値が一致しない不一致ビットの位置のうち最も上位の位置である差分ビット位置を取得する差分ビット位置取得ステップと、
前記差分ビット位置がビット列の最上位以外の位置のとき、記憶された前記経路を参照して最長一致ノードを設定する最長一致ノード設定ステップであって、
前記ルートノードが前記リーフノードの場合または前記ルートノードが前記ブランチノードであり該ルートノードの前記弁別ビット位置が前記差分ビット位置よりも下位の位置の場合は、前記ルートノードを前記最長一致ノードとして設定し、
その他の場合は、前記経路上のノードであって前記弁別ビット位置が前記差分ビット位置よりも上位にある前記ブランチノードのうち前記弁別ビット位置が最下位の前記ブランチノードの次に前記検索ステップにおいて記憶された前記ブランチノードまたは前記リーフノードを前記最長一致ノードとして設定する最長一致ノード設定ステップと、
を備えることを特徴とする最長一致検索方法。
【請求項４】
前記最長一致ノードをルートノードとする前記カップルドノードツリーの部分木に含まれる前記リーフノードを選択し、選択した該リーフノードに含まれるインデックスキーを取得するインデックスキー取得ステップをさらに備えることを特徴とする請求項３に記載の最長一致検索方法。
【請求項５】
前記カップルドノードツリーは、配列に記憶され、前記位置情報は、該位置情報に対応する前記代表ノードが格納された前記配列の配列要素の配列番号であり、前記検索ステップにおいて、前記経路上のノードの格納された前記配列要素の前記配列番号を順次スタックに保持していくことにより、前記経路を記憶することを特徴とする請求項３に記載の最長一致検索方法。
【請求項６】
ビット列からなる最短一致検索キーにより、検索対象であるビット列からなるインデックスキーが格納されたツリーのデータ構造に基づいて、前記インデックスキーのうち前記最短一致検索キーとの最短一致条件を満たすインデックスキーを検索する最短一致検索装置において、
ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対、からなるビット列検索に用いるツリーであって、
前記ルートノードは、ツリーの始点を表すノードであって、該ツリーのノードが１つのときは前記リーフノード、ツリーのノードが２つ以上のときは前記ブランチノードであり、前記ブランチノードは、ビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードである代表ノードの位置を示す位置情報を含み、前記リーフノードは検索対象のビット列からなるインデックスキーを含み、
前記ツリーの任意のノードを検索開始ノードとして、前記ブランチノードにおいて該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいはそれと隣接した記憶領域に配置されたノードにリンクすることを順次前記リーフノードに至るまで繰り返すことにより、前記リーフノードに格納されたインデックスキーを、前記検索開始ノードをルートノードとする前記ツリーの任意の部分木の前記検索キーによる検索の結果である検索結果キーとするように構成されたカップルドノードツリーと、
前記カップルドノードツリーの前記ルートノードを前記検索開始ノードとし、指定された最長一致検索キーを前記検索キーとして、前記ブランチノードにおいて該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいはそれと隣接した記憶領域に配置されたノードにリンクすることを順次リーフノードに至るまで繰り返し、前記ルートノードから該リーフノードまでの経路を記憶しながら該リーフノードに格納されたインデックスキーを前記検索結果キーとして取得する検索手段と、
前記最短一致検索キーと前記検索結果キーのビット列を比較して、ビット値が一致しない不一致ビットの位置のうち最も上位の位置である差分ビット位置を取得する差分ビット位置取得手段と、
前記差分ビット位置がビット列の最上位以外の位置のとき、記憶された前記経路を参照して最短一致ノードを設定する最短一致ノード設定手段であって、
前記経路が、前記ルートノードと、該ルートノードのリンク先のノード対の一方のブランチノードとを含み、前記ルートノードの弁別ビット位置が前記差分ビット位置よりも上位の位置の場合は、前記ブランチノードの次に前記検索手段により記憶されたノードとノード対を構成するノードを前記最短一致ノードとして設定する最短一致ノード設定手段と、
を備えることを特徴とする最短一致検索装置。
【請求項７】
前記最短一致ノードをルートノードとする前記カップルドノードツリーの部分木に含まれる前記リーフノードを選択し、選択した該リーフノードに含まれるインデックスキーを取得するインデックスキー取得手段をさらに備えることを特徴とする請求項６に記載の最短一致検索装置。
【請求項８】
ビット列からなる最短一致検索キーにより、検索対象であるビット列からなるインデックスキーが格納されたツリーのデータ構造に基づいて、前記インデックスキーのうち前記最短一致検索キーとの最短一致条件を満たすインデックスキーを検索する最短一致検索方法であって、
前記ツリーは、ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対、からなるビット列検索に用いるツリーであって、
前記ルートノードは、ツリーの始点を表すノードであって、該ツリーのノードが１つのときは前記リーフノード、ツリーのノードが２つ以上のときは前記ブランチノードであり、前記ブランチノードは、ビット列検索を行う検索キーの弁別ビット位置とリンク先のノード対の一方のノードである代表ノードの位置を示す位置情報を含み、前記リーフノードは検索対象のビット列からなるインデックスキーを含み、
前記ツリーの任意のノードを検索開始ノードとして、前記ブランチノードにおいて該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいはそれと隣接した記憶領域に配置されたノードにリンクすることを順次前記リーフノードに至るまで繰り返すことにより、前記リーフノードに格納されたインデックスキーを、前記検索開始ノードをルートノードとする前記ツリーの任意の部分木の前記検索キーによる検索の結果である検索結果キーとするように構成されたカップルドノードツリーである最短一致検索方法において、
前記カップルドノードツリーの前記ルートノードを前記検索開始ノードとし、指定された最長一致検索キーを前記検索キーとして、前記ブランチノードにおいて該ブランチノードに含まれる弁別ビット位置の検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいはそれと隣接した記憶領域に配置されたノードにリンクすることを順次リーフノードに至るまで繰り返し、前記ルートノードから該リーフノードまでの経路を記憶しながら該リーフノードに格納されたインデックスキーを前記検索結果キーとして取得する検索ステップと、
前記最短一致検索キーと前記検索結果キーのビット列を比較して、ビット値が一致しない不一致ビットの位置のうち最も上位の位置である差分ビット位置を取得する差分ビット位置取得ステップと、
前記差分ビット位置がビット列の最上位以外の位置のとき、記憶された前記経路を参照して最短一致ノードを設定する最短一致ノード設定ステップであって、
前記経路が、前記ルートノードと、該ルートノードのリンク先のノード対の一方のブランチノードとを含み、前記ルートノードの弁別ビット位置が前記差分ビット位置よりも上位の位置の場合は、前記ブランチノードの次に前記検索ステップにおいて記憶されたノードとノード対を構成するノードを前記最短一致ノードとして設定する最短一致ノード設定ステップと、
を備えることを特徴とする最短一致検索方法。
【請求項９】
前記最短一致ノードをルートノードとする前記カップルドノードツリーの部分木に含まれる前記リーフノードを選択し、選択した該リーフノードに含まれるインデックスキーを取得するインデックスキー取得ステップをさらに備えることを特徴とする請求項８に記載の最短一致検索方法。
【請求項１０】
前記カップルドノードツリーは、配列に記憶され、前記位置情報は、該位置情報に対応する前記代表ノードが格納された前記配列の配列要素の配列番号であり、前記検索ステップにおいて、前記経路上のノードの格納された前記配列要素の前記配列番号を順次スタックに保持していくことにより、前記経路を記憶することを特徴とする請求項８に記載の最短一致検索方法。
【請求項１１】
請求項３〜請求項５のいずれか１項に記載の最長一致検索方法または請求項８〜請求項１０のいずれか１項に記載の最短一致検索方法をコンピュータに実行させるためのプログラム。
【請求項１２】
請求項３〜請求項５のいずれか１項に記載の最長一致検索方法または請求項８〜請求項１０のいずれか１項に記載の最短一致検索方法をコンピュータに実行させるためのプログラムを記憶したことを特徴とするコンピュータ読み取り可能な記憶媒体。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】発明の名称
【補正方法】変更
【補正の内容】
【発明の名称】カップルドノードツリーの最長一致／最短一致検索装置、検索方法及びプログラム
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００２５
【補正方法】変更
【補正の内容】
【００２５】
本発明による前記カップルドノードツリーを用いた最長一致検索は、前記カップルドノードツリーの前記ルートノードを前記検索開始ノードとし、指定された最長一致検索キーを前記検索キーとして、前記ルートノードからの経路を記憶しながらの検索による前記検索結果キーの取得と、前記最長一致検索キーと前記検索結果キーのビット列比較による、ビット値が一致しない不一致ビットの位置のうち最も上位の位置である差分ビット位置の取得と、さらに、前記差分ビット位置がビット列の最上位以外の位置のとき、記憶された前記経路を参照し、前記ルートノードが前記リーフノードの場合または前記ルートノードが前記ブランチノードであり該ルートノードの前記弁別ビット位置が前記差分ビット位置よりも下位の位置の場合は、前記ルートノードを最長一致ノードとし、その他の場合は、前記経路上のノードであって前記弁別ビット位置が前記差分ビット位置よりも上位にある前記ブランチノードのうち前記弁別ビット位置が最下位の前記ブランチノードの次に記憶された前記ブランチノードまたは前記リーフノードを前記最長一致ノードとして設定する最長一致ノードの設定により実現される。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００２６
【補正方法】変更
【補正の内容】
【００２６】
本発明による前記カップルドノードツリーを用いた最短一致検索は、前記最長一致検索キーのかわりに最短一致検索キーを用いる以外は上記と同様の検索および差分ビット位置の取得と、前記差分ビット位置がビット列の最上位以外の位置のときの、記憶された前記経路を参照した最短一致ノードの設定であって、前記経路が、前記ルートノードと、該ルートノードのリンク先の前記ノード対の一方の前記ブランチノードである第一のノードとを含み、前記ルートノードの前記弁別ビット位置が前記差分ビット位置よりも上位の位置の場合は、前記ブランチノードの次に記憶されたノードとノード対を構成するノードを前記最短一致ノードとして設定する最短一致ノードの設定により実現される。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００５７
【補正方法】変更
【補正の内容】
【００５７】
図３は、本発明を実施するためのハードウェア構成例を説明する図である。
本発明の最長一致／最短一致検索装置による検索処理及びデータメンテナンスは中央処理装置３０２及びキャッシュメモリ３０３を少なくとも備えたデータ処理装置３０１によりデータ格納装置３０８を用いて実施される。カップルドノードツリーが配置される配列３０９と検索中にたどるノードが格納された配列要素の配列番号を記憶する探索経路スタック３１０を有するデータ格納装置３０８は、主記憶装置３０５または外部記憶装置３０６で実現することができ、あるいは通信装置３０７を介して接続された遠方に配置された装置を用いることも可能である。