Original
Eingespart

Verfahren

Mehr über Kompression

Kompressions-Demonstrator

Wie kann eine Datei kleiner werden, ohne einen einzigen Buchstaben zu verlieren? Indem man bemerkt, dass sie sich wiederholt. Fügen Sie einen Text ein oder wählen Sie ein Beispiel und sehen Sie drei klassischen Verfahren bei der Arbeit zu: LZ77 verweist auf früheren Text zurück, LZW lernt beim Lesen ein Wörterbuch von Zeichenfolgen, und die Lauflängencodierung zählt Läufe desselben Zeichens. Jedes Verfahren wird wieder dekomprimiert, um zu zeigen, dass nichts verloren ging, und ein Diagramm vergleicht sie mit ZIP und mit der Entropiegrenze. Geben Sie einen Text ein, fügen Sie ihn ein oder wählen Sie ein Beispiel, und wählen Sie ein Verfahren. LZ77 ersetzt Wiederholungen durch Verweise auf früheren Text: Klicken Sie auf einen hervorgehobenen Teil, um zu sehen, was er kopiert. LZW baut beim Lesen ein Wörterbuch von Zeichenfolgen auf und sendet deren Nummern. RLE fasst Läufe desselben Zeichens zusammen. Das Diagramm vergleicht jedes Verfahren mit ZIP und mit der Entropiegrenze, und die App dekomprimiert das Ergebnis wieder, um zu prüfen, dass nichts verloren gegangen ist.

Wie es funktioniert

  1. Geben Sie einen Text ein, fügen Sie ihn ein oder wählen Sie ein Beispiel: einen Absatz, ein Lied mit Refrain, eine Pixelzeile, eine Datentabelle, zufällige Buchstaben oder DNA.
  2. Wählen Sie LZ77, LZW oder RLE. Legen Sie bei LZ77 fest, wie weit es zurückblicken darf, und klicken Sie auf einen hervorgehobenen Verweis, um den früheren Text zu sehen, den er kopiert.
  3. Vergleichen Sie die Größen in den Kacheln und im Diagramm mit ZIP und mit der Entropiegrenze; die Prüfung unter dem Text bestätigt, dass das Dekomprimieren das Original zurückgibt.

Wiederholungen sind der Schlüssel

Verlustfreie Kompression funktioniert, weil echte Daten sich wiederholen. LZ77 behält ein Fenster mit dem gerade gelesenen Text; wann immer die nächsten Zeichen schon in diesem Fenster vorkamen, schreibt es statt der Zeichen selbst einen kurzen Verweis: so weit zurückgehen und so viele Zeichen kopieren. Ein Verweis kostet eine feste Anzahl Bit, egal wie lang die Kopie ist, daher sparen lange und häufige Wiederholungen am meisten. LZW erreicht dieselbe Wirkung auf andere Weise: Es baut ein Wörterbuch aus jeder neuen Zeichenfolge auf, der es begegnet, und sendet von da an die Nummer der Zeichenfolge.

Warum manche Daten nicht schrumpfen

Ein Verfahren, das manche Dateien kleiner macht, muss andere größer machen: Es gibt weniger kurze Dateien als lange, also können nicht alle kürzer werden. Kompression gewinnt bei Daten mit Mustern wie Text, Tabellen und einfachen Bildern und verliert bei Daten ohne Muster. Zufällige Buchstaben, verschlüsselte Daten und bereits komprimierte Dateien bieten den Verfahren nichts, worauf sie zurückverweisen könnten, und die Ausgabe wird so groß wie die Eingabe oder größer. Die Lauflängencodierung zeigt das am deutlichsten: Bei Text ohne Läufe verdoppelt sie die Größe.

Häufig gestellte Fragen

Was ist der Unterschied zwischen verlustfreier und verlustbehafteter Kompression?

Verlustfreie Kompression gibt genau das Original zurück, Bit für Bit; sie ist für Text, Programme und Daten nötig, und dieser Demonstrator zeigt nur verlustfreie Verfahren. Verlustbehaftete Kompression, wie bei JPEG-Fotos, MP3-Musik und Video, verwirft Details, die Menschen kaum bemerken, und erzielt viel kleinere Dateien, aber das Original lässt sich nicht wiederherstellen.

Wie komprimiert ZIP Dateien?

ZIP und gzip verwenden deflate, das zuerst LZ77 mit einem Fenster von 32 KB anwendet und dann die Literale und Verweise mit Huffman-Codes schreibt: kurze Codes für häufige Werte und lange für seltene. Dieser zweite Schritt ist der Grund, warum ZIP meist besser abschneidet als das hier gezeigte einfache LZ77, das für jedes Token eine feste Anzahl Bit aufwendet.

Kann LZ77 unter die Entropie kommen?

Die angezeigte Entropie zählt die Zeichen einzeln, ohne Kontext. LZ77 und LZW nutzen Kontext, weil ein Verweis ein ganzes Stück früheren Textes kopiert, und können diese Zahl daher bei sich wiederholendem Text weit unterbieten. Die wahre Entropie der Quelle, die allen Kontext berücksichtigt, können sie nie unterbieten.

Warum weichen die Größen von einer echten ZIP-Datei ab?

Der Demonstrator zählt nur die Bits der codierten Daten. Eine echte ZIP-Datei fügt Header, den Dateinamen, eine Prüfsumme und die Huffman-Tabellen hinzu, die sehr kleine Dateien eher größer als kleiner machen.

Wird mein Text irgendwohin gesendet?

Nein. Jedes Verfahren, auch der ZIP-Vergleich, läuft in Ihrem Browser, und Ihr Text bleibt im lokalen Speicher dieses Browsers.

Bereit, es auszuprobieren?

Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.

Zum Editor