つーさのくーかん

疑問
gzipやらbzip2やらlzfだとかデータ圧縮のことを考えていてふと思ったこと
円周率πやネイピア数eといった数の文字の並びはデタラメにみえるのだが、
この数の並びを"圧縮"することが可能なのだろうか？

いぬふぐり日記(2010-02-03)
http://nagato.homelinux.org/diary/?date=20100203#p02

ちょっと興味をそそられたので、なんか色々考えたり、昔読んだ本を思い出したりしてた。

円周率を10進小数で表したものについて。
データ長が無限であるものには、そもそも圧縮とか複合とかいう概念が通用しない気がするので、
とりあえずhoge桁で打ち切られた有限長のものを持ってくることにします。

円周率はっと、14159265358979323 までしか覚えていない、何バイトですかこれ。
ASCIIで表したら 17B ですか。でも、整数だったらInt64に収まってしまいます。 17B → 8B に圧縮成功です！

さらに、もし何らかの手段を用いて「この数列は円周率である」ということを知ることができたら、
πであることと先頭からhoge桁であることさえ保持すればいいのだから……。

結局、可逆圧縮なんて「どう表現するか」「より短い表現はないか」という問題なんですよねー。
このとき、圧縮機と伸張機の長さに言及していないところがポイントになるんですかね。
伸張機がπを計算できれば、πの圧縮について無敵というかですね。
その計算プログラムが、任意桁のπを表しているとも考えれば、
データ長はプログラム長で、伸張機はプログラムを実行する計算機そのものということにでもなりますか？
伸張のための時間が現実的じゃなくなりそうですか。

……はて、脱線しまくった。

一般には、何の法則性もないデータ列ほど圧縮しにくいという話だったですね。
というのは、1の後には2が来やすいとか、3の後は必ず4とか、そういう事前情報に沿って、1桁を表すのに必要なデータ量を削減してるから。
だから、文字の圧縮のためには、○○なアルゴリズムが優れていて、画像には××法で、音声には△△。
それぞれを表現したものが、一般的にはどんな傾向がある、という知識のお陰で圧縮できてるわけですよ。
逆に、出現率が完全に均等なデータ列とゆーのはそれ以上圧縮できないんです。
このそれ以上圧縮できない下限を情報量とかエントロピーと言、ったんだっけな……？

ここでπは現れる数列に「π」という規則性を持ってしまっているので、πと言えばそれで足りてしまいます。
同時に、たぶんここがこの情報の持つエントロピーの下限で、πと言わずしてπであることを表現する方法が見つからないと……。

余談

πであることがわかってない数列には、数列として圧縮アルゴリズムを適用することになるのですが、
14159265358979323 なので、多い順に並べると 359124678 で確率が333221111ですから、適当にハフマン圧縮すると
010 1100 010 100 00 011 1101 100 101 100 1111 00 1110 00 101 011 101 で、6.5バイトでしょうかー

数列として見た場合のエントロピーは、(3*(3*-lg(3/17))+2*(2*-lg(2/17))+4*(1*-lg(1/17))) = 6.4バイトらしいです。
これ以上はどんな圧縮アルゴリズムを持ってしても縮まないのです?
理論値の101.5625%だったら結構すてきな圧縮率かもしれないですねー。

ねむいですー。