概要
データの圧縮は、ランダムなデータに対しては効果がない。
よく聞く話ですが、実際に圧縮ができないのか調査したデータが見つからなかったので、試してみました。
ランダムなデータを用意して、複数の圧縮形式で圧縮して、どの程度圧縮されるのか試してみました。
TL;DR
ランダムデータの圧縮はどのアーカイブ形式でも不可能。
でも、圧縮率はどのアーカイブ形式も優秀でした。
詳細
データの準備
今回、圧縮する元データは 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 % はデータとの相性も考えられますが、驚異的な圧縮率だと思います。
アーカイブ形式 | サイズ | 圧縮率 |
---|---|---|
無圧縮 | 830,482,024 byte | - |
7z | 436,574,275 byte | 52.57 % |
bzip2 | 421,852,599 byte | 50.80 % |
gzip | 463,621,497 byte | 55.83 % |
バイナリファイル
本題です。
どの圧縮形式でも、100 % 以下の圧縮率になるものはありませんでした。
しかし、 7z や gzip 形式は 100.01 % という驚異的なオーバーヘッドの少なさでした。
アーカイブ形式 | サイズ | 圧縮率 |
---|---|---|
無圧縮 | 415,241,012 byte | - |
7z | 415,266,836 byte | 100.01 % |
bzip2 | 416,405,338 byte | 100.28 % |
gzip | 415,284,140 byte | 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 % |
結論
ランダムなファイルの圧縮は不可能であることを再確認できました。
また、どのアーカイブ形式も優秀な成績でした。
そのため、データの圧縮は自分で頑張るよりも、既存のアーカイブを通したほうが楽ということがわかりました。
以上