LZ77-Algorithmus im Detail: Wie funktioniert Wörterbuchkomprimierung?

Fazit vorab: LZ77 ist ein auf einem gleitenden Fenster basierender Wörterbuch-Komprimierungsalgorithmus. Die Kernidee lautet „historische Daten als Wörterbuch verwenden, bei Wiederholungen zurückverweisen". Bei der Codierung wird ein Tripel (distance, length, next_char) ausgegeben: Gehe distance Zeichen zurück, um eine Übereinstimmung zu finden, mit der Länge length, gefolgt von einem nicht übereinstimmenden Zeichen next_char. Am Beispiel der 11 Zeichen „abracadabra" reicht die LZ77-Codierung mit nur 5 Tripeln aus — ein signifikanter Komprimierungseffekt. LZ77 ist eine Kernkomponente von DEFLATE (ZIP/GZIP/PNG) und der gemeinsame Vorfahre moderner Komprimierungsalgorithmen wie LZSS/LZMA/LZ4. Im Folgenden wird beginnend mit dem Prinzip des gleitenden Fensters der Codierungsprozess schrittweise demonstriert.

Wenn Sie mit den Prinzipien der Huffman-Codierung noch nicht vertraut sind, lesen Sie zunächst Huffman-Codierungsprinzip: Der Grundstein der Komprimierungsalgorithmen.

1. Was ist Wörterbuchkomprimierung

Komprimierungsalgorithmen lassen sich in zwei Hauptrichtungen unterteilen: Statistische Codierung (wie Huffman-Codierung) weist ZeichenCodes variabler Länge nach Häufigkeit zu; Wörterbuchkomprimierung ersetzt wiederkehrende Inhalte durch „Zeigerverweise". LZ77 gehört zur Richtung der Wörterbuchkomprimierung und baut keine vorab erstellte Wörterbuchtabelle auf, sondern verwendet bereits verarbeitete historische Daten als implizites Wörterbuch — bei Wiederholungen wird ein „Rückverweis" auf eine zuvor erschienene Position ausgegeben.

Komprimierungsrichtung	Kernprinzip	Repräsentative Algorithmen	Vorteile	Nachteile
Statistische Codierung	Nach Häufigkeit variable Codes zuweisen	Huffman, arithmetische Codierung	Nähert sich Entropie-Grenze	Schwach bei langreichweiten Wiederholungen
Wörterbuchkomprimierung	Wiederholungen durch Verweise ersetzen	LZ77, LZW, LZMA	Stark bei Wiederholungsmustern	Wirkungslos bei Zufallsdaten
Hybridcodierung	Wörterbuch + Statistik in zwei Stufen	DEFLATE, ZSTD	Gesamt optimal	Komplexere Implementierung
Transformationscodierung	Transformation in Frequenzbereich + Quantisierung	DCT (JPEG), DWT	Hohe verlustbehaftete Komprimierung	Informationsverlust

In der Praxis sind die beliebtesten Komprimierungsalgorithmen fast alle „Hybridcodierungen" — zuerst eliminiert LZ77 Wiederholungsmuster, dann komprimiert Huffman die Restdaten nach Häufigkeit. DEFLATE ist die klassische Kombination aus LZ77 + Huffman und wird von ZIP, GZIP und PNG weit verbreitet eingesetzt.

2. LZ77-Algorithmusprinzip im Detail

Der Kern von LZ77 ist der Mechanismus des gleitenden Fensters. Das Fenster ist in zwei Teile unterteilt: den Suchpuffer (bereits verarbeitete historische Daten) und den Lookahead-Puffer (zu verarbeitende zukünftige Daten). Bei der Codierung wird ein Abschnitt aus dem Lookahead-Puffer entnommen und im Suchpuffer die längste Übereinstimmung gesucht. Wird eine gefunden, wird ein Tripel ausgegeben, andernfalls das Originalzeichen.

1. Struktur des gleitenden Fensters

Die Größe des gleitenden Fensters bestimmt direkt die Komprimierungswirkung — je größer das Fenster, desto mehr historische Daten können durchsucht werden, und desto höher ist die Match-Wahrscheinlichkeit. Die Fenstergrößen verschiedener Algorithmen unterscheiden sich erheblich.

