THcompは実在するのだろうか

「これが…動作原理なのです」といわれても、すぐには納得できない人もいるかもしれない。「なるほど、人類の作るデータに番号をつけていっても番号自体がそれほど 大きくならないのはわかった。そこまではいいとしよう。でもそれがどうした。番号づけとデータ圧縮とは別のものじゃないか」

そうだろうか?

ここに奇妙な証明がある—

情報は圧縮できないことの証明

ここでは可逆な圧縮のみを考える。

I. 1ビットの情報は圧縮できない

もし圧縮できたとすれば、その符号の長さは0ビットになる。情報が消滅してしまうことになる。1ビットの情報は1ビットに圧縮する(つまり無圧縮)が最善だ。その対応は

の二通りである。どんな圧縮アルゴリズムもこのどちらかをとるしかない。が、どちらにせよ符合として1ビットのパターン(“0”と“1”)を使い切ってしまう。

II. 2ビットの情報は圧縮できない

もし圧縮できたとすれば、その符号は1ビットということになる。しかし、1ビットの符号はIの議論で使い切ってしまった。したがって2ビットの情報の最善の圧縮方法は、2ビットに圧縮することである。これまた無圧縮だ。

2ビットの情報から2ビットの符号への変換は「何もしない」を含めて24通り ある。どんな圧縮アルゴリズムもこの24通りの対応のどれかを行うことになる。 しかしいずれにせよ符合としてとして2ビットのパターン（“00”〜“11”）を使い切ってしまう。

III. nビットの情報は圧縮できない

もし圧縮できたとすれば，それはnビットより小さくなる。しかしI・IIの議論からわかるように、nビットの情報の圧縮を考えるときにはnビットより小さい符号はすべて使い切ってしまった後である。圧縮のしようがない。

結論: 情報を圧縮するアルゴリズムは存在しない

情報圧縮の原理

前の証明は何が間違っているのだろうか。 いろいろな言い方があるけれども、「情報圧縮」の「情報」は すべてのビットパターンを意味しないのだ。前の証明はすべての ビットパターンについて考察してしまっている。

パターン「0」「1」「00」は圧縮できなくてもよいことにしよう。それなら

という対応が考えられる。符合を入れ替えただけなので全体としては 何の得にもならないが、圧縮したいパターンだけを考えれば得をしている。 圧縮しなくていいパターンを切り捨てて、圧縮したいパターンだけを「情報」と 呼ぶことにすれば、この対応は情報を圧縮していることになる。

実際、数十バイトくらいにの長さになると圧縮できなくてもよいパターンの方が はるかに多い。64バイトのビット列について考えてみよう。512ビットだ。 可能性としては2⁵¹²通りのパターンが考えられる。 この中にはたとえば、人類がつくるすべての短歌が含まれている。平安の過去から現在までに作られた短歌はもちろんのこと、遠い未来に人類が終焉を向かえるまでに作るはずの短歌のすべてが含まれているのだ。さらに、人名・映画や書籍の題名・電話番号・メールアドレス・…とにかく64バイト以内で表せそうなことなら何でも入っている。 それらを全部かぞえても、2⁵¹²を分母にした比率はゼロと見分けがつかない。

このことはモンテカルロ法を使って確認できる。 ランダムなバイト列を生成して64バイトごとに出力する仕掛けを作り、ずっと眺めていたまえ。一日眺めていたって意味のある60バイト以上のパターンが出てくることはまず一回もないだろう。

極端に短くないかぎり、どの長さのビット列でも事情は同じだ。ほとんどがランダムで用のないパターンなのだ。 用のないパターンに圧縮アルゴリズムを適用したときは符合が 大きくなってしまってもべつに困らない。だから1ビットと2ビットの例で説明した考え方が使える。それは一般化すればこう表すことができる: 無用な短いパターンにはそれよりも長いパターンを符合として割りあてる。 そうすることでその短いパターンと同じ長さの符合の集合に「空き」が できる。それを、長いけれども有用なパターンの符合として割りあてる。 そして、有用なパターンだけを「情報」と呼ぶ。

これこそが「情報圧縮」のほんとうの姿なのだ。 どんなまじめな圧縮アルゴリズムもやってることは本質的にこれだ。 あなたが恩恵を受けている圧縮ソフト達もすべてこの原理で動いている。 単なる符合の入れかえ+欺瞞くさい言葉遊びなのだ。

その証拠に、圧縮アーカイバはほとんどのパターンを圧縮することができない。 「そんなバカな」だって? モンテカルロ法を使って確認してみたまえ。ランダムな バイト列を生成するプログラムで適当な長さのファイルを作り、お気に入りの 圧縮アーカイバにかけてみるといい。 ほとんどすべての場合、かえって大きなアーカイブファイルができてしまうだろう。