(57)【要約】【課題】配列データを、当該配列データ中の任意の部分を速やかに復元できるように、良好な圧縮効率で圧縮する。【解決手段】配列データVLを複数のブロックに分割し、ブロックに近似関数を設定する。各ブロックkに含まれる各エントリについて、当該エントリの値V_iと、当該エントリの順位iを、当該エントリが含まれるブロックkに設定された近似関数F_kに代入して求まる値F_k (i)との差分値dV_iを求め、差分値dV_iを、当該差分値dV_iを求めたエントリの順位順に配列して当該ブロックkの差分値リストdVL_kを作成する。そして、各ブロックkの近似関数F_kと差分値リストdVL_kのセットとを当該ブロックkのブロックデータBLD_ kとし、各ブロックについて求めたブロックデータBLD_ kの集合を、配列データの圧縮データとする。【選択図】図１
2018046406.tif 000002
【特許請求の範囲】
【請求項１】
値を配列した配列データを圧縮するデータ圧縮方法であって、
前記配列データ複数のブロックに分割する分割ステップと、
前記各ブロックの各々について、当該ブロックのブロックデータを作成し、作成した各ブロックの前記ブロックデータを前記圧縮データに含めるブロックデータ作成ステップとを有し、
当該ブロックデータ作成ステップにおいて、前記ブロックデータを作成するブロックに、当該ブロック内の各値の参照値を表す所定の関数を近似関数として設定し、当該ブロックに含まれる各値について、当該値と、当該ブロックに設定された前記近似関数によって表される参照値との差分を求め、求めた差分を、当該差分を求めた値のブロック内の順序と同じ順序で配列した差分値配列データを作成し、前記設定した近似関数と前記作成した差分配列データとを当該ブロックのブロックデータとして作成することを特徴とするデータ圧縮方法。
【請求項２】
請求項１記載のデータ圧縮方法であって、
前記ブロックデータ作成ステップにおいて、前記近似関数として、各ブロックに、当該ブロック内の各値の近似値を、当該値の参照値として表す関数を設定することを特徴とするデータ圧縮方法。
【請求項３】
請求項１または２記載のデータ圧縮方法であって、
前記ブロックデータ作成ステップにおいて、前記近似関数として、各ブロックに、当該各ブロックの各値と、当該近似関数によって表される当該値の参照値との差分の最大値、もしくは、当該最大値の絶対値が最小となる関数を設定することを特徴とするデータ圧縮方法。
【請求項４】
請求項１、２または３記載のデータ圧縮方法であって、
前記ブロックデータ作成ステップにおいて、前記ブロックに設定する近似関数として、当該ブロック内の各値の前記参照値を、当該値の前記配列データ中の順序、または、当該ブロック内の順序を変数として表す関数を設定することを特徴とするデータ圧縮方法。
【請求項５】
請求項１、２、３または４記載のデータ圧縮方法であって、
前記ブロックデータ作成ステップにおいて、前記各ブロックに前記近似関数として、前記ブロック毎に異なる種類の関数を設定可能であることを特徴とするデータ圧縮方法。
【請求項６】
請求項１、２、３、４または５記載のデータ圧縮方法であって、
前記分割ステップにおいて、
１番目のブロックに含める前記配列データの値を、前記配列データの先頭の値より、当該ブロックに対する当該ブロックの前記ブロックデータの圧縮率が所定レベル以上劣化するまで追加していくことにより、配列データから１番目のブロックを分割し、
２番目以降のブロックに含める前記配列データの値を、前記配列データの一つ前のブロックに含めた最後の値の次の値より、当該ブロックに対する当該ブロックの前記ブロックデータの圧縮率が所定レベル以上劣化するまで追加していくことにより、配列データから２番目以降のブロックを分割することを特徴とするデータ圧縮方法。
【請求項７】
値を配列した配列データを圧縮するデータ圧縮装置であって、
前記配列データ複数のブロックに分割する分割手段と、
前記各ブロックの各々について、当該ブロックのブロックデータを作成し、作成した各ブロックの前記ブロックデータを前記圧縮データに含めるブロックデータ作成手段とを有し、
当該ブロックデータ作成手段は、前記ブロックデータを作成するブロックに、当該ブロック内の各値の参照値を表す所定の関数を近似関数として設定し、当該ブロックに含まれる各値について、当該値と、当該ブロックに設定された前記近似関数によって表される参照値との差分を求め、求めた差分を、当該差分を求めた値のブロック内の順序と同じ順序で配列した差分値配列データを作成し、前記設定した近似関数と前記作成した差分配列データとを当該ブロックのブロックデータとして作成することを特徴とするデータ圧縮装置。
【請求項８】
請求項７記載のデータ圧縮装置であって、
前記ブロックデータ作成手段は、前記近似関数として、各ブロックに、当該ブロック内の各値の近似値を、当該値の参照値として表す関数を設定することを特徴とするデータ圧縮装置。
【請求項９】
請求項７または８記載のデータ圧縮装置であって、
前記ブロックデータ作成手段は、前記近似関数として、各ブロックに、当該各ブロックの各値と、当該近似関数によって表される当該値の参照値との差分の最大値、もしくは、当該最大値の絶対値が最小となる関数を設定することを特徴とするデータ圧縮装置。
【請求項１０】
請求項７、８または９記載のデータ圧縮装置であって、
前記ブロックデータ作成手段は、前記ブロックに設定する近似関数として、当該ブロック内の各値の前記参照値を、当該値の前記配列データ中の順序、または、当該ブロック内の順序を変数として表す関数を設定することを特徴とするデータ圧縮装置。
【請求項１１】
請求項７、８、９または１０記載のデータ圧縮装置であって、
前記ブロックデータ作成手段は、前記各ブロックに前記近似関数として、前記ブロック毎に異なる種類の関数を設定可能であることを特徴とするデータ圧縮装置。
【請求項１２】
請求項７、８、９、１０または１１記載のデータ圧縮装置であって、
前記分割手段は、
１番目のブロックに含める前記配列データの値を、前記配列データの先頭の値より、当該ブロックに対する当該ブロックの前記ブロックデータの圧縮率が所定レベル以上劣化するまで追加していくことにより、配列データから１番目のブロックを分割し、
２番目以降のブロックに含める前記配列データの値を、前記配列データの一つ前のブロックに含めた最後の値の次の値より、当該ブロックに対する当該ブロックの前記ブロックデータの圧縮率が所定レベル以上劣化するまで追加していくことにより、配列データから２番目以降のブロックを分割することを特徴とするデータ圧縮装置。
【請求項１３】
コンピュータによって読み取られ実行されるコンピュータプログラムであって、
前記コンピュータに請求項１、２、３、４、５または６記載のデータ圧縮方法を実行させることを特徴とするコンピュータプログラム。
【請求項１４】
請求項７、８、９、１０、１１または１２記載のデータ圧縮装置と、前記圧縮データを含むデータベースを備えたデータベースシステムであって、
前記配列データの所定部分の値を、前記圧縮データの、当該部分の値が含まれる前記ブロックのブロックデータの前記近似関数が表す当該部分の参照値の各々に、当該ブロックデータの前記差分配列データの当該部分に対応する差分値の各々を、それぞれ加算して算出するデータベース操作手段を有することを特徴とするデータベースシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、主としてデータベースのデータサイズを圧縮する技術に関するものである。
【背景技術】
【０００２】
データベースのデータサイズを圧縮する技術としては、図６ａに示すようなRDB（Relational Database）のテーブルを、図６ｂに示すような当該テーブルのインデックスのセットであるインデックスセットに圧縮する技術が知られている（たとえば、特許文献１）。
【０００３】
ここで、図６ａテーブルは、複数のフィールド（図では、「性別」と「回数」）を持つレコードを行とする表であり、各レコードにはテーブル中の当該レコードの（図では、0から12の）順番を示すレコード番号が付与されている。なお、レコード番号は０から始まる。
【０００４】
また、図６ｂに示すインデックスセットは、図６ａのテーブルのレコードのフィールド毎に設けられたインデックスより構成される。図６ａでは、テーブルのレコードのフィールドは、「性別」と「回数」であるので、「性別」のインデックスと、「回数」のインデックスがインデックスセットに含まれる。
【０００５】
そして、各インデックスは、VNo、VLとを含む。
VLは、対応するテーブルの対応するフィールドの値として用いられている値を所定の基準（たとえば、値の昇順）でソートして各エントリに登録したリストである。
すなわち、たとえば、図６ａに示すテーブルのテーブルデータセットのインデックスセットの「性別」のインデックスであれば、テーブルの「性別」のフィールドに登録されているのはFとMのみであるので、VLは、Fを登録したエントリとMを登録したエントリよりなるリストとなる。
【０００６】
次に、VNoは、対応するテーブルのレコード数と同数のエントリよりなるリストであり、VNoの順位ｎのエントリには、テーブルのレコード番号nのレコードの対応するフィールドの値が登録されているVLのエントリのVL中の順位を示す値が登録される。なお、VNo、VLの順位は０から始まる。
【０００７】
すなわち、たとえば、図６ａに示すテーブルのテーブルデータセットのインデックスセットの「性別」のインデックスであれば、テーブルのレコード番号２のレコードの「性別」のフィールドの値はMであり、Mが登録されているVLのエントリの順位は１であるので、VNoの順位２のエントリには1が登録される。
【０００８】
ここで、このようなインデックスによれば、VNoのエントリ数より、対応するテーブルのレコード数を速やかに求めることができ、VNoとVLより、各レコード番号のレコードの対応するフィールドの値を速やかに求めることができる。
【０００９】
すなわち、たとえば、「性別」のインデックスの、レコード番号２に対応するVNoの順位２のエントリからVLの順位１が求まり、このVLの順位１のエントリにはMが登録されているので、レコード番号２の「性別」のフィールドの値はMとして求まる。
【００１０】
よって、このようなレコードのフィールド毎に設けられたインデックスより構成されるインデックスセットによってテーブルを完全に表現することができると共に、当該インデックスセットを用いてテーブルを速やかに利用できるようになる。
【００１１】
また、各フィールドに対応するインデックスのVLには、当該フィールドの値として用いられている値が、当該値がテーブルにおいて対応するフィールドに何度現れるものであっても、一回のみ登録される。よって、インデックスセットは、テーブルを圧縮したデータとなる。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】特開２０００-３３９３９０号公報
【発明の概要】
【発明が解決しようとする課題】
【００１３】
さて、上述のようにテーブルをレコードのフィールド毎に設けられたインデックスより構成されるインデックスセットに圧縮した場合でも、図６ｂのフィールドに現れる値がFとMの二つだけであるフィールド「性別」のインデックスと、フィールドに６から１１０までの７つの値が現れるフィールド「回数」のインデックスとの比較よりも理解されるように、フィールドの値として用いられている値の数（ユニークな値の数）が多くなると、充分な圧縮効率をもってテーブルを圧縮することができなくなる。
【００１４】
一方で、テーブルのインデックスセットへの圧縮は、テーブルを速やかに利用できるように、インデックスセットからテーブルの必要部分を速やかに取得できるように行う必要がある。
【００１５】
したがって、VLのような配列データを、当該配列データ中の任意の部分を速やかに復元できるように良好な圧縮効率で圧縮できれば、テーブルについても、これを速やかに利用できるように良好な圧縮効率で圧縮することができるようになる。
【００１６】
そこで、本発明は、配列データを、当該配列データ中の任意の部分を速やかに復元できるように、良好な圧縮効率で圧縮することを課題とする。
【課題を解決するための手段】
【００１７】
前記課題達成のために、本発明は、値を配列した配列データを圧縮するデータ圧縮方法として、前記配列データ複数のブロックに分割する分割ステップと、前記各ブロックの各々について、当該ブロックのブロックデータを作成し、作成した各ブロックの前記ブロックデータを前記圧縮データに含めるブロックデータ作成ステップとを備えたデータ圧縮方法を提供する。ここで、このデータ圧縮方法は、ブロックデータ作成ステップにおいて、前記ブロックデータを作成するブロックに、当該ブロック内の各値の参照値を表す所定の関数を近似関数として設定し、当該ブロックに含まれる各値について、当該値と、当該ブロックに設定された前記近似関数によって表される参照値との差分を求め、求めた差分を、当該差分を求めた値のブロック内の順序と同じ順序で配列した差分値配列データを作成するものである。
【００１８】
ここで、このようなデータ圧縮方法では、前記ブロックデータ作成ステップにおいて、前記近似関数として、各ブロックに、当該ブロック内の各値の近似値を、当該値の参照値として表す関数を設定するように構成してもよい。
【００１９】
また、以上のデータ圧縮方法は、前記ブロックデータ作成ステップにおいて、前記近似関数として、各ブロックに、当該各ブロックの各値と、当該近似関数によって表される当該値の参照値との差分の最大値、もしくは、当該最大値の絶対値が最小となる関数を設定するように構成してもよい。
【００２０】
また、以上のデータ圧縮方法は、前記ブロックデータ作成ステップにおいて、前記ブロックに設定する近似関数として、当該ブロック内の各値の前記参照値を、当該値の前記配列データ中の順序、または、当該ブロック内の順序を変数として表す関数を設定するように構成してもよい。
【００２１】
また、以上のデータ圧縮方法は、前記ブロックデータ作成ステップにおいて、前記各ブロックに前記近似関数として、前記ブロック毎に異なる種類の関数を設定可能としてもよい。
【００２２】
また、以上のデータ圧縮方法は、前記分割ステップにおいて、１番目のブロックに含める前記配列データの値を、前記配列データの先頭の値より、当該ブロックに対する当該ブロックの前記ブロックデータの圧縮率が所定レベル以上劣化するまで追加していくことにより、配列データから１番目のブロックを分割し、２番目以降のブロックに含める前記配列データの値を、前記配列データの一つ前のブロックに含めた最後の値の次の値より、当該ブロックに対する当該ブロックの前記ブロックデータの圧縮率が所定レベル以上劣化するまで追加していくことにより、配列データから２番目以降のブロックを分割するように構成してもよい。
【００２３】
このようなデータ圧縮方法によれば、配列データを複数のブロックに分割し、近似関数をブロック毎に設定する。したがって、傾向が共通している値の範囲毎にブロックを設定し、各ブロックに対して当該ブロック内の値の傾向に応じた適切な近似関数を設定することができる。そして、各ブロックに対して当該ブロック内の値の傾向に応じた適切な近似関数を設定することができれば、各ブロックデータの差分配列データに登録される差分の範囲を、配列データに登録されている値の範囲に比べ、小さな値の範囲とすることができる。そして、これにより、差分配列データにおいて差分を表すデータのビット数を少なくすることができ、配列データを圧縮効率良く圧縮したデータとして圧縮データを生成することができるようになる。
【００２４】
また、本発明による圧縮データによれば、配列データの必要な部分の復元を、当該部分を含むブロックのブロックデータのみを用いて復元することができる。また、値が昇順または降順に並んでおらず、値を配列データ上一つ前の値に符号化する差分圧縮によっては充分に配列データを効果的に圧縮できない場合でも、効果的な圧縮が行えることが期待できる。値を配列上一つ前の値に符号化する差分圧縮により充分に配列データを圧縮できない場合でも、本発明によれば効果的な圧縮が行えることが期待できる。また、値を可変長符号化した場合には、配列データの特定の値を復元するためには、可変長符号化されたデータ中において当該値を表しているデータ部分の位置を算定するために特段の処理を行った上で当該データ部分にアクセスする必要があるが、本発明による圧縮データによれば、各ブロックデータのビット長を等しくしても圧縮の効果を期待することができると共に、各ブロックデータのビット長を等しくすることによりブロックデータ中において各値を表している差分のデータ位置を容易に算定して、当該差分にアクセスすることができるようになる。
【００２５】
また、併せて本発明は、以上のようなデータ圧縮方法を実行するデータ圧縮装置や、以上のようなデータ圧縮方法をコンピュータに実行させるコンピュータプログラムも提供する。
【００２６】
また、さらに、本発明は、以上のようなデータ圧縮方法を実行するデータ圧縮装置と、前記圧縮データを含むデータベースを備えたデータベースシステムであって、前記配列データの所定部分の値を、前記圧縮データの、当該部分の値が含まれる前記ブロックのブロックデータの前記近似関数が表す当該部分の参照値の各々に、当該ブロックデータの前記差分配列データの当該部分に対応する差分値の各々を、それぞれ加算して算出するデータベース操作手段を備えたデータベースシステムも提供する。
【発明の効果】
【００２７】
以上のように、本発明によれば、配列データを、当該配列データ中の任意の部分を速やかに復元できるように、良好な圧縮効率で圧縮することができる。
【図面の簡単な説明】
【００２８】
【図１】本発明の実施形態に係る圧縮手順の概要を示す図である。
【図２】本発明の実施形態に係る近似関数の例を示す図である。
【図３】本発明の実施形態に係るデータ処理システムの構成を示すブロック図である。
【図４】本発明の実施形態に係る圧縮処理を示すフローチャートである。
【図５】本発明の実施形態に係るテーブルの圧縮例を示す図である。
【図６】従来のテーブルの圧縮例を示す図である。
【発明を実施するための形態】
【００２９】
以下、本発明の実施形態について説明する。
まず、本実施形態に係る配列データの圧縮手順の概要について説明する。
図１ａは、圧縮の対象とする配列データVLであり、配列データVLは、各々値Vが登録された複数のエントリの一次元配列となっている。また、配列データVL中において、配列データVLの各エントリには値Vが各々登録されている。また、各エントリには配列データVL中の順番を示す順位Nが与えられている。
【００３０】
そして、本実施形態に係る配列データの圧縮手順では、図１ｂに示すように、配列データVLを複数のブロックに分割する。ここで、この分割の詳細については後述する。
そして、各ブロックに近似関数を設定する。ここで、ｋ番目のブロックをブロックｋと表すこととし、ブロックkに設定した近似関数をF_kで表すこととする。なお、この近似関数の詳細についても後述する。
【００３１】
そして、各ブロックについて、以下の処理を行う。
すなわち、図１ｃに示すように、当該ブロックkに含まれる各エントリについて、当該エントリiの値V_iと、当当該エントリiが含まれるブロックkに設定された近似関数F_kに当該エントリiの配列データVLにおける順位iを代入して求まる値F_k (i)との差分値dV_i=V_i-F_k (i)を求める。ここで、エントリiは配列データVLの順位iのエントリを、V_iはエントリiに登録されている値vを、dV_iは、エントリiについて求めた得差分値dVを表している。
【００３２】
そして、差分値dV_iを、当該差分値dV_iを求めたブロックkのエントリの順位の順に配列したリストを当該ブロックkの差分値リストdVL_kとして生成する。
そして、以上のようにして各ブロックkについて求めた近似関数F_kと差分値リストdVL_kのセットとを当該ブロックkのブロックデータBLD_ kとし、各ブロックについて求めたブロックデータの集合を、図１ａの配列データの圧縮データとする。ただし、各ブロックkの差分値リストdVL_kの各差分値dVのデータのビット数は、当該差分値リストdVL_kに登録される差分値dVの分布範囲内の値を表現するのに足る最小のビット数となるように、各ブロックkの差分値リストdVL_kは生成する。
【００３３】
以上の操作を、図１に沿ってより具体的に述べれば、図１ａに示した圧縮の対象とする配列データVLは、０から１３までの順位を持つ１４個のエントリよりなり、各エントリには、値Vが昇順に各々登録されている。
【００３４】
ここで、以下では、便宜上、配列データVLのエントリの配列データVLにおける順位を「エントリ順位」と表記することとして説明を行う。
次に、この図１ａの配列データVLは、図１ｂに示すように、エントリ順位０-３のエントリを含むブロック０、エントリ順位４-７のエントリを含むブロック１、エントリ順位８-１３のエントリを含むブロック２の３つのブロックに分割される。
【００３５】
そして、図１ｃに示すように、ブロック０に対しては近似関数F_0として、定数関数F_0（N）=２が設定され、ブロック１に対しては近似関数F_1として、一次関数F_1（N）=N+3が設定され、ブロック2に対しては近似関数F_2として、定数関数F_2（N）=100が設定される。なお、Ｎはエントリ順位を表している。
【００３６】
そして、ブロック０については、ブロック０に含まれる配列データVLのエントリ順位０-３のエントリの各エントリの値V_1-V_3と、近似関数F_0（N）=2にエントリ順位を代入して求まる値（ここでは定数２）との差分が、エントリ順位０-３の差分値dV_0-dV_3として算出される。すなわち、たとえば、エントリ順位２のエントリの値V_2は２であり、F_0（2）=２であるので、２と２の差分０が、エントリ順位２の差分値dV_2として算出される。そして、エントリ順位０-３の各エントリについて求めた差分値dV_0-dV_3が、差分値dVを求めたエントリのエントリ順位に従った順序で登録された配列が当該ブロック０の差分値リストdVL_0となる。また、この例では、図示するように、差分値リストdVL_0に登録される差分値dVの分布範囲は０のみを含む範囲であり、０は１ビットのみで表現できるので、差分値リストdVL_0は、各差分値dVとしてビット数１のデータを格納した配列となる。
【００３７】
同様に、ブロック１については、ブロック１に含まれるエントリ順位４-７のエントリの各エントリの値V_4-V_７と、近似関数F_1=N+3にエントリ順位を代入して、図２ａに三角で示すように求まるF_1(N)=N+3との差分dVが、エントリ順位４-７の各エントリの差分値dV_4-dV_7として算出される。すなわち、たとえば、エントリ順位５のエントリの値V_5は6であり、F_1(5)=5+3=8であるので、６と８の差分-２が、エントリ順位５のエントリの差分値dV_5として算出される。そして、エントリ順位４-７について求めた差分値dV_4-dV_7のエントリ順位順の配列が当該ブロック１の差分値リストdVL_1となる。また、この例では図示するように、差分値リストdVL_1に登録される差分値dVの分布範囲は-2から１の範囲であり、この範囲内の値は正負の符号に１ビットを割り当てるものとして３ビットで表現できるので、差分値リストdVL_1は、各差分値dVとしてビット数３のデータを格納した配列となる。
【００３８】
また、同様に、ブロック２については、ブロック２に含まれるエントリ順位８-１３のエントリの各エントリの値V_8-V_13と、近似関数F_2(N)=100にエントリ順位を代入して図２ｂに三角で示すように求まる求まる値（ここでは定数１００）との差分dVが、エントリ順位８-１３の差分値dV_8-dV_13として算出される。すなわち、たとえば、エントリ順位９のエントリの値V_9は１２０であり、F_2（９）=１００であるので、１２０と１００の差分２０が、エントリ順位９の差分値dV_9として算出される。そして、エントリ順位８-１３について求めた差分値dV_8-dV_13のエントリ順位順の配列が当該ブロック２の差分値リストdVL_2となる。また、この例では図示するように、差分値リストdVL_2に登録される差分値dVの分布範囲は-20から20の範囲であり、この範囲内の値は正負の符号に１ビットを割り当てるものとして6ビットで表現できるので、差分値リストdVL_1は、各差分値dVとしてビット数６のデータを格納した配列となる。
【００３９】
そして、ブロック０について設定した近似関数F_0とブロック０について求めた差分値リストdVL_0がブロック０のブロックデータBLD_ 0となり、ブロック１について設定した近似関数F_1とブロック１について求めた差分値リストdVL_1がブロック１のブロックデータBLD_ 1となり、ブロック２について設定した近似関数F_2とブロック２について求めた差分値リストdVL_2がブロック２のブロックデータBLD_ 2となり、ｃ_ 1、ブロックデータBLD_ 2、ブロックデータBLD_ 3が圧縮データとなる。
【００４０】
ここで、この圧縮データには、各ブロックのブロックデータBLDの他に、各ブロックを管理するための、ブロック管理データを含めるようにしてよい。また、この場合、ブロック管理データには、各ブロックに含めた配列データVLのエントリ順位や、各ブロックのブロックデータBLDの識別を表すデータなどを含めるようにしてよい。
【００４１】
以上、本実施形態に係る配列データの圧縮手順の概要について説明した。
さて、ここで、図１ｃに示す圧縮データより、配列データVLの各エントリ順位のエントリの値Vは、次のように求めることができる。すなわち、配列データVLのエントリ順位iのエントリについては、エントリ順位iの属するブロックｋを求め、ブロックｋのブロックデータBLD_ kより近似関数F_kを取得する。また、ブロックｋの先頭のエントリのエントリ順位をiから減じた値をjとして、ブロックｋのブロックデータBLD_ kの差分値リストdVL_kのj番目のエントリより、エントリ順位iのエントリについて求めた差分値dV_iを取得する。そして、V_i=F_k(i)+ dV_iによって求まる値を、配列データVLのエントリ順位iのエントリの値V_iとする。
【００４２】
なお、図中の差分値リストdVL_nの各エントリの左の括弧内の数字は、当該エントリの差分値dVを求めたブロックのエントリの配列データVLにおけるエントリ順位を表している。
【００４３】
具体的には、たとえば、配列データVLのエントリ順位５のエントリについては、エントリ順位５のエントリはブロック１に属しており、ブロックデータBLD_ 1に登録されている近似関数はF_1（N）=N+3となる。また、ブロック１の先頭のエントリのエントリ順位は４であるので、エントリ順位５から４を減じた値は１となる。そして、ブロックデータBLD_ 1の差分値リストdVL_1の順位１のエントリに登録されている差分値は-2となり、V_5=F_1(5)+-2=8-2=6に従って、配列データVLのエントリ順位５のエントリの値６が求まる。
【００４４】
このように、本実施形態に係る圧縮データによれば、配列データVLの所望のエントリ順位のエントリの値を、当該エントリ順位のエントリが属するブロックのブロックデータBLD_ kを参照するのみで、圧縮データの全体を解凍するなどの処理を必要とすることなく速やかに求めることができる。
【００４５】
さて、次に、各差分値リストdVL_kに登録される差分値dVの範囲を、配列データVLの各エントリの値Vを表すデータのビット数に比べ小さいビット数のデータで表すことができる範囲とすれば、圧縮データを、配列データよりもデータ量の少ないデータ、すなわち、配列データVLを圧縮したデータとすることができる。
【００４６】
そして、差分値dVの分布は、各ブロック内の各エントリの値Vの分布と、当該ブロックに設定する近似関数によって定まる。また、配列データVLの配置が近い値V、したがって、各ブロック内の値Vは、何かしらの傾向と相関性が高いことが多いので、このような傾向に整合し、差分値dVの分布を小さく抑えることのできる近似関数が存在することが期待できる。
【００４７】
また、各差分値リストdVL_kは、それぞれ独立した配列データとして設けられており、各ブロックの差分値リストdVL_kの差分値dVのデータのビット数は、他のブロックの差分値dVから独立して設定することができる。
【００４８】
したがって、各ブロックと、各ブロックの近似関数を適切に設定することにより、配列データを圧縮効率良く圧縮したデータとして圧縮データを生成することができる。
そこで、本実施形態では、以下に示すようにブロックと近似関数を、良好な圧縮効率が得られるように設定して圧縮データを生成する。
ここで、配列データから圧縮データを生成する、より詳細な構成について説明する。
まず、配列データからの圧縮データの生成は、たとえば、図３ａに示すデータ処理装置において行うことができる。
図３ａに示すデータ処理装置は、ストレージ１とプロセッサ２と入力装置３と表示装置４等を備えている。
そして、ストレージ１には、圧縮の対象となる配列データが格納されており、プロセッサ２は、配列データをストレージ１から読み出して圧縮データを作成しストレージ１に格納する。
【００４９】
ここで、プロセッサ２は、配列データから圧縮データを生成するために図４に示す圧縮処理を行う。なお、圧縮処理は、プロセッサ２が所定のコンピュータプログラムを実行することにより実現される処理である。
【００５０】
さて、図４に示すように、圧縮処理では、まず、k=0、StN=0に設定する（ステップ４０２）。
次に、EdNをStN+１に設定し（ステップ４０４）、配列データのエントリ順位がStNからEdNのエントリをブロックkに設定する（ステップ４０６）。なお、ブロックkは、ｋ番目のブロックを表す。
【００５１】
そして、関数G0(N)を、定数関数G0(N)=V_StNに設定し、CE0を０に設定する（ステップ４０８）。ここで、V_StNは、配列データVLのエントリ順位がStNのエントリの値Vである。
【００５２】
次に、ブロックkの各エントリ順位のエントリの値Vに対して求めた差分V-G1(N)の絶対値の最大値を最小とする関数G1(N)を算出する（ステップ４１０）。ここで、ステップ４１０では、たとえば、予め近似関数として用いる関数の種別として定義しておいた定数関数、一次関数、二次関数、三角関数、その他の任意の関数のそれぞれで、ブロックkの値Vをエントリ順位順に結んだ線を近似し、最も良く近似できた関数を近似関数G1(N)として算出する。ただし、V-G1(N)の絶対値の最大値が小さいG1(N)ほど、ブロックkの値Vをエントリ順位順に結んだ線をより良く近似している関数であるものとして、近似関数G1(N)の算出は行う。また、近似関数G1(N)は、ブロックkの各エントリの値Vに対して求めた差分V-G1(N)が必ず正になるように算出してもよい。このようにすることにより、差分値dVは必ず正となるので、差分値dVを表すデータとして共通に正負の符号無しのデータを用いることができる。
【００５３】
そして、次に、算出した関数G1(N)をブロックkの近似関数F_kとして用いて、ブロックkを上述したブロックデータBLD_kに圧縮した場合の圧縮効率を算定もしくは推定しCE1に設定する（ステップ４１２）。ここでは、たとえば、実際に関数G1(N)をブロックkの近似関数F_kとして用いて上述のようにブロックkのブロックデータBLD_kを生成した場合における、ブロックデータBLD_kのデータ量を見積もり、圧縮効率を、
圧縮効率=（配列データVLのブロックｋのデータ量-ブロックデータBLD_kのデータ量）/（配列データVLのブロックｋのデータ量）
によって算出し、算出した圧縮効率をCE1に設定する。
【００５４】
ここで、圧縮効率は、配列データVLのブロックｋをブロックデータBLD_kに置き換えることにより、データ量が、どの程度圧縮されているかを表しており、その値が大きいほど、データ量がが大きく圧縮されていること、すなわち、ブロックデータBLD_kが、配列データVLのブロックｋを大きく圧縮したものであることを表している。また、圧縮効率０は、ブロックデータBLD_kのデータ量が、配列データVLのブロックｋのデータ量と等しく、データ量が全く圧縮されていないことを表している。
【００５５】
次に、ステップ４１２で算出したCE1がCE0から所定のマージンMGNを減じた値以上の値であるかどうかを調べる（ステップ４１４）。ここで、マージンMGNは、配列データVLのブロックへの分割され易さを調整するためのパラメータであり、マージンMGNには、配列データVLの圧縮ポリシーに従って適当な値を設定してよい。また、マージンMGNは０としてもよい。
【００５６】
そして、CE1がCE0から所定のマージンMGNを減じた値以上であれば（ステップ４１４）、EdNが配列データVLの最後のエントリ順位MaxNと等しいかどうかを調べる（ステップ４１６）。
【００５７】
そして、EdNがMaxNと等しくなければ（ステップ４１６）、現在のCE1を以降のCE0とし、現在のG1(N)を以降の G0(N)とする（ステップ４１８）。
そして、EdNを１増加し（ステップ４２０）、配列データVLのエントリ順位がStNからEdNのエントリをブロックkに設定し（ステップ４２２）、ステップ４１０からの処理に戻る。
【００５８】
一方、ステップ４１４において、CE1がCE0から所定のマージンMGNを減じた値以上でなければ（ステップ４１４）、配列データVLのエントリ順位がStNからEdN-1のエントリをブロックkに設定し（ステップ４２４）、現在のG0(N)をブロックｋの近似関数F_kとして保存する（ステップ４２６）。また、保存した近似関数F_kを用いて、上述のようにブロックｋの差分値リストdVL_kを作成し保存する（ステップ４２８）。
【００５９】
そして、ｋを１増加すると共に、現在のEdNを新たなStNに設定し（ステップ４３０）、ステップ４０４からの処理に戻る。
一方、ステップ４１６において、EdNがMaxNと等しければ、現在のG1(N)をブロックｋの近似関数F_kとして保存する（ステップ４３２）。また、保存した近似関数F_kを用いて、上述のようにブロックｋの差分値リストdVL_kを作成し保存する（ステップ４３４）。
【００６０】
そして、圧縮処理を完了する。
以上、プロセッサが行う圧縮処理について説明した。
なお、上述したブロック管理データを圧縮データに含める場合には、図４の圧縮処理中において、または、圧縮処理の後に、ブロック管理データを作成して保存する処理を追加する。
【００６１】
さて、このような圧縮処理によれば、仮ブロックに含める配列データVLのエントリを、最後に設定したブロックの末尾のエントリの次のエントリから一つずつ増加しながら、仮ブロックを圧縮した場合の圧縮効率を見積もり、圧縮効率が最後のエントリを増加する前に比べ所定レベル以上悪化しなかったならば、もしくは、圧縮効率が最後のエントリを増加する前に比べ悪化しなかったならば、もしくは、圧縮効率が最後のエントリを増加する前に比べ所定レベル以上向上しなかったならば、最後のエントリを増加する前の仮ブロックをブロックとして設定する処理を繰り返すことにより、配列データVLを複数のブロックに分割する。
【００６２】
また、このような圧縮処理によれば、各ブロック毎に近似関数を、当該ブロックの差分値リストdVLに登録される差分dVLの絶対値の最大値ができるだけ小さくなるように設定することができる。そして、差分値リストdVLに登録される差分dVLの絶対値の最大値が小さければ、差分dVLを表すデータとしてビット数の少ないデータを用いることができるので、差分値リストdVLのデータ量を小さな量に抑えることができる。
【００６３】
したがって、このような圧縮処理によれば、ブロックと近似関数を良好な圧縮効率が得られるように設定することができ、この結果、配列データVLを、高い圧縮効率で圧縮データに圧縮することができるようになる。
【００６４】
また、このような圧縮処理によって生成した圧縮データによれば、配列データの必要な部分の復元を、当該部分を含むブロックのブロックデータのみを用いて復元することができる。また、このような圧縮処理によれば、値が昇順または降順に並んでおらず、値を配列データ上一つ前の値に符号化する差分圧縮によっては充分に配列データを効果的に圧縮できない場合でも、効果的な圧縮が行えることが期待できる。また、値を可変長符号化した場合には、配列データの特定の値を復元するためには、可変長符号化されたデータ中において当該値を表しているデータ部分の位置を算定するために特段の処理を行った上で当該データ部分にアクセスする必要があるが、以上のような圧縮処理によって生成した圧縮データによれば、各ブロックデータのビット長を等しくしても圧縮の効果を期待することができると共に、各ブロックデータのビット長を等しくすることによりブロックデータ中において各値を表している差分のデータ位置を容易に算定して、当該差分にアクセスすることができるようになる。
【００６５】
さて、以上で示してきた配列データVLの圧縮の技術は、先に図６に示したインデックスセットの圧縮に適用することができる。
すなわち、この場合には、図３ｂに示すように、プロセッサ２に、データ圧縮部１１と、ＲＤＢＭＳ１２（リレーショナルデータベースマネジメントシステム１２）とを備える。なお、データ圧縮部１１、ＲＤＢＭＳ１２は、プロセッサ２が所定のコンピュータプログラムを実行することにより実現される機能部である。
【００６６】
そして、データ圧縮部１１においてストレージ１に格納されたインデックスセットを圧縮した圧縮インデックスセットを作成しストレージ１に格納し、インデックスセットを消去する。また、ＲＤＢＭＳ１２において、圧縮インデックスセットを用いて、圧縮インデックスセットが表すテーブル（インデックスセットが表していたテーブル）の操作を行う。
【００６７】
ここでデータ圧縮部１１におけるインデックスセットを圧縮した圧縮インデックスセットの作成は、以下のように行う。
すなわち、インデックスセットの各インデックスのVLを、圧縮対象の配列データVLとして、上述の圧縮処理によって圧縮した圧縮データを、圧縮VLとして生成する。そして、インデックスセットの各インデックスのVLを当該VLを圧縮した圧縮VLで置換したデータを圧縮インデックスセットとして生成する。
【００６８】
ここで、各インデックスのVLを圧縮して作成した圧縮VLの例を図５に示す。
図５において、図５ｂは、図５ａに示すインデックスセット中のフィールド「回数」のインデックスのVLを、圧縮VLに置換して生成した、圧縮インデックスセット中のフィールド「回数」のインデックスを表している。
【００６９】
図示するように、圧縮VLは、ブロック毎の差分値リストdVL_nと、ブロック順に近似関数F_nを格納した近似関数リストFLと、BL_MAPを備えている。BL_MAPは上述したブロック管理データに該当し、BL_MAPには、ブロック順に各ブロックの次のブロックの先頭のエントリ順位が格納される。ただし、BL_MAPの最後のエントリにはVLの最大のエントリ順位に１加えた数が登録される。
【００７０】
ここで、インデックスのVLは、所定の基準でソートされて登録されているので、各ブロック内の値Vには上記基準に沿った一定の傾向があり、ブロックごとに、差分値dVの分布を効果的に小さく抑えることのできる近似関数を設定できること場合が多い。よって、本実施形態によれば、インデックスのVLを圧縮VLを高い圧縮効率をもって圧縮するできることが期待できる。
【００７１】
さて、ＲＤＢＭＳ１２は、圧縮インデックスセットが表すテーブルを操作する際、各レコードの各フィールドの値を次のように求める。
すなわち、レコード番号Ａの、図５ｂに示したインデックスに対応するフィールドＸの値を求める場合には、フィールドＸのインデックスのVNoを参照してレコード番号ＡのフィールドＸの値を格納しているVLのエントリ順位Ｂを求める。次に、BL_MAPを参照して、VLのエントリ順位Ｂのエントリが属するブロックの順番ｋと、当該ブロックｋ内のエントリ順位Ｂのエントリから求めた差分値dVが格納されている、差分値リストdVL_1のエントリの順位ｊを求める。そして、ブロックｋの近似関数F_kを近似関数リストFLから取得し、VLのエントリ順位Ｂのエントリの差分値dV_Bを、ブロックｋの差分値リストdVL_kの順位jのエントリから取得する。そして、近似関数F_kと差分値dV_Bより、レコード番号ＡのレコードのフィールドＸの値Vを、F_k(B)+dV_Bによって算出する。
【００７２】
より具体的には、たとえば、レコード番号２の、図５ｂに示したインデックスに対応するフィールド「回数」の値を求める場合には、VNoを参照してレコード番号２のフィールド「回数」の値を格納しているVLのエントリ順位６を求める。次に、BL_MAPの順位０のエントリに２番目のブロックの先頭のエントリのエントリ順位が４であることが、BL_MAPの順位１のエントリに２番目のブロック末尾のエントリのエントリ順位の次の値が７であることが登録されているので、VLのエントリ順位６のエントリが属するブロックは、２番目のブロック１であることが求まる。また、２番目のブロック１の先頭のエントリのエントリ順位が４であることより、VLのエントリ順位６のエントリから求めた差分値dVは、ブロック１の差分値リストdVL_1の順位２のエントリに格納されていることが求まる。
【００７３】
そこで、近似関数FLの順位１のエントリに格納されているブロック１の近似関数F_1=100を取得する。また、ブロック１の差分値リストdVL_1の順位２のエントリに格納されている差分値１０を取得する。
【００７４】
そして、取得した近似関数F_1=100と、差分値１０より、レコード番号２のレコードのフィールド「回数」の値Vを、V=100+10=110によって算定する。
以上、図６に示したインデックスセットの圧縮について説明した。
なお、以上では、インデックスのVLを圧縮VLに圧縮する場合について説明したが、インデックスのVNoについても同様に圧縮VNoに圧縮するようにしてもよい。
ここで、インデックスのVNoは、VLのように、所定の基準で値がソートされていないが、値を配列データ上一つ前の値に符号化する差分圧縮により充分に配列データを圧縮できない場合でも、差分圧縮に比べて効果的な圧縮が行えることが期待できる。
【００７５】
以上、本発明の実施形態について説明した。
ところで、以上の実施形態では、圧縮データに圧縮する配列データVLが値Vとして数値を格納している場合について説明したが、本実施形態は配列データVLが値Vとして文字列を格納している場合にも同様に適用することができる。すなわち、この場合には、文字列を表す文字コード列を数値と見なして、もしくは、数値に変換して、以上と同様の処理を行えばよい。
【００７６】
また、以上の実施形態は、差分値リストdVLに、差分値dVを適当な圧縮符号化則に従って圧縮符号化したデータを格納するようにしてもよい。
また、以上の実施形態では、各ブロックｋに近似関数Fとして、ブロックのエントリの配列データVL内の順位Nを変数とする関数 F_k(N)を設定する例について示したが、各ブロックには、近似関数として、ブロックのエントリの当該ブロック内の順位ｎを変数とする関数 F_k (n)を設定するようにしてもよい。
【００７７】
また、以上の実施形態では、各ブロックの差分値リストdVLを相互に独立した配列データとして設けたが、差分値リストdVL毎にビット数を異ならせる必要のない場合などには、各ブロックの差分値リストdVLは、これらをまとめて一つの配列データとして設けるようにしてもよい。
【符号の説明】
【００７８】
１…ストレージ、２…プロセッサ、３…入力装置、４…表示装置、１１…データ圧縮部、１２…ＲＤＢＭＳ。
【図１】
2018046406.tif 000003
【図２】
2018046406.tif 000004
【図３】
2018046406.tif 000005
【図４】
2018046406.tif 000006
【図５】
2018046406.tif 000007
【図６】
2018046406.tif 000008