> lz77 | sliding | window <
// LZ77 – Gleitfenster-Kompression mit Wörterbuchreferenzen
>> Funktionen
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.