LZ77, LZW und Deflate

Kurz: LZ77 und LZW sind Wörterbuchverfahren der Kompression: Sie ersetzen Wiederholungen durch kurze Verweise auf schon gesehene Daten. Deflate kombiniert LZ77 mit Huffman-Codierung.

Genauer: Deflate steckt in ZIP, gzip, PNG und HTTP-Kompression. Es ist das meistverwendete Kompressionsverfahren überhaupt.

Im Detail

• LZ77: Hält ein „Fenster” der letzten Kilobytes. Trifft der Encoder auf eine Wiederholung, schreibt er (Abstand, Länge) statt der Bytes. Aus abcabcabc wird abc plus „kopiere 6 Zeichen von 3 zurück”.
• LZW: Baut während des Laufs ein Wörterbuch aus Zeichenfolgen und gibt nur noch Indexe aus. Genutzt in GIF und frühem TIFF. Die Patentfrage hat seine Verbreitung einst gebremst.
• Deflate: LZ77 liefert Zeichen und Verweise, dann codiert Huffman häufige Symbole kurz. Fenster 32 KiB.
• Nachfolger: Zstandard und Brotli erreichen bessere Raten bei höherer Geschwindigkeit, siehe Brotli und Zstandard.
• Kompressionsgrenze: Zufällige oder schon komprimierte Daten lassen sich kaum verkleinern.

Siehe auch: Kompression