【手続補正書】
【提出日】平成22年2月22日(2010.2.22)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対、からなるビット列検索に用いるツリーであって、
前記ルートノードは、ツリーの始点を表すノードであって、該ツリーのノードが１つのときは前記リーフノード、ツリーのノードが２つ以上のときは前記ブランチノードであり、
前記ブランチノードは、ビット列検索を行うための検索キーの弁別ビット位置と、リンク先のノード対の一方のノードである代表ノードの位置を示す位置情報を含み、
前記リーフノードは、検索対象のビット列からなるインデックスキーを含む、カップルドノードツリーのデータ構造に基づいてコンピュータが前記インデックスキーを検索するビット列検索方法において、
前記インデックスキーは、有意ビットのみからなるビット列、ビットの値を問わないドントケアビットのみからなるビット列、または１ビット以上の有意ビットに１ビット以上のドントケアビットが連なるビット列のいずれかである、前方有意ビット列を符号化した符号化ビット列からなり、
前記検索キーは、前方有意ビット列を符号化した符号化ビット列からなり、
前記符号化ビット列は、前記前方有意ビット列を構成する各ビットに対応するビット対であって、該ビットがドントケアビットであるか有意ビットであるかを示す識別ビットと、該ビットがドントケアビットの場合は予め決められた値であり、該ビットが有意ビットの場合は該ビットの値を示すデータビットとのビット対からなるビット列であり、
前記ビット列検索方法が、
前記カップルドノードツリーの任意の部分木のルートノードを検索開始ノードとして、前記ブランチノードにおいて該ブランチノードに含まれる弁別ビット位置の前記検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいは該代表ノードと対になる非代表ノードにリンクすることを、前記符号化ビット列において識別ビットが存在する位置に前記弁別ビット位置が相当するブランチノードのアドレス情報を少なくとも記憶することにより、リンクしてたどった経路を記憶しながら、前記リーフノードに至るまで順次繰り返す初期検索ステップと、
前記初期検索ステップで到達した前記リーフノードからインデックスキーを取得するインデックスキー取得ステップと、
前記取得した前記インデックスキーと前記検索キーとの間で、ビット列の先頭から、前記取得した前記インデックスキーにおける、末尾の有意ビットを符号化したビット対の位置と、前記検索キーにおける、先頭のドントケアビットを符号化したビット対の位置のうち、いずれか前記符号化ビット列の先頭に近いビット位置までの範囲でビット列比較し、異なるビット値となる先頭のビット位置を差分ビット位置として取得する差分ビット位置取得ステップと、
前記取得した前記インデックスキーと前記検索キーとが、前記範囲において一致するならば、前記取得した前記インデックスキーを、最長一致キーとして取得する第１の最長一致キー取得ステップと、
前記比較の結果、前記取得した前記インデックスキーと前記検索キーとが一致しないならば、前記符号化ビット列において識別ビットが存在する位置に弁別ビット位置が相当するとともに該弁別ビット位置が前記差分ビット位置よりも前記符号化ビット列の先頭に近いビット位置の、前記経路上のブランチノードのうち、前記弁別ビット位置が前記符号化ビット列の末尾に最も近いビット位置であるブランチノードを選択するブランチノード選択ステップと、
前記選択した前記ブランチノードからリンクされるノード対のうち、前記ドントケアビットを示す前記識別ビットの値に対応してリンクされるリーフノードである終端側ノードに含まれるインデックスキーを最長一致キーとして取得する第２の最長一致キー取得ステップと、
を備えることを特徴とするビット列検索方法。
【請求項２】
前記リーフノードの前記インデックスキーが、前記符号化ビット列のかわりに符号化前の前記前方有意ビット列からなり、
前記差分ビット位置取得ステップ及び前記第１の最長一致キー取得ステップでは、前記取得した前記インデックスキーのかわりに、前記取得した前記インデックスキーを符号化した符号化ビット列を前記検索キーと比較する、
ことを特徴とする請求項１記載のビット列検索方法。
【請求項３】
前記初期検索ステップにおいて前記経路を記憶する際、前記ブランチノードの前記位置情報に加えて、該ブランチノードからリンクされるノード対のうち、前記有意ビットを示す前記識別ビットの値に対応してリンクされるノードである非終端側ノードの位置を示す位置情報も記憶することを特徴とする請求項１記載のビット列検索方法。
【請求項４】
前記第２の最長一致キー取得ステップにおいて、記憶された前記非終端側ノードの前記位置情報から、該非終端側ノードとノード対をなす前記終端側ノードの位置情報を求めることを特徴とする請求項３記載のビット列検索方法。
【請求項５】
前記経路はスタックに記憶されることを特徴とする請求項１記載のビット列検索方法。
【請求項６】
前記カップルドノードツリーは配列に記憶され、前記ブランチノードに含まれる前記位置情報は、該位置情報に対応する前記代表ノードが格納された前記配列の配列要素の配列番号であることを特徴とする請求項１記載のビット列検索方法。
【請求項７】
ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対、からなるビット列検索に用いるツリーであって、
前記ルートノードは、ツリーの始点を表すノードであって、該ツリーのノードが１つのときは前記リーフノード、ツリーのノードが２つ以上のときは前記ブランチノードであり、
前記ブランチノードは、ビット列検索を行うための検索キーの弁別ビット位置と、リンク先のノード対の一方のノードである代表ノードの位置を示す位置情報を含み、
前記リーフノードは、検索対象のビット列からなるインデックスキーを含む、カップルドノードツリーに、
所望のビット列からなるインデックスキーを含むリーフノードをコンピュータが挿入する挿入方法において、
前記インデックスキーは、有意ビットのみからなるビット列、ビットの値を問わないドントケアビットのみからなるビット列、または１ビット以上の有意ビットに１ビット以上のドントケアビットが連なるビット列のいずれかである、前方有意ビット列を符号化した符号化ビット列からなり、
前記検索キーは、前方有意ビット列を符号化した符号化ビット列からなり、
前記符号化ビット列は、前記前方有意ビット列を構成する各ビットに対応するビット対であって、該ビットがドントケアビットであるか有意ビットであるかを示す識別ビットと、該ビットがドントケアビットの場合は予め決められた値であり、該ビットが有意ビットの場合は該ビットの値を示すデータビットとのビット対からなるビット列であり、
符号化ビット列である前記所望のビット列は、符号化ビット列または符号化される前の前方有意ビット列の形式で指定され、
前記挿入方法が、
前記符号化ビット列によって前記所望のビット列が指定された場合は、指定された該符号化ビット列を検索キーとし、
前記前方有意ビット列によって前記所望のビット列が指定された場合は、指定された前記前方有意ビット列を符号化して符号化ビット列を取得し、取得した該符号化ビット列を検索キーとし、
前記ブランチノードにおいて該ブランチノードに含まれる弁別ビット位置の前記検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいは該代表ノードと対になる非代表ノードにリンクすることを、前記ルートノードから順次前記リーフノードに至るまで経路を記憶しながら繰り返し、
前記リーフノードのインデックスキーと前記検索キーとの間で、大小比較とビット列比較を行い、
前記ビット列比較で異なるビット値となる先頭のビット位置である差分ビット位置と、前記経路上のブランチノードの弁別ビット位置との相対的位置関係により、挿入される前記リーフノードともう一方のノードからなるノード対の挿入位置を決定し、
前記所望のビット列からなるインデックスキーを含む前記リーフノードを、挿入される前記ノード対のどちらのノードとするかを、前記大小関係により決定する、
ことを含む方法であることを特徴とする挿入方法。
【請求項８】
前記リーフノードの前記インデックスキーが、前記符号化ビット列のかわりに前記前方有意ビット列からなり、
前記大小比較と前記ビット列比較の前に前記インデックスキーを符号化して符号化ビット列を取得し、前記リーフノードのインデックスキーと前記検索キーとの間で前記大小比較と前記ビット列比較を行うかわりに、取得した前記符号化ビット列と前記検索キーとの間で前記大小比較と前記ビット列比較を行う、
ことを特徴とする請求項７記載の挿入方法。
【請求項９】
前記カップルドノードツリーは配列に記憶され、前記ブランチノードに含まれる前記位置情報は、該位置情報に対応する前記代表ノードが格納された前記配列の配列要素の配列番号であることを特徴とする請求項７記載の挿入方法。
【請求項１０】
ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対、からなるビット列検索に用いるツリーであって、
前記ルートノードは、ツリーの始点を表すノードであって、該ツリーのノードが１つのときは前記リーフノード、ツリーのノードが２つ以上のときは前記ブランチノードであり、
前記ブランチノードは、ビット列検索を行うための検索キーの弁別ビット位置と、リンク先のノード対の一方のノードである代表ノードの位置を示す位置情報を含み、
前記リーフノードは、検索対象のビット列からなるインデックスキーを含む、カップルドノードツリーから、
所望のビット列からなるインデックスキーを含むリーフノードをコンピュータが削除する削除方法において、
前記インデックスキーは、有意ビットのみからなるビット列、ビットの値を問わないドントケアビットのみからなるビット列、または１ビット以上の有意ビットに１ビット以上のドントケアビットが連なるビット列のいずれかである、前方有意ビット列を符号化した符号化ビット列からなり、
前記検索キーは、前方有意ビット列を符号化した符号化ビット列からなり、
前記符号化ビット列は、前記前方有意ビット列を構成する各ビットに対応するビット対であって、該ビットがドントケアビットであるか有意ビットであるかを示す識別ビットと、該ビットがドントケアビットの場合は予め決められた値であり、該ビットが有意ビットの場合は該ビットの値を示すデータビットとのビット対からなるビット列であり、
符号化ビット列である前記所望のビット列は、符号化ビット列または符号化される前の前方有意ビット列の形式で指定され、
前記削除方法が、
前記符号化ビット列によって前記所望のビット列が指定された場合は、指定された該符号化ビット列を検索キーとし、
前記前方有意ビット列によって前記所望のビット列が指定された場合は、指定された前記前方有意ビット列を符号化して符号化ビット列を取得し、取得した該符号化ビット列を検索キーとし、
前記ブランチノードにおいて該ブランチノードに含まれる弁別ビット位置の前記検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいは該代表ノードと対になる非代表ノードにリンクすることを、前記ルートノードから順次前記リーフノードに至るまで繰り返し、
前記リーフノードとノード対をなすノードの内容を、当該ノード対のリンク元のブランチノードに格納し、
当該ノード対を削除する、
ことを含む方法であることを特徴とする削除方法。
【請求項１１】
前記リーフノードの前記インデックスキーが、前記符号化ビット列のかわりに前記前方有意ビット列からなることを特徴とする請求項１０記載の削除方法。
【請求項１２】
前記カップルドノードツリーは配列に記憶され、前記ブランチノードに含まれる前記位置情報は、該位置情報に対応する前記代表ノードが格納された前記配列の配列要素の配列番号であることを特徴とする請求項１０記載の削除方法。
【請求項１３】
請求項１〜６いずれか１項記載のビット列検索方法をコンピュータに実行させるためのプログラム。
【請求項１４】
請求項７〜９いずれか１項記載の挿入方法をコンピュータに実行させるためのプログラム。
【請求項１５】
請求項１０〜１２いずれか１項記載の削除方法をコンピュータに実行させるためのプログラム。
【請求項１６】
請求項１３〜１５いずれか１項記載のプログラムを記憶したことを特徴とするコンピュータ読み取り可能な記憶媒体。
【請求項１７】
ビット列検索に用いるツリー状のデータ構造であって、
ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対、からなるビット列検索に用いるツリーであって、
前記ルートノードは、ツリーの始点を表すノードであって、該ツリーのノードが１つのときは前記リーフノード、ツリーのノードが２つ以上のときは前記ブランチノードであり、
前記ブランチノードは、ビット列検索を行うための検索キーの弁別ビット位置と、リンク先のノード対の一方のノードである代表ノードの位置を示す位置情報を含み、
前記リーフノードは、検索対象のビット列からなるインデックスキーを含み、
前記インデックスキーは、有意ビットのみからなるビット列、ビットの値を問わないドントケアビットのみからなるビット列、もしくは１ビット以上の有意ビットに１ビット以上のドントケアビットが連なるビット列のいずれかである、前方有意ビット列、または該前方有意ビット列を符号化した符号化ビット列からなり、
前記検索キーは、前方有意ビット列を符号化した符号化ビット列からなり、
前記符号化ビット列は、前記前方有意ビット列を構成する各ビットに対応するビット対であって、該ビットがドントケアビットであるか有意ビットであるかを示す識別ビットと、該ビットがドントケアビットの場合は予め決められた値であり、該ビットが有意ビットの場合は該ビットの値を示すデータビットとのビット対からなるビット列であり、
コンピュータが、任意のノードを検索開始ノードとして、前記ブランチノードにおいて該ブランチノードに含まれる弁別ビット位置の前記検索キーのビット値に応じてリンク先のノード対の代表ノードかあるいは該代表ノードと対になる非代表ノードにリンクすることを順次前記リーフノードに至るまで繰り返すことにより、前記検索キーによる検索の実行を可能とすることを特徴とするデータ構造。
【請求項１８】
前記データ構造は配列に記憶され、前記ブランチノードが含む前記位置情報は、該位置情報に対応する前記代表ノードが格納された前記配列の配列要素の配列番号であることを特徴とする請求項１７記載のデータ構造。
【請求項１９】
請求項１７又は請求項１８記載のデータ構造を記憶したことを特徴とするコンピュータ読み取り可能な記憶媒体。
【請求項２０】
ビット列検索装置において、
ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対、からなるビット列検索に用いるツリーであって、前記ルートノードは、ツリーの始点を表すノードであって、該ツリーのノードが１つのときは前記リーフノード、ツリーのノードが２つ以上のときは前記ブランチノードであり、前記ブランチノードは、ビット列検索を行うための検索キーの弁別ビット位置と、リンク先のノード対の一方のノードである代表ノードの位置を示す位置情報を含み、前記リーフノードは、検索対象のビット列からなるインデックスキーを含む、カップルドノードツリーであって、
前記インデックスキーは、有意ビットのみからなるビット列、ビットの値を問わないドントケアビットのみからなるビット列、または１ビット以上の有意ビットに１ビット以上のドントケアビットが連なるビット列のいずれかである、前方有意ビット列を符号化した符号化ビット列からなり、
前記符号化ビット列は、前記前方有意ビット列を構成する各ビットに対応するビット対であって、該ビットがドントケアビットであるか有意ビットであるかを示す識別ビットと、該ビットがドントケアビットの場合は予め決められた値であり、該ビットが有意ビットの場合は該ビットの値を示すデータビットとのビット対からなるビット列であるカップルドノードツリーと、
前記カップルドノードツリーの任意の部分木のルートノードを検索開始ノードとして、前記ブランチノードにおいて、前方有意ビット列を符号化した符号化ビット列からなる前記検索キーの該ブランチノードに含まれる弁別ビット位置のビット値に応じてリンク先のノード対の代表ノードかあるいは該代表ノードと対になる非代表ノードにリンクすることを、前記符号化ビット列において識別ビットが存在する位置に前記弁別ビット位置が相当するブランチノードのアドレス情報を少なくとも記憶することにより、リンクしてたどった経路を記憶しながら、前記リーフノードに至るまで順次繰り返す初期検索手段と、
前記初期検索手段により到達した前記リーフノードからインデックスキーを取得するインデックスキー取得手段と、
前記取得した前記インデックスキーと前記検索キーとの間で、ビット列の先頭から、前記取得した前記インデックスキーにおける、末尾の有意ビットを符号化したビット対の位置と、前記検索キーにおける、先頭のドントケアビットを符号化したビット対の位置のうち、いずれか前記符号化ビット列の先頭に近いビット位置までの範囲でビット列比較し、異なるビット値となる先頭のビット位置を差分ビット位置として取得する差分ビット位置取得手段と、
前記取得した前記インデックスキーと前記検索キーとが、前記範囲において一致するならば、前記取得した前記インデックスキーを、最長一致キーとして取得する第１の最長一致キー取得手段と、
前記比較の結果、前記取得した前記インデックスキーと前記検索キーとが一致しないならば、前記符号化ビット列において識別ビットが存在する位置に弁別ビット位置が相当するとともに該弁別ビット位置が前記差分ビット位置よりも前記符号化ビット列の先頭に近いビット位置の、前記経路上のブランチノードのうち、前記弁別ビット位置が前記符号化ビット列の末尾に最も近いビット位置であるブランチノードを選択するブランチノード選択手段と、
前記選択した前記ブランチノードからリンクされるノード対のうち、前記ドントケアビットを示す前記識別ビットの値に対応してリンクされるリーフノードである終端側ノードに含まれるインデックスキーを最長一致キーとして取得する第２の最長一致キー取得手段と、
を備えることを特徴とするビット列検索装置。
【請求項２１】
前記リーフノードの前記インデックスキーが、前記符号化ビット列のかわりに符号化前の前記前方有意ビット列からなり、
前記差分ビット位置取得手段及び前記第１の最長一致キー取得手段は、前記取得した前記インデックスキーのかわりに、前記取得した前記インデックスキーを符号化した符号化ビット列を前記検索キーと比較する、
ことを特徴とする請求項２０記載のビット列検索装置。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】発明の名称
【補正方法】変更
【補正の内容】
【発明の名称】ビット列検索装置、検索方法及びプログラム
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００９３
【補正方法】変更
【補正の内容】
【００９３】
図４は、本出願人による出願である上記特願２００６−２９３６１９で提案されたビット列検索の基本動作を示したフローチャートである。
まず、ステップＳ４０１で、検索開始ノードの配列番号を取得する。取得された配列番号に対応する配列要素は、カップルドノードツリーを構成する任意のノードを格納したものである。検索開始ノードの指定は、後述の各種応用検索において行われる。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０１０６
【補正方法】変更
【補正の内容】
【０１０６】
そして、図４の検索において記憶された探索経路スタックを遡り、弁別ビット位置が差分ビット位置よりも上位にあるブランチノードのうち、弁別ビット位置が最下位のブランチノードの配列番号の次に探索経路スタックに記憶された配列番号のノードを最長一致ノードとして取得する。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】０１９４
【補正方法】変更
【補正の内容】
【０１９４】
続いてステップＳ８１１で、ステップＳ８０６で取り出した弁別ビット位置が偶数か否かを判定する。
本実施形態の符号化によれば、符号化ビット列における偶数のビット位置にあるビットは識別ビットであり、奇数のビット位置にあるビットはデータビットである。よって、ステップＳ８１１の判定が偶数の場合、識別ビットが、該識別ビットを含むビット対が有意ビットを符号化して得られたか否かの判定のためにステップＳ８１２に進み、ステップＳ８０７で取り出したビット値が１か否かを判定する。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】０２０７
【補正方法】変更
【補正の内容】
【０２０７】
次に図９のフローチャートを参照して、差分ビット位置を求める図６のステップＳ６０４の処理の詳細を説明する。
ステップＳ９０１で、比較ビット長を設定する。比較ビット長に設定する値は、検索キー中の、元検索キーの最上位のドントケアビットを符号化したビット対の位置と、図６のステップＳ６０３で得られたインデックスキー中の、元インデックスキーの最下位の有意ビットを符号化したビット対の位置のうち、より上位の位置までの、最上位である０ビット目からの長さである。別の言い方をすれば、比較ビット長は次の（１）〜（３）のように定められる。
（１）  元検索キーに有意ビットが含まれない場合、すなわち元検索キーの０ビット目がドントケアビットの場合は、元検索キーの０ビット目のドントケアビットを符号化したビット対は検索キーの０〜１ビット目である。よって、比較ビット長を２に設定する。
（２）  元検索キーに有意ビットが含まれるが、元インデックスキーに有意ビットが含まれない場合は、比較ビット長を０に設定する。
（３）  元検索キーと元インデックスキーの双方が有意ビットを含む場合は、比較ビット長を次のように定める。