はじめに
数字の多いテキストデータを7zで圧縮したのですが、思ったほど圧縮できませんでした。
情報源符号化定理と併せて考察しました。
結論としては、7z圧縮値と理論値はほぼ一致しました。
思ったほど圧縮できなかった理由としては乱数で数値を発生させたため、
数字の出現頻度が一様になりエントロピーが増加したためでした。
7z圧縮
数字の多いテキストデータを7zで圧縮しました。
元データサイズは185kBで、圧縮後のデータサイズは77.3kBでした。
圧縮率は41.78%です。数字がほとんどなのでもっと圧縮できると思っていたのですがいまいちでした。
最大圧縮率はどのくらいなのかと調べてみたところ、
情報源符号化定理で見積もることができることがわかりました。
なお、"情報源(の)符号化"という耳慣れない言葉がでてきますが、
"情報源" = "圧縮前データ", "符号化" = "圧縮" ととらえても大きくは違わないと思います。
情報源符号化定理
情報源符号化定理とは、情報源の符号化において、
最小の平均符号長を与える定理です。
(情報源エントロピー) = (最小の平均符号長)
となる符号が存在します。
エントロピーとは情報量の期待値として定義される量です。
まず、情報量$I$の定義から
I = -log_2 P = log_2 \frac{1}{P}
$P$は事象の生起確率です。生起確率が大きいほど情報量は小さくなります。
よく発生する事柄は情報量が小さく、めったに起こらない事柄は情報量が大きいということになります。
次に、エントロピー$H$を定義します。N個の事象があり、それぞれの生起確率を$P_i$、情報量を$I_i$とします。
H = \sum^{N}{P_i * I_i} = \sum^{N}{P_i * (-log_2 P_i)}
エントロピーは情報量の期待値(平均値)になっています。
まとめると、情報源記号の生起確率が分かれば、最小の平均符号長が分かることになります。
数字の多いテキストデータへの応用
情報源記号は8bit固定長の文字の並びです。
表現できる記号は2の8乗である256種類となります。
一方、実際に使用している記号は、
- 数字0~9文字
- 小数点"."
- 改行(\n)
- 半角空白
13種類です。256-13 = 243種類は使用しておらず、
生起確率0の無駄な記号となっています。
文字毎に個数をカウントして、生起確率$Pi$を計算しました。
生起確率からエントロピーを計算すると3.55(bit)になります。
情報源は8bit固定なので44.42%圧縮できることが分かります。
7z圧縮率は41.78%なので近い値になっています。
7zの方が圧縮率が高い
ここで興味深いのは7zの方が圧縮率が高いことです。
情報源符号化定理の条件として、"無記憶情報源"である必要があるのですが、
使用したデータは"マルコフ情報源"になっていたからではないかと考えています。
つまり情報源記号は完全なランダムではなく、並びに規則性があったためです。
データを抜粋します。" 0."という文字列が繰り返し現れています。
0.8798806169075407 0.6572010431772227 0.5013760835440487
0.427608301274456 0.2199377737264211 0.652005591194716
7zではここらへんの事情も考慮して圧縮しているようです。
Appendix 文字出現頻度のカウント
テキストデータ内の文字の出現頻度をカウントするpythonスクリプトを作成したので記載します。
(*)ファイル名は"data.txt"固定値となっています。
d = {}
total = 0
with open("data.txt", "r") as f:
for ln in f:
for ch in ln:
total = total + 1
if ch in d:
d[ch] = d[ch] + 1
else:
d[ch] = 1
for k, v in sorted(d.items(), key=lambda x:x[1]):
print(k, v, v/total)
print("total:", total)