Datenkompression erklärt
Jede Webseite, die Sie laden, jede ZIP-Datei und jedes PNG-Bild wurde komprimiert: verkleinert, ohne ein einziges Bit zu verlieren, und bei der Ankunft wieder entpackt. Die Verfahren dahinter sind überraschend einfach. Sie suchen nach Dingen, die sich wiederholen, und sagen „dasselbe wie vorhin“, statt es noch einmal zu sagen. Wie weit diese Idee trägt und wo sie an ihre Grenze stößt, ist eine der schönsten Geschichten der Informatik.
Verlustfrei und verlustbehaftet
Kompression gibt es in zwei Arten. Verlustfreie Kompression gibt genau das Original zurück, was für Text, Programme, Tabellen und alles unverzichtbar ist, bei dem ein einziges falsches Bit zählt. Verlustbehaftete Kompression, die für Fotos, Musik und Video verwendet wird, verwirft Details, die Menschen kaum wahrnehmen, und erreicht weit kleinere Größen, doch das Original ist für immer verloren. Diese Seite und der Demonstrator behandeln verlustfreie Kompression, die funktioniert, indem sie Redundanz findet und entfernt: die Teile der Daten, die sich hätten vorhersagen lassen.
Lauflängencodierung
Das einfachste Verfahren ersetzt einen Lauf gleicher Symbole durch eine Anzahl und das Symbol: Zwölf weiße Pixel werden zu 12W. Faxgeräte, frühe Bitmap-Formate und das Bildformat PCX nutzten es, weil gescannte Seiten und einfache Zeichnungen voller langer Läufe sind. Bei gewöhnlichem Text ist es nutzlos, sogar schädlich: Läufe sind selten, und für jeden einzelnen Buchstaben eine Anzahl zu schreiben, verdoppelt die Größe. Die Lauflängencodierung lebt dennoch in anderen Verfahren weiter, für Läufe von Nullen, die nach einer ersten Transformation übrig bleiben.
LZ77: Zurückverweisen
1977 veröffentlichten Abraham Lempel und Jacob Ziv, zwei Forscher am Technion in Israel, ein Verfahren, das das Fachgebiet veränderte. Der Encoder behält ein Fenster mit dem gerade verarbeiteten Text. Kamen die nächsten Zeichen schon im Fenster vor, schreibt er ein Paar: wie weit zurück die frühere Kopie beginnt und wie lang sie ist. Andernfalls schreibt er das Zeichen selbst. Der Decoder braucht überhaupt kein Wörterbuch, nur den Text, den er bereits wiederhergestellt hat. Ein Verweis darf sogar den Text überlappen, den er erzeugt, sodass ein Lauf von 100 gleichen Buchstaben aus einem Buchstaben und einem Verweis besteht.
LZW: Ein Wörterbuch lernen
Das zweite Verfahren von Lempel und Ziv, LZ78, baut ein Wörterbuch auf, statt in einem Fenster zurückzublicken. Terry Welchs Verfeinerung von 1984, LZW, beginnt mit allen 256 Bytewerten, sendet bei jedem Schritt die Nummer der längsten Zeichenfolge, die es bereits kennt, und fügt diese Zeichenfolge plus das nächste Zeichen als neuen Eintrag hinzu. Der Decoder baut dasselbe Wörterbuch allein aus den Nummern wieder auf. LZW war schnell und einfach und fand Eingang in den Unix-Befehl compress, das Bildformat GIF und TIFF-Dateien, bis Patente darauf in den 1990er-Jahren einen langen Streit auslösten.
Deflate, ZIP und mehr
Das Verfahren deflate von Phil Katz, 1993 mit PKZIP 2 eingeführt, kombiniert LZ77 mit Huffman-Codierung: Nachdem es die Wiederholungen gefunden hat, gibt es den häufigsten Literalen, Längen und Abständen die kürzesten Bitcodes. Deflate wird in ZIP, gzip, PNG-Bildern und bei der Kompression von Webseiten verwendet, und es ist das Verfahren, das der Demonstrator mit dem browsereigenen Kompressor misst. Neuere Verfahren wie Zstandard, Brotli und xz nutzen größere Fenster, eine klügere Suche nach Übereinstimmungen und eine präzisere Entropiecodierung und verkleinern typische Dateien um weitere 10 bis 30 %.
Warum nicht alles schrumpfen kann
Kein Verfahren kann jede Datei verkleinern. Es gibt 2ⁿ Dateien mit n Bit, aber nur 2ⁿ − 1 Dateien, die kürzer sind. Würde ein Verfahren sie alle verkleinern, kämen zwei auf dasselbe Ergebnis und ließen sich nicht beide wiederherstellen: das Schubfachprinzip. Jeder Kompressor vergrößert daher manche Eingaben, meist zufällig wirkende Daten wie verschlüsselte Dateien, bereits komprimierte Dateien und Rauschen. Das ist zugleich ein Test auf Zufälligkeit: Daten, die kein Kompressor verkleinern kann, wirken zufällig.
Die Entropiegrenze
Claude Shannon zeigte 1948, dass die Entropie einer Quelle die kleinstmögliche durchschnittliche Anzahl Bit pro Symbol für jeden verlustfreien Code ist. Buchstabe für Buchstabe gezählt hat englischer Text eine Entropie von etwa 4 Bit pro Buchstabe, die Hälfte der 8 Bit, in denen er gespeichert wird. Verfahren, die Kontext nutzen, wie LZ77, kommen bei sich wiederholendem Text unter diesen Wert für einzelne Buchstaben, weil ein Verweis für ein ganzes Stück auf einmal steht. Die besten modernen Kompressoren, die jeden Buchstaben aus allem Vorhergehenden vorhersagen, bringen Englisch auf unter 2 Bit pro Buchstabe.
Selbst ausprobieren
Öffnen Sie den Kompressions-Demonstrator, um LZ77, LZW und Lauflängencodierung auf einen Absatz, ein Lied mit Refrain, eine Pixelzeile, eine Datentabelle, zufällige Buchstaben oder DNA anzuwenden oder auf Ihren eigenen Text. Klicken Sie auf einen beliebigen LZ77-Verweis, um zu sehen, was er kopiert, beobachten Sie, wie das LZW-Wörterbuch wächst, und vergleichen Sie alle Verfahren mit ZIP und der Entropiegrenze.
Häufig gestellte Fragen
Was bedeutet ein Kompressionsverhältnis von 3 : 1?
Dass das Original dreimal so groß ist wie die komprimierte Fassung: Die komprimierte Datei belegt also ein Drittel des Platzes und spart zwei Drittel ein. Text erreicht mit ZIP typischerweise 2 : 1 bis 4 : 1, Daten mit vielen Wiederholungen wie Logdateien oft weit mehr.
Warum hilft es nicht, eine ZIP-Datei noch einmal zu komprimieren?
Der erste Durchgang hat die Wiederholungen bereits entfernt, und seine Ausgabe wirkt nahezu zufällig. Ein zweiter Durchgang findet nichts, worauf er zurückverweisen könnte, und fügt nur seinen eigenen Overhead hinzu, sodass die Datei gleich groß bleibt oder leicht wächst.
Warum ist ein größeres LZ77-Fenster besser?
Ein größeres Fenster lässt den Encoder Wiederholungen finden, die weiter zurückliegen, etwa einen Refrain, der nach mehreren Strophen wiederkehrt. Der Preis ist, dass jeder Abstand mehr Bit zum Schreiben braucht und die Suche länger dauert; deshalb hört deflate bei 32 KB auf, während neuere Verfahren Megabytes erlauben.
Ist Kompression dasselbe wie Verschlüsselung?
Nein. Kompression macht Daten kleiner, und jeder kann sie rückgängig machen; Verschlüsselung macht Daten ohne Schlüssel unlesbar. Beides wird oft kombiniert, und dann müssen die Daten zuerst komprimiert werden: Verschlüsselte Daten wirken zufällig und lassen sich nicht mehr komprimieren.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Kompressions-Demonstrator öffnen