LZ77
LZ77 ist der 1977 von Lempel und Ziv vorgeschlagene Wörterbuch-Kompressionsalgorithmus mit Schiebefenster, der frühere Daten über Tripel (Distanz, Länge, Literal) referenziert.
Zweck
Erreicht universelle verlustfreie Kompression durch Ausnutzung wiederholter Muster in den Daten; Grundlage von DEFLATE, LZSS, LZMA und anderen.
Mechanismus
Es werden ein Schiebefenster (Historienpuffer) und ein Look-ahead-Puffer gehalten; die längste Übereinstimmung des Look-ahead im Fenster wird gesucht, eine (Distanz, Länge)-Referenz oder ein Literal ausgegeben und das Fenster nach vorne geschoben.
Anwendungsfälle
- Kern der DEFLATE/gzip-Kompression
- Allgemeine Dateikompression
- Echtzeit-Stromkompression