可逆圧縮
可逆データ圧縮アルゴリズムは、すべての入力データ セットに対する圧縮を保証することはできません。 言い換えると、任意のロスレス データ圧縮アルゴリズムについて、アルゴリズムによって処理されたときに小さくならない入力データセットが存在し、少なくとも 1 つのファイルを小さくする任意のロスレス データ圧縮アルゴリズムについて、それが大きくなるファイルが少なくとも 1 つ存在することになります。 これは、次のように、計数論を使用した初等数学で簡単に証明できます。
- 各ファイルが任意の長さのビットの文字列として表されると仮定します。
- すべてのファイルを元のファイルより長くない出力ファイルに変換する圧縮アルゴリズムがあり、少なくとも 1 つのファイルが元のファイルより短い出力ファイルに圧縮されるとします。
- より短いものに圧縮される、長さ M ビットのファイル F が存在する最小数を M とします。 N を F の圧縮バージョンの長さ (ビット数) とします。
- N<M なので、長さ N のすべてのファイルは圧縮中にそのサイズを維持します。 このようなファイルは 2N 個存在する可能性があります。 F と共に、これは、長さ N の 2N のファイルの 1 つにすべて圧縮される 2N+1 のファイルを作ります。
- しかし、2N は 2N+1 より小さいので、鳩目の原理により、2 つの異なる入力で同時に圧縮関数の出力である長さ N のファイルが存在するはずです。
- したがって、元の仮説 (圧縮関数がどのファイルも長くしないという仮説) は、必ずしも真実ではないと結論づけなければなりません。 ほとんどの実用的な圧縮アルゴリズムには「エスケープ」機能があり、エンコードされることによって長くなるファイルに対して通常のコーディングをオフにすることができます。 理論的には、入力全体に対して通常の符号化をオフにしたことをデコーダに伝えるために、1ビット追加するだけでよい。しかし、ほとんどの符号化アルゴリズムでは、この目的のために少なくとも1バイト（通常は2バイト以上）を使用している。
実際、長さ N のファイルを考える場合、すべてのファイルが同じ確率であれば、あるファイルのサイズを縮小する任意のロスレス圧縮では、圧縮ファイルの予想長さ (長さ N のすべての可能なファイルの平均) は必然的に N より大きくなければなりません。したがって、圧縮するデータのプロパティについて何も知らない場合、まったく圧縮しないほうがよいでしょう。 可逆圧縮アルゴリズムは、特定のタイプのファイルを他よりも圧縮する可能性が高い場合にのみ有用です。 アルゴリズムを選択することは、常に、有用に短くなるすべてのファイルのサブセットを選択することを暗黙のうちに意味します。 これが、異なる種類のファイルに対して異なる圧縮アルゴリズムが必要な理論的な理由である。
設計されたデータの種類に使用される可逆圧縮アルゴリズムが、そのようなファイルを一貫して短く圧縮できる「トリック」は、アルゴリズムが作用するように設計されたファイルはすべて、アルゴリズムが除去するように設計された、容易にモデル化できる何らかの形式の冗長性があり、したがって、そのアルゴリズムは、他のファイルは圧縮しないか大きくなるのに対し、短くできるファイルのサブセットに属しているということです。 たとえば、可逆音声圧縮プログラムはテキスト ファイルではうまく機能しませんし、その逆も同様です。
特に、ランダムなデータのファイルは、考えうるあらゆる可逆データ圧縮アルゴリズムによって一貫して圧縮することはできません。 任意の数 N のランダム ビットが常に N – 1 ビットに圧縮されるような「完全な圧縮」を実現した企業の主張は長年にわたって数多くありますが、この種の主張は、主張された圧縮スキームに関するさらなる詳細を見ることなく安全に破棄することができます。 このようなアルゴリズムは、数学の基本法則に反しており、もし存在すれば、繰り返し適用して、任意のファイルをロスレスで長さ 0 にすることができるからです。 したがって、任意の特定のファイルが、たとえランダムに見えても、解凍器のサイズを含めても、著しく圧縮されている可能性があるのです。 例えば、数学の定数πの桁は、ランダムに見えるが、非常に小さなプログラムで生成することができる。 しかし、特定のファイルが非圧縮性であるかどうかを判断できない場合でも、非圧縮性の文字列に関する簡単な定理により、任意の長さのファイルの 99% 以上は 1 バイト (解凍器のサイズを含む) 以上で圧縮できないことがわかります。
数学的背景
抽象的には、圧縮アルゴリズムはシーケンス (通常はオクテットの) 上の関数として見なすことができます。 圧縮は、結果のシーケンスが元のシーケンス (および伸長マップの命令) よりも短ければ成功です。 圧縮アルゴリズムが可逆であるためには、圧縮マップは「プレーン」から「圧縮」ビット配列への射影を形成しなければなりません。
鳩目の原理により、長さ N の配列のコレクションと長さ N-1 の配列のコレクションの任意のサブセットの間の双対射影は禁止されています。 したがって、すべての可能な入力シーケンスのサイズを縮小するロスレス アルゴリズムを作成することはできません。
実際の圧縮理論における適用ポイント
実際の圧縮アルゴリズムの設計者は、高い情報エントロピーのストリームは圧縮できないことを受け入れ、それに応じて、この状態を検出し処理する機能を含めます。 検出の明白な方法は、生の圧縮アルゴリズムを適用し、その出力が入力よりも小さいかどうかをテストすることです。 例えば、圧縮アプリケーションは、名前の末尾が “.zip”, “.arj”, “.lha” であるファイルを、より高度な検出をせずに圧縮不可能とみなすことがある。 この状況を扱う一般的な方法は、入力や圧縮できない部分を出力に引用して、 圧縮のオーバーヘッドを最小にすることである。 たとえば、zip データ フォーマットは、アーカイブにそのままコピーされた入力ファイルの「圧縮方法」を「保存」に指定します。
The Million Random Digit ChallengeEdit
Mark Nelson は、comp.Logic の「魔法の圧縮アルゴリズム」というクレームに対抗して、「Million Random Digit ChallengeEdit」と名付けました。
ニュースグループ comp.compression の FAQ には、ランダムなデータを圧縮できるプログラムに対して 5,000 ドルを提供する Mike Goldman によるチャレンジがあります。 Patrick Craig はこの挑戦を受けましたが、データを圧縮するのではなく、データを別々のファイルに分割し、そのすべてがファイルの一部として保存されていない数字の 5 で終わっていました。 この文字を省略することで、出来上がったファイル（プラス、ルールに従って、それらを再集合したプログラムのサイズ）は、元のファイルより小さくすることができたのだ。 しかし、実際には圧縮は行われず、ファイル名に格納された情報は、元のファイルで正しい順序で組み直すために必要なものであり、この情報はファイルサイズの比較に考慮されませんでした。 このように、元のファイルを再構成するためには、ファイルそのものだけでは不十分で、ファイル名も必要なのです。 Patrick Craigは，意味のある圧縮が行われていないことに同意しましたが，課題の文言が実際にはこれを要求していないと主張しました． 挑戦が技術的に達成されたかどうかについての議論を含む、このイベントの完全な歴史は、Patrick Craig の Web サイトにあります。