Lempel-Ziv-Algorithmus: Daten verkleinern mit dem Wörterbuch
Kompressionsalgorithmen sind ein unverzichtbarer Bestandteil des Internets und der Computerlandschaft. Ihr Ziel ist es, häufig vorkommende Daten mit möglichst wenig Speicher abzubilden. Das lässt sich grundsätzlich auf zwei Wegen erreichen: durch eine Optimierung der Codewörter, so dass etwa häufig vorkommende Buchstaben mit nur wenigen Bits repräsentiert werden (Entropie-Codierung, darauf basiert die Huffman-Codierung, g+ ), oder indem häufig vorkommende Datenblöcke durch Codes ersetzt werden.
Der zweite Ansatz wird als Wörterbuchkompression bezeichnet, da die zu codierenden Daten wie ein Text aufgefasst werden. Die Idee ist, dass sie aus Blöcken – sinnbildlich den Wörtern – bestehen, die idealerweise mehrfach vorkommen. Anstatt die Wörter auszuschreiben, werden ihre Einträge im Wörterbuch angegeben. Je nach Länge und Anzahl der Wörter kann diese Darstellung mit deutlich weniger Speicher auskommen. Der wohl bekannteste Algorithmus wurde 1977 von den beiden israelischen Wissenschaftlern Abraham Lempel und Jacob Ziv veröffentlicht (PDF)(öffnet im neuen Fenster) . Bekannt ist er als LZ77 – wir erklären, wie er funktioniert.