"N個からなるMbit整数列を、基数ソートを用いて並び替えを行う際のデータ量を削減するためのソート時のキー削減方法であって、ソート処理手段が、入力された並び替え対象の整数列を部分ソート列記憶手段に格納し、基数ソート実行手段が、入力された並び替え対象の整数列の上位Kビットを対象として、前記ソート処理手段から指定された上位Kビットのビット位置の出現頻度のヒストグラムを作成し、ヒストグラム記憶手段に格納し、前記ソート処理手段が、前記ヒストグラム記憶手段から読み出した前記ヒストグラムに基づいて、上位Kビットを並び替えた部分ソート列を前記部分ソート列記憶手段に格納する処理をMK但し、M整数対象、K奇数ソートを行う単位回繰り返し、整列済みの整数列を生成することを特徴とするソート時のキー削減方法。N個からなるMbit整数列を、基数ソートを用いて並び替えを行う際のデータ量を削減するためのソート時のキー削減装置であって、ソート処理手段と、基数ソート実行手段と、を有し、前記ソート処理手段は、入力された並び替え対象の整数列を部分ソート列記憶手段に格納する手段と、前記基数ソート実行手段で作成されたヒストグラムに基づいて、上位Kビットを並び替えた部分ソート列を前記部分ソート列記憶手段に格納する処理をMK但し、M整数対象、K基数ソートを行う単位回繰り返し、整列済みの整数列を生成する部分ソート列生成手段と、を有し、基数ソート実行手段は、入力された並び替え対象の整数列の上位Kビットを対象として、前記ソート処理手段から指定された上位Kビットのビット位置の出現頻度のヒストグラムを作成し、ヒストグラム記憶手段に格納するヒストグラム作成手段を有することを特徴とするソート時のキー削減装置。コンピュータを、請求項2記載のキー削減装置の各手段として機能させるためのキー削減プログラム。しかしながら、上記従来の技術では、MK回の基数ソートを実行する際に、各整数値のMK回の読み出しと、MK回の書き出し処理が発生する。整数値総数をNとした場合、全体でbyteの読み出しと書き出しが発生することになる。そのためセンサ情報や、アクセスログデータなど大規模データ内のM個の整数列を並び替える必要がある時、部分的に並び替えられた整数列を書き出す、もしくは次の並び替えのために読み出すもしくは,書き出すデータ量が非常に大きくなってしまう問題がある。本発明は、上記の点に鑑みなされたもので、基数ソート毎に発生する読み出しと書き出しデータ量の削減を行うことが可能なソート時のキー削減方法及び装置及びプログラムを提供することを目的とする。上記の課題を解決するため、本発明は、N個からなるMbit整数列を、基数ソートを用いて並び替えを行う際のデータ量を削減するためのソート時のキー削減方法であって、ソート処理手段が、入力された並び替え対象の整数列を部分ソート列記憶手段に格納し、基数ソート実行手段が、入力された並び替え対象の整数列の上位Kビットを対象として、前記ソート処理手段から指定された上位Kビットのビット位置の出現頻度のヒストグラムを作成し、ヒストグラム記憶手段に格納し、前記ソート処理手段が、前記ヒストグラム記憶手段から読み出した前記ヒストグラムをに基づいて、上位Kビットを並び替えた部分ソート列を前記部分ソート列記憶手段に格納する処理をMK但し、M整数対象、K基数ソートを行う単位回繰り返し、整列済みの整数列を生成する。上記のように本発明によれば、各領域における並び替え済みの上位dKbitを共通化することで並び替え中に発生する読み込みもしくは,書き込み整数値のデータ量を削減することが可能となる。以下図面と共に、本発明の実施の形態を説明する。図4は、本発明の一実施の形態におけるキー削減装置の構成を示す。同図に示すキー削減装置10は、整数列入力装置1、パラメータK入力装置2、結果出力装置3に接続されている。キー削減装置10は、ソート処理部11、基数ソート実行部12、部分ソート列記憶部13、ヒストグラム記憶部14から構成される。部分ソート列記憶部13、ヒストグラム記憶部14は、ハードディスク装置やメモリ等の記憶媒体である。上記の構成において、まず、ソート処理部11は、入力値として整数列入力装置1とパラメータK入力装置2から値を受け取り、入力された並び替え対象の整数列を部分ソート列記憶部13に記録する。そして、基数ソート実行部12は、入力された整数列の上位Kbitを対象に上位Kbitの出現頻度のヒストグラムを作成し、ヒストグラム記憶部14に記録する。そして、ソート処理部11では、作成されたヒストグラムをもとに上位Kbitを並び替えた部分ソート列を部分ソート列記憶部13に再度書き出す。この処理をMK回繰り返すことで、整列済みの整数列を作成し、最終的に結果出力装置3に出力する。以下に、各処理部の動作を説明する。ソート処理部11は、整数列入力装置1から整列対象整数列、パラメータK入力装置2からパラメータKを取得する。入力された整数列を基数ソート実行部12を利用しながら上位Kbitずつ並び替えを実施する。上位bitを部分的に並び替えられた中間整数列は部分ソート列記憶部13に記憶しながら並び替えを実施し、整列結果整数列を結果出力装置3に出力する。基数ソート実行部12は、ソート処理部11からヒストグラム作成対象のbit位置が入力され、整数列入力装置1から整数列が入力されると、指定されたbit位置の出現頻度を数え上げ、ヒストグラムを作成し、ヒストグラム記憶部14に書き出す。以下に、ソート処理部11の詳細な動作を説明する。図5は、本発明の一実施の形態におけるソート処理部の動作のフローチャートである。ステップ500ソート処理部11は、パラメータK入力装置2から入力があるまで待機し、パラメータKを設定する。ステップ505整数列入力装置2から入力があるまで待機する。ステップ510整数列入力装置2からN個の整数列が入力されると、当該整数列を部分ソート列記憶部2に記録する。ステップ515d並び替え済み上位ビットを値1で初期化する。ステップ520上位のKbitからKbitを対象に基数ソート実行部12を実行するため、dとN個の整数列を基数ソート実行部12に渡すことで処理を実行させる。ステップ525基数ソート実行部12がヒストグラム作成処理を行う詳細については図6にて後述する。ステップ530基数ソート実行部12で作成されたヒストグラムをヒストグラム記憶部14から読み出し、参照することで上位dKbitが並び替えられた整数列を生成する。ステップ535iを値1で初期化する。ステップ540並び替え済み上位ビットを示すdと、並び替え対象整数の総数を取得し、並び替え済みの上位dKbitの値を共通化する上位dKbitの共通化処理を行い、内部の各整数値のデータ量を削減する図8。当該処理の詳細は図7にて後述する。ステップ545iに1を加算し、i≦2Kになるまでステップ540を繰り返す。ステップ550dに1を加算し、d≦MKであればステップ555に移行し、dMKであればステップ520に戻る。ステップ555部分ソート列記憶部13から整列された結果整数列を読み出し、結果出力装置3に出力する。次に、基数ソート実行部12の処理を説明する。図6は、本発明の一実施の形態における基数ソート実行部の動作のフローチャートである。ステップ600基数ソート実行部12は、ソート処理部11からヒストグラム対象の整数内bit列位置を示すdの値を受け取る。ステップ605入力された整数の出現頻度のヒストグラムを作成するために、2K個のエントリを持つヒストグラムを初期化する。ステップ610jを値1で初期化する。ステップ615j番目の整数列の上位KbitからKbitを抜き出す。ステップ620抜き出されたKbitの値に対応するヒストグラムのカウント値に1を加算する。ステップ625ステップ620で作成されたヒストグラムをヒストグラム記憶部14に記録する。次に、図5のステップ540の上位dKbitの共通化処理について説明する。図7は、本発明の一実施の形態における図5のS540の詳細な動作のフローチャートである。ステップ700ソート処理部11は、ステップ520でソートされた並び替え済み上位ビットを示すdと、並び替え対象整数の総数Aを入力値として受け取る。ステップ705共通値である上位bitをメモリの共通化領域内のヘッダに格納する。格納された状態を図8に示す。このとき、整数値はまだ格納されていない状態である。ステップ710jを値1で初期化する。ステップ715j番目の整数と、先頭に共通値、その後続に共通値を削除した整数が連結されたデータ列を取得し、j番目の整数の上位bitを削除し、連結したデータ列の後続に加える。jに1を加算し、j>Aであれば当該ステップの処理を繰り返し、j≦Aであればステップ720に移行する。ステップ720連結したデータ列を部分ソート列記憶部13に記憶する。上述のように、本発明は、各領域図3における太枠四角内における並び替え済みの上位dKbitを共通化することで並び替え中に発生する読み込みもしくは、書き込み整数値のデータ量を削減することに特徴がある。共通化された上位dKbitは、図8に示すように、各部分領域の先頭にあるヘッダに格納する。部分的に並び替えられた整数列を書き出す際には、この削減された整数値を用いて並び替えを実施し、最終的な整列整数値を書き出す際に、ヘッダに格納された共通値を利用して元の値を復元する。このように並び替え済みの値を共通化することで、並び替え済みbit長が大きくなるにつれて、並び替え対象の各整数値のデータ量が削減され、結果としてこれらの値を読み書きするために必要なデータ総量が減少する。このように、本発明を適用することで、基数ソート毎に発生する読み出しと書き出しデータ量の削減効果が得られる。入力整数の総数をN,整数のbit長をM,基数ソートを行うbit長をKとする。1回目の基数ソートで読み込まれるデータ量はbyte、書き出されるデータ量は並び替え済みの上位Kbitを除去した8byteとなる。実際には共通化された各整数値から除去された並び替え済みのKbitを各領域のヘッダに保存するための書き出しデータ量αが存在するが、Nが大きい場合にαは非常に小さくなるため、これ以降では無視して説明を行う。続けて2回目の基数ソートで読み込まれるデータ量は8byteで、書き出されるデータ量は8byteとなる。そしてMK回目の書き出し処理で各共通領域のヘッダに存在する値を利用して元値を復元して並び替えを終了する。最終的に読み出しと書き出しのデータ総量はとなる。以下に具体的に説明する。例えば、232個の32bit整数を4bit毎に基数ソートする場合を考える。従来の手法では、この整数列に対して通常の基数ソートを実行する場合、232個の32bit整数全体を8回読み書きする必要があり、その総サイズは128GiBとなる。一方、本発明の場合は、ソート済みのbit列を共通化することで、必要な読み書きの総数が72GiBとなり、結果的に56GiBの節約が可能になる。なお、図4に示すキー削減装置の構成要素の図5~7に示す動作をプログラムとして構築し、キー削減装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更応用が可能である。"