Algorithmus	Suchpuffer	Lookahead-Puffer	Max. Match-Länge	Typisches Szenario
LZ77 (Original)	Wenige KB	Wenige Dutzend Bytes	16 Bytes	Lehrbeispiel
DEFLATE	32 KB	258 Bytes	258 Bytes	ZIP/GZIP/PNG
LZMA	8 MB (konfigurierbar)	273 Bytes	273 Bytes	7z/xz-Archiv
LZ4	64 KB	Unbegrenzt	Unbegrenzt	Echtzeitkomprimierung
ZSTD	8 MB (max. 1 GB)	Unbegrenzt	Unbegrenzt	Moderne Universalkomprimierung

2. Tripel-Codierungsformat

Die Ausgabeeinheit von LZ77 ist das Tripel (distance, length, next_char). Die Bedeutung der drei Felder ist in der folgenden Tabelle aufgeführt.

Feld	Bedeutung	Wertebereich (DEFLATE)	Codierungsbits	Beispiel
distance	Rückbezugsdistanz (wie viele Zeichen zurück)	1–32768	15 Bit	distance=10 → 10 Zeichen zurück
length	Match-Länge (wie viele Zeichen übereinstimmend)	3–258	8 Bit	length=5 → 5 Zeichen Übereinstimmung
next_char	Zeichen nach dem Match	0–255	8 Bit	next_char='d' → ASCII 100

Das Geniale am Tripel ist, dass nach dem Match ein zusätzliches next_char ausgegeben wird, wodurch sichergestellt wird, dass der Encoder immer mindestens 1 Zeichen vorankommt und nicht stecken bleibt. Wenn keine Übereinstimmung gefunden wird (length=0), sind distance und length beide 0, und nur next_char wird ausgegeben — entsprechend einer Rückkehr zur direkten Zeichenspeicherung.

3. Match-Suchstrategie

Die Match-Suche ist der Leistungsengpass von LZ77 — ein Abschnitt aus dem Lookahead-Puffer wird mit dem Suchpuffer auf die längste Übereinstimmung verglichen. Die Brute-Force-Suche hat O(n×m)-Komplexität, praktische Implementierungen verwenden Hashtabellen oder Suffixbäume zur Beschleunigung.

Suchstrategie	Datenstruktur	Suchkomplexität	Speicherbedarf	Typische Anwendung
Brute-Force	Keine	O(n×m)	Keine	Lehrbeispiel
Hash-Kette	Hashtabelle + verkettete Liste	O(n) durchschnittlich	Niedrig	zlib (DEFLATE)
Hash-Bucket	Hashtabelle + Array	O(1) durchschnittlich	Mittel	LZ4
Suffix-Baum	Suffix-Baum / Suffix-Array	O(n) Worst-Case	Hoch	LZMA

3. Praxisbeispiel: „abracadabra"-Codierungsdemonstration

LZ77 wird verwendet, um „abracadabra" (11 Zeichen) vollständig zu codieren. Der Anfangszustand: Der Suchpuffer ist leer, der Lookahead-Puffer enthält die gesamte Zeichenkette. Es wird Position für Position gescannt und im historischen Datenbereich die längste Übereinstimmung gesucht.

Originaltext: a b r a c a d a b r a

Codierungsprozess:

Schritt	Aktuelle Position	Lookahead-Inhalt	Suchpuffer-Suche	Ausgabe-Tripel	Beschreibung
1	Position 1	abracadabra	Leer, kein Match	(0, 0, 'a')	Erstes Zeichen, direkt ausgeben
2	Position 2	bracadabra	„a", kein Match für „b"	(0, 0, 'b')	Erstes Vorkommen, direkt ausgeben
3	Position 3	racadabra	„ab", kein Match für „r"	(0, 0, 'r')	Erstes Vorkommen, direkt ausgeben
4	Position 4	acadabra	„a" in „abr" gefunden	(0, 0, 'a')	„a" vorhanden, aber Folge stimmt nicht
5	Position 5	cadabra	Kein „c" in „abra"	(0, 0, 'c')	Erstes Vorkommen, direkt ausgeben
6	Position 6	adabra	„a" in „abrac" gefunden	(0, 0, 'a')	„a" Match, aber Folge stimmt nicht
7	Position 7	dabra	Kein „d" in „abraca"	(0, 0, 'd')	Erstes Vorkommen, direkt ausgeben
8	Position 8	abra	7 zurück, Match „abra" gefunden	(7, 4, end)	Match „abra" 4 Zeichen

Codierungseffizienz-Vergleich:

