p20190524a

データの圧縮について思いついたこと

• (by K, 2019.05.24)

(1)

• 「無限の猿定理」という定理がある。Wikipediaによれば「ランダムに文字列を作り続ければどんな文字列もいつかはできあがるという定理」だとされる。
• ランダムでは心もとないし、重複もあって効率がよくないと思うので、たとえば1MBのバイナリファイルを考える。これは 256^1048576 通りの内容を持ちうる。テキストであれば、ヌル文字をファイルの終端だと考えれば、1MB未満のテキストも表せることになる。アプリケーションであれば、余分なNOPを追加して1MB未満の内容もこの中に含めることができる。
• まあとにかく、 256^1048576 通りの中には1MB以下で表せるほぼすべてのファイルが含まれているだろう。その中にはまだ誰も読んだことのないすばらしい文学作品やその英訳版、ドイツ語版、日本語版などが含まれているだろうし、まだ証明されていない高度な数学の論文も含まれているだろうし、私が狂喜しそうなプログラムも含まれているだろう。
• これは1MBを超えるものは含まれていないわけだけど、まあファイルを大きくして組み合わせを大きく取れば、もっともっとカバー範囲を広げることはできる。

(2)

• しかし一方で、256^1048576 通りの中のほとんどはガラクタである。悲しい。このガラクタとそうではないものを容易に識別できないだろうか。もしそれができれば、オールゼロから+1していってすべてのパターンでガラクタ判定をして残ったものをチェックしていくだけで、電子的なあらゆる創作活動ができることになる。すごいじゃないか。私も失業だ。
• これは現実的ではないと思うかもしれない。しかしこの作業は並列演算が可能であり、しかも1MBなんて言わずに1KBとかでやってもよいのだ。それでも結構いいものが見つかるかもしれない。だからガラクタかどうかを見分けるフィルタはとても重要である。
• とここまで考えて、多くの名作はデータ圧縮が可能であるということに気付いた。つまりデータ圧縮を試みて小さくならないものはガラクタである。この基準は結構厳しい。ここを読んでいる人の多くは、データを圧縮するとほとんどいつもサイズが半分とかになることを経験しているせいで、それが当たり前だと思っていることだろう。しかしそれはちっとも当たり前ではない。人間が作ったものは小さくなりやすいのであってランダムデータ列は全然縮まない。だからこれこそ重要な判定方法だと考えるのである。

(3)

• しかし、データを作っては圧縮をかけてみて小さくなったかどうかを調べる・・・というのはいかにも遅そうである。だから逆にしてみよう。つまり圧縮データを作って展開してみるのだ。これなら1MBのファイルを作って試す必要はなく、512KBくらいのファイルを作って展開してみるだけで必要な探索は完了するだろう（圧縮率が50%だと仮定して）。もし展開に失敗したりアーカイブが壊れているなどの場合は、失敗なのでスキップするとする。

(4)

• この試みをする場合は、当然だけどアーカイブが壊れているエラーが頻出しないほうが効率がよい。つまり理想的には全てのビットパターンが有効なアーカイブであって、何らかの有効な出力が得られるとよい。
• これが達成されたとき、圧縮率は相当に高くなっているのではないかと想像する。

(5)

• そうであれば、データ圧縮プログラムの目指すべきところは、できるだけ多くのビットパターンが有効なアーカイブであることなのかもしれない。
• ということで、たとえば256バイトのファイルのすべての組み合わせに対して（組み合わせは 256^256 通り）、何パーセントくらいが有効なアーカイブであるか、その割合を求めることはデータ圧縮フォーマットの効率を測る指標になっているのかもしれない。
• まず無圧縮はすべての組み合わせが有効なので、効率は100%だ。しかしそれは全然すごくない。うーん、ここまでの推論はあまり正しくなかったのだろうか？

こめんと欄