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.

Eine Textzeile, in der wiederholte Abschnitte durch Pfeile ersetzt sind, die auf ihr erstes Vorkommen zurückzeigen, daneben Balken mit der ursprünglichen und der komprimierten Größe
Eine Textzeile, in der wiederholte Abschnitte durch Pfeile ersetzt sind, die auf ihr erstes Vorkommen zurückzeigen, daneben Balken mit der ursprünglichen und der komprimierten Größe

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.

Abraham Lempel, der 1977 am Technion zusammen mit Jacob Ziv das Fenster-und-Verweis-Verfahren veröffentlichte, das heute LZ77 heißt.
Abraham Lempel, der 1977 am Technion zusammen mit Jacob Ziv das Fenster-und-Verweis-Verfahren veröffentlichte, das heute LZ77 heißt.

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.

Claude Shannon, der 1948 bei Bell Labs präzise bestimmte, wie viel Information eine Nachricht enthält, und sie in Bits maß.
Claude Shannon, der 1948 bei Bell Labs präzise bestimmte, wie viel Information eine Nachricht enthält, und sie in Bits maß.

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