Codierungsart	Anzahl Ausgabeeinheiten	Bit pro Einheit	Gesamt-Bit	vs Original Ersparnis
ASCII-Original	11 Zeichen	8	88	— (Basis)
LZ77 (ohne Match-Optimierung)	8 Tripel	31 (Durchschnitt)	248	-182 % (Aufblähung)
LZ77 (optimierte Markierungsbits)	8 Einheiten	12 (Durchschnitt)	96	-9 % (leichte Aufblähung)
LZ77+Huffman	8 Einheiten	4,5 (Durchschnitt)	36	59 %

Ergebnisanalyse: Reines LZ77 kann bei kurzen Zeichenketten aufblähen (Tripel beanspruchen mehr Platz als Originalzeichen). Das ist der Grund, warum LZ77 normalerweise mit Huffman-Codierung kombiniert wird — DEFLATE ist LZ77 + Huffman. Im „abracadabra"-Beispiel ist die Übereinstimmung an Position 8 („abra", distance=7, length=4) der entscheidende Komprimierungspunkt, bei dem 4 Zeichen durch ein Tripel dargestellt werden. Bei längeren Texten mit mehr Wiederholungsmustern (wie Code-Dateien, Logs) steigt die Komprimierungswirkung von LZ77 deutlich.

4. LZ77-Varianten und moderne Weiterentwicklung

Seit der Veröffentlichung von LZ77 im Jahr 1977 sind zahlreiche Varianten entstanden, die jeweils eine bestimmte Dimension für spezifische Szenarien optimieren. Die folgende Tabelle vergleicht die wichtigsten Mitglieder der LZ77-Familie.

Algorithmus	Schlüsselverbesserung	Komprimierungsrate	Komprimierungsgeschw.	Dekomprimierungsgeschw.	Typische Anwendung
LZ77 (Original)	Tripel-Codierung	Niedrig	Langsam	Mittel	Lehre
LZSS	Markierungsbits zur Unterscheidung Match/Literal	Mittel	Mittel	Schnell	Frühe Systeme
DEFLATE	LZSS + Huffman in zwei Stufen	Mittel-hoch	Mittel	Schnell	ZIP/GZIP/PNG
LZMA	Großes Fenster + Range-Codierung + optimale Analyse	Hoch	Langsam	Mittel	7z/xz-Archiv
LZ4	Komprimierungsrate für maximale Geschwindigkeit geopfert	Niedrig	Sehr schnell	Sehr schnell (4 GB/s)	Echtzeit / Kernel
LZW	Explizite Wörterbuchtabelle (kein gleitendes Fenster)	Mittel	Schnell	Schnell	GIF/TIFF
ZSTD	LZ77-Variante + FSE + Wörterbuchvorgabe	Hoch	Schnell	Sehr schnell	Moderne Universalkomprimierung

Der Entwicklungstrend zeigt, dass moderne Algorithmen (ZSTD, brotli) bei gleichzeitig hoher Komprimierungsrate die Geschwindigkeit erheblich steigern und DEFLATE allmählich als neue Generation ablösen. Die Kernidee von LZ77 — Wörterbuchverweise über ein gleitendes Fenster — ist jedoch unverändert geblieben, und alle Varianten bauen auf dieser Grundlage auf.

Szenario	Empfohlener Algorithmus	Begründung	Referenz-Komprimierungsrate
Dateiarchivierung	LZMA (xz)	Höchste Komprimierungsrate, Geschwindigkeit sekundär	70 %–85 %
Universelle Komprimierung	ZSTD	Komprimierungsrate und Geschwindigkeit ausgewogen	60 %–80 %
Echtzeitübertragung	LZ4	Dekomprimierung 4 GB/s, minimale Latenz	50 %–65 %
Web-Übertragung	DEFLATE/GZIP	Beste Kompatibilität, alle Browser unterstützen	50 %–70 %
Bildformat	DEFLATE (PNG)	Verlustfrei, geeignet für Grafiken	50 %–75 %
In-Memory-Daten	LZ4	Niedrige CPU-Last, geeignet für hochfrequente Komprimierung	50 %–65 %

Die spezifische Anwendung von DEFLATE im PNG-Format wird unter PNG-Kompressionsprinzipien im Detail erläutert. Den Unterschied zwischen verlustfreier und verlustbehafteter Komprimierung finden Sie unter Verlustfrei vs. verlustbehaftet: Die Kernunterschiede.

5. Häufig gestellte Fragen (FAQ)

F1: Was ist der LZ77-Algorithmus?

