【手続補正書】
【提出日】平成24年10月23日(2012.10.23)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ビット列からなる分類対象のキーを分類キーとして選択し、該分類キーの値に基づいて複数のブロックに分類するビット列キー分類装置において、
前記分類対象のキーを記憶するキー記憶手段と、
ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対、からなるツリーであって、前記ルートノードは、ツリーの始点を表すノードであって、該ツリーのノードが１つのときは前記リーフノード、ツリーのノードが２つ以上のときは前記ブランチノードであり、前記ブランチノードは、前記分類キーの弁別ビット位置とリンク先のノード対の一方のノードである代表ノードの位置を示す位置情報を含み、前記リーフノードは前記キー記憶手段に記憶されている前記分類キーの位置情報を取得するために用いるキーアクセス情報を含み、
前記ツリーの任意のノードを検索開始ノードとし、前記ブランチノードにおいて、該ブランチノードに含まれる弁別ビット位置の前記分類キーのビット値に応じてリンク先のノード対の代表ノードかあるいはそれと隣接した記憶領域に配置されたノードにリンクすることを順次前記リーフノードに至るまで繰り返すことにより、前記リーフノードに格納されたキーアクセス情報を、前記検索開始ノードをルートノードとする前記ツリーの任意の部分木の前記分類キーによる検索結果とするように構成された分類ツリーを生成する分類ツリー生成手段と、
前記分類対象のキーを分類する複数のブロックの数に応じた前記分類ツリーの最大段数を取得する分類ツリー最大段数取得手段と、
を備え、
前記分類ツリー生成手段は、
前記キー記憶手段から１つのキーを分類キーとして選択して該分類キーの位置情報を取得し、該取得した分類キーの位置情報を取得するために用いる前記キーアクセス情報を含むリーフノードをルートノードとする前記分類ツリーを生成するとともに、前記キーアクセス情報を用いて前記分類キーの位置情報を取得するための情報を格納するキー位置検索表を生成するルートノード生成手段と、
前記キー記憶手段からさらに順次分類対象のキーを分類キーとして選択して該分類キーの位置情報を取得し、前記分類ツリー最大段数取得手段で取得した分類ツリーの最大段数の範囲で、該取得した分類キーの位置情報を取得するために用いる前記キーアクセス情報を含むリーフノードを前記分類ツリーに挿入するとともに、前記キー位置検索表に、前記分類ツリーに挿入されるリーフノードの含まれるキーアクセス情報を用いて前記分類キーの位置情報を取得するための情報を追加して新たなキー位置検索表を生成するか、あるいは、前記キー位置検索表の、既存のリーフノードに含まれるキーアクセス情報を用いて分類キーの位置情報を取得する情報に、前記分類キーとして選択された分類対象のキーの位置情報を取得する情報を追加することにより新たなキー位置検索表を生成する分類キー挿入手段と、を含み、
前記分類対象のキーの全てを前記分類キーとして選択して前記分類ツリーを生成するとともに、該分類ツリーの各リーフノードに含まれるキーアクセス情報を用いて前記分類キーの位置情報を取得する情報を格納する前記キー位置検索表を生成することにより、前記分類対象のキーの全てを、前記各リーフノードに対応する複数のブロックに分類することを特徴とするビット列キー分類装置。
【請求項２】
請求項１記載のビット列キー分類装置において、
前記キー位置検索表は、前記複数のブロックに対応するエントリを有するキー分類表と、前記分類対象のキーに対応するエントリを有するキーリンク表から構成され、
前記キー分類表のエントリは、前記キーリンク表のエントリを指すキー管理ポインタが格納される領域である先頭リンクと末尾リンクを含み、
前記キーリンク表のエントリは、前記対応する分類対象のキーが記憶された前記キー記憶手段の位置情報を指すキー参照ポインタを格納する領域と、前記キー管理ポインタを格納する領域であるリンクを含むものであり、
前記キーアクセス情報は、前記キー分類表のエントリを指す分類参照ポインタであることを特徴とするビット列キー分類装置。
【請求項３】
請求項２記載のビット列キー分類装置において、
前記キー分類表のエントリは、さらに、前記対応するブロックに分類されているキーの最小値を格納する領域である最小値キーと前記対応するブロックに分類されているキーの最大値を格納する領域である最大値キーを含み、
前記ルートノード生成手段は、前記キー記憶手段から１つのキーを分類キーとして選択して読出し、該分類キーの位置情報を取得するとともに、前記キー分類表の空エントリを指す分類参照ポインタを取得し、該分類参照ポインタ含むリーフノードをルートノードとする前記分類ツリーを生成し、さらに、前記キーリンク表の空エントリを指すキー管理ポインタを取得し、該キー管理ポインタを前記取得したキー分類表のエントリの前記先頭リンクと前記末尾リンクに格納し、前記最小値キーと最大値キーに前記読み出した分類キーを格納するとともに、前記取得した位置情報を前記取得したキーリンク表のエントリのキー参照ポインタに格納するものであり、
前記分類キー挿入手段は、前記キー記憶手段からさらに順次分類対象のキーを分類キーとして選択して読み出し、該分類キーの位置情報を取得するとともに、前記ルートノードを検索開始ノードとして前記分類キーによる検索結果である分類参照ポインタを求める検索手段と、
前記キーリンク表の空エントリを指すキー管理ポインタを取得し、該キー管理ポインタの指すキーリンク表のキー参照ポインタに前記検索手段が取得した位置情報を格納するとともに、前記分類参照ポインタの指す前記キー分類表のエントリの末尾リンクの指すキーリンク表のリンクに、前記キー管理ポインタを格納することにより、前記分類参照ポインタを用いて分類キーの位置情報を取得するための情報を前記キー分類表とキーリンク表に追加する第１の分類キー連結手段と
前記キーリンク表の空エントリを指すキー管理ポインタを取得し、該キー管理ポインタの指すキーリンク表のキー参照ポインタに前記検索手段が取得した位置情報を格納するとともに、前記分類参照ポインタの指す前記キー分類表のエントリの末尾リンクの指すキーリンク表のリンクに、前記キー管理ポインタを格納することにより、前記分類参照ポインタを用いて分類キーの位置情報を取得するための情報を前記キー分類表とキーリンク表に追加するとともに、前記分類キーが該分類参照ポインタの指すキー分類表の最小値キーより小さければ、該最小値キーに該分類キーを書き込み、一方、前記分類キーが前記分類参照ポインタの指すキー分類表の最大値キーより大きければ、該最大値キーに該分類キーを書き込む第２の分類キー連結手段と、
前記検索手段が求めた分類参照ポインタの指す前記キー分類表のエントリの最小値キーあるいは最大値キーの一方を検索結果キーとし、該検索結果キーと前記分類キーの間でビット列比較を行い、該ビット列比較で異なるビット値となる先頭のビット位置である差分ビット位置を求め、前記検索手段が前記分類参照ポインタを求めたときのリンク経路のブランチノードの弁別ビット位置と前記差分ビット位置との相対的位置関係により、前記分類キーの位置情報を取得するために用いる分類参照ポインタを含むリーフノードと該リーフノードと対をなすノードからなるノード対を前記分類ツリーに挿入したときに該ノード対のリンク元となるノードの位置情報を該ノード対の挿入位置として決定するノード対挿入位置決定手段と、
前記分類キーの位置情報を取得するために用いる分類参照ポインタを含むリーフノードと対をなすノードの内容を、前記挿入位置のノードの内容とし、該挿入位置のノードのノード種別にはブランチノードを示すものを書き込み、弁別ビット位置には前記差分ビット位置を書き込み、代表ノード番号には、前記ノード対挿入位置決定手段で挿入位置を求めたノード対の代表ノードの位置情報を書き込むことで該ノード対を挿入するノード対挿入手段と、
前記ノード対挿入位置決定手段が決定したノード対の挿入位置に該ノード対を挿入したときに、該挿入位置のノードより下位のリーフノードの段数が前記最大段数を越さないかチェックを行い、前記最大段数を超すリーフノードがあれば、そのリーフノードを含むノード対の直近上位のノードである親ノードをリーフノードとし、前記ノード対を構成するリーフノードそれぞれの分類参照ポインタと、該分類参照ポインタの指す前記キー分類表のデータに基づいて、前記リーフノードとした親ノードの分類参照ポインタを決定するとともに、該分類参照ポインタの指すキー分類表のデータとキーリンク表のデータを更新し、前記ノード対を削除することを、前記挿入位置のノードより下位の全てのリーフノードに対して行うことにより、ノード対を挿入しても前記最大段数を超えないことを保証する処理を行うノード対連結手段と、を含み、
前記読み出された分類キーの値が、前記検索手段が求めた分類参照ポインタの指す前記キー分類表のエントリの最小値キーの値と最大値キーの値の間の範囲のものである場合に、
前記第１の分類キー連結手段が、前記分類参照ポインタを用いて分類キーの位置情報を取得するための情報を前記キー分類表とキーリンク表に追加し、
前記読み出された分類キーの値が、前記検索手段が求めた分類参照ポインタの指す前記キー分類表のエントリの最小値キーの値と最大値キーの値の間の範囲外のものである場合に、
前記ノード対挿入位置決定手段が、前記ノード対のリンク元となるノードの位置情報を該ノード対の挿入位置として決定し、
該決定された挿入位置のノードがリーフノードであって、該リーフノードの段数が前記最大段数のとき、前記第２の分類キー連結手段が、前記分類参照ポインタを用いて分類キーの位置情報を取得するための情報を前記キー分類表とキーリンク表に追加するとともに、前記分類キーが該分類参照ポインタの指すキー分類表の最小値キーより小さければ、該最小値キーに該分類キーを書き込み、一方、前記分類キーが前記分類参照ポインタの指すキー分類表の最大値キーより大きければ、該最大値キーに該分類キーを書き込み、
前記決定された挿入位置のノードがリーフノードであって、該リーフノードの段数が前記最大段数ではないとき、前記ノード対挿入手段が前記ノード対を挿入し、
前記ノード対挿入位置決定手段が決定した挿入位置のノードがブランチノードのとき、前記ノード対連結手段が前記ノード対を挿入しても前記最大段数を超えないことを保証する処理を行い、前記ノード対挿入手段が前記ノード対を挿入する、
ことを特徴とするビット列キー分類装置。
【請求項４】
請求項３記載のビット列キー分類装置において、前記分類ツリーは配列に配置され、前記代表ノードの位置を示す位置情報は、該代表ノードが配置された前記配列の配列要素の配列番号であることを特徴とするビット列キー分類装置。
【請求項５】
請求項１記載のビット列キー分類装置により複数のブロックに分類されたキーをブロック毎に取り出して出力するビット列キー分配装置において、
前記分類ツリーから順次リーフノードを取り出すリーフノード取り出し手段と、
該取り出したリーフノードから、前記キーアクセス情報を読み出し、該キーアクセス情報を用いて前記キー位置検索表からキーの位置情報を取り出し、該キーの位置情報に基づいて該キーを前記キー記憶手段から読み出して出力先に出力する分類キー出力手段と、
を備えることを特徴とするビット列キー分配装置。
【請求項６】
請求項５記載のビット列キー分配装置において、
前記キー位置検索表は、前記複数のブロックに対応するエントリを有するキー分類表と、前記分類対象のキーに対応するエントリを有するキーリンク表から構成され、
前記キー分類表のエントリは、前記キーリンク表のエントリを指すキー管理ポインタが格納される領域である先頭リンクと末尾リンクを含み、
前記キーリンク表のエントリは、前記対応する分類対象のキーが記憶された前記キー記憶手段の位置情報を指すキー参照ポインタを格納する領域と、前記キー管理ポインタを格納する領域であるリンクを含むものであり、
前記キーアクセス情報は、前記キー分類表のエントリを指す分類参照ポインタであることを特徴とするビット列キー分配装置。
【請求項７】
請求項６記載のビット列キー分配装置において、前記分類ツリーは配列に配置され、前記代表ノードの位置を示す位置情報は、該代表ノードが配置された前記配列の配列要素の配列番号であることを特徴とするビット列キー分配装置。
【請求項８】
分類対象のキーを記憶するキー記憶手段を備えたビット列分類装置が、ビット列からなる分類対象のキーを分類キーとして選択し、該分類キーの値に基づいて複数のブロックに分類するビット列キー分類方法において、
前記分類対象のキーを分類する複数のブロックの数に応じた後記分類ツリーの最大段数を取得する分類ツリー最大段数取得ステップと、
ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対、からなるツリーであって、前記ルートノードは、ツリーの始点を表すノードであって、該ツリーのノードが１つのときは前記リーフノード、ツリーのノードが２つ以上のときは前記ブランチノードであり、前記ブランチノードは、前記分類キーの弁別ビット位置とリンク先のノード対の一方のノードである代表ノードの位置を示す位置情報を含み、前記リーフノードは前記キー記憶手段に記憶されている前記分類キーの位置情報を取得するために用いるキーアクセス情報を含み、
前記ツリーの任意のノードを検索開始ノードとし、前記ブランチノードにおいて、該ブランチノードに含まれる弁別ビット位置の前記分類キーのビット値に応じてリンク先のノード対の代表ノードかあるいはそれと隣接した記憶領域に配置されたノードにリンクすることを順次前記リーフノードに至るまで繰り返すことにより、前記リーフノードに格納されたキーアクセス情報を、前記検索開始ノードをルートノードとする前記ツリーの任意の部分木の前記分類キーによる検索結果とするように構成された分類ツリーを生成する分類ツリー生成ステップと、
を備え、
前記分類ツリー生成ステップは、
前記キー記憶手段から１つのキーを分類キーとして選択して該分類キーの位置情報を取得し、該取得した分類キーの位置情報を取得するために用いる前記キーアクセス情報を含むリーフノードをルートノードとする前記分類ツリーを生成するとともに、前記キーアクセス情報を用いて前記分類キーの位置情報を取得するための情報を格納するキー位置検索表を生成するルートノード生成ステップと、
前記キー記憶手段からさらに順次分類対象のキーを分類キーとして選択して該分類キーの位置情報を取得し、前記分類ツリー最大段数取得手段で取得した分類ツリーの最大段数の範囲で、該取得した分類キーの位置情報を取得するために用いる前記キーアクセス情報を含むリーフノードを前記分類ツリーに挿入するとともに、前記キー位置検索表に、前記分類ツリーに挿入されるリーフノードの含まれるキーアクセス情報を用いて前記分類キーの位置情報を取得するための情報を追加して新たなキー位置検索表を生成するか、あるいは、前記キー位置検索表の、既存のリーフノードに含まれるキーアクセス情報を用いて分類キーの位置情報を取得する情報に、前記分類キーとして選択された分類対象のキーの位置情報を取得する情報を追加することにより新たなキー位置検索表を生成する分類キー挿入ステップと、を含み、
前記分類対象のキーの全てを前記分類キーとして選択して前記分類ツリーを生成するとともに、該分類ツリーの各リーフノードに含まれるキーアクセス情報を用いて前記分類キーの位置情報を取得する情報を格納する前記キー位置検索表を生成することにより、前記分類対象のキーの全てを、前記各リーフノードに対応する複数のブロックに分類することを特徴とするビット列キー分類方法。
【請求項９】
請求項８記載のビット列キー分類方法において、
前記キー位置検索表は、前記複数のブロックに対応するエントリを有するキー分類表と、前記分類対象のキーに対応するエントリを有するキーリンク表から構成され、
前記キー分類表のエントリは、前記キーリンク表のエントリを指すキー管理ポインタが格納される領域である先頭リンクと末尾リンクを含み、
前記キーリンク表のエントリは、前記対応する分類対象のキーが記憶された前記キー記憶手段の位置情報を指すキー参照ポインタを格納する領域と、前記キー管理ポインタを格納する領域であるリンクを含むものであり、
前記キーアクセス情報は、前記キー分類表のエントリを指す分類参照ポインタであることを特徴とするビット列キー分類方法。
【請求項１０】
請求項９記載のビット列キー分類方法において、
前記キー分類表のエントリは、さらに、前記対応するブロックに分類されているキーの最小値を格納する領域である最小値キーと前記対応するブロックに分類されているキーの最大値を格納する領域である最大値キーを含み、
前記ルートノード生成ステップは、前記キー記憶手段から１つのキーを分類キーとして選択して読出し、該分類キーの位置情報を取得するとともに、前記キー分類表の空エントリを指す分類参照ポインタを取得し、該分類参照ポインタ含むリーフノードをルートノードとする前記分類ツリーを生成し、さらに、前記キーリンク表の空エントリを指すキー管理ポインタを取得し、該キー管理ポインタを前記取得したキー分類表のエントリの前記先頭リンクと前記末尾リンクに格納し、前記最小値キーと最大値キーに前記読み出した分類キーを格納するとともに、前記取得した位置情報を前記取得したキーリンク表のエントリのキー参照ポインタに格納するものであり、
前記分類キー挿入ステップは、前記キー記憶手段からさらに順次分類対象のキーを分類キーとして選択して読み出し、該分類キーの位置情報を取得するとともに、前記ルートノードを検索開始ノードとして前記分類キーによる検索結果である分類参照ポインタを求める検索ステップと、
前記キーリンク表の空エントリを指すキー管理ポインタを取得し、該キー管理ポインタの指すキーリンク表のキー参照ポインタに前記検索ステップにおいて取得した位置情報を格納するとともに、前記分類参照ポインタの指す前記キー分類表のエントリの末尾リンクの指すキーリンク表のリンクに、前記キー管理ポインタを格納することにより、前記分類参照ポインタを用いて分類キーの位置情報を取得するための情報を前記キー分類表とキーリンク表に追加する第１の分類キー連結ステップと
前記キーリンク表の空エントリを指すキー管理ポインタを取得し、該キー管理ポインタの指すキーリンク表のキー参照ポインタに前記検索ステップにおいて取得した位置情報を格納するとともに、前記分類参照ポインタの指す前記キー分類表のエントリの末尾リンクの指すキーリンク表のリンクに、前記キー管理ポインタを格納することにより、前記分類参照ポインタを用いて分類キーの位置情報を取得するための情報を前記キー分類表とキーリンク表に追加するとともに、前記分類キーが該分類参照ポインタの指すキー分類表の最小値キーより小さければ、該最小値キーに該分類キーを書き込み、一方、前記分類キーが前記分類参照ポインタの指すキー分類表の最大値キーより大きければ、該最大値キーに該分類キーを書き込む第２の分類キー連結ステップと、
前記検索手段ステップにおいて求めた分類参照ポインタの指す前記キー分類表のエントリの最小値キーあるいは最大値キーの一方を検索結果キーとし、該検索結果キーと前記分類キーの間でビット列比較を行い、該ビット列比較で異なるビット値となる先頭のビット位置である差分ビット位置を求め、前記検索ステップにおいて前記分類参照ポインタを求めたときのリンク経路のブランチノードの弁別ビット位置と前記差分ビット位置との相対的位置関係により、前記分類キーの位置情報を取得するために用いる分類参照ポインタを含むリーフノードと該リーフノードと対をなすノードからなるノード対を前記分類ツリーに挿入したときに該ノード対のリンク元となるノードの位置情報を該ノード対の挿入位置として決定するノード対挿入位置決定ステップと、
前記分類キーの位置情報を取得するために用いる分類参照ポインタを含むリーフノードと対をなすノードの内容を、前記挿入位置のノードの内容とし、該挿入位置のノードのノード種別にはブランチノードを示すものを書き込み、弁別ビット位置には前記差分ビット位置を書き込み、代表ノード番号には、前記ノード対挿入位置決定ステップにおいて挿入位置を求めたノード対の代表ノードの位置情報を書き込むことで該ノード対を挿入するノード対挿入ステップと、
前記ノード対挿入位置決定ステップにおいて決定したノード対の挿入位置に該ノード対を挿入したときに、該挿入位置のノードより下位のリーフノードの段数が前記最大段数を越さないかチェックを行い、前記最大段数を超すリーフノードがあれば、そのリーフノードを含むノード対の直近上位のノードである親ノードをリーフノードとし、前記ノード対を構成するリーフノードそれぞれの分類参照ポインタと、該分類参照ポインタの指す前記キー分類表のデータに基づいて、前記リーフノードとした親ノードの分類参照ポインタを決定するとともに、該分類参照ポインタの指すキー分類表のデータとキーリンク表のデータを更新し、前記ノード対を削除することを、前記挿入位置のノードより下位の全てのリーフノードに対して行うことにより、ノード対を挿入しても前記最大段数を超えないことを保証する処理を行うノード対連結ステップと、を含み、
前記読み出された分類キーの値が、前記検索手段が求めた分類参照ポインタの指す前記キー分類表のエントリの最小値キーの値と最大値キーの値の間の範囲のものである場合に、
前記第１の分類キー連結ステップにおいて、前記分類参照ポインタを用いて分類キーの位置情報を取得するための情報を前記キー分類表とキーリンク表に追加し、
前記読み出された分類キーの値が、前記検索手段が求めた分類参照ポインタの指す前記キー分類表のエントリの最小値キーの値と最大値キーの値の間の範囲外のものである場合に、
前記ノード対挿入位置決定ステップにおいて、前記ノード対のリンク元となるノードの位置情報を該ノード対の挿入位置として決定し、
該決定された挿入位置のノードがリーフノードであって、該リーフノードの段数が前記最大段数のとき、前記第２の分類キー連結ステップにおいて、前記分類参照ポインタを用いて分類キーの位置情報を取得するための情報を前記キー分類表とキーリンク表に追加するとともに、前記分類キーが該分類参照ポインタの指すキー分類表の最小値キーより小さければ、該最小値キーに該分類キーを書き込み、一方、前記分類キーが前記分類参照ポインタの指すキー分類表の最大値キーより大きければ、該最大値キーに該分類キーを書き込み、
前記決定された挿入位置のノードがリーフノードであって、該リーフノードの段数が前記最大段数ではないとき、前記ノード対挿入手段が前記ノード対を挿入し、
前記ノード対挿入位置決定ステップにおいて決定した挿入位置のノードがブランチノードのとき、前記ノード対連結ステップにおいて前記ノード対を挿入しても前記最大段数を超えないことを保証する処理を行い、前記ノード対挿入ステップにおいて前記ノード対を挿入する、
ことを特徴とするビット列キー分類方法。
【請求項１１】
請求項１０記載のビット列キー分類方法において、前記分類ツリーは配列に配置され、前記代表ノードの位置を示す位置情報は、該代表ノードが配置された前記配列の配列要素の配列番号であることを特徴とするビット列キー分類方法。
【請求項１２】
ビット列キー分配装置が、請求項１記載のビット列キー分類装置により複数のブロックに分類されたキーをブロック毎に取り出して出力するビット列キー分配方法において、
前記分類ツリーから順次リーフノードを取り出すリーフノード取り出しステップと、
該取り出したリーフノードから、前記キーアクセス情報を読み出し、該キーアクセス情報を用いて前記キー位置検索表からキーの位置情報を取り出し、該キーの位置情報に基づいて該キーを前記キー記憶手段から読み出して出力先に出力する分類キー出力ステップと、
を備えることを特徴とするビット列キー分配方法。
【請求項１３】
請求項１２記載のビット列キー分配方法において、
前記キー位置検索表は、前記複数のブロックに対応するエントリを有するキー分類表と、前記分類対象のキーに対応するエントリを有するキーリンク表から構成され、
前記キー分類表のエントリは、前記キーリンク表のエントリを指すキー管理ポインタが格納される領域である先頭リンクと末尾リンクを含み、
前記キーリンク表のエントリは、前記対応する分類対象のキーが記憶された前記キー記憶手段の位置情報を指すキー参照ポインタを格納する領域と、前記キー管理ポインタを格納する領域であるリンクを含むものであり、
前記キーアクセス情報は、前記キー分類表のエントリを指す分類参照ポインタであることを特徴とするビット列キー分配方法。
【請求項１４】
請求項１３記載のビット列キー分配方法において、前記分類ツリーは配列に配置され、前記代表ノードの位置を示す位置情報は、該代表ノードが配置された前記配列の配列要素の配列番号であることを特徴とするビット列キー分配方法。
【請求項１５】
請求項８〜請求項１１のいずれか１項記載のビット列キー分類方法をコンピュータに実行させることを特徴とするプログラム。
【請求項１６】
請求項８〜請求項１１のいずれか１項記載のビット列キー分類方法をコンピュータに実行させるプログラムを記憶したことを特徴とするコンピュータ読み取り可能な記憶媒体。
【請求項１７】
請求項１２〜請求項１４のいずれか１項記載のビット列キー分配方法をコンピュータに実行させることを特徴とするプログラム。
【請求項１８】
請求項１２〜請求項１４のいずれか１項記載のビット列キー分配方法をコンピュータに実行させるプログラムを記憶したことを特徴とするコンピュータ読み取り可能な記憶媒体。
【請求項１９】
キー記憶手段に記憶され、複数のブロックに分類されたビット列キーを出力先に出力するビット列キー分配装置に用いられるデータ構造において、
ルートノードと、隣接した記憶領域に配置されるブランチノードとリーフノードまたはブランチノード同士またはリーフノード同士のノード対、からなるツリーであって、前記ルートノードは、ツリーの始点を表すノードであって、該ツリーのノードが１つのときは前記リーフノード、ツリーのノードが２つ以上のときは前記ブランチノードであり、前記ブランチノードは、前記分類キーの弁別ビット位置とリンク先のノード対の一方のノードである代表ノードの位置を示す位置情報を含み、前記リーフノードは前記キー記憶手段に記憶されている前記分類キーの位置情報を取得するために用いるキーアクセス情報を含み、
前記ツリーの任意のノードを検索開始ノードとし、前記ブランチノードにおいて、該ブランチノードに含まれる弁別ビット位置の前記分類キーのビット値に応じてリンク先のノード対の代表ノードかあるいはそれと隣接した記憶領域に配置されたノードにリンクすることを順次前記リーフノードに至るまで繰り返すことにより、前記リーフノードに格納されたキーアクセス情報を、前記検索開始ノードをルートノードとする前記ツリーの任意の部分木の前記分類キーによる検索結果とするように構成された分類ツリーと、
前記キーアクセス情報を用いて前記キーの位置情報を取得するための情報を格納するキー位置検索表と、
を備え、
前記ビット列キー分配装置が、前記分類ツリーと前記キー位置検索表により、請求項１２記載のビット列キー分配方法を実行し、複数のブロックに分類されたビット列キーの出力先への出力を可能とすることを特徴とするデータ構造。
【請求項２０】
請求項１９記載のデータ構造において、
前記キー位置検索表は、前記複数のブロックに対応するエントリを有するキー分類表と、前記分類対象のキーに対応するエントリを有するキーリンク表から構成され、前記キー分類表のエントリは、前記キーリンク表のエントリを指すキー管理ポインタが格納される領域である先頭リンクと末尾リンクを含み、前記キーリンク表のエントリは、前記対応する分類対象のキーが記憶された前記キー記憶手段の位置情報を指すキー参照ポインタを格納する領域と、前記キー管理ポインタを格納する領域であるリンクを含み、
前記分類ツリーのリーフノードに含まれる前記キーアクセス情報は、前記キー分類表のエントリを指す分類参照ポインタであり、
前記ビット列キー分配装置が、前記分類ツリー、前記キー分類表及びキーリンク表により、請求項１３記載のビット列キー分配方法を実行し、複数のブロックに分類されたビット列キーの出力先への出力を可能とすることを特徴とするデータ構造。
【請求項２１】
請求項２０記載のデータ構造において、
前記分類ツリーは配列に配置され、前記代表ノードの位置を示す位置情報は、該代表ノードが配置された前記配列の配列要素の配列番号であり、
前記ビット列キー分配装置が、前記分類ツリー、前記キー分類表及びキーリンク表により、請求項１４記載のビット列キー分配方法を実行し、複数のブロックに分類されたビット列キーの出力先への出力を可能とすることを特徴とするデータ構造。
【請求項２２】
請求項１９〜請求項２１のいずれか１項記載のデータ構造を記憶したことを特徴とするコンピュータ読み取り可能な記憶媒体。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００３３
【補正方法】変更
【補正の内容】
【００３３】
図３は、本発明の一実施の形態における分類処理の概念を説明する図である。図３に例示するものは、４つのブロックにキーを分類するものである。したがって、分類ツリーは３段である。本発明によるキーの分類は、弁別ビット位置に基づいて、分類ツリーの第１段目から第２段目へ、第２段目から第３段目へと実行されるため、分類処理としては段数２の分類となる。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００４４
【補正方法】変更
【補正の内容】
【００４４】
図５は、本発明の一実施の形態に係る分類ツリーのツリー構造を概念的に示すとともに、インデックスキーの管理領域を説明する図である。
図５に例示する分類ツリー２００は、図２Ｂに例示するインデックスキーの記憶領域３１１に記憶されたインデックスキーを４つのブロックに分類するためのものである。
図５に示すインデックスキーの管理領域３２０には、キー分類表３２１とキーリンク表３２２が格納されている。キー分類表３２１とキーリンク表で、先に述べたキー位置検索表の例を構成しており、キー分類表３２１のエントリを指す分類参照ポインタは、先に述べたキーアクセス情報の例である。
図５のインデックスキーの管理領域３２０に記載された３７０ｈ等の符号は、図２Ｂのインデックスキーの記憶領域３１１に記載された２７０ｈ等の符号で示すインデックスキー“１０１０１１”等に対応している。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００９８
【補正方法】変更
【補正の内容】
【００９８】
さらにステップＳ８０７において、ステップＳ８０６で得た配列番号の配列要素に、生成するルートノードのノード種別として１（リーフノード)と分類参照ポインタとしてステップＳ８０２で得た分類参照ポインタを書き込み、ステップＳ８０８で、ステップＳ８０５で取得したルートノードの配列番号を登録して処理を終了する。
上述の最初に処理される分類キーがキー２７１ｄとすると、図６Ａに示すリーフノード２１０ｂが、最初に生成されるルートノードとなる。なお、図５に示すキー分類表には分類参照ポインタ２８０ｄの指すエントリは記載されていないが、分類キーを順次挿入していく過程において、当初用いられていたキー分類表のエントリが他のエントリと結合されて用いられなくなる場合がある。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】０１０８
【補正方法】変更
【補正の内容】
【０１０８】
一方、ステップＳ９１６において、分類キーは最大値キーより大きいと判定されると、ステップＳ９１８に進み、インデックスキーに最大値を設定してステップＳ９２０に進む。
また、先に述べたステップＳ９１５において、分類キーは最小値キーより小さいと判定されると、ステップＳ９１９において、インデックスキーに最小値を設定してステップＳ９２０に進む。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】０１５２
【補正方法】変更
【補正の内容】
【０１５２】
次にステップＳ１２０８において、ステップＳ１２０４で求めたリーフノードのキーリンク表に連結したキーと、そのリーフノードと対をなすリーフノードのキーリンク表に連結したキーとに連結するリーフノードを、ステップＳ１２０７で設定した配列番号、すなわち親ノードの配列要素に書き込む。言い換えれば、ステップＳ１２０４で求めたリーフノードの直近上位のブランチノード（親ノード）をリーフノードとし、リーフノードとした親ノードのキーリンク表に、ステップＳ１２０４で求めたリーフノードのキーリンク表に連結したキーと、そのリーフノードと対をなすリーフノードのキーリンク表に連結したキーを連結する。
ステップＳ１２０８の処理の詳細は、後に図１４を参照して説明する。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】０１５３
【補正方法】変更
【補正の内容】
【０１５３】
次にステップＳ１２０８ａにおいて、探索経路カウンタのカウント値を１つ減らし、ステップＳ１２０９に進む。ここで探索経路カウンタのカウント値を１つ減らすのは、上記ステップＳ１２０８の処理で親ノードをリーフノードとしたことにより、リーフノードの段数が１つ減ったからである。この処理により、再度ステップＳ１２０４において最小値検索を行うときの探索経路カウンタのカウント値を、探索経路の段数と一致させることができる。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】０１５４
【補正方法】変更
【補正の内容】
【０１５４】
ステップＳ１２０９では、ステップＳ１２０６で取り出した配列番号あるいはステップＳ１２０７で取り出した配列番号が挿入位置の配列番号であるか判定する。判定の結果、挿入位置の配列番号であれば、挿入位置のノードより下位の全てのリーフノードについての処理が完了しているので、連結処理を終了する。判定の結果、挿入位置の配列番号でなければ、ステップＳ１２１１に進む。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】０１６５
【補正方法】変更
【補正の内容】
【０１６５】
ステップＳ１３０５では、ノード種別はブランチノードのものか判定し、ノード種別がブランチノードのものと判定されると、ステップＳ１３０５ａに進み、探索経路カウンタの値を１つ増やす。次にステップＳ１３０６に進み、ノードから代表ノード番号を取り出し、ステップＳ１３０７で、取り出した代表ノード番号に値０を加算してその結果を新たな配列番号として、ステップＳ１３０２に戻る。
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】０１７６
【補正方法】変更
【補正の内容】
【０１７６】
最後に、ステップＳ１４１４で、Ｓ１４０２で得た代表ノード番号の指すノード対を削除し、ステップＳ１４１５で、Ｓ１４０５で得た１側の分類参照ポインタの指すキー分類表のエントリを削除して処理を終了する。
【手続補正１１】
【補正対象書類名】図面
【補正対象項目名】図１４
【補正方法】変更
【補正の内容】
【図１４】
2011095849.tif 000001