これは機械翻訳であり、原文は英語です。 原文を読む
すべてのファイルを縮小できる圧縮プログラムは存在せず、その証明はわずか1段落で終わる
数年ごとに、あらゆるファイルを50%圧縮できるアルゴリズムを発表する者が現れる。それを2回適用すればどんなファイルも4分の1に縮小され、十分な回数適用すればわずか1ビットになってしまうことになる。
ちょうど1,000ビットのすべてのあり得るファイルを考えてみよう。それらは2¹⁰⁰⁰個存在する。次に、それより短いすべてのあり得るファイル――999ビット、998ビット、そして空のファイルに至るまで――を考えてみよう。それらをすべて足し合わせると2¹⁰⁰⁰ − 1個のファイルになり、最初に用意した数より1つ少なくなる。
可逆圧縮プログラムは、異なる入力を異なる出力へとマッピングしなければならない。さもなければ元に戻すことができなくなるからだ。しかし、2¹⁰⁰⁰個のものを2¹⁰⁰⁰ − 1個の箱に納めようとすれば、1つの箱に2個を入れることなしには不可能である。したがって、すべての入力を縮小できる可逆圧縮プログラムは存在しない。一部の入力を縮小できるのであれば、他の入力を拡大しなければならないのである。
アルゴリズムについての前提条件は一切必要なかったため、いかなる巧妙な工夫もこれを回避することはできない。これこそが鳩の巣原理であり、実際のすべての圧縮プログラムにおいて、出力が入力よりわずかに大きくなってしまう最悪のケース（元のデータに加えて数バイトのヘッダが付加されるケース）が存在する理由である。
では、実際に利用されているものは何か
構造である。圧縮とは、漠然とした意味で「冗長性」を取り除くことではない。頻繁に発生するものに対して、より短いコードを再割り当てすることなのだ。
英語のテキストは極めて予測しやすい。「th」の後に続く文字は圧倒的に「e」であることが多い。スペースは最も頻出する文字である。壁の画像には、ほぼ同一のピクセルが長く連続して並んでいる。いずれのケースにおいても、確率変数として捉えたファイルは低いエントロピー――1記号あたりの平均的な「驚き」が小さい状態――を持っており、1948年にシャノンはこの量が理論上の厳密な下限であることを示した。情報源をそのエントロピーよりも少ない1記号あたりのビット数で符号化することはできず、かつ常にその下限にいくらでも近づけることができる。
これにより、圧縮とは予測の精度を競うゲームとなる。情報源を適切にモデル化する圧縮プログラムは、短いコードを正確に割り当ててエントロピーの近くに到達する。モデル化が不十分な圧縮プログラムは、ビットを無駄にする。テキスト圧縮における最新技術が言語モデルに酷似してきているのはそのためだ。次の記号を正確に予測することと、効率よく圧縮することは、姿を変えた同じ問題なのである。
理論的限界に近づいていく様子は Entropy Coding ツールで確認でき、コードの割り当てそのものは Huffman Encoding で観察できる。
ZIPファイルをさらにZIP圧縮しても意味がない理由
十分に圧縮されたファイルからは、構造がすでに取り除かれている。残されたものは統計的にノイズのように見え、あらゆる記号がほぼ等しい確率で出現し、隣接する記号間に有用な相関関係が存在しない。1ビットあたりのエントロピーは1に近いため、利用できる要素は何も残っておらず、2回目の圧縮を行うと通常はわずかに大きくなってしまう――ヘッダの付加に加え、符号化する価値のあるパターンを圧縮プログラムが発見できないからだ。
同じ理由により、ZIPアーカイブ内のJPEGファイルがほとんど縮小しないこと、暗号化されたデータが圧縮不可能であること（優れた暗号化は意図的にノイズに見えるよう設計されている）、そして暗号化する前に圧縮するのが正しい手順であること（暗号化した後には圧縮できるものが何も残っていないため）が説明できる。
「50%縮小」の誠実な意味
圧縮に関するあらゆる誠実な主張とは、入力クラスについての主張である。「英文テキストのサイズを半分にする」というのは現実的で有用な主張である。「あらゆるファイルのサイズを半分にする」というのは証明可能な偽であり、その証明こそが冒頭の段落なのだ。
非可逆圧縮が全く別物である理由
ここまでの話は非可逆圧縮を何ら制約しない。非可逆圧縮は可逆である必要がないからだ。JPEG、MP3、そしてあらゆるビデオコーデックは意図的に情報を切り捨てており、人間の目や耳が気づかないものをモデル化して、何を捨てるかを選択している。
これにより問いは「どれだけの構造が存在するか」から「苦情が出ない範囲でどれだけ捨てられるか」へと変化する。これは数学というよりは知覚の問題である。非可逆圧縮のトレードオフには調整ノブが存在し、可逆圧縮には存在しないのもこれが理由だ。エントロピーはデータについての客観的事実であるが、許容できる歪みは聞き手や見手の判断だからである。
両者に共通する唯一の点は、誠実な仕様記述は常に条件付きであるということだ。可逆圧縮プログラムは特定の入力クラスに対して優れており、非可逆圧縮プログラムは指定された歪みの範囲において優れているのである。