> lz77 | sliding | window <
// LZ77 – Gleitfenster-Kompression mit Wörterbuchreferenzen
Wörterbuchkodierung
Verwendet Referenzen mit Versatz und Länge für wiederholte Muster.
Gleitendes Fenster
Hält ein bewegliches Fenster für die Mustersuche.
Basisalgorithmus
Bildet die Grundlage für ZIP, GZIP, DEFLATE und PNG.
>> Technische Infos
Wie LZ77 funktioniert:
LZ77 verwaltet ein gleitendes Fenster mit kürzlich gesehenen Daten. Für jede Position sucht der Algorithmus im Fenster nach der längsten passenden Teilzeichenkette. Wird ein Treffer gefunden, wird eine Referenz (Versatz, Länge, nächstes Zeichen) ausgegeben. Wenn kein Treffer existiert, wird ein Literal (0,0,Zeichen) ausgegeben. Dadurch werden Wiederholungen durch kurze Referenzen ersetzt und die Daten verlustfrei komprimiert.
LZ77-Beispiel:
Text: "ABCABCABC" Window=4, Lookahead=4 Position 0: 'A' – kein Treffer → (0,0,A) Position 1: 'B' – kein Treffer → (0,0,B) Position 2: 'C' – kein Treffer → (0,0,C) Position 3: 'ABC' – Treffer mit Versatz 3 → (3,3,A) Position 7: 'BC' – Treffer mit Versatz 3 → (3,2,) Ausgabe: (0,0,A)(0,0,B)(0,0,C)(3,3,A)(3,2,)
Warum LZ77 verwenden?:
- ▸Verlustfreie Komprimierung
- ▸Keine Vorkenntnisse über die Daten nötig
- ▸Passt sich den Datenmustern an
- ▸Einfach zu implementieren
- ▸Basis vieler moderner Komprimierungsverfahren
>> Häufig gestellte Fragen
Was ist LZ77?
LZ77 ist ein universeller, verlustfreier Datenkomprimierungsalgorithmus, der 1977 von Abraham Lempel und Jacob Ziv veröffentlicht wurde. Er ersetzt wiederkehrende Daten im Strom durch Referenzen auf frühere Vorkommen im unkomprimierten Datenstrom.
Wie funktioniert das Gleitfenster?
Das Gleitfenster besteht aus einem Suchpuffer (bereits verarbeitete Daten) und einem Lookahead-Puffer (zu komprimierende Daten). Der Algorithmus sucht im Suchpuffer nach dem längsten Match mit dem Beginn des Lookahead-Puffers und gibt dann eine Referenz oder ein Literal aus.
LZ77 im Vergleich zu moderner Komprimierung?
LZ77 ist die Grundlage vieler moderner Komprimierungsalgorithmen. DEFLATE, das in ZIP und GZIP verwendet wird, kombiniert LZ77 mit Huffman-Codierung. LZSS reduziert Redundanz in LZ77, während LZ78 und LZW das Wörterbuch anders aufbauen, aber auf ähnlichen Prinzipien basieren.
Welche Fenstergrößen sind sinnvoll?
Typische Fenstergrößen liegen bei 32–64 KB für allgemeine Daten. Größere Fenster finden mehr Übereinstimmungen, benötigen aber mehr Speicher und Zeit. DEFLATE verwendet 32 KB. Der Lookahead-Puffer ist in der Regel 256–512 Byte groß. Die optimale Größe hängt von den Wiederholungsmustern Ihrer Daten ab.
// Durchgerechnetes Beispiel
| # | Offset | Length | Next | Output |
|---|---|---|---|---|
| 1 | 0 | 0 | a | a |
| 2 | 0 | 0 | b | b |
| 3 | 0 | 0 | r | r |
| 4 | 3 | 1 | c | a + c |
| 5 | 2 | 1 | d | a + d |
| 6 | 7 | 4 | — | abra |
// Codebeispiele
Input abracadabra (positions 0..10)
Token (offset, length, next)
offset = distance back into the window, length = bytes copied
Decode copy `length` bytes starting `offset` back, then append `next`
(the copy may overlap its own output, e.g. (1,5,x) repeats a byte)
Window the sliding search buffer; deflate/gzip use 32 KiB
>> Weitere Fragen
F: Was bedeutet das Tripel (Offset, Länge, Zeichen)?
A: Der Offset gibt an, wie weit im bereits gesehenen Fenster zurückgegriffen wird, die Länge, wie viele Bytes von dort kopiert werden, und das Zeichen ist das nächste neue Byte. Der Decoder baut die Ausgabe damit schrittweise wieder auf.
F: Warum darf sich die Kopie überlappen?
A: Ist der Offset kleiner als die Länge, liest die Kopie Bytes, die sie gerade erst geschrieben hat. So entstehen Wiederholungen: (1, 5, x) erzeugt fünfmal das vorherige Zeichen. Das ist die Grundlage von Lauflängen-ähnlichen Effekten in LZ77.
F: Wo wird LZ77 eingesetzt?
A: LZ77 steckt in DEFLATE (gzip, zlib, PNG, ZIP) und, in Varianten, in LZ4, Snappy, Zstandard und Brotli. Die Größe des Fensters und die Suchstrategie bestimmen Kompressionsrate und Geschwindigkeit.