LZ77 ist ein auf einem gleitenden Fenster basierender Wörterbuch-Komprimierungsalgorithmus, der 1977 von Lempel und Ziv vorgestellt wurde. Die Kernidee: Bereits verarbeitete Daten dienen als Wörterbuch; bei wiederkehrenden Inhalten wird das Original durch ein Tripel (distance, length, next_char) ersetzt, wobei distance die Rückbezugsdistanz, length die Übereinstimmungslänge und next_char das Zeichen nach der Übereinstimmung angibt. LZ77 ist eine Kernkomponente von DEFLATE (ZIP/GZIP/PNG) und der Vorfahre moderner Algorithmen wie LZSS/LZMA/LZ4.

F2: Was bedeutet das gleitende Fenster bei LZ77?

Das gleitende Fenster ist die Kern-Datenstruktur von LZ77 und besteht aus dem Suchpuffer (bereits verarbeitete historische Daten) und dem Lookahead-Puffer (zu verarbeitende zukünftige Daten). Bei der Codierung wird ein Abschnitt aus dem Lookahead-Puffer entnommen und im Suchpuffer die längste Übereinstimmung gesucht. Eine typische Fenstergröße ist 32 KB (DEFLATE-Standard) — je größer das Fenster, desto höher die Match-Wahrscheinlichkeit, aber desto größer der Speicherbedarf. Die Fenstergröße bestimmt die Obergrenze der maximalen Rückbezugsdistanz distance.

F3: Was ist der Unterschied zwischen LZ77 und LZ78?

LZ77 verwendet ein gleitendes Fenster als implizites Wörterbuch, wobei Übereinstimmungen direkt auf historische Daten verweisen, ohne ein separates Wörterbuch zu speichern; LZ78 verwendet eine explizite Wörterbuchtabelle, in der bereits gesehene Zeichenfolgen als nummerierte Einträge gespeichert und bei der Codierung als Wörterbuchindizes ausgegeben werden. LZ77 eignet sich besser für Daten mit lokalen Wiederholungen (wie Text), LZ78 besser für global wiederkehrende Daten. In der Praxis sind die Nachfahren von LZ77 (DEFLATE/LZMA/LZ4) weitaus verbreiteter als die Nachfahren von LZ78 (LZW).

F4: Welcher hat die höchste Komprimierungsrate: LZ77, LZMA oder LZ4?

Rangfolge der Komprimierungsraten: LZMA > LZ77 (DEFLATE) > LZ4. LZMA verwendet ein größeres Fenster (standardmäßig 8 MB), einen besseren Match-Algorithmus und Range-Codierung und erreicht die höchste Komprimierungsrate bei der langsamsten Geschwindigkeit; DEFLATE mit 32-KB-Fenster + Huffman bietet mittlere Komprimierungsrate bei mittlerer Geschwindigkeit; LZ4 opfert Komprimierungsrate für maximale Geschwindigkeit und erreicht Dekomprimierungsraten bis zu 4 GB/s. Die Wahl hängt vom Szenario ab: Archivierung → LZMA, universell → DEFLATE/ZSTD, Echtzeit → LZ4.

Zusammenfassung

LZ77 ist der Urvater der Wörterbuch-Komprimierungsalgorithmen. Das Kernprinzip lautet „gleitendes Fenster + Tripel-Verweis": Historische Daten dienen als implizites Wörterbuch, und bei Wiederholungen wird ein Tripel (distance, length, next_char) ausgegeben. Reines LZ77 kann bei kurzen Texten aufblähen, aber in Kombination mit Huffman-Codierung (DEFLATE) wird es zum Standard-Komprimierungsverfahren von ZIP/GZIP/PNG. Die moderne Variante LZMA strebt nach maximaler Komprimierungsrate, LZ4 nach maximaler Geschwindigkeit, und ZSTD vereint beide.

Drei Schlüsselpunkte zum Verständnis von LZ77: Erstens bestimmt das gleitende Fenster den Match-Bereich (DEFLATE 32 KB, LZMA 8 MB). Zweitens ist das Tripel die Grundeinheit der Codierung (Rückbezug + Länge + nächstes Zeichen). Drittens bestimmt die Match-Suchstrategie die Leistung (Hash-Kette am schnellsten, Suffix-Baum am optimalsten). Die Hybridcodierung aus LZ77 + Huffman ist der Goldstandard der modernen verlustfreien Komprimierung.