Dies ist eine maschinelle Übersetzung; der englische Text ist das Original. Originalartikel lesen
Kein Kompressor kann jede Datei verkleinern, und der Beweis umfasst einen einzigen Absatz
Alle paar Jahre kündigt jemand einen Algorithmus an, der jede beliebige Datei um 50 % komprimiert. Zweimal angewendet würde er jede Datei auf ein Viertel verkleinern und bei hinreichend häufiger Anwendung auf ein einzelnes Bit.
Betrachten Sie alle möglichen Dateien von exakt 1.000 Bit. Davon gibt es 2¹⁰⁰⁰. Betrachten Sie nun jede mögliche Datei, die kürzer ist — 999 Bit, 998 und so weiter bis hin zu gar nichts. Addiert man diese auf, erhält man 2¹⁰⁰⁰ − 1 Dateien, also genau eine weniger als am Anfang.
Ein verlustfreier Kompressor muss verschiedene Eingaben auf verschiedene Ausgaben abbilden, da er sonst nicht umkehrbar wäre. Man kann jedoch nicht 2¹⁰⁰⁰ Objekte in 2¹⁰⁰⁰ − 1 Fächer unterbringen, ohne zwei in dasselbe Fach zu legen. Folglich verkleinert kein verlustfreier Kompressor jede Eingabe. Wenn er manche verkleinert, muss er andere vergrößern.
Dafür waren keinerlei Annahmen über den Algorithmus nötig; kein noch so kluger Kniff kann diese Tatsache umgehen. Es handelt sich um das Schubfachprinzip, und es ist der Grund, warum jeder reale Kompressor einen ungünstigsten Fall aufweist, in dem die Ausgabe etwas größer ist als die Eingabe: das Original zuzüglich einiger Byte Header-Daten.
Was also tatsächlich ausgenutzt wird
Struktur. Kompression entfernt nicht „Redundanz“ in einem vagen Sinne; sie weist den häufig auftretenden Dingen die kurzen Codes zu.
Englischer Text ist enorm vorhersagbar. Nach „th“ folgt überwältigend oft das „e“. Leerzeichen sind das häufigste Zeichen. Das Bild einer Wand weist lange Ketten nahezu identischer Pixel auf. In jedem dieser Fälle besitzt die Datei, betrachtet als Zufallsvariable, eine geringe Entropie — der durchschnittliche Überraschungswert pro Symbol ist klein — und Shannon zeigte 1948, dass diese Größe die exakte untere Schranke bildet. Man kann eine Quelle nicht mit weniger Bit pro Symbol kodieren als durch ihre Entropie vorgegeben, und man kann dieser Grenze stets beliebig nahe kommen.
Das macht Kompression zu einem Wettbewerb um die Vorhersage. Ein Kompressor, der die Quelle gut modelliert, weist kurze Codes präzise zu und landet nahe der Entropie. Ein Kompressor, der sie schlecht modelliert, verschwendet Bit. Aus diesem Grund ähnelt der Stand der Technik bei der Textkompression zunehmend einem Sprachmodell: Das nächste Symbol gut vorherzusagen und gut zu komprimieren, sind dasselbe Problem in unterschiedlicher Gewandung.
Wie man sich dieser unteren Schranke nähert, lässt sich im Werkzeug Entropy Coding beobachten; die Code-Zuweisung selbst wird in Huffman Encoding sichtbar.
Warum das erneute Komprimieren einer ZIP-Datei nichts bewirkt
Einer gut komprimierten Datei wurde ihre Struktur entzogen. Was übrig bleibt, gleicht statistisch gesehen einem Rauschen: Jedes Symbol ist ungefähr gleich wahrscheinlich, und es gibt keine nutzbaren Korrelationen zwischen benachbarten Symbolen. Ihre Entropie pro Bit liegt nahe bei 1, sodass nichts mehr ausnutzbar ist, und ein zweiter Durchgang macht die Datei gewöhnlich minimal größer — bedingt durch den Header und den vergeblichen Versuch des Kompressors, codierungswürdige Muster zu finden.
Dasselbe erklärt, warum eine JPEG-Datei in einem ZIP-Archiv kaum schrumpft, warum verschlüsselte Daten unkomprimierbar sind (gute Verschlüsselung ist gezielt so konzipiert, wie Rauschen auszusehen) und warum Komprimierung vor Verschlüsselung die richtige Reihenfolge ist — danach gibt es nichts mehr zu komprimieren.
Die ehrliche Variante von „um 50 % kleiner“
Jedes wahrheitsgemäße Versprechen bezüglich einer Kompression bezieht sich auf eine Klasse von Eingaben. „Halbiert die Größe englischer Prosa“ ist eine reale und nützliche Aussage. „Halbiert die Größe jeder beliebigen Datei“ ist nachweislich falsch — und der Beweis dafür steht im ersten Absatz.
Wo verlustbehaftete Kompression eine völlig andere Kategorie ist
Nichts davon schränkt verlustbehaftete Kompression ein, da diese nicht umkehrbar sein muss. JPEG, MP3 und jeder Videocodec verwerfen gezielt Informationen; sie wählen das Auszulassende anhand von Modellen dessen aus, was das menschliche Auge und Ohr nicht wahrnehmen.
Das verschiebt die Frage von „Wie viel Struktur ist vorhanden?“ hin zu „Wie viel kann verworfen werden, bevor es jemandem auffällt?“, was eher eine Frage der Wahrnehmung als der Mathematik ist. Das ist auch der Grund, warum der Kompromiss bei verlustbehafteter Kompression einen Stellregler hat und bei verlustfreier nicht: Die Entropie ist eine Eigenschaft der Daten, die akzeptable Verzerrung hingegen ein Urteil über das Zielpublikum.
Die eine Gemeinsamkeit beider Ansätze besteht darin, dass eine ehrliche Spezifikation stets bedingt ist. Ein verlustfreier Kompressor ist gut für eine Klasse von Eingaben. Ein verlustbehafteter ist gut bei einer gegebenen Verzerrung.