Ziv und Lempel komprimierten Daten, indem sie auf bereits gesendeten Text zurückverwiesen

Die klassische Kompression drehte sich um die Huffman-Kodierung, doch Huffman benötigt ein Symbolwahrscheinlichkeitsmodell, das vor der Kodierung aufgebaut sein muss. Bis 1977 ging man in den meisten Arbeiten davon aus, dass dieses Modell von irgendwoher kommen müsse.

In „A Universal Algorithm for Sequential Data Compression“ zeigten Jacob Ziv und Abraham Lempel am Technion, dass das Modell entfallen kann. Der Encoder hält ein Fenster mit kürzlich gesehenem Text und gleicht den eintreffenden Look-ahead-Puffer damit ab; eine Übereinstimmung wird als Offset und Länge geschrieben, sodass Wiederholungen fast nichts kosten.

Das Ergebnis ist ein universelles Verfahren – es komprimiert jede Quelle ohne vorherige Statistiken, weil das Wörterbuch die Daten selbst sind. Die Arbeit von 1977 ist der Klassiker, der die Wörterbuchkompression zur Grundlage von gzip, PNG und der ZIP-Familie machte.

Auf bereits gesehenen Text zurückverweisen, statt ihn vorab zu berechnen

Den bereits gesendeten Text als Wörterbuch zu verwenden, erfordert keine vorab berechnete Wahrscheinlichkeitstabelle.

Ein einzelnes Token aus Offset und Länge behandelt jede wiederholte Phrase, ob lang oder kurz.

Das Verfahren funktioniert bei unbekannten Quellen, daher ist es universell und nicht auf einen Dateityp zugeschnitten.

Baue nicht im Voraus ein Modell der Daten auf; lass die Daten ihre eigene Struktur im Verlauf liefern. Eine selbstreferenzielle Darstellung passt sich an jede Eingabe an, ganz gleich, was sie ist.

Der LZ-Ansatz wurde zur Grundlage der modernen verlustfreien Kompression: LZ77 und seine Nachfolger LZ78/LZW treiben gzip, zip, PNG und den im Web verwendeten DEFLATE-Stream an. Die Arbeiten von Ziv und Lempel erhielten 1997 den Golden Jubilee Technological Innovation Award der IEEE Information Theory Society.