(57)【要約】【課題】本発明の課題は、データの可逆圧縮においてエントロピーを削減することを目的とする。【解決手段】上記課題は、複数の整数で表現されるデータを指定した圧縮要求を受け付ける圧縮要求受付部と、前記圧縮要求で指定される前記データを行列で表したデータ行列に、行列式が１である変換行列を乗算して、エントロピーを削減するエントロピー削減部とを有することを特徴とする情報処理装置により達成される。【選択図】図１３
2018113583.tif 000002
【特許請求の範囲】
【請求項１】
複数の整数で表現されるデータを指定した圧縮要求を受け付ける圧縮要求受付部と、
前記圧縮要求で指定される前記データを行列で表したデータ行列に、行列式が１である変換行列を乗算して、エントロピーを削減するエントロピー削減部と
を有することを特徴とする情報処理装置。
【請求項２】
前記エントロピー削減部は、
前記データ行列に前記変換行列を乗算する際に、各要素の値を所定数値で剰余をとることを特徴とする請求項１記載の情報処理装置。
【請求項３】
任意の行列を積により表現可能な第１行列と第２行列の少なくとも１つ以上を用いて、エントロピーが最も小さくなるべき乗数を探索して、前記変換行列を求め、圧縮データを格納するファイルのヘッダに記憶する変換行列探索部を更に有することを特徴とする請求項２記載の情報処理装置。
【請求項４】
前記ファイルに格納された前記圧縮データを解凍して得た解凍データを行列で表し、前記ファイルの前記ヘッダに格納された前記変換行列と前記所定数値とを用いて得られる逆変換行列を該解凍データの行列に乗算し、該所定数値で剰余をとり前記エントロピーを増大させることで前記データ行列を復元するエントロピー増大部
を有することを特徴とする請求項３記載の情報処理装置。
【請求項５】
前記所定数値の２のｎ乗分の１の整数倍の値を示すテーブルを作成する数値変換テーブル作成部と、
前記データの前記複数の整数において、出現頻度の高い順に、前記数値変換テーブル作成部によって作成された前記テーブルの先頭から順に得られた数値を写像先として該データの各整数の値を変換する数値変換部とを更に有し、
前記データ行列は、前記数値変換部による変換後の前記データを表わすことを特徴とする請求項３記載の情報処理装置。
【請求項６】
前記変換行列によって変換された前記データ行列では、出現する整数の種類の出現頻度が偏ることを特徴とする請求項１乃至５のいずれか一項記載の情報処理装置。
【請求項７】
複数の整数で表現されるデータを指定した圧縮要求を受け付け、
前記圧縮要求で指定される前記データを行列で表したデータ行列に、行列式が１である変換行列を乗算して、エントロピーを削減する
処理をコンピュータに行わせることを特徴とするプログラム。
【請求項８】
複数の整数で表現されるデータを指定した圧縮要求を受け付け、
前記圧縮要求で指定される前記データを行列で表したデータ行列に、行列式が１である変換行列を乗算して、エントロピーを削減する
処理をコンピュータが行うことを特徴とする情報処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データの可逆圧縮技術に関する。
【背景技術】
【０００２】
監視カメラやマイク、センサーがインターネットでつながって、それぞれからデータを取得し、それらを分析・照合しビジネスに生かすことが求められている。そのためにはデータを取得し、利活用できる形式で保存することが望ましい。
【０００３】
しかし全てのセンサーからデータを取得し、データ量が莫大になった場合には、テープデバイス等の大量のデータを記録可能な装置に保持する場合がある。しかしそれらの装置は読み出し速度が遅く、利活用には向いていない。
【０００４】
大量のデータを圧縮しハードディスク等に保持することが好ましいが、そのためのデータ圧縮技術が重要である。また、ネットワークトラフィックが増大する為、センサーデバイスでデータ圧縮し、それを転送することでトラフィック量を下げることも重要である。
【０００５】
このような観点から、同じビットが連続する確率が高くなるようにビット列を並べ替えた後、多値の画像データの可逆圧縮を行う技術、入力したデジタル画像信号に応じて得られる要素に基づいてマルチ多段変換関数を算出し、その係数を可逆性を満たすように、かつ、出力エントロピーが小さくなるように決定する技術等が知られている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００１−３０９１８５号公報
【特許文献２】特開２００３−２３０１３９号公報
【非特許文献】
【０００７】
【非特許文献１】David  Salomon，“Data  Compression”，ISBN：978-0-387-40697-8
【非特許文献２】Jean-Pierre  Serre，“A  Course  in  Arithmetic  (Graduate  Texts  in  Mathematics)”，Springer-Verlag  New  York，1973
【発明の概要】
【発明が解決しようとする課題】
【０００８】
可逆圧縮技術は、主に、ＬＺ系の辞書圧縮、ランレングス圧縮、及びエントロピー符号化に分けられる。これらのいずれの可逆圧縮技術は、エントロピーを削減することができない。
【０００９】
上述したマルチ多段変換関数を用いた技術においても、マルチ多段変換関数の係数の決定方法について開示がなく、エントロピーを削減する課題を十分に解決することができない。
【００１０】
したがって、１つの側面では、データの可逆圧縮においてエントロピーを削減することを目的とする。
【課題を解決するための手段】
【００１１】
一態様によれば、複数の整数で表現されるデータを指定した圧縮要求を受け付ける圧縮要求受付部と、前記圧縮要求で指定される前記データを行列で表したデータ行列に、行列式が１である変換行列を乗算して、エントロピーを削減するエントロピー削減部とを有することを特徴とする情報処理装置が提供される。
【００１２】
また、上記課題を解決するための手段として、プログラム、及び、情報処理方法とすることもできる。
【発明の効果】
【００１３】
データの可逆圧縮においてエントロピーを削減することができる。
【図面の簡単な説明】
【００１４】
【図１】トーラスの例を示す図である。
【図２】記号出現頻度（エントロピー）の変更方法を説明するための図である。
【図３】２バイトの組の出現頻度の結果例を示す図である。
【図４】図３の結果例に基づく、１バイト記号の出現頻度の結果例を示す図である。
【図５】図４の結果例に基づく１バイト記号のヒストグラムを示す図である。
【図６】図３の結果例に基づく１バイト記号の二次元のヒストグラムを示す図である。
【図７】変換後の２バイトの組の出現頻度の結果例を示す図である。
【図８】図７の結果例に基づく、変換後の１バイト記号の出現頻度の結果例を示す図である。
【図９】図８の結果例に基づく、記号出現頻度変更後の、１バイト記号のヒストグラムを示す図である。
【図１０】図７の結果例に基づく、記号出現頻度変更後の１バイト記号の二次元のヒストグラムを示す図である。
【図１１】格納形式の例を示す図である。
【図１２】情報処理装置のハードウェア構成図である。
【図１３】第１実施例における情報処理装置の機能構成例を示す図である。
【図１４】第１実施例における圧縮処理の概要を説明するためのフローチャートである。
【図１５】第１実施例における変換行列探索処理を説明するためのフローチャート図である。
【図１６】第１実施例におけるエントロピー削減処理を説明するためのフローチャート図である。
【図１７】第１実施例における解凍処理を説明するためのフローチャート図である。
【図１８】第１実施例におけるエントロピー増大処理を説明するためのフローチャート図である。
【図１９】第２実施例における機能構成例を示す図である。
【図２０】数値変換テーブルの一例を示す図である。
【図２１】トーラスの例を示す図である。
【図２２】図２０の数値変換テーブルの改良例を示す図である。
【図２３】「３２」を含む二次元トーラスの例を示す図である。
【図２４】図２０の数値変換テーブルの作成処理を説明するためのフローチャート図である。
【図２５】図２２の数値変換テーブルの作成処理を説明するためのフローチャート図である。
【図２６】第２実施例における圧縮処理の概要を説明するためのフローチャート図である。
【図２７】第２実施例における数値変換処理を説明するためのフローチャート図である。
【図２８】第２実施例における解凍処理の概要を説明するためのフローチャート図である。
【図２９】第２実施例における逆数値変換処理を説明するためのフローチャート図である。
【発明を実施するための形態】
【００１５】
以下、本発明の実施の形態を図面に基づいて説明する。主な可逆圧縮技術として、ＬＺ系の辞書圧縮、ランレングス圧縮、及びエントロピー符号化に分けられる。先ず、これらの可逆圧縮技術について簡単に説明する。
【００１６】
辞書圧縮は、ファイルをバイトから成る列と見做し、先頭からバイト列を読み込み、同じ部分バイト列が現れた場合、既に出現しているバイト列の先頭位置へのポインタと、一致する文字数とを示す符号で、部分バイト列を置換する技術である。
【００１７】
ランレングス圧縮は、同じバイト文字が連続する場合、連続するバイト文字と連続回数とを示す符号へと置換する技術である。
【００１８】
エントロピー符号化は、例えば、ハフマン符号化等が知られており、バイト文字の出現頻度から計算されるエントロピーに基づいて、多数回出現する文字を短いビット列に変換してデータ量を削減する技術である。
【００１９】
データ量を削減する観点において、画像、音声、センサーデータ等は、取得される信号の数値間で相関が強いデータは、隣り合う数値が似ていることに着目する。信号の数値列を高次元の空間中の点とし、適当な座標変換を行うことで、元の信号の殆どの情報を少ない数の数値で表すことができる。画像であれば、離散コサイン変換、ウェーブレット変換等を用いればよい。高次元での数値演算ができれば、信号を少ない数値で表すことで、０となる数値を増やすことや、同じ数値を増やすことが可能となり、高効率可逆圧縮が可能となる。
【００２０】
このような数値演算は、浮動小数点による演算か整数演算に分けられる。浮動小数演算は、小数点のまるめがある為、非可逆な計算である。整数演算は、可逆にすることは可能だが、例えば、０から２５５の数値の差は−２５５から＋２５５の範囲に入るなど、数値の値域が定義域より広がってしまう。
【００２１】
つまり、一例として、１バイトデータと１バイトデータの和や差は２バイトで表され、更に、それらの和や差を表わす場合には、より長いバイトが必要となり、演算処理中のデータ量は増えることになる。
【００２２】
上述した可逆圧縮技術では、エントロピーの削減を十分に行うことができず、また、数値演算には、以下の問題がある。
・整数値データに対し、それらを浮動小数点数に変換し浮動小数演算を行うと、丸め誤差により可逆演算にならない。
・整数値データに対し整数値の演算を行った場合、例えば、０から２５５の数値の差は−２５５から＋２５５の範囲に入るなど数値の値域の広がりを許容しなければ、可逆演算にならない。
【００２３】
まず、第１実施例では、
バイト列を高次元トーラス中の点と見なすことで、数値の範囲の広がりを抑止し、整数演算の範囲で可逆演算を可能とする。数直線を考え、０と２５６とを同一視することで、和も差も同じ円の内部に閉じることができる。このため、１バイトデータと１バイトデータとの和と差の結果を１バイトで表現できる。
【００２４】
また、Ｎバイトを組とすることで、トーラスからトーラスへの変換の行列演算を可能とし、エントロピーを削減する。つまり、トーラスからトーラスへの変換の行列演算を可能とすることで、データ量を増やすことなく、１バイトデータの出現頻度を偏らせることができ、結果、エントロピーを削減する。
【００２５】
更に、エントロピーが削減されたデータの圧縮及び解凍は、公知の技術を用いることができる。解凍後のデータに対しては、圧縮前に行ったエントロピー削減の手順の逆を行うことで元のデータを復元できる。
【００２６】
第１実施例は、
１．トーラスによるバイトの広がりの抑制
２．トーラスからトーラスへの変換の行列演算による記号出現頻度の変更
３．エントロピー削減のための変換行列の探索方法
４．エントロピー削減データの格納形式
５．データの圧縮
６．データの解凍
７．元データへの復元
により実現される。各要素１〜７について説明する。以下、２５６を一例とし、０と２５６を同一視した場合で説明するが、５１２、７６８等の１バイトの整数倍を、取り得る数値の範囲としてもよい。また、１２７などバイトより小さい整数を取り得る数値の範囲としてもよい。
【００２７】
＜１．トーラスによるバイトの広がりの抑制＞
全てのデータは、バイトの列として情報処理装置１００（図１２）の記憶部１３０に保持されている。１バイトの列と見なすと、１バイトの文字は、１から２５５の間の数値で表される。
【００２８】
数直線を考え０と２５６を同一視することで円を作る。これは情報処理装置１００では整数ｐに対し２５６の剰余を取ることで実施される。以下、整数ｐに対し２５６の剰余を取ることを、“ｐ％２５６”で表す。％はmoduloを示す。ｐ＝５００の場合、５００％２５６＝２４４であることから、数値５００は２４４で表わされる。１６進数で表現すれば、0x01F4が0xF4に変換される。
【００２９】
数式で表すと、同値関係〜を整数ｐ、ｑに対し、
【００３０】
【数１】
2018113583.tif 000003
が、ある整数ｋで成り立つと定義すると、
【００３１】
【数２】
2018113583.tif 000004
である。この円Ｓの上では１バイトの文字は０から２５５の数値として自然に表現される。
【００３２】
また、この円Ｓの上にある２つの数値の和や差は、同じ円の上にある。例えば、４０と２４４との和は、
(40+244)%256=28
になり、差は、
(40-244)%256=52
になる。また、この円上の数値に対し整数値を乗算した結果も、同じ円の上にある。例えば、１バイト文字４０に対する整数「８」の積は、
(8*40)%256=64
である。＊は乗算を示す。
【００３３】
Ｎバイトに対し、それを長さをＮとする１バイト文字の列とすれば、それぞれの成分を円の上にある数値と扱うことができ、和と差の演算を０から２５５の範囲内で行える。例えば、１バイト文字列(100,  200,  250)と１バイト文字列(150,  250,  50)の和は、
(100+150，  200+250,  250+50)%256  =  (250,  194,  44)
である。この様な円達SxSx…xSは、Ｎ次元トーラスＴと呼ばれる幾何構造である。また、１バイト文字列に対する整数値の乗算も、トーラスＴの上にある。例えば、１バイト文字列(100,  200,  250)の整数「３」の乗算は、
(3*100,  3*200,  3*250)%256  =  (44,  88,  238)
である。
【００３４】
長さをＮとする１バイト文字の列の成すＮ次元トーラスＴは、それぞれの成分が０から２５５の数値であり、Ｎ個の１バイトで表現することが可能である。つまり、ＮバイトをＮ次元トーラスＴと見なすと、Ｎ個のバイトの和や積、さらに整数倍もＮバイトで表現可能である。これを、バイト列のトーラスへの埋め込みと呼称する。
【００３５】
これにより、Ｎ個のバイトに数値演算をした結果はＮ個のバイトに抑制することが可能となる。従来の演算による数値の範囲の広がりによるデータ量の増大を考慮しなくてよい。第１実施例における効果の１つである。
【００３６】
図１は、トーラスの例を示す図である。図１では、Ｎが２の場合の二次元トーラスＴを表わしている。図１全体は、
【００３７】
【数３】
2018113583.tif 000005
の二次元空間であり、点(0,0)を通る縦横の線と、点(256,256)を通る縦横の線とで囲まれる矩形の領域がトーラスＴを表わす。点(0,256)、点(0,512)及び点(0,768)を通る縦の線と、点(256,0)、点(512,0)及び点(768,0)を通る横の線は、それぞれ点(0,0)を通る縦線と横線と同一視される。
【００３８】
トーラスＴで取り得る最大値は、「256」以外の数値であってもよい。例えば、対象データがテキストデータの場合、0から127のASCIIコードで書かれており、256よりも小さい数字「128」であってもよい。また他にも、二バイト以上の長さの文字を考えることで256よりも大きい数字、例えば「512」であってもよい。素数であってもよい。
【００３９】
暗号理論では整数を素数で剰余を取った数値で計算を進めることが広く行われており、それらは可逆である。しかし、１バイト記号を表すには、256よりも大きい素数の中で最も小さいものは「267」であり、９ビット以上を必要とする。特に現在広く使われている計算機では、９ビットは２バイトで表現する方が演算機の効率が良く、２バイトとして表してしまうとデータのサイズが大きくなってしまう。したがって、以下の説明では、トーラスＴで取り得る最大値を「256」とする。
【００４０】
＜２．トーラスからトーラスへの変換の行列演算による記号出現頻度の変更＞
図２を参照して、第１実施例における、トーラスからトーラスへの変換による同一１バイト記号の出現頻度（エントロピー）の変更方法を説明する。図２は、記号出現頻度（エントロピー）の変更方法を説明するための図である。
【００４１】
先ず、Ｎ個のバイトから成る１バイト文字列を縦に並べ、
【００４２】
【数４】
2018113583.tif 000006
と書く。全ての要素が整数である行列を整数系列行列と呼ぶ。N-by-N整数系列行列Ａを、
【００４３】
【数５】
2018113583.tif 000007
とする。以下、N-by-N整数系列行列Ａを単に変換行列Ａと呼ぶ場合がある。
【００４４】
変換行列Ａをｖに乗算でき、
【００４５】
【数６】
2018113583.tif 000008
と表せる。変換行列Ａの乗算の結果は、０から２５５の範囲を超えてしまうが、２５６での剰余を取ることでＮバイトに戻すことができる。
【００４６】
【数７】
2018113583.tif 000009
この数７における変換行列Ａの乗算および２５６での剰余の計算は、コンピュータにより実行可能である。
【００４７】
一例として、Ｎが２であり、変換行列Ａが
【００４８】
【数８】
2018113583.tif 000010
の場合、図２（Ａ）のトーラスＴは、変換行列Ａを乗算することで、図２（Ｂ）のトーラスＴ’に変形される。そして、数７に示したように、２５６で剰余を取ると、図２（Ｃ）のように元のトーラスＴ’の領域へ戻る。
【００４９】
変換行列Ａの行列式が１のとき、逆変換行列Ａ−１も整数係数行列である。逆変換行列Ａ−１は、
【００５０】
【数９】
2018113583.tif 000011
で表すと、
【００５１】
【数１０】
2018113583.tif 000012
を満たす。即ち、変換行列Ａと逆変換行列Ａ−１の積は、交換法則を満たし、単位行列となる。
【００５２】
この逆変換行列Ａ−１を数７に掛けることで、次の恒等式を得る。
【００５３】
【数１１】
2018113583.tif 000013
行列式が１である整数係数行列の変換行列Ａを乗算することで、ＮバイトからＮバイトへ可逆の操作が可能となる。
【００５４】
以上の操作を用いて、１バイト記号の出現頻度を偏らせることで、エントロピーを削減できることを説明する。簡単な例として、Ｎが２の場合を考える。データとして、０と１２８のみが現れる例を考える。データが
0,0,128,0,128,128,0,128,…
である場合、先頭から２バイト毎に記号を組にする。
【００５５】
(0,0),(128,0),(128,128),(0,128),…
２バイト毎の組は、(0,0),(0,128),(128,0),(128,128)の４組のいずれかに該当する。２バイトの組のそれぞれの出現頻度を調べ、図３に示すような結果を得たとする。
【００５６】
図３は、２バイトの組の出現頻度の結果例を示す図である。図３に示す組毎の出現頻度の結果７１は、２バイトの組それぞれの出現回数を示している。図３において、記号ベクトルは、２バイトの組を示す。出現回数は、組それぞれがデータに出現した回数を示している。
【００５７】
図３の出現頻度の結果７１では、組(0,0)の出現回数は「50」、組(0,128)の出現回数は「20」、組(128,0)の出現回数は「10」、組(128,128)の出現回数は「30」を示している。出現頻度の結果７１から、１バイト記号の出現頻度を得ることができる。
【００５８】
図４は、図３の結果例に基づく、１バイト記号の出現頻度の結果例を示す図である。図４に示す１バイト記号の出現頻度の結果７３は、１バイト記号のそれぞれの出現回数を示している。図４において、１バイト記号は、「0」と「128」のみを示す。出現回数は、各１バイト記号がデータに出現した回数を示す。
【００５９】
図４の出現頻度の結果７３では、１バイト記号「0」の出現回数は「130」、１バイト記号「128」の出現回数は「90」を示している。
【００６０】
ここで、第１実施例において記号出現頻度が変更される前のヒストグラムを示す。図５は、図４の結果例に基づく１バイト記号のヒストグラムを示す図である。図５に示すヒストグラム７５は、１バイト記号を横軸に示し、１バイト記号の出現頻度を縦軸に示している。
【００６１】
ヒストグラム７５は、図４の出現頻度の結果７３に基づき、０から２５５の１バイト記号のそれぞれの出現回数を頻度で示している。１バイト記号は「0」と「128」のみであるため、ヒストグラム７５は、１バイト記号「0」で頻度「130」を示し、１バイト記号「128」で頻度「90」を示したヒストグラムとなる。
【００６２】
図６は、図３の結果例に基づく１バイト記号の二次元のヒストグラムを示す図である。図６に示す二次元のヒストグラム７７は、２バイトの組の最初の値を第１要素の軸に示し、次の値を第２要素の軸に示し、組の出現頻度を縦軸に示している。
【００６３】
ヒストグラム７７は、図３の出現頻度の結果７１に基づき、２バイトの４つの組のそれぞれの出現回数を頻度で示している。したがって、ヒストグラム７５は、組(0,0)に対して頻度「50」を示し、組(0,128)に対して頻度「20」を示し、組(128,0)に対して頻度「10」を示し、組(128,128)に対して頻度「30」を示したヒストグラムとなる。
【００６４】
第１実施例では、このような２バイトの組を、数８に示した変換行列Ａを用いて変換し、出現頻度を偏らせることで、エントロピーを削減する。各２バイトは、
【００６５】
【数１２】
2018113583.tif 000014
のように変換される。数１２の変換により、２バイトの組の出現頻度が変化する。
【００６６】
図７は、変換後の２バイトの組の出現頻度の結果例を示す図である。図７に示す組毎の出現頻度の結果８１は、２バイトの組それぞれの出現回数を示している。記号ベクトル出現回数は、図３で説明した通りである。
【００６７】
図７の出現頻度の結果８１では、組(0,0)の出現回数は「50」、組(0,128)の出現回数は「30」、組(128,0)の出現回数は「20」、組(128,128)の出現回数は「10」を示している。出現頻度の結果８１は、図３に示す変換前の出現頻度の結果７１とは異なっている。
【００６８】
図８は、図７の結果例に基づく、変換後の１バイト記号の出現頻度の結果例を示す図である。図８に示す１バイト記号の出現頻度の結果８３は、１バイト記号のそれぞれの出現回数を示している。図８において、１バイト記号は、「0」と「128」のみを示す。出現回数は、各１バイト記号がデータに出現した回数を示す。
【００６９】
図８の出現頻度の結果８３では、１バイト記号「0」の出現回数は「150」、１バイト記号「128」の出現回数は「70」を示している。出現頻度の結果８３は、図４に示す変換前の出現頻度の結果７３とは異なっている。
【００７０】
ここで、第１実施例において記号出現頻度が変更された後のヒストグラムを示す。図９は、図８の結果例に基づく、記号出現頻度変更後の、１バイト記号のヒストグラムを示す図である。図９に示すヒストグラム８５は、１バイト記号を横軸に示し、１バイト記号の出現頻度を縦軸に示している。
【００７１】
ヒストグラム８５は、図８の出現頻度の結果８３に基づき、０から２５５の１バイト記号のそれぞれの出現回数を頻度で示している。１バイト記号は「0」と「128」のみであるため、ヒストグラム８５は、１バイト記号「0」で頻度「150」を示し、１バイト記号「128」で頻度「70」を示したヒストグラムとなる。
【００７２】
図５のヒストグラム７５と比べると、ヒストグラム８５では、１バイト記号「0」の出現頻度が高くなり、１バイト記号「128」の出現頻度が低くなっている。１バイト記号「0」に偏らせた状態を示している。
【００７３】
図１０は、図７の結果例に基づく、記号出現頻度変更後の１バイト記号の二次元のヒストグラムを示す図である。図１０に示す二次元のヒストグラム８７は、２バイトの組の最初の値を第１要素の軸に示し、次の値を第２要素の軸に示し、組の出現頻度を縦軸に示している。
【００７４】
ヒストグラム８７は、図７の出現頻度の結果８１に基づき、２バイトの４つの組のそれぞれの出現回数を頻度で示している。したがって、ヒストグラム８５は、組(0,0)に対して頻度「50」を示し、組(0,128)に対して頻度「30」を示し、組(128,0)に対して頻度「20」を示し、組(128,128)に対して頻度「10」を示したヒストグラムとなる。
【００７５】
次に、１バイト記号のエントロピーについて説明する。エントロピーは、
【００７６】
【数１３】
2018113583.tif 000015
のように定義される。数１３において、piは、記号「ｉ」の出現回数を全体の記号の数で割った値を示し、各記号の出現確率を表わす。出現頻度の変更前のエントロピーは、
【００７７】
【数１４】
2018113583.tif 000016
となる。一方で、出現頻度の変更後のエントロピーは、
【００７８】
【数１５】
2018113583.tif 000017
を示す。出現頻度の変更後のエントロピーは、出現頻度の変更前のエントロピーより減少している。
【００７９】
変換行列Ａは可逆行列であり、その逆行列は、
【００８０】
【数１６】
2018113583.tif 000018
で与えられる。この逆行列は、吐き出し法等によりコンピュータにより求めることが可能である。吐き出し法は、一般に、浮動小数演算を用いて実施されるため、丸め誤差が生じる可能性がある。しかし、逆変換行列Ａ−１が整数係数行列であることが分かっているため、計算の過程は、有理数を用いれば、最終結果は整数に約分される。
【００８１】
その為、コンピュータによる処理では、有理数により掃き出し法を用いることで、逆変換行列Ａ−１を求めることができる。また、有理数は分子と分母とを保持すれば良い。つまり、分子と分母は整数であるから、多倍長整数を用いれば全ての過程を丸め誤差なく計算できる。
【００８２】
＜３．エントロピー削減のための変換行列の探索方法＞
先の例により、第１実施例では、エントロピーを削減できることを説明した。次に、エントロピーを削減する変換行列Ａの求め方について説明する。
【００８３】
簡単のため、Ｎ＝２の場合で説明する。まず、次の行列Ｔ１及び行列Ｔ２を考える。
【００８４】
【数１７】
2018113583.tif 000019
非特許文献２によれば、任意の整数係数2-by-2行列は、行列Ｔ１と行列Ｔ２の積で表すことができる。つまり、整数係数2-by2行列の変換行列Ａは、適当な整数の列n1,n2,…,nmを用いて、
【００８５】
【数１８】
2018113583.tif 000020
と表すことができる。一方で、行列Ｔ１と行列Ｓ
【００８６】
【数１９】
2018113583.tif 000021
との積で表現するという定理が良く知られている。行列Ｓは、
【００８７】
【数２０】
2018113583.tif 000022
で表せる。したがって、同様に、任意の整数係数2-by-2行列を、行列Ｔ１と行列Ｔ２の積で表すことを導ける。
【００８８】
第１実施例では、行列Ｔ１と行列Ｔ２とを乗算することで、効果的にエントロピーを削減する。一般に、
【００８９】
【数２１】
2018113583.tif 000023
であり、探索すべき行列の数は無限大である。しかし、第１実施例では、２５６で剰余を取るため、任意の二バイト文字ｖ
【００９０】
【数２２】
2018113583.tif 000024
に対し、
【００９１】
【数２３】
2018113583.tif 000025
である。その為、整数係数2-by-2行列は、適当な０から２５６までの整数の列n1,n2,…,nmを用いて、
【００９２】
【数２４】
2018113583.tif 000026
を探索するだけで十分である。
【００９３】
さらに、
【００９４】
【数２５】
2018113583.tif 000027
である為、探索すべき行列の数は有限であり、０から２５６までの整数の列n1,n2,…,nmは有限の長さである。
【００９５】
データが次の様なバイト列（ａ）であるとき、
d1d2d3…                ----（ａ）
2-by-K行列Ｍに次の様に保持する。
【００９６】
【数２６】
2018113583.tif 000028
また、次の様に保持してもよい。
【００９７】
【数２７】
2018113583.tif 000029
以降は、数２６で説明し、この行列Ｍをデータ行列と呼称する。データ行列Ｍに対し、行列Ｔ１を０回から２５５回乗算する。
【００９８】
【数２８】
2018113583.tif 000030
数２８の全パターンにおいて変化するのは、第一成分だけである。
【００９９】
すなわち、エントロピーが変化するのは、第一成分の１バイト記号のエントロピーだけである。その為、数２８に示した全てのパターンの内、第一成分の１バイト記号のエントロピーが最も小さい値となるパターンを探す。特定したパターンの行列Ｔ１の乗算回数をα1とする。
【０１００】
【数２９】
2018113583.tif 000031
に対し、行列Ｔ１を０回から２５５回乗算する。
【０１０１】
【数３０】
2018113583.tif 000032
数３０の全パターンにおいて変化するのは、第二成分だけである。
【０１０２】
すなわち、エントロピーが変化するのは、第二成分の１バイト記号のエントロピーだけである。その為、数３０に示した全てのパターンの内、第二成分の１バイト記号のエントロピーが最も小さい値となるパターンを探す。特定したパターンの行列Ｔ２の乗算回数をα2とする。
【０１０３】
以上の手続きを、例えば３回実施した場合、１回目では、行列Ｔ１の乗算回数α1及び行列Ｔ２の乗算回数α2を得て、
【０１０４】
【数３１】
2018113583.tif 000033
を得る。２回目では、行列Ｔ１の乗算回数α3及び行列Ｔ２の乗算回数α4を得て、
【０１０５】
【数３２】
2018113583.tif 000034
を得る。３回目では、行列Ｔ１の乗算回数α5及び行列Ｔ２の乗算回数α6を得て、
【０１０６】
【数３３】
2018113583.tif 000035
を得る。任意の回数実施した場合の行列Ｍ’は、
【０１０７】
【数３４】
2018113583.tif 000036
で表す。
【０１０８】
数３４は、2-by-K行列であるから、
【０１０９】
【数３５】
2018113583.tif 000037
と表せる。数３２の全ての成分ｄｉ’（ｉ＝１，２，…）は２Ｋバイトで表現される。各成分ｄｉ’は、
【０１１０】
【数３６】
2018113583.tif 000038
と表せ、０から２５５の整数である。
【０１１１】
数３４より、変換行列Ａは、
【０１１２】
【数３７】
2018113583.tif 000039
である。
【０１１３】
行列Ｍ’を構成する１バイト記号達（複数の１バイト記号）に対して、出現頻度が偏る（エントロピーが減少する）ように変更したため、数１４及び数１５で説明したように、元の行列Ｍを構成する１バイト記号達のエントロピーより減少している。これにより、１バイト記号のエントロピーが削減される。
【０１１４】
バイト列（ａ）に復元する場合には、行列Ｔ１及び行列Ｔ２のそれぞれのべき数（０から２５５）を示すα1,α2,...,αmのｍバイトが必要である。以下、α1,α2,...,αmを指数列という。この情報をヘッダに記憶しておき、データ全体のエントロピーを削減するための変更後のデータをボディに記憶する。格納形式の詳細は、図１１で説明する。
【０１１５】
第１実施例において、上述したように、変換行列Ａを、αiでべき乗した行列Ｔ１とαi+1でべき乗した行列Ｔ２とを交互にｍ回乗算して定めることが好ましいが、行列Ｔ１又は行列Ｔ２のいずれか一方の行列で定めてもよい。即ち、所定回数べき乗した行列Ｔ１で変換行列Ａを定めてもよく、また、所定回数べき乗した行列Ｔ２で変換行列Ａを定めてもよい。
【０１１６】
上述した第１実施例に係る手法は、全てコンピュータにより実現可能である。また、２次元ではなく任意のＮ次元に対して、第１実施例に係る手法はコンピュータにより実現可能である。例えば、Ｎが３の場合、上記の例を、第一成分と第二成分とからなる２次元空間で実施し、その結果に対し第二成分と第三成分の成す二次元空間で実施することができる。
【０１１７】
＜４．エントロピー削減データの格納形式＞
第１実施例では、エントロピーを削減したデータは、図１１に示すような格納形式で保持される。
【０１１８】
図１１は、格納形式の例を示す図である。第１実施例において、元のバイト列（ａ）をエントロピーを削減した削減後データ６を格納するための格納形式２は、ヘッダ３とボディ４とを有する。削減後データ６が、格納形式２により、後述される記憶部１３０の格納領域９（図１３）に保持される。
【０１１９】
ヘッダ３は、識別子、次元情報、指数個数、指数列等のデータを記憶する。識別子は、ボディ４が変更後のデータを記憶していることを示す情報である。識別子は、例えば４バイト記号で示される。次元情報は、実施した次元数を示す。２次元で実施した場合、次元情報は「２」を示す。
【０１２０】
指数列長さは、行列Ｔ１及び行列Ｔ２のそれぞれのべき数（０から２５５）を表わす指数列α1,α2,…,αmの長さ（ｍバイト）を示す。指数列は、α1,α2,…,αmを示す。各α1,α2,…,αmは１バイトずつで示され、指数列全体でｍバイトを要する。
【０１２１】
ボディ４は、先ず、2-by-K行列Ｍ’の各成分で表される削減後データ６を保持する。削減後データ６は、元のバイト列（ａ）のd1,d2,d3…に従って、d1’,d2’,…,d2K’の順で保持される。また、元のバイト列（ａ）が２の倍数でなければ、その余りの１バイトを保持する。削減後データ６の圧縮後には、圧縮されたデータがボディ４に記憶される。
【０１２２】
＜５．データの圧縮＞
第１実施例では、ボディ４に記憶されている、エントロピーを削減した削減後データ６を取得して、取得した削減後データ６を、算術符号化等の公知の可逆圧縮技術を用いて圧縮する。ボディ４は、圧縮データ７で置き換えられる。
【０１２３】
＜６．データの解凍＞
算術符号化等の公知の可逆圧縮技術に対応する解凍技術を用いて、圧縮されたデータを解凍する。解凍データ８は、エントロピーを削減した削減後データ６に相当する。
【０１２４】
削減後データ６に対し、エントロピー削減と逆の手順を行う。詳細を以下で説明する。
【０１２５】
簡単のため、二次元の場合で説明する。図１１に示すように格納形式２のヘッダ３には、行列Ｔ１及び行列Ｔ２のそれぞれのべき数を示す指数列α1,α2,…,αmのｍバイトデータを読み出して、指数列α1,α2,…,αmに基づいて、解凍後のデータを記憶部１３０（図１２）に
【０１２６】
【数３８】
2018113583.tif 000040
のように展開する。数３８は、コンピュータにより実行可能である。
【０１２７】
また、数３８は、エントロピー削減の逆操作である。なぜなら、
【０１２８】
【数３９】
2018113583.tif 000041
であり、行列Ｔ２に対しても同様の関係が成り立つ。したがって、
【０１２９】
【数４０】
2018113583.tif 000042
である。これにより、元のデータ（バイト列（ａ））を得られる。
【０１３０】
＜７．元データへの復元＞
数４０から得られた行列Ｍを記憶した領域から、行列Ｍの要素を所定順に読み出すことで、バイト列（ａ）、即ち、元のデータを取得する。上述した手法に基づく第１実施例は、図１２に示すような情報処理装置１００により実現される。
【０１３１】
図１２は、情報処理装置のハードウェア構成図である。図１２は、情報処理装置のハードウェア構成を示す図である。図１２において、情報処理装置１００は、コンピュータによって制御される情報処理装置であって、ＣＰＵ（Central  Processing  Unit）１１と、主記憶装置１２と、補助記憶装置１３と、入力装置１４と、表示装置１５と、通信Ｉ／Ｆ（インターフェース）１７と、ドライブ装置１８とを有し、バスＢに接続される。
【０１３２】
ＣＰＵ１１は、主記憶装置１２に格納されたプログラムに従って情報処理装置１００を制御するプロセッサに相当する。主記憶装置１２には、ＲＡＭ（Random  Access  Memory）、ＲＯＭ（Read  Only  Memory）等が用いられ、ＣＰＵ１１にて実行されるプログラム、ＣＰＵ１１での処理に必要なデータ、ＣＰＵ１１での処理にて得られたデータ等を記憶又は一時保存する。
【０１３３】
補助記憶装置１３には、ＨＤＤ（Hard  Disk  Drive）等が用いられ、各種処理を実行するためのプログラム等のデータを格納する。補助記憶装置１３に格納されているプログラムの一部が主記憶装置１２にロードされ、ＣＰＵ１１に実行されることによって、各種処理が実現される。
【０１３４】
入力装置１４は、マウス、キーボード等を有し、ユーザが情報処理装置１００による処理に必要な各種情報を入力するために用いられる。表示装置１５は、ＣＰＵ１１の制御のもとに必要な各種情報を表示する。入力装置１４と表示装置１５とは、一体化したタッチパネル等によるユーザインタフェースであってもよい。通信Ｉ／Ｆ１７は、有線又は無線などのネットワークを通じて通信を行う。通信Ｉ／Ｆ１７による通信は無線又は有線に限定されるものではない。  
情報処理装置１００によって行われる処理を実現するプログラムは、例えば、ＣＤ−ＲＯＭ（Compact  Disc  Read-Only  Memory）等の記憶媒体１９によって情報処理装置１００に提供される。
【０１３５】
ドライブ装置１８は、ドライブ装置１８にセットされた記憶媒体１９（例えば、ＣＤ−ＲＯＭ等）と情報処理装置１００とのインターフェースを行う。
【０１３６】
また、記憶媒体１９に、後述される本実施の形態に係る種々の処理を実現するプログラムを格納し、この記憶媒体１９に格納されたプログラムは、ドライブ装置１８を介して情報処理装置１００にインストールされる。インストールされたプログラムは、情報処理装置１００により実行可能となる。
【０１３７】
尚、プログラムを格納する記憶媒体１９はＣＤ−ＲＯＭに限定されず、コンピュータが読み取り可能な、データの構造（structure）を有する１つ以上の非一時的（non-transitory）な、有形（tangible）な媒体であればよい。コンピュータ読取可能な記憶媒体として、ＣＤ−ＲＯＭの他に、ＤＶＤ（Digital  Versatile  Disk）ディスク、ＵＳＢメモリ等の可搬型記録媒体、フラッシュメモリ等の半導体メモリであっても良い。
【０１３８】
図１３は、第１実施例における情報処理装置の機能構成例を示す図である。図１３において、情報処理装置１００は、主に、圧縮処理部１１０と、解凍処理部１２０とを有する。また、記憶部１３０には、元データ１、ヘッダ情報５、削減後データ６、圧縮データ７、解凍データ８等が記憶される。
【０１３９】
少なくとも、ヘッダ情報５、削減後データ６、圧縮データ７、及び解凍データ８は、図１１に示す格納形式２に従って、格納領域９に記憶される。圧縮処理部１１０と、解凍処理部１２０とは、それぞれ別の情報処理装置１００に実装されてもよい。格納領域９は、格納形式２のデータファイルに相当する。
【０１４０】
圧縮処理部１１０は、元データ１に対して、本実施例によるエントロピーを削減したデータに変換して、エントロピーが削減されたデータを圧縮する処理部である。データ圧縮処理中のデータ容量の増大を抑制することができる。
【０１４１】
圧縮処理部１１０は、圧縮要求受付部１１１と、変換行列探索部１１３と、エントロピー削減部１１４と、データ圧縮部１１５とを有する。圧縮要求受付部１１１と、変換行列探索部１１３と、エントロピー削減部１１４と、データ圧縮部１１５とは、ＣＰＵ１１がそれぞれに対応するプログラムを実行するこにより行われる処理により実現される。
【０１４２】
圧縮要求受付部１１１は、ユーザからデータ圧縮要求３１を受け付けると、データ圧縮要求３１に含まれている元データ１を記憶部１３０に記憶し、変換行列探索部１１３に元データ１の圧縮要求を行う。ユーザは、記憶部１３０に記憶されている元データ１を指定してデータ圧縮要求３１を行ってもよい。元データ１は、データファイルにより与えられてもよい。その場合、元データ１は、データファイル内の圧縮対象のデータに相当する。
【０１４３】
変換行列探索部１１３は、圧縮要求受付部１１１からの圧縮要求に応じて、記憶部１３０に記憶された元データ１に対して変換行列探索処理を行う。変換行列探索処理により、元データ１を表わす行列Ｍに、行列Ｔ１及び行列Ｔ２を交互に掛ける際の行列Ｔ１及び行列Ｔ２それぞれ自身の乗算回数を示す指数αiを取得することで、指数列α1,α2,…,αm及び指数列長さを得る。
【０１４４】
変換行列探索処理の結果に基づいて、ヘッダ情報５が格納領域９に格納形式２で記憶される。ヘッダ情報５は、識別子、次元情報、指数列長さ、指数列α1,α2,…,αm等を含む。
【０１４５】
エントロピー削減部１１４は、格納領域９から指数列α1,α2,…,αmを取得して、数３４により行列Ｍ’の各成分、即ち、削減後データ６を取得する。削減後データ６は、格納領域９のボディ４に格納される。
【０１４６】
データ圧縮部１１５は、エントロピー削減部１１４によって格納領域９に記憶された削減後データ６に対してデータ圧縮処理を行い、圧縮データ７を格納領域９のボディ４に格納する。削減後データ６を圧縮データ７で置き換える。データ圧縮処理は、算術符号化等によりデータ圧縮を行なえばよい。
【０１４７】
解凍処理部１２０は、圧縮データ７を解凍し、エントロピーを増大させて元データ１を復元する。本実施例では、可逆的にデータ圧縮が行われるため、元データ１を完全に復元できる。
【０１４８】
解凍処理部１２０は、解凍要求受付部１２１と、データ解凍部１２２と、エントロピー増大部１２３とを有する。解凍要求受付部１２１と、データ解凍部１２２と、エントロピー増大部１２３とは、ＣＰＵ１１がそれぞれに対応するプログラムを実行するこにより行われる処理により実現される。
【０１４９】
解凍要求受付部１２１は、ユーザからデータ解凍要求３２を受け付けると、データ解凍要求３２で指定された格納領域９の圧縮データ７の解凍要求をデータ解凍部１２２に行う。ユーザは、格納形式２に基づいて圧縮データ７が記憶された外部記憶領域を指定して、データ解凍要求３２を行ってもよい。この場合、外部記憶領域の圧縮データ７が情報処理装置１００に読み込まれて、記憶部１３０の格納領域９に記憶される。
【０１５０】
データ解凍部１２２は、解凍要求受付部１２１からの圧縮データ７の解凍要求に応じて、格納領域９内の圧縮データ７に対してデータ解凍処理を行い、解凍データ８を取得する。格納領域９のボディ４は、解凍データ８、即ち、削減後データ６に置き換えられる。データ解凍処理は、算術符号化等により圧縮データ７を解凍すればよい。
【０１５１】
エントロピー増大部１２３は、データ解凍処理の終了に応じて、解凍データ８に対してエントロピーを増大させる処理を施すことで、元データ１を復元する。エントロピー増大部１２３は、格納領域９のヘッダ３から次元情報、指数列等を取得して、エントロピーを増大させる逆変換行列Ａ−１を生成して、解凍データ８に乗算することで、元データ１を復元する。ヘッダ３の識別子が、エントロピーの削減を行っていないことを示す場合には、エントロピー増大部１２３によるエントロピー増大処理は抑止される。
【０１５２】
図１４は、第１実施例における圧縮処理の概要を説明するためのフローチャートである。図１４において、ユーザが情報処理装置１００に対してデータ圧縮要求３１を行うと、圧縮処理部１１０の圧縮要求受付部１１１が、データ圧縮要求３１を受け付ける（ステップＳ２０１）。圧縮要求受付部１１１は、変換行列探索部１１３に元データ１の圧縮要求を通知する。
【０１５３】
変換行列探索部１１３は、圧縮要求受付部１１１からの圧縮要求の通知に応じて、元データ１に対してデータ圧縮処理時のデータ量を削減する最適な変換行列Ａ（数３７）を求める変換行列探索処理を行う（ステップＳ２０２）。
【０１５４】
変換行列Ａが得られると、エントロピー削減部１１４は、変換行列Ａを用いて元データ１に対してエントロピーを削減するエントロピー削減処理を行う（ステップＳ２０３）。
【０１５５】
そして、削減後データ６を得ると、データ圧縮部１１５が、削減後データ６に対してデータ圧縮処理を行う（ステップＳ２０４）。圧縮データ７が格納領域９のボディ４に格納される。
【０１５６】
図１５は、第１実施例における変換行列探索処理を説明するためのフローチャート図である。図１５では、次元Ｎが２の場合で説明するが、本実施例はＮ＝２に限定されない。
【０１５７】
図１５において、変換行列探索部１１３は、元データ１を読み込んで行列で表して2-by-K行列Ｍ（以下、行列Ｍという）の初期値として設定する（ステップＳ２１０）。変換行列探索部１１３は、また、変数Ｌ，ｉ、ｄ、及びｐを１に初期化する（ステップＳ２１１）。
【０１５８】
変換行列探索部１１３は、変数Ｌが２以下であるか否かを判定する（ステップＳ２１２）。変数Ｌが２以下である場合（ステップＳ２１２のＹＥＳ）、変換行列探索部１１３は、変数ｄが２より大か否かを判定する（ステップＳ２１３）。変数ｄが２以下の場合（ステップＳ２１３のＮＯ）、変換行列探索部１１３は、変数ｄが１であるか否かを判断する（ステップＳ２１４）。
【０１５９】
変数ｄが１の場合（ステップＳ２１４のＹＥＳ）、変換行列探索部１１３は、変数Ｔに行列Ｔ１を設定し（ステップＳ２１５）、ステップＳ２１７へと進む。一方、変数ｄが１でない場合（ステップＳ２１４のＮＯ）、変換行列探索部１１３は、変数Ｔに行列Ｔ２を設定し（ステップＳ２１６）、ステップＳ２１７へと進む。
【０１６０】
変換行列探索部１１３は、変数ｐが２５６より大きいか否かを判断する（ステップＳ２１７）。変数ｐが２５６以下の場合（ステップＳ２１７のＮＯ）、変換行列探索部１１３は、変数Ｔを行列Ｍにｐ回乗算した行列を変数Ｍ２に設定し、変数Ｍ２の各成分を２５６で剰余を取る（ステップＳ２１８）。
【０１６１】
また、変換行列探索部１１３は、変数Ｍ２の第ｄ行の数値のエントロピーを計算し、得られた値を変数ｅ＿ｐに設定する（ステップＳ２１９）。そして、変換行列探索部１１３は、変数ｐを１インクリメントして（ステップＳ２２０）、ステップＳ２１７へと戻る。
【０１６２】
一方、変数ｐが２５６より大きい場合（ステップＳ２１７のＹＥＳ）、変換行列探索部１１３は、変数ｅ＿１、ｅ＿２、・・・、ｅ＿２５６の中で最も小さい変数ｅ＿ｊを特定し、αiにｊを代入する（ステップＳ２２３）。
【０１６３】
そして、変換行列探索部１１３は、変数Ｔを行列Ｍにｊ回乗算した行列の各成分を２５６で剰余を取り、得られた行列を改めて行列Ｍとする（ステップＳ２２４）。変換行列探索部１１３は、その後、変数ｄ及び変数ｉを１インクリメントし、変数ｐを１に設定して（ステップＳ２２５）、ステップＳ２１３へと戻り、上述同様の処理を繰り返す。
【０１６４】
ところで、変数Ｌが２より大の場合（ステップＳ２１２のＮＯ）、変換行列探索部１１３は、ヘッダ情報５を記憶部１３０の格納領域９のヘッダ３に格納する（ステップＳ２２２）。得られた指数列α1,α2,...,αmと指数列長さとがヘッダ情報５に含まれる。そして、この変換行列探索処理を終了する。
【０１６５】
図１６は、第１実施例におけるエントロピー削減処理を説明するためのフローチャート図である。図１６において、エントロピー削減部１１４は、格納領域９のヘッダ３から指数列長さに基づいて、指数列を読み（ステップＳ２５１）、変数ｉに１を設定し初期化する（ステップＳ２５２）。指数列長さをｍとする。
【０１６６】
エントロピー削減部１１４は、変数ｉが奇数か否かを判断する（ステップＳ２５３）。変数ｉが奇数の場合（ステップＳ２５３のＹＥＳ）、エントロピー削減部１１４は、行列Ｔ１を行列Ｍへαi回乗算して、得られた行列の各成分を２５６で剰余を取り、Ｍに設定し（ステップＳ２５４）、ステップＳ２５６へと進む。
【０１６７】
一方、変数ｉが偶数の場合（ステップＳ２５３のＮＯ）、エントロピー削減部１１４は、行列Ｔ２を行列Ｍへαi回乗算して、得られた行列の各成分を２５６で剰余を取り、Ｍに設定し（ステップＳ２５５）、ステップＳ２５６へと進む。
【０１６８】
エントロピー削減部１１４は、変数ｉがｍ（指数列長さ）以下であるか否かを判断する（ステップＳ２５７）。変数ｉがｍ以下の場合（ステップＳ２５７のＹＥＳ）、エントロピー削減部１１４は、ステップＳ２５３へと進み、上述した同様の処理を繰り返す。
【０１６９】
一方、変数ｉがｍより大きい場合（ステップＳ２５７のＮＯ）、エントロピー削減部１１４は、格納形式２に従って、格納領域９のボディ４に、エントロピーが削減された行列Ｍの成分データを示す削減後データ６を格納する（ステップＳ２５８）。そして、エントロピー削減部１１４は、このエントロピー削減処理を終了する。圧縮データ７が格納された格納領域９は、データファイルに相当する。
【０１７０】
削減後データ６は、データ圧縮部１１５により圧縮され、圧縮データ７として、格納領域９のボディ４に記憶される。
【０１７１】
次に、解凍処理部１２０による解凍処理の概要について説明する。図１７は、第１実施例における解凍処理を説明するためのフローチャート図である。図１７において、解凍処理部１２０では、解凍要求受付部１２１が、ユーザからデータ解凍要求３２を受け付けると（ステップＳ２７１）、データ解凍部１２２に圧縮データ７の解凍要求が通知される。
【０１７２】
データ解凍部１２２は、格納領域９のボディ４から圧縮データ７を読み込んでデータ解凍処理を行う（ステップＳ２７２）。解凍データ８はボディ４に格納される。解凍データ８が得られると、エントロピー増大部１２３が、エントロピー増大処理を行う（ステップＳ２７３）。エントロピー増大処理により、元データ１が復元される（ステップＳ２７４）。
【０１７３】
図１８は、第１実施例におけるエントロピー増大処理を説明するためのフローチャート図である。図１８において、エントロピー増大部１２３は、格納領域９のヘッダ３から、指数列長さに基づいて、指数列α1,α2,...,αmを読み込む（ステップＳ２８１）。指数列長さがｍに設定される。
【０１７４】
また、エントロピー増大部１２３は、解凍データ８、即ち、削減後データ６を行列で表してＭに設定する（ステップＳ２８２）。そして、エントロピー増大部１２３は、変数ｉを１に初期設定する（ステップＳ２８３）。
【０１７５】
エントロピー増大部１２３は、変数ｉがｍ（指数列長さ）より大きいか否かを判断する（ステップＳ２８４）。変数ｉがｍ以下の場合（ステップＳ２８４のＮＯ）、エントロピー増大部１２３は、変数ｉが奇数か否かを判断する（ステップＳ２８５）。
【０１７６】
変数ｉが奇数の場合（ステップＳ２８５のＹＥＳ）、エントロピー増大部１２３は、変数Ｔに行列Ｔ１を設定し（ステップＳ２８６）、ステップＳ２８８へと進む。一方、変数ｉが偶数の場合（ステップＳ２８５のＮＯ）、エントロピー増大部１２３は、変数Ｔに行列Ｔ２を設定し（ステップＳ２８７）、ステップＳ２８８へと進む。
【０１７７】
エントロピー増大部１２３は、変数Ｔを行列Ｍに（２５６−αi）回乗算し、得られた行列の各成分を２５６で剰余を取って得た行列をＭとする（ステップＳ２８８）。そして、エントロピー増大部１２３は、変数ｉを１インクリメントして（ステップＳ２８９）、ステップＳ２８４へと戻り、上述した同様の処理を繰り返す。
【０１７８】
一方、変数ｉがｍより大きい場合（ステップＳ２８４のＹＥＳ）、エントロピー増大部１２３は、元データ１を出力し（ステップＳ２９０）、このエントロピー増大処理を終了する。
【０１７９】
上述したように、第１実施例では、データのバイト数を増やさずに、１バイト文字の出現頻度を偏らせることで、エントロピーを削減することができる。上記では、Ｎ＝２の場合で説明したが、Ｎが３以上であっても、第１実施例を適用可能である。
【０１８０】
次に、第１実施例におけるエントロピー削減を効率化する第２実施例について説明する。第１実施例では、エントロピーを下げるための変換行列Ａを探索する方法について説明した。変換行列Ａの探索では、行列Ｔ１及び行列Ｔ２を複数回乗算していくが、その全ての乗算に於いて常にエントロピーが下がるわけでは無い。エントロピーの増大には、二つの要因がある。
【０１８１】
一つは、出現する記号の種類が増えることによるエントロピーの増大である。もう一つは、記号種類は同じだが、出現する頻度が偏らず（即ち、どの記号も同じような出現頻度を示し）、エントロピーが増大することである。ここでは、前者の記号種類の増大を抑える方法について説明する。
【０１８２】
第１実施例では、１バイト文字をそのまま整数値として扱っていた。つまり、「0xF0」は「240」、「0x80」は「80」、という整数値として扱っている。英数字「a」は0x61であり、９６である。
【０１８３】
一例として、データがASCII文字「a」と「b」とから成立しているテキストデータを考える。文字「a」と「b」とは、それぞれ、整数値の「96」と「97」とにより表される。この場合m=1,2,...,255に対して、
【０１８４】
【数４１】
2018113583.tif 000043
を乗算すると、生成される１バイト記号は、
96,(96+m*97)%256,97,(97+m*96)%256
である。特に、(96+m*97)%256と(97+m*96)%256は、ｍが０でない限り、「96」と「97」以外の数値を取ってしまう。例えば、ｍ＝１なら「193」と「193」、ｍ＝２なら「34」と「33」といった具合である。
【０１８５】
ｍが０であることは、何も演算しないことと同じである為、エントロピーは上がりも下がりもしない。ｍを０でない値にして、エントロピーを下げようとしているにも係らず、「96」と「97」以外の記号が出現してしまう。「96」と「97」の出現頻度が極端に偏っている場合以外は、１バイト記号のエントロピーは上昇してしまう。その為、第１実施例における変換行列Ａの探索では、エントロピーが減少する変換行列Ａを見つけることが困難になる場合がある。
【０１８６】
以下の説明では、
【０１８７】
【数４２】
2018113583.tif 000044
という行列を使用する。
【０１８８】
発明者は、「0」、「128」、「64」、及び「198」が、２５６の２ｎ分の１の整数倍であり、このような点は、トーラス上の行列演算結果が、同一記号内で閉じる性質があり、元データ１に含まれない１バイト記号を生成することがない、ことに着目した。
【０１８９】
また、エントロピーは出現する記号の種類が増えると増大する傾向がある。しかし、以下に説明する第２実施例における数値変換テーブルを用いてデータの数値を変換しておくことで、記号の増大を抑止することができ、したがって、エントロピーの増大を抑えることができる。第２実施例は、ASCII記号の可読文字からなるテキストデータの場合により効果を奏する。
【０１９０】
第２実施例における情報処理装置１００のハードウェア構成は、図１２に示す通りであるため、その説明を省略する。
【０１９１】
図１９は、第２実施例における機能構成例を示す図である。図１９において、第１実施例との違いは、圧縮処理部１１０−２において、数値変換テーブル作成部１０９と、数値変換部１１２とが追加され、解凍処理部１２０−２において、逆数値変換部１２４が追加されている点である。
【０１９２】
また、記憶部１３０は、更に、数値変換テーブル５１、変換後データ１−２等を記憶する。それ以外の処理部及びデータは、第１実施例と同様であるため、同一の符号を付し、その説明を省略する。
【０１９３】
図１９に示す、第２実施例における数値変換テーブル作成部１０９は、元データ１の１バイト記号を、周期２５６の２ｎ分の１の整数倍に写像するための数値変換テーブル５１を作成する。
【０１９４】
数値変換テーブル５１は、格納形式２に従って格納領域９のヘッダ３に保持される。数値変換テーブル５１は、後述される数値変換テーブル５１ａ（図２０）又は数値変換テーブル５１ｂ（図２３）である。数値変換テーブル５１は、データ圧縮要求３１に応じて、数値変換テーブル作成部１０９により、数値変換部１１２による数値変換処理の前に作成されてもよいし、予め、ユーザの指示に応じて、作成されてもよい。
【０１９５】
また、数値変換部１１２は、元データ１の１バイト記号の種類ごとに出現回数をカウントし、出現回数の多い順に１バイト記号の種類を並べ替えて、出現頻度の高い順に、１バイト記号の種類を数値変換テーブル５１の先頭から順に置き換える。元データ１において、１バイト記号の種類ごとに、出現頻度に応じて数値変換テーブル５１に基づいて置き換えられた変換後データ１−２が、格納形式２に従って格納領域９のヘッダ３とボディ４の間に記憶される。
【０１９６】
変換行列探索部１１３によって、変換後データ１−２に対して、変換行列Ａが探索され、エントロピー削減部１１４によって、削減後データ６が生成され、データ圧縮部１１５によって削減後データ６が圧縮される。
【０１９７】
解凍処理部１２０−２では、データ解凍部１２２によって得られた解凍データ８から、エントロピー増大部１２３がエントロピーを増大させた増大後データ１−２’が生成される。増大後データ１−２’は、変換後データ１−２に相当する。
【０１９８】
増大後データ１−２’の取得に応じて、逆数値変換部１２４が、１バイト記号の種類ごとの出現頻度に応じて、増大後データ１−２’を先頭から順に数値ごとに変換前の１バイト記号へと逆変換することによって、元データ１を復元する。
【０１９９】
元データ１の１バイト記号を周期２５６の２ｎ分の１の整数倍に写像する数値変換テーブル５１について説明する。
【０２００】
図２０は、数値変換テーブルの一例を示す図である。図２０に示す数値変換テーブル５１ａは、単純に、０から開始して、周期２５６の２ｎ分の１の整数倍を順にリストしたテーブルである。数値変換テーブル５１ａの作成方法は、図２４のフローチャートで詳述される。
【０２０１】
数値変換テーブル５１ａを用いた場合、元データ１において、
出現頻度が最も高い１バイト記号が「０」、
出現頻度が２番目に高い１バイト記号が「１２８」、
出現頻度が３番目に高い１バイト記号が「６４」、
出現頻度が４番目に高い１バイト記号が「１９２」、
出現頻度が５番目に高い１バイト記号が「３２」、
出現頻度が６番目に高い１バイト記号が「９６」、
・・・
出現頻度が２５６番目に高い１バイト記号が「２５５」
に変換される。
【０２０２】
ここで、写像する写像先の数値について説明する。写像先の数値は、周期２５６の２ｎ分の１の整数倍であり、出現頻度が大きい程、対応するｎは小さい。
【０２０３】
周期２５６の２ｎ分の１の整数倍の点が非常に良い性質を持つことを説明する。図２１は、トーラスの例を示す図である。図２１において、二次元トーラス中の傾きが１の閉じた直線を描いた図である。
【０２０４】
図２１を参照して、具体的に説明すると、直線ＬＮ＿１は、点(0,0)を通り、点(128,128)や点(192,192)を通る直線である。直線ＬＮ＿２は、点(64,0)、点(128,64)、点(192,128)、及び点(0,192)を通る直線である。直線ＬＮ＿３は、点(128,0)、点(192,64)、点(0,128)、及び点(64,192)を通る直線である。直線ＬＮ＿４は、点(192,0)、点(0,64)、点(64,128)、及び点(128,192)を通る直線である。
【０２０５】
仮に、行列Ｔ１−１
【０２０６】
【数４３】
2018113583.tif 000045
を乗算した場合、これらの直線の上にある点は、同じ第一成分の値を持つ。例えば、直線ＬＮ＿２上の点は、第一成分が６４になる。
【０２０７】
例えば、元データ１に含まれる記号が４種類のみである場合、第２実施例では、記号の出現回数が高い順に、「０」、「１２８」、「６４」、及び「１９２」に写像される。行列Ｔ１−１（数４３）を乗算した場合、これらの数値と異なる数値が出てくることは無い。さらに、m=0,2,...,255に対し、行列Ｔ１ｍ（数４１）を乗算しても、２５６での剰余を取る限り、上記４種類の数値以外の数値は現れない。
【０２０８】
この例のように、周期２５６の２ｎ分の１の整数倍の点は行列を乗算しても２５６での剰余を取ることで、それらの数値以外の数値は現れない性質がある。発明者は、この性質に着目し、図２０に示す数値変換テーブル５１ａを改良し、変換行列Ａを求める際に、エントロピーの上昇を抑え、エントロピーが減少する行列を求め易くした。
【０２０９】
図２２は、図２０の数値変換テーブルの改良例を示す図である。図２２に示す数値変換テーブル５１ｂは、単純に、０から開始して、周期２５６の２ｎ分の１の整数倍を順にリストした数値変換テーブル５１ａとは、周期２５６の２ｎ分の１の整数倍の値の出現順が異なっている。
【０２１０】
数値変換テーブル５１ｂでは、例えば、５番目に頻度の高い１バイト記号に「３２」を割り振り、６番目に頻度の高い１バイト記号に「２２４」を割り振る。図２０の数値変換テーブル５１ａでは、５番目に頻度の高い１バイト記号には同様に「３２」が割り振られるが、６番目に頻度の高い１バイト記号には「９６」が割り振られている。
【０２１１】
この理由を述べる。出現頻度を考えた場合、「３２」を含む数値は、(32,0)か(0,32)が最も多く現れると期待される。点(32,0)及び点(0,32)それぞれから斜め４５度の閉直線上の点について考察する。
【０２１２】
図２３は、「３２」を含む二次元トーラスの例を示す図である。図２３では、周期２５６とした、点(32,0)からの斜め４５度の閉直線ＬＮ＿５と、点(0,32)からの４５度の閉直線ＬＮ＿６とを示している。
【０２１３】
斜め４５度の閉直線ＬＮ＿５及びＬＮ＿６上の点で、「96」を含む点は、閉直線ＬＮ＿５では点(96,64)であり、閉直線ＬＮ＿６では点(64,96)であるのに対し、「224」を含む点は、閉直線ＬＮ＿６では点(0,224)であり、閉直線ＬＮ＿５では点(244,0)である。
【０２１４】
「64」と「96」の組は、数値変換テーブル５１ａでは３番目と６番目に出現頻度の高い記号の組であり、「0」と「244」の組は、数値変換テーブル５１ｂでは１番目と６番目に出現頻度の高い記号の組である。その為、数値変換テーブル５１ｂを参照した場合の「0」と「244」の組の方が、数値変換テーブル５１ａを参照した場合の「64」と「96」の組より現れやすい。
【０２１５】
故に、行列Ｔ１−１（数４３）を乗算し、斜め４５度の閉直線を縦に伸びる閉直線へ変換した際の「32」という１バイト記号の出現頻度の増大が期待されるのは、「0」と「244」の組である。出現頻度が５番目の「32」の次を「244」とすることで、エントロピー削減をより効率的に行える。
【０２１６】
上記の例では、５、６番目の１バイト記号の写像先について説明したが、１７、１８番目の１バイト記号の写像先についても同様のことが成り立つ。すなわち、数値変換テーブル５１ａの「8」の次の「24」は、数値変換テーブル５１ｂのように「8」の次に「248」とする。
【０２１７】
このようにすることで、変換行列探索部１１３によるエントロピーが減少する行列を見つけ易くすることができる。数値変換テーブル作成部１０９によって作成された数値変換テーブル５１は、変換後データ１−２を格納する格納領域９のヘッダ３に格納される。
【０２１８】
第２実施例では、１バイト記号の出現頻度に応じて、発明者により見出された数値変換テーブル５１を用いて、元データ１の１バイト記号を数値に変換する。第２実施例では、１バイト記号を扱い、周期を２５６とするが、任意のＸバイトからなる記号を扱い、周期をＸ×２５６としてもよい。２バイトの文字を扱う場合には、２５６×２５６となる。
【０２１９】
また、１バイトよりも小さい７ビットからなる記号を扱い、周期を２７＝１２８としてもよい。以下の説明では１バイト記号を扱い、周期を２５６とする。即ち、第２実施例は、任意のバイト又はビットに適応可能である。
【０２２０】
データに表れる１バイト記号を、それぞれの記号が現れる出現回数をカウントし、出現回数の多い順に並べ替える。一例として、図２２の数値変換テーブル５１ｂを用いた場合、元データ１は、
出現頻度の最も高い１バイト記号が「０」、
出現頻度の２番目に高い１バイト記号が「１２８」、
出現頻度の３番目に高い１バイト記号が「６４」、
出現頻度の４番目に高い１バイト記号が「１９２」、
出現頻度の５番目に高い１バイト記号が「３２」、
出現頻度の６番目に高い１バイト記号が「２２４」、
・・・
出現頻度の２５６番目に高い１バイト記号を「１２９」
に変換される。
【０２２１】
よって、変換後データ１−２は、２５６バイトで、元データ１の先頭から１バイト記号を整数値として見なしたときの位置に、同記号の変換後の数値を保持する。例えば、
0x00,  0x01,  0x02,  0x03,  ...
が
40,  128,  64,  192,  ...
に写像されるとき、２５６バイトは、
40,  128,  64,  192,  ...
で表され、１６進数では、
0x28,  0x80,  0x40,  0xC0,  ...
となる。この２５６バイトの情報は、第１実施例で説明した格納形式２に従って、ヘッダ３とボディ４の間に保持されればよい。数値から逆変換する際には、先頭からのバイト位置に基づいて元データ１を復元する。
【０２２２】
次に、数値変換テーブル作成部１０９による数値変換テーブル５１の作成処理について説明する。先ず、図２０の数値変換テーブル５１ａの作成処理を説明する。
【０２２３】
図２４は、図２０の数値変換テーブルの作成処理を説明するためのフローチャート図である。図２４において、数値変換テーブル作成部１０９は、データ圧縮要求３１に応じて、数値変換テーブル５１ａを作成しても良いし、予め、数値変換テーブル５１ａを作成してもよい。
【０２２４】
数値変換テーブル作成部１０９は、変数ｉに０を設定し、変数divisorに１を設定し、変数list1を空にする初期設定を行う（ステップＳ３０１）。変数ｉは、数値変換テーブル５１ａの先頭からの位置までのバイト数を示す。変数divisorは、ｉバイト位置における２のべき乗ｎを示す。変数list1は、数値変換テーブル５１ａを表わす。
【０２２５】
次に、数値変換テーブル作成部１０９は、変数ｉが２５６以上であるか否かを判断する（ステップＳ３０２）。変数ｉが２５６未満である場合（ステップＳ３０２のＮＯ）、数値変換テーブル作成部１０９は、変数ｉを超える最小の２のｎ乗を変数ｘに設定し（ステップＳ３０３）、
divisor  =  log_2(x)
kk  =  i  -  divisor/2
を計算する（ステップＳ３０４）。
【０２２６】
さらに、数値変換テーブル作成部１０９は、
mul  =  2*kk  +  1
を計算する（ステップＳ３０５）。
【０２２７】
よって、数値変換テーブル作成部１０９は、
256*mul  /  divisor
を算出することにより、出現頻度がｉ番目の写像先（２５６の２ｎ分の１の整数倍の値）を得て、list1に追加し（ステップＳ３０６）、変数ｉを１インクリメントして（ステップＳ３０７）、ステップＳ３０２へ戻り上述同様の処理を繰り返す。
【０２２８】
変数ｉが２５６以上である場合（ステップＳ３０２のＹＥＳ）、数値変換テーブル作成部１０９は、数値変換テーブル５１ａを格納形式２に従って、格納領域９のヘッダ１に記憶した後、この数値変換テーブル作成処理を終了する。
【０２２９】
図２４のフローチャートにより、図２０の数値変換テーブル５１ａにおいて、
・１番目（ｉ＝０）は、写像先「０」、
・２番目（ｉ＝１）は、写像先「１２８」、
・３番目（ｉ＝２）は、写像先「６４」、
・４番目（ｉ＝３）は、写像先「１９２」、
・５番目（ｉ＝４）は、写像先「３２」、
・６番目（ｉ＝５）は、写像先「９６」、
・・・・
・２５５番目（ｉ＝２５５）は、写像先「２５５」
に設定される。
【０２３０】
図２５は、図２２の数値変換テーブルの作成処理を説明するためのフローチャート図である。図２５において、数値変換テーブル作成部１０９は、データ圧縮要求３１に応じて、数値変換テーブル５１ａを作成しても良いし、予め、数値変換テーブル５１ｂを作成してもよい。
【０２３１】
数値変換テーブル作成部１０９は、変数ｉに０を設定し、変数divisorに１を設定し、変数list2を空にする初期設定を行う（ステップＳ４０１）。変数ｉは、数値変換テーブル５１ｂの先頭からの位置までのバイト数を示す。変数divisorは、ｉバイト位置における２のべき乗ｎを示す。変数list2は、数値変換テーブル５１ｂを表わす。
【０２３２】
次に、数値変換テーブル作成部１０９は、変数ｉが２５６以上であるか否かを判断する（ステップＳ４０２）。変数ｉが２５６未満である場合（ステップＳ４０２のＮＯ）、数値変換テーブル作成部１０９は、変数ｉを超える最小の２のｎ乗を変数ｘに設定し（ステップＳ４０３）、
divisor  =  log_2(x)
kk  =  i  -  divisor/2
を計算する（ステップＳ４０４）。
【０２３３】
そして、数値変換テーブル作成部１０９は、変数ｋｋが偶数か否かを判断する（ステップＳ４０５）。変数ｋｋが偶数の場合（ステップＳ４０５のＹＥＳ）、数値変換テーブル作成部１０９は、変数kkの値に１を加算した値を変数mulに設定して（ステップＳ４０６）、ステップＳ４０８へと進む。
【０２３４】
一方、変数ｋｋが奇数の場合（ステップＳ４０５のＮＯ）、数値変換テーブル作成部１０９は、変数divisorから変数kkを減算した値を変数mulに設定して（ステップＳ４０７）、ステップＳ４０８へと進む。
【０２３５】
数値変換テーブル作成部１０９は、
256*mul  /  divisor
を算出することにより、出現頻度がｉ番目の写像先（２５６の２ｎ分の１の整数倍の値）を得て、list2に追加する（ステップＳ４０９）、変数ｉを１インクリメントして（ステップＳ３０９）、ステップＳ４０２へ戻り上述同様の処理を繰り返す。
【０２３６】
変数ｉが２５６以上である場合（ステップＳ４０２のＹＥＳ）、数値変換テーブル作成部１０９は、数値変換テーブル５１ｂを格納形式２に従って、格納領域９のヘッダ１に記憶した後、この数値変換テーブル作成処理を終了する。
【０２３７】
図２５のフローチャートにより、図２２の数値変換テーブル５１ｂにおいて、
・１番目（ｉ＝０）は、写像先「０」、
・２番目（ｉ＝１）は、写像先「１２８」、
・３番目（ｉ＝２）は、写像先「６４」、
・４番目（ｉ＝３）は、写像先「１９２」、
・５番目（ｉ＝４）は、写像先「３２」、
・６番目（ｉ＝５）は、写像先「２２４」、
・・・・
・２５５番目（ｉ＝２５５）は、写像先「１２９」
に設定される。
【０２３８】
次に、第２実施例における圧縮処理部１１０−２による圧縮処理の概要を説明する。図２６は、第２実施例における圧縮処理の概要を説明するためのフローチャート図である。図２６において、ユーザが情報処理装置１００に対してデータ圧縮要求３１を行うと、圧縮処理部１１０−２の圧縮要求受付部１１１が、データ圧縮要求３１を受け付ける（ステップＳ５０１）。圧縮要求受付部１１１は、数値変換テーブル作成部１０９に元データ１の圧縮要求を通知する。
【０２３９】
圧縮要求受付部１１１からの圧縮要求に応じて、数値変換テーブル作成部１０９は、数値変換テーブル作成処理を行う（ステップＳ５０２）。数値変換テーブル作成処理は、図２４又は図２５のフローチャートに従って行われればよい。
【０２４０】
また、既に、数値変換テーブル５１が記憶部１３０の格納領域９に存在する場合には、この数値変換テーブル作成処理を省略してもよい。その後、数値変換テーブル作成部１０９は、数値変換部１１２へ元データ１の圧縮要求を通知する。
【０２４１】
数値変換テーブル作成部１０９は、格納領域９のヘッダ３から数値変換テーブル５１を取得し、元データ１の１バイト記号を変換する数値変換処理を行う（ステップＳ５０３）。変換後データ１−２が格納領域９のヘッダ３とボディ４の間に記憶される。そして、数値変換テーブル作成部１０９は、変換行列探索部１１３に元データ１の圧縮要求を通知する。
【０２４２】
変換行列探索部１１３は、数値変換テーブル作成部１０９からの圧縮要求の通知に応じて、変換後データ１−２に対してデータ圧縮処理時のデータ量を削減する最適な変換行列Ａ（数３７）を求める変換行列探索処理を行う（ステップＳ５０４）。変換後データ１−２の先頭から１バイト記号ごとにd1d2d3…とすることで、バイト列（ａ）と見なし、第１実施例と同様の変換行列探索処理を行うことができ、かつ、第１実施例よりも効率的に変換行列Ａを取得できる。
【０２４３】
変換行列Ａが得られると、エントロピー削減部１１４は、変換行列Ａを用いて変換後データ１−２に対してエントロピーを削減するエントロピー削減処理を行う（ステップＳ５０５）。
【０２４４】
そして、削減後データ６を得ると、データ圧縮部１１５が、削減後データ６に対してデータ圧縮処理を行う（ステップＳ５０６）。圧縮データ７が格納領域９のボディ４に格納される。
【０２４５】
図２６におけるステップＳ５０２では、図２４又は図２５のフローチャートに従って数値変換テーブル５１ａ又は数値変換テーブル５１ｂ（単に、数値変換テーブル５１と言う）を作成する。
【０２４６】
数値変換部１１２による、作成された数値変換テーブル５１を用いた数値変換処理について説明する。図２７は、第２実施例における数値変換処理を説明するためのフローチャート図である。
【０２４７】
図２７において、数値変換部１１２は、格納領域９から数値変換テーブル５１を取得する（ステップＳ５４１）。そして、数値変換部１１２は、元データ１に含まれる１バイト記号の種類ごとに出現回数をカウントし（ステップＳ５４２）、出現回数の多い順に１バイト記号の種類をソートする（ステップＳ５４３）。
【０２４８】
そして、数値変換部１１２は、出現回数の多い１バイト記号から、数値変換テーブル５１の数値を先頭から順に写像する（ステップＳ５４４）。
【０２４９】
数値変換部１１２は、出現頻度に応じて変換した数値を用いて、元データ１から変換後データ１−２を作成する（ステップＳ５４５）。２５６バイトの先頭から１バイト記号を整数値として見なしたときの位置に同記号の変換後の数値を対応付けて、格納領域９のヘッダ３とボディ４の間に保持する。
【０２５０】
変換行列探索部１１３は、数値変換テーブル５１により変換された変換後データ１−２に対して、変換行列Ａを求める。変換行列探索部１１３による変換行列探索処理は、元データ１の代わりに、変換後データ１−２を、エントロピーを削減する対象のデータとして読み替えることで、図１５のフローチャートに従って行われる。そして、変換後データ１−２に対する変換行列Ａを取得する。変換行列Ａを表わす行列Ｔ１及び行列Ｔ２を交互に乗算するたびに自乗する回数を示す指数列α1,α2,...,αmと指数列長さ等を含むヘッダ情報５が格納領域９のヘッダ３に保持される。
【０２５１】
そして、エントロピー削減部１１４により、指数列α1,α2,...,αmに基づいて、変換行列Ａを生成して、変換後データ１−２を表わす行列に乗算し、２５６で剰余を取ることで、削減後データ６を得る。得られた削減後データ６は、格納領域９のボディ４に記憶される。
【０２５２】
その後、データ圧縮部１１５により削減後データ６が圧縮され、圧縮データ７が格納領域９のボディ４に上書きされ保持される。削減後データ６は消去される。格納領域９は、圧縮データ７を含むデータファイルを形成する。
【０２５３】
ここで、数値変換テーブル５１ａ又は５１ｂを用いて元データ１の数値を変換し、行列式が１である行列を乗算したとしても、変換した値と異なる数値は出現しないことについて、以下に示す。
【０２５４】
（256×k/2n）の数値に対して整数係数行列Ａを掛けた式を
【０２５５】
【数４４】
2018113583.tif 000046
で表す。kは0から2n-1のいずれかの値を取り得る。kを行列（0,...,  2n-1）で表わし、数４４を
【０２５６】
【数４５】
2018113583.tif 000047
と書き換える。
【０２５７】
一方、行列Ａは、整数係数行列であるから、行列Ａを数４５に掛けた場合、各要素は整数倍され合算される。さらに、256で剰余を取ると、
【０２５８】
【数４６】
2018113583.tif 000048
のように表される。
【０２５９】
ここで、数４６において、
【０２６０】
【数４７】
2018113583.tif 000049
は、仮分数である可能性が高く、整数Ｃと分子Ｄとに分解でき、
【０２６１】
【数４８】
2018113583.tif 000050
と表す。さらに、数４８の整数Ｃは、256の乗算と256の剰余とにより消去でき、
【０２６２】
【数４９】
2018113583.tif 000051
で表せる。即ち、数４９による結果は、数４５が取り得る値の集合に包含され、行列Ａの乗算後に変換した値と異なる値が出現することはない。
【０２６３】
次に、第２実施例における解凍処理部１２０−２による解凍処理について説明する。図２８は、第２実施例における解凍処理の概要を説明するためのフローチャート図である。
【０２６４】
図２８において、ユーザがデータ解凍要求３２を情報処理装置１００に行うと、解凍要求受付部１２１がデータ解凍要求３２を受け付ける（ステップＳ５７１）。圧縮データ７の解凍要求は、データ解凍部１２２に通知される。圧縮データ７を保持するデータファイルが記憶部１３０に記憶される。記憶部１３０に記憶されたデータファイルは、格納領域９に相当する。
【０２６５】
データ解凍部１２２は、格納領域９から圧縮データ７を読み出して解凍し、解凍データ８を得る（ステップＳ５７２）。その後、エントロピー増大部１２３は、エントロピー増大処理を行う（ステップＳ５７３）。エントロピー増大部１２３は、図１８のフローチャートに従い解凍データ８に対してエントロピーを増大させた増大後データ１−２’を生成する。増大後データ１−２’は、圧縮時の変換後データ１−２に相当し、格納領域９のボディ４に保持される。
【０２６６】
増大後データ１−２’が得られると、第２実施例における逆数値変換部１２４による逆数値変換処理が行われる（ステップＳ５７４）。逆数値変換処理により元データ１が復元される。逆数値変換部１２４は、復元した元データ１を記憶部１３０に格納する（ステップＳ５７５）。そして、解凍処理部１２０−２による解凍処理は終了する。
【０２６７】
図２９は、第２実施例における逆数値変換処理を説明するためのフローチャート図である。図２９において、逆数値変換部１２４は、記憶部１３０の格納領域９からエントロピー増大部１２３からエントロピーを増大させた増大後データ１−２’を読み込む（ステップＳ５９１）。また、逆数値変換部１２４は、格納領域９のヘッダ３から数値変換テーブル５１を取得する（ステップＳ５９２）。
【０２６８】
そして、逆数値変換部１２４は、数値変換テーブル５１を用いて、増大後データ１−２’を１バイトごとに順に１バイト記号へと逆変換して、元データ１を復元し（ステップＳ５９３）、復元した元データ１を記憶部１３０に出力する（ステップＳ５９４）。
【０２６９】
上述したように、第２実施例では、第１実施例でのエントロピーの削減に係る処理を行う前に、エントロピーの削減を効率的に行えるように元データ１の１バイト列を出現頻度に応じた数値へ変換することで、より確実にエントロピー削減を行なえる。
【０２７０】
本発明は、具体的に開示された実施例に限定されるものではなく、特許請求の範囲から逸脱することなく、主々の変形や変更が可能である。
【０２７１】
以上の第１〜第２実施例を含む実施形態に関し、更に以下の付記を開示する。
（付記１）
複数の整数で表現されるデータを指定した圧縮要求を受け付ける圧縮要求受付部と、
前記圧縮要求で指定される前記データを行列で表したデータ行列に、行列式が１である変換行列を乗算して、エントロピーを削減するエントロピー削減部と
を有することを特徴とする情報処理装置。
（付記２）
前記エントロピー削減部は、
前記データ行列に前記変換行列を乗算する際に、各要素の値を所定数値で剰余をとることを特徴とする付記１記載の情報処理装置。
（付記３）
任意の行列を積により表現可能な第１行列と第２行列の少なくとも１つ以上を用いて、エントロピーが最も小さくなるべき乗数を探索して、前記変換行列を求め、圧縮データを格納するファイルのヘッダに記憶する変換行列探索部を更に有することを特徴とする付記２記載の情報処理装置。
（付記４）
前記変換行列探索部は、
前記第１行列と前記第２行列を交互に積算し、積算ごとに前記エントロピーが最も小さくなる前記べき乗数を求める
ことを特徴とする付記３記載の情報処理装置。
（付記５）
前記所定数値は、２５６であることを特徴とする付記２乃至４のいずれか一項記載の情報処理装置。
（付記６）
前記ファイルに格納された前記圧縮データを解凍して得た解凍データを行列で表し、前記ファイルの前記ヘッダに格納された前記変換行列と前記所定数値とを用いて得られる逆変換行列を該解凍データの行列に乗算し、該所定数値で剰余をとり前記エントロピーを増大させることで前記データ行列を復元するエントロピー増大部
を有することを特徴とする付記３乃至５のいずれか一項記載の情報処理装置。
（付記７）
前記所定数値の２のｎ乗分の１の整数倍の値を示すテーブルを作成する数値変換テーブル作成部と、
前記データの前記複数の整数において、出現頻度の高い順に、前記数値変換テーブル作成部によって作成された前記テーブルの先頭から順に得られた数値を写像先として該データの各整数の値を変換する数値変換部とを更に有し、
前記データ行列は、前記数値変換部による変換後の前記データを表わすことを特徴とする付記３乃至５のいずれか一項記載の情報処理装置。
（付記８）
前記数値変換テーブル作成部は、
剰余を取る前記所定数値を周期とした二次元トーラスにおいて、斜め４５度の閉直線を縦に伸びる閉直線へ変換した際に前記複数の整数の所定種類の出現頻度の増大が期待される、該斜め４５度の閉直線上の点を選択することを特徴とする付記７記載の情報処理装置。
（付記９）
前記変換行列によって変換された前記データ行列では、出現する整数の種類の出現頻度が偏ることを特徴とする付記１乃至７のいずれか一項記載の情報処理装置。
（付記１０）
複数の整数で表現されるデータを指定した圧縮要求を受け付け、
前記圧縮要求で指定される前記データを行列で表したデータ行列に、行列式が１である変換行列を乗算して、エントロピーを削減する
処理をコンピュータに行わせることを特徴とするプログラム。
（付記１１）
複数の整数で表現されるデータを指定した圧縮要求を受け付け、
前記圧縮要求で指定される前記データを行列で表したデータ行列に、行列式が１である変換行列を乗算して、エントロピーを削減する
処理をコンピュータが行うことを特徴とする情報処理方法。
【符号の説明】
【０２７２】
１          元データ
１−２      変換後データ
１−２’    増大後データ
２          格納形式
３          ヘッダ
４          ボディ
５          ヘッダ情報
６          削減後データ
７          圧縮データ
８          解凍データ
９          格納領域
１１        ＣＰＵ
１２        主記憶装置
１３        補助記憶装置
１４        入力装置
１５        表示装置
１７        通信Ｉ／Ｆ
１８        ドライブ装置
１９        記憶媒体
３１        データ圧縮要求
３２        データ解凍要求
７１        出現頻度の結果
７３        出現頻度の結果
８１        出現頻度の結果
８３        出現頻度の結果
１００      情報処理装置
１１０、１１０−２  圧縮処理部
１２０、１２０−２  解凍処理部
１０９      数値変換テーブル
１１１      圧縮要求受付部
１１２      数値変換部
１１３      変換行列探索部
１１４      エントロピー削減部
１１５      データ圧縮部
１２０、１２０−２  解凍処理部
１２１      解凍要求受付部
１２２      データ解凍部
１２３      エントロピー増大部
１２４      逆数値変換部
【図１】
2018113583.tif 000052
【図２】
2018113583.tif 000053
【図３】
2018113583.tif 000054
【図４】
2018113583.tif 000055
【図５】
2018113583.tif 000056
【図６】
2018113583.tif 000057
【図７】
2018113583.tif 000058
【図８】
2018113583.tif 000059
【図９】
2018113583.tif 000060
【図１０】
2018113583.tif 000061
【図１１】
2018113583.tif 000062
【図１２】
2018113583.tif 000063
【図１３】
2018113583.tif 000064
【図１４】
2018113583.tif 000065
【図１５】
2018113583.tif 000066
【図１６】
2018113583.tif 000067
【図１７】
2018113583.tif 000068
【図１８】
2018113583.tif 000069
【図１９】
2018113583.tif 000070
【図２０】
2018113583.tif 000071
【図２１】
2018113583.tif 000072
【図２２】
2018113583.tif 000073
【図２３】
2018113583.tif 000074
【図２４】
2018113583.tif 000075
【図２５】
2018113583.tif 000076
【図２６】
2018113583.tif 000077
【図２７】
2018113583.tif 000078
【図２８】
2018113583.tif 000079
【図２９】
2018113583.tif 000080