"M個の整数列から任意の整数を探索する処理を高速化するために構造化されたN分木の内部ノードのデータサイズを縮小するためのN分木内部ノードの圧縮装置であって、入力された前記M個の整数列に対してN分木作成を行い、ROOTノードを含む部分木を先頭として、部分木を幅優先に並び替えたN分木の部分木内の分岐判断の数値である比較キーの表現空間を縮退する変換を行い、変換された比較キーを含むブロックを記憶手段に格納する初期化手段と、前記記憶手段から前記ROOTノードを含む前記ブロックを読み出し、入力された前記探索キーを前記初期化手段で行った変換処理と同様の変換処理を行い、変換された探索キーと読み出されたブロックの前記比較キーを比較する処理をリーフノードになるまで繰り返し、リーフノード内に該探索キーと同じ比較キーが存在する場合は、該比較キーに対応する整数列内の位置情報を出力する探索キー処理手段と、を有することを特徴とするN分木内部ノードの圧縮装置。前記初期化手段は、前記N分木を前記ROOTノードから高さHずつの部分木に分解し、幅優先に並び替え、該部分木内の比較キーの表現空間を8×Sビットから8×Tビットに縮退する手段を含む請求項1記載のN分木内部ノードの圧縮装置。前記探索キー処理手段は、前記初期化手段で変換された比較キーを変換するために用いられた情報を利用して、前記探索キーをブロック毎に比較可能な値に変換する手段と、前記探索キーと前記比較キーの比較を行うことにより探索対象の次のブロックを決定する処理を次の部分木に移動しながら目的位置まで探索する手段と、を含む請求項1記載のN分木内部ノードの圧縮装置。前記探索キー処理手段は、前記リーフノード内の比較キーを利用して、最初に探索されたリーフノードが前記探索キーに対応する正しいリーフノードか否かを判定し、正しくない場合には、リーフノードを順に読み込み、位置を補正する手段を含む請求項1または3記載のN分木内部ノードの圧縮装置。M個の整数列から任意の整数を探索する処理を高速化するために構造化されたN分木の内部ノードのデータサイズを縮小するためのN分木内部ノードの圧縮方法であって、初期化手段が、入力された前記M個の整数列に対してN分木作成を行い、ROOTノードを含む部分木を先頭として、部分木を幅優先に並び替えたN分木の部分木内の分岐判断の数値である比較キーの表現空間を縮退する変換を行い、変換された比較キーを含むブロックを記憶手段に格納する初期化ステップと、探索キー処理手段が、前記記憶手段から前記ROOTノードを含む前記ブロックを読み出し、入力された前記探索キーを前記初期化手段で行った変換処理と同様の変換処理を行い、変換された探索キーと読み出されたブロックの前記比較キーを比較する処理をリーフノードになるまで繰り返し、リーフノード内に該探索キーと同じ比較キーが存在する場合は、該比較キーに対応する整数列内の位置情報を出力する探索キー処理ステップと、を行うことを特徴とするN分木内部ノードの圧縮方法。前記初期化ステップにおいて、前記N分木を前記ROOTノードから高さHずつの部分木に分解し、幅優先に並び替え、該部分木内の比較キーの表現空間を8×Sビットから8×Tビットに縮退する請求項5記載のN分木内部ノードの圧縮方法。前記探索キー処理ステップにおいて、前記初期化手段で変換された比較キーを変換するために用いられた情報を利用して、前記探索キーをブロック毎に比較可能な値に変換し、前記探索キーと前記比較キーの比較を行うことにより探索対象の次のブロックを決定する処理を次の部分木に移動しながら目的位置まで探索する請求項5記載のN分木内部ノードの圧縮方法。前記探索キー処理ステップにおいて、前記リーフノード内の比較キーを利用して、最初に探索されたリーフノードが前記探索キーに対応する正しいリーフノードか否かを判定し、正しくない場合には、リーフノードを順に読み込み、位置を補正する請求項5または7記載のN分木内部ノードの圧縮方法。請求項1乃至4のいずれか1項に記載のN分木内部ノードの圧縮装置を構成する各手段としてコンピュータを機能させるためのプログラム。M個の整数列に対してN分木を構成した場合、N分木の高さはで表され、N分木内部ノード内の総比較キー数Nkeyは初項N1で、公比Nの等比級数となり、になる。N分木内部ノードの比較キーのデータサイズは、前述の従来技術の非特許文献1,2、特許文献2においては、N分木を構成する整数列と同じデータサイズこのデータサイズをSバイトとするになるため、整数列のデータサイズが4バイトS4の場合は、内部ノードの総サイズはNkey×4バイトになり、8バイトS8の場合は、Nkey×8バイトになる。このN分木の総ノードサイズは、整数列が少ないMが小場合には問題にならないが、センサ情報や、アクセスログデータなど大規模データ内の整数列に対するN分木を構成する際、N分木の内部ノードサイズが非常に大きくなる問題がある。本発明は、上記の点に鑑みなされたもので、1つの比較キーN分木のノードに設定される分岐判断の数値のサイズを小さくすることが可能なN分木内部ノードの圧縮方法及び装置及びプログラムを提供することを目的とする。上記の課題を解決するため、本発明は、M個の整数列から任意の整数を探索する処理を高速化するために構造化されたN分木の内部ノードのデータサイズを縮小するためのN分木内部ノードの圧縮装置であって、入力された前記M個の整数列に対してN分木作成を行い、ROOTノードを含む部分木を先頭として、部分木を幅優先に並び替えたN分木の部分木内の分岐判断の数値である比較キーの表現空間を縮退する変換を行い、変換された比較キーを含むブロックを記憶手段に格納する初期化手段と、前記記憶手段から前記ROOTノードを含む前記ブロックを読み出し、入力された前記探索キーを前記初期化手段で行った変換処理と同様の変換処理を行い、変換された探索キーと読み出されたブロックの前記比較キーを比較する処理をリーフノードになるまで繰り返し、リーフノード内に該探索キーと同じ比較キーが存在する場合は、該比較キーに対応する整数列内の位置情報を出力する探索キー処理手段と、を有する。また、上記の初期化手段は、前記N分木を前記ROOTノードから高さHずつの部分木に分解し、幅優先に並び替え、該部分木内の比較キーの表現空間を8×Sビットから8×Tビットに縮退する手段を含む。また、上記の探索キー処理手段は、前記初期化手段で変換された比較キーを変換するために用いられた情報を利用して、前記探索キーをブロック毎に比較可能な値に変換する手段と、前記探索キーと前記比較キーの比較を行うことにより探索対象の次のブロックを決定する処理を次の部分木に移動しながら目的位置まで探索する手段と、を含む。また、上記の探索キー処理手段は、前記リーフノード内の比較キーを利用して、最初に探索されたリーフノードが前記探索キーに対応する正しいリーフノードか否かを判定し、正しくない場合には、リーフノードを順に読み込み、位置を補正する手段を含む。上記にように、N分木内部ノード内の単体比較キーが8×Sビットから、8×Tビットで表現可能となるため、N分木の全内部ノードサイズはNkey×SバイトからNkey×Tバイトとなり、総サイズが約TSメタデータ要の領域は相対的に小さいため無視した場合になる。より具体的には、M個の整数列を4バイトS=4として、Tを1とした場合、N分木の全内部ノードサイズが変換前の約25になる。以下図面と共に、本発明の実施の形態を説明する。図1は、本発明の一実施の形態における装置構成を示す。同図に示す装置は、N分木初期化部10、探索キー処理部20、N分木記憶部30から構成され、N分木初期化部10にはM個の整数列を入力する整数列入力装置1が、探索キー処理部20には探索キーを入力する探索キー入力装置2及び結果出力装置3が接続されている。以下に上記の構成における処理を説明する。N分木初期化部10は、探索キーの高速な処理を行うために、整数列入力装置1から入力されたM個の整数列に対してN分木Nはシステムパラメータ作成を行う。N分木初期化部10では、整数列入力装置1から入力された昇順並び替え済みのN分木対象整数列から従来通りのN分木を作成する。その後、図2に示すように、N分木を高さH毎の部分木に分解し、幅優先で部分木を並び替え、内部の比較キーを昇順に配列配置することでN分木のデータ構造ブロックとする。ブロックに変換する際に、ブロック毎の比較キーの表現空間を8×Sビットから8×TビットTは本発明における任意のパラメータで、S>Tとするに縮退する点が本発明の特徴である。詳細については図7、図8で詳述する。部分木内の比較キー変換処理の具体例として、四則演算を利用して比較キー縮退変換処理の例を図3に示す。探索キー処理部20は、探索キー入力装置2から入力された探索キーが、整数列入力装置1から入力された整数列内に含まれているかどうかを判定し、その位置情報を返す。探索の際に、比較を行う各ブロック内に含まれているメタデータブロック内の比較キーを変換するために利用した情報を利用して、探索キーをそのブロック毎で比較可能な値に変換した後に、ブロック内の比較キーとの比較を行う。探索を行うべき次ブロックの決定を行い、次の部分木に移動しながら、目的位置までの探索処理を行う。探索処理においては、部分木内の比較キーを圧縮する際に発生する異なる比較キーが同一の値に変換されてしまう問題具体例として図4のフローチャートを利用した、この問題の説明を図5に示すに対処する必要表現空間を縮退したことによるペナルティがある。より具体的には、異なる比較キーが同一の値に変換されてしまうことにより、本来探索すべき部分木からのズレが発生する点である。このズレに関しては、図6に示すように、LEAFノードに到着した際に、探索キーと内部の比較キーを比較することで、ズレを修正する処理に加える。次に、N分木初期化部10の詳細な処理を説明する。図7は、本発明の一実施の形態におけるN分木初期化部の処理のフローチャートである。ステップ500整数列入力装置1から昇順のM個の整数列が入力される。ステップ505入力されたM個の整数値に対して、従来技術の方法によりN分木を作成し、通常のN分木のデータ構造を得る。ステップ510ステップ505で得られたN分木を、図2に示すようにROOTノードから順に高さH毎の部分木に分解して、幅優先に並び替える。ステップ515iを値1で初期化する。ステップ520N分木を高さHごとに分解したS個の部分木からi番目の部分木を取り出す。ステップ525部分木内の比較キー変換処理例えば、図4のフローチャートモジュールを利用し、i番目の部分木内に含まれる比較キーを変換してブロック化する。この変換処理において、各部分木内比較キーの表現空間を8×Sビットから8×Tビットに縮退する任意の変換処理を行う。この縮退変換処理の1つの具体例として四則演算を利用した変換手法がある。この手法については後述する。ステップ530ステップ525で変換処理され圧縮されたブロックが入力されると、当該入力されたブロックをFIFOバッファ図示せずに格納する。ステップ535iに1を加算する。ステップ540FIFOバッファ図示せず内の全てのブロックを順に読み出し、N分木記憶部30に格納する。以下に、上記のステップ525の縮退変換処理について図4を用いて説明する。ステップ600N分木初期化部10において、部分木の比較キー集合が入力されると、部分木の比較キーを昇順に以下のように並び替える。V1,V2...,VN1ステップ605比較キー集合内の全ての比較キーを、比較キー内最小値Vminで減算し、x補正項を加算する。補正項xは部分木内の最小値を1に対応付けるために存在し、図3に示すように、比較キーを変換後にgreaterthan比較処理を想定左端の部分木への探索を可能にする。ステップ610比較キー集合内の全ての比較キーVn-Vminxを、Vmax-Vminxで割る。ステップ615比較キー集合内の全ての比較キーに28Tを掛け、小数点以下を切り捨てる。上記のステップ605,610,615までの部分木内の比較キーは、で変換TS,Vnは右辺を四捨五入した値する。ステップ620先頭にメタデータVmin、Vmaxを付与した変換処理後の昇順比較キーをブロックとして出力する。次に、探索キー処理部20の処理を図8のフローチャートに沿って説明する。ステップ700探索キー処理部20は、探索キー入力装置2から探索キーが入力される。ステップ705N分木記憶部30からROOTノードのブロックを読み出す。ステップ710読み出したブロック内に含まれるメタデータブロック内の比較キーを変換するために利用した情報を読み出して、ブロック内の比較キーが変換処理された内容と同じ処理を探索キーに行い、変換処理された探索キーを出力する。ステップ715変換処理された探索キーを利用して、例えば、URLhttpwwwgeocitiesjpmhiroilightabcruby13htmlに示される手法を用いて、ブロック内の比較キーと比較処理を行う。その後、次に読み出すブロックを決定し、N分木記憶部30から次に探索を行うべきブロックを読み出す。次に読み出すブロックがLEAFノードである場合はステップ720に移行する。LEAFブロックで無い場合はステップ710に移行する。ステップ720LEAFノードを含むブロック情報を取得し、N分木内部ノードの比較キーの変換処理図5により発生する探索位置のズレの問題に対処するために、最初に探索されたLEAFノードが探索キーに対応する正しいLEAFノードかどうかをLEAFノード内の比較キーを利用することで判定する。正しくない場合には、本来探索されるべきLEAFノード位置を、LEAFノードを順に読み込むことで図6に示すように補正する。ステップ725LEAFノード内に、探索キーと同じ比較キーを持つものがあるかを調べ、もしある場合は、その比較キーに対応する整数列内のポインタを結果出力装置3に出力する。無い場合には、整数列には探索キーと同じ値を持つもの無しとして出力する。上記のように、本発明では、ROOTノードを含む部分木を先頭として、部分木を幅優先に並び替えた列からN分木の内部データ構造であるブロックに変換する際ステップ520~ステップ535、ブロックごとの比較キーの表現空間を縮退する処理ステップ525を行うことが特徴である。なお、H1としてステップ525の部分木内の比較キー変換処理を行わない場合が従来技術に対応する。本発明のような比較キーの変換を行うことで、探索キーと比較可能な状態で表現空間0~2S-1から0~2T11を縮退させ、比較キーを構成するN分木のノード圧縮を可能とする。なお、上記の図1に示すN分木内部ノード圧縮装置の構成要素の動作をプログラムとして構築し、N分木内部ノード圧縮装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更応用が可能である。"