More than 1 year has passed since last update.

ランダムなデータは圧縮できない、を試してみた。

Posted at 2023-03-18

概要

データの圧縮は、ランダムなデータに対しては効果がない。
よく聞く話ですが、実際に圧縮ができないのか調査したデータが見つからなかったので、試してみました。

ランダムなデータを用意して、複数の圧縮形式で圧縮して、どの程度圧縮されるのか試してみました。

ランダムデータの圧縮はどのアーカイブ形式でも不可能。
でも、圧縮率はどのアーカイブ形式も優秀でした。

今回、圧縮する元データは 2種類用意しました。
検証可能なランダムなデータとして、最初に思い浮かぶのは円周率なので、円周率をもとにランダムデータを用意しました。

データの準備は y-cruncher を用いて生成しました。
hex 形式で出力したファイルを以下の通り処理したものを圧縮ソフトで圧縮しました。

テキストファイルは Hex 出力したものから、 sed 's/^[0-9]*\.//' で小数点前の整数部を削除したものを利用します。
これは、以下のバイナリファイルとデータの複雑さに関する条件を揃えるための処理です。

空間利用率は、 1byte あたり、 [0-9A-F] の 16 通りのため $\frac{log_2 16}{log_2 256} = \frac{1}{2} = 50 \% $ から、
論理的には、$\frac{1}{2}$ までデータ圧縮が可能なデータとなります。

テキストファイルを、バイナリ変換したものを利用します。

空間利用率は、 1byte あたり、 [0x00-0xFF] の 256通りのデータで利用しており、$\frac{log_2 256}{log_2 256} = 1 = 100 \% $ から、
円周率が完全にランダムであるなら、圧縮が不可能なデータになります。

圧縮は、7-Zip 22.01 (x64) を用います。

アーカイブ形式	圧縮レベル	圧縮方式	辞書サイズ	ワードサイズ	ソリッドブロックサイズ
7z	9 - 超圧縮	LZMA2	64MB	64	16GB
bzip2	9 - 超圧縮	BZip2	900KB	-	-
gzip	9 - 超圧縮	Deflate	32 KB	128	-

ゴリゴリの超圧縮処理で対抗します。

どの圧縮形式もおおよそ理論値まで圧縮がかかっていました。
特に、 bzip2 の 50.80 % はデータとの相性も考えられますが、驚異的な圧縮率だと思います。

本題です。
どの圧縮形式でも、100 % 以下の圧縮率になるものはありませんでした。
しかし、 7z や gzip 形式は 100.01 % という驚異的なオーバーヘッドの少なさでした。

最後に、テキストファイルとバイナリファイルのサイズ差をアーカイブ形式ごとに見てみます。
bzip2 が特に突出した増加率の少なさでした。

アーカイブ形式	テキストファイルサイズ	バイナリファイルサイズ	増加率
無圧縮	830,482,024 byte	415,241,012 byte	200 %
7z	436,574,275 byte	415,266,836 byte	105.13 %
bzip2	421,852,599 byte	416,405,338 byte	101.31 %
gzip	463,621,497 byte	415,284,140 byte	111.64 %

ランダムなファイルの圧縮は不可能であることを再確認できました。
また、どのアーカイブ形式も優秀な成績でした。

そのため、データの圧縮は自分で頑張るよりも、既存のアーカイブを通したほうが楽ということがわかりました。

以上