LZ77 (Lempel-Ziv 77) ist ein 1977 von Abraham Lempel und Jacob Ziv veröffentlichtes verlustfreies Kompressionsverfahren und der Begründer der Wörterbuchverfahren. Statt ein separates Wörterbuch zu übertragen, nutzt LZ77 ein Gleitfenster über die bereits gelesenen Daten: Wiederkehrende Textstellen werden nicht erneut gespeichert, sondern durch einen Verweis auf ihr früheres Vorkommen ersetzt.
So funktioniert das Gleitfenster
Ein Fenster gleitet über den Datenstrom und besteht aus zwei Teilen: dem bereits codierten Abschnitt (Suchpuffer) und dem als Nächstes zu codierenden Teil (Vorschau-puffer). Findet sich der aktuelle Text im Suchpuffer, wird er als Tripel aus Distanz, Länge und nächstem Zeichen codiert — Distanz misst, wie weit das Vorkommen zurückliegt, Länge, wie viele Zeichen übereinstimmen. Passt nichts, wird das Zeichen literal ausgegeben und das Fenster um eine Position weitergeschoben. Der Decoder kann jeden Verweis auflösen, weil das Fenster beim Dekomprimieren genauso entsteht.
DEFLATE und die LZ-Familie
Die Weiterentwicklung LZ78 (1978) baute das Wörterbuch explizit auf; daraus entstand LZW (GIF, TIFF). Die mit Abstand einflussreichste Kombination ist DEFLATE: Es führt LZ77 mit einer nachgelagerten Huffman-Codierung zusammen und steckt in ZIP, gzip und PNG. Moderne Verfahren wie LZMA (7z), zstd und Brotli verfeinern die LZ77-Idee mit größeren Fenstern und besserer Entropiecodierung.
Verwandte Grundlagen: Verlustfreie Kompression, Huffman-Code, Lauflängencodierung.