06.05.2026
Auf dieser Seite geht es um eine Familie von Datenkompressionsalgorithmen aus den 1970er Jahren. Sie bilden die Grundlage vieler heutiger Kompressionstechniken, wie sie etwa in ZIP-, GIF- und PNG-Dateien zu finden sind. Wer meine Seite über Huffman-Kodierung gelesen hat, kennt bereits eine Kompressionstechnik. Huffman nimmt eine Eingabe fester Größe und kodiert sie in eine Ausgabe variabler Länge. Lempel-Ziv '77, besser bekannt als LZ77, macht das Gegenteil: Es kodiert einen Eingabeabschnitt variabler Länge mit einem Code fester Länge.
Oben ist die LZ77-Kompression in Aktion zu sehen: Beim einmaligen Durchlaufen des Eingabecodes (links) vergleicht der Algorithmus ein Schiebefenster hinter der aktuellen Position (in Grün) mit einem Vorausschaubereich (in Blau) davor. Gibt es eine gemeinsame Teilzeichenkette, wird sie in der Ausgabe durch ein (Offset, Länge)-Paar referenziert, sodass die Teilzeichenkette nicht doppelt kodiert werden muss. Die Ausgabe dieses Schritts enthält also einfache Zeichen aus der Eingabe, gemischt mit Paaren, die auf frühere Eingabe verweisen.
Der LZ77-Algorithmus ist nach seinen Erfindern Abraham Lempel und Jacob Ziv benannt. Expansion bzw. Dekompression ist hier einfacher als Kompression. Das Programm kopiert die Eingabezeichen einfach zurück in die Ausgabe und fügt Zeichenketten aus Rückverweisen an der aktuellen Position ein. Dies ist oben zu sehen. Bei diesem kleinen Beispiel erreichen wir nicht besonders viel Kompression. In einem realen System wären die Schiebefenster größer, und es gäbe mehr Möglichkeiten für Übereinstimmungen, auf Kosten von mehr Rechenaufwand.
LZ78 ist der Verwandte von LZ77 und wurde, wie der Name vermuten lässt, ein Jahr später erfunden. Während LZ77 lokale Kompression innerhalb eines Fensters durchführt, setzt LZ78 auf globale Kompression, indem es ein Wörterbuch von Zeichenketten pflegt, das bei der Verarbeitung der Eingabe immer weiter wächst. Oben befindet sich nun ein Wörterbuch zwischen Eingabe und Ausgabe, das automatisch beim Durchlaufen der Eingabe aufgebaut wird. Die Ausgabe ist eine Folge von Paaren, bestehend aus einem Code gefolgt von einem Zeichen. Ist der Code null, bedeutet das, bei der Expansion einfach das Zeichen auszugeben. Gleichzeitig erhält das Zeichen einen inkrementellen Code im Wörterbuch. Ist der Code in der Ausgabe größer als null, steht das Paar für den entsprechenden Eintrag im Wörterbuch gefolgt vom Zeichen, und auch diese neue Zeichenkette bekommt einen Code in unserem Übersetzungswörterbuch.
Das Kodierungswörterbuch wächst automatisch während der Kompression und Dekompression und sollte in beiden Fällen die gleichen Codes enthalten. Durch diese Raffinesse der Algorithmen muss das Wörterbuch nicht in der komprimierten Datei gespeichert werden, was viel Platz spart. Das letzte Paar hat kein Zeichen und markiert das Ende der Ausgabe.
Die LZ78-Expansion ist unkompliziert, aber es muss darauf geachtet werden, das Wörterbuch mit exakt dem gleichen Inhalt wie bei der Kompression aufzubauen. Nach der Ausgabe einer Zeichenkette muss diese wie zuvor mit dem nächsten inkrementellen Code in unser Wörterbuch aufgenommen werden. Ein blauer Hintergrund im Wörterbuch zeigt einen neuen Eintrag an, während ein grüner Hintergrund eine erfolgreiche Suche kennzeichnet.
Das Wörterbuch, das LZ78 während der Kompression aufbaut, ist im Wesentlichen ein Trie. Jeder Knoten zeigt links das Zeichen und rechts seinen Wörterbuchcode. Der Wurzelknoten repräsentiert das leere Präfix mit Code 0. Wenn ein neuer Eintrag hinzugefügt wird, durchläuft der Algorithmus den Trie von der Wurzel bis zum Knoten des passenden Präfixes und hängt dann ein neues Kind für das nächste Zeichen an. Der Trie, der während der Kompression aufgebaut wird, enthält die gleichen Informationen wie das Wörterbuch bei der Dekompression. Während LZ78 bei globaler, dateiweiter Kompression besser abschneidet als LZ77, benötigt es mehr Speicher, um den Trie im Arbeitsspeicher zu halten. Oben ist zu sehen, wie der Trie beim Kodieren einer kurzen Zeichenkette aufgebaut wird.
LZW ist eine Variante von LZ78, die 1984 von Terry Welch veröffentlicht wurde. Der wesentliche Unterschied besteht darin, dass das Wörterbuch mit allen Einzelzeichen aus der Eingabe vorinitialisiert wird. Da jedes Zeichen bereits im Wörterbuch steht, muss LZW nie ein rohes Zeichen ausgeben — es gibt immer einen Code aus. Oben ist zu sehen, wie das Wörterbuch mit Einzelzeichen-Einträgen beginnt und wächst, wenn während der Kompression längere Zeichenketten entdeckt werden. Die Ausgabe ist eine Folge von Codes, die jeweils auf einen Wörterbucheintrag verweisen. Die Datenstruktur wird hier als Tabelle dargestellt, aber wie bei LZ78 wird sie bei der Kompression als Trie implementiert.
Die LZW-Expansion rekonstruiert das Wörterbuch aus dem Strom von Codes. Der Decoder beginnt mit dem gleichen Einzelzeichen-Wörterbuch wie der Encoder. Für jeden empfangenen Code wird die entsprechende Zeichenkette nachgeschlagen und ausgegeben. Gleichzeitig wird ein neuer Wörterbucheintrag hinzugefügt, der aus der vorherigen Ausgabezeichenkette plus dem ersten Zeichen der aktuellen besteht. Auf diese Weise rekonstruiert der Decoder exakt das gleiche Wörterbuch, das der Encoder aufgebaut hat, ohne dass es in den komprimierten Daten gespeichert werden muss.
Wir haben auf dieser Seite drei klassische Kompressionsmethoden kennengelernt, jede in ihrer ursprünglichen Formulierung recht einfach. Doch zusammen sind sie die Vorfahren vieler moderner Datei- und Stromkompressionen.
Das Claude Opus LLM hat bei der Erstellung dieser Seite geholfen. Weitere Algorithmen und Datenstrukturen finden sich auf der Hauptseite.
Bitte teilt diese Seite auf Social Media!