LZ77 (Lempel-Ziv 77)Jacob Ziv, Abraham Lempel: A Universal Algorithm for Sequential Data Compression. In: IEEE Transactions on Information Theory, Nr. 3, Volume 23, 1977, S. 337–343 cs.duke.edu (PDF; 481 kB) ist ein verlustloses Verfahren zur Datenkompression, das 1977 von Abraham Lempel und Jacob Ziv veröffentlicht wurde. Es ist ein wörterbuchbasiertes Verfahren, das sich erstmals zunutze macht, dass ganze Sequenzen von Daten mehrfach in einem Datensatz vorkommen. In früher entwickelten Verfahren (z. B. Huffman-Kodierung bzw. Shannon-Fano-Kodierung) wurde ausschließlich die Häufigkeit einzelner Zeichen ausgenutzt (siehe auch Entropiekodierung). LZ77 wird als erstes LZ-Verfahren auch LZ1 genannt.
Definition Die LZ77-Faktorisierung einer Zeichenkette ist eine Zerlegung in nicht-leere Zeichenketten , sodassAnisa Al-Hafeedh et al.: A Comparison of Index-based Lempel-Ziv LZ77 Factorization Algorithms. In: ACM Computing Surveys, Nr. 1, Volume 45, 2012, S. 5:1–5:17 und für jedes mit gilt: ist ein neuer Buchstabe , der nicht in auftaucht oder ist die längste Zeichenkette, die mindestens zweimal in auftaucht. Die einzelnen Zeichenketten werden als Faktoren oder Phrasen bezeichnet.
Aus der Definition ist direkt ableitbar, dass ist. Dabei bezeichnet die Zeichenkette , die von der Position an alle Zeichen aus bis einschließlich zur Position enthält. ist die abkürzende Schreibweise für die Zeichenkette .
Algorithmus Die Idee des Algorithmus zur Berechnung der LZ77-Kompression besteht darin, den bereits verarbeiteten Präfix der Zeichenkette als Wörterbuch zu verwenden. Aus implementierungstechnischen Gründen ist die Größe dieses Wörterbuchs in der Praxis beschränkt, um die Dauer der Suche zu beschränken. Es wird deshalb in der Regel ein gleitendes Fenster (engl. ) verwendet, welches sowohl das Wörterbuch als auch den zu betrachtenden Textausschnitt (Vorschaupuffer) begrenzt. Komprimierte Zeichen werden so nach und nach vom Vorschaupuffer in das Wörterbuch verschoben. In der Praxis enthält der Puffer für das Wörterbuch mehrere tausend Zeichen und der Vorschaupuffer für den zu codierenden Ausschnitt der Zeichenkette in etwa 100 Zeichen (teilweise auch weniger).
Der Algorithmus erzeugt als Ausgabe eine Sequenz von Tripeln, mit denen der ursprüngliche Text zurückgewonnen werden kann. Ein Tripel für einen Faktor hat die Form , wobei die Position des vorherigen Vorkommens von in angibt (bzw. , falls kein vorheriges Vorkommen in existiert), die Länge des vorherigen Vorkommens von ist (bzw. 0, falls ein neues Zeichen ist) und der Mismatch-Buchstabe ist, d. h. für ist . Dabei ist zu beachten, dass bei Verwendung eines Puffers für das Wörterbuch die Position einer Zeichenkette relativ zum linken oder rechten Rand des Puffers zu verstehen ist (dies kann je nach Implementierung variieren), neue Zeichen müssen dann mit eingeführt werden. Durch das Ausgabeformat der Kompression ist die Rekonstruktion des Textes ohne explizites Abspeichern des Wörterbuches möglich.
Pseudocode Der Pseudocode ist eine Wiedergabe des LZ77-Kompressionsalgorithmus mit gleitendem Fenster: while Der Vorschaupuffer nicht leer ist; do Durchsuche rückwärts das Wörterbuch nach der längsten übereinstimmenden Zeichenkette mit dem Vorschaupuffer; if Eine Übereinstimmung wurde gefunden; then Gib das Tripel (Versatz zum Rand des Wörterbuch, Länge der gefundenen Zeichenkette, erstes nicht übereinstimmendes Zeichen aus dem Vorschaupuffer) aus; Verschiebe das Fenster um die Länge+1; else Gib das Tripel (0, 0, erstes Zeichen im Vorschaupuffer) aus; Verschiebe das Fenster um 1; end if end while
Beispiel Die Berechnung der LZ77-Faktorisierung wird anhand der Zeichenkette aacaacabcabaaac veranschaulicht.
Die Tabelle zeigt die Berechnung der LZ77-Faktorisierung unter Verwendung eines Wörterbuchs der Länge 12 und einem Vorschaupuffer der Länge 10 (Index von 0 bis 9). In der ganz rechten Spalte findet sich von oben nach unten gelesen die Ausgabe des Algorithmus (0, 0, a ), (1, 1, c ), (3, 4, b ), (3, 3, a ) und (12, 3, Ende). Die Position ist relativ zum rechten Rand des Wörterbuchs angegeben, dies muss bei der Decodierung genauso geschehen.
Die Puffer funktionieren nach dem Prinzip des gleitenden Fensters (engl.: sliding window), d. h. der zu komprimierende Datenstrom wird von rechts in die Puffer hineingeschoben. Wie im Algorithmus vermerkt, erfolgt die Verschiebung um die Länge der gefundenen Übereinstimmung im Wörterbuch und eine weitere Position. Dies führt dazu, dass redundante Tripel vermieden werden, da neue Zeichen sonst immer einzeln in das Wörterbuch übernommen werden. Im Beispiel müsste so das dritte Tripel (0, 0, c ) mit aufgenommen werden, was die Kompressionsrate allerdings deutlich verschlechtert. Dabei sind die Übereinstimmungen grün und die zu verschiebende Zeichenkette in rot gekennzeichnet. Dabei gilt zu beachten, dass immer ein Zeichen mehr verschoben wird, als in der Übereinstimmung gefunden wurde, um neue Zeichen nicht doppelt codieren zu müssen.
+ Beispiel für eine LZ77-Kompression mit gleitendem FensterZeile 12 11 10 9 8 7 6 5 4 3 2 1 0 1 2 3 4 5 6 7 8 9 Ausgabe 1 leer a a c a a c a b c a (0, 0, a ) 2 leer a a c a a c a b c a b (1, 1, c ) 3 leer a a c a a c a b c a b a a (3, 4, b ) 4 leer a a c a a c a b c a b a a a c Ende (3, 3, a ) 5 a a c a a c a b c a b a a a cEnde (12, 3, Ende)fertig
Das erste gesehene Zeichen ist unbekannt, sodass das erste a mit (0, 0, a ) aufgenommen wird. In der 2. Zeile kann das a bereits aus dem Wörterbuch gelesen werden (grün markiert), sodass c als neues Zeichen übernommen wird. In der 3. Zeile ist ein Sonderfall des LZ77-Algorithmus zu sehen, da die übereinstimmende Zeichenkette bis in das Vorschaufenster hineinragt, dies ist im Beispiel durch die grün-rote Zellfärbung dargestellt. Zeile 4 und 5 sind äquivalent zu den ersten beiden zu behandeln, mit der Ausnahme, dass im letzten Tripel ein Ende-Marker als nächstes Zeichen eingeführt wird, da der Text vollständig komprimiert wurde und es kein nächstes Zeichen gibt.
Laufzeitanalyse Wenn ein effizienter Suchalgorithmus im Wörterbuch verwendet wird, wird die Laufzeit des Algorithmus mit angegeben, wobei l die Länge des Wörterbuchs ist. Dies ist möglich, wenn der Vorschau- und Wörterbuchpuffer eine konstante Größe hat und die Suche nach einer übereinstimmenden Zeichenkette bei großen Texten nicht ins Gewicht fällt. In der praktischen Anwendung ist die Implementierung mit einer normalen Suche (ohne zusätzliche Datenstrukturen) eher langsam.
Vor- und Nachteile Ein großer Vorteil des LZ77 ist, dass er ohne jegliche Kenntnis des Textes komprimieren kann und des Weiteren nicht mit einem Patent belegt ist. Der LZ78 (der direkte Nachfolger des LZ77) benötigt für die Rekonstruktion des Textes das initiale Wörterbuch (was aber meist das triviale Wörterbuch ist, in dem jedes Einzeichen-Symbol sortiert einmal vorkommt) und war bis ins Jahr 2004 teilweise durch Patente geschützt. Ein großer Nachteil des LZ77 ist jedoch, dass er allein insbesondere bei kleinen oder nicht natürlichsprachlichen Texten wenig komprimiert oder gar die Datenmenge vergrößert. Dies wird im angegebenen Beispiel deutlich, da der originale Text 16 Zeichen beinhaltet und die Komprimierung 15 Zeichen benötigt, was nur 1 Zeichen Ersparnis bedeutet. Er eignet sich ähnlich wie die Burrows-Wheeler-Transformation oder Move-to-front-Coder sehr gut als Präprozessor, um mittels anderen Kompressionsverfahren wie z. B. einer Huffman-Kodierung Daten effektiv zu komprimieren.
Dekompression Die Dekompression von LZ77 komprimierten Dateien ist deutlich einfacher als die Kompression, da keine Suche nach übereinstimmenden Zeichenketten stattfinden muss. Die Laufzeit ist linear und hat genau so viele Schritte wie der Originaltext lang ist, also .
Pseudocode Der Pseudocode ist eine Wiedergabe des LZ77 Dekompressionsalgorithmus mit gleitendem Fenster:
for Jedes Tripel (offset, length, symbol) if length > 0; then Durchlaufe Rückwärts die bisherige Ausgabe und gib solange Zeichen aus bis eine Länge von length erreicht ist, bei einem Überlauf beginne erneut bei Offset; end if Gib Symbol aus; end for
Beispiel Die Dekompression von LZ77-Codierungen benötigt kein zusätzliches Wörterbuch, die ausgegebenen Tripel sind eindeutig, um den Text zu rekonstruieren. Die rot hinterlegten Zellen sind Zellen, die für die Rekonstruktion in der darauffolgenden Zeile verwendet werden.
+ Beispiel für eine LZ77-Dekompression mit gleitendem Fenster Zeile Eingabe 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 1 (0, 0, a ) leer a 2 (1, 1, c ) leer a a c 3 (3, 4, b ) leer a a c a a c a b 4 (3, 3, a ) leer a a c a a c a b c a b a 5 (12, 3, Ende) a a c a a c a b c a b a a a c Ende fertig
Ist der erste Eintrag eines Tripels gleich 0, wird der letzte Eintrag im Tripel an den Text angehängt (siehe Zeile 1). In Zeile 2 mit der Eingabe (1, 1, c ), wird bereits der erste Eintrag des rekonstruierten Textes aus Zeile 1 (erste Eintrag des Tripels für Position 1 und die zweite Eintrag des Tripels für die Länge 1) wieder verwendet und anschließend das Zeichen c hinten angehängt. In Zeile 3 ist die Länge der wieder verwendeten Zeichenkette länger als die gespeicherten Daten im Wörterbuch (Länge 4, aber ab Speicherzelle 3 sind nur 3 Zellen verfügbar), es wird deshalb wieder bei der Startposition (Speicherzelle 3) mit der Ausgabe fortgefahren und ein zusätzliches a ausgegeben. Anschließend wird das b als letzter Eintrag des zu verarbeitenden Tripels angehängt. Die Zeilen 4 und 5 sind analog zu verstehen. Das Ende-Zeichen wird bei Rekonstruktion ignoriert, da es global als Ende des Textes zu verstehen ist. Der vollständig rekonstruierte Text lautet aacaacabcabaaac.
Effiziente Konstruktion Für eine Laufzeit-effizientere Berechnung der LZ77-Faktorisierung einer Zeichenkette wird im Folgenden die Faktorisierung auf der kompletten Zeichenkette berechnet und das Prinzip des gleitenden Fensters aufgegeben. Schließlich wird in mehreren Anwendungen (siehe Abschnitt Verwendung) auch die LZ77-Kompression auf der gesamten Zeichenkette verwendet.
Eine bezüglich der Laufzeit effiziente Berechnung der LZ77-Faktorisierung für eine Zeichenkette ist mit Hilfe von zusätzlichen Datenstrukturen möglich. Für eine Zeichenkette bezeichne das Suffixarray und das inverse Suffixarray von , d. h. es ist genau dann, wenn . Zudem bezeichne die Länge des längsten gemeinsamen Präfixes der Zeichenketten und , wobei ist.
Die Berechnung nutzt aus, dass für einen Faktor von mit für die Bestimmung der Position des Tupels nur die Textpositionen und betrachtet werden müssen. Dabei ist (NSV steht für next smaller value) und (PSV steht für previous smaller value).Juha Kärkkäinen, Dominik Kempa, Simon J. Puglisi: Linear Time Lempel-Ziv Factorization: Simple, Fast, Small. In: CPM 2013, Lecture Notes in Computer Science, Volume 7922, Springer, 2013, ISBN 978-3-642-38904-7
Pseudocode Der Algorithmus LZ_Factor(i, psv, nsv) liefert als Rückgabe die Startposition des nächstens Faktors
Algorithmus LZ_Factor(k, psv, nsv): i = ISA[k] if lcp(k, SA[psv[i]]) > lcp(k, SA[nsv[i]]); then (pos, len) <- (SA[psv[i]], lcp(k, SA[psv[i]])) else (pos, len) <- (SA[nsv[i]], lcp(k, SA[nsv[i]])) end if if len = 0; then pos <- x[k] end if if k + len > n; then print Factor(pos, len, 'Ende') else print Factor(pos, len) end if return k + max(len, 1)
Beispiel Betrachten wir die Zeichenkette x = aaaba und k = 1. Im Suffixarray SA der Zeichenkette x starten wir bei dem Index i = ISA[k], also i = ISA = 2. Aus der Tabelle erhalten wir psv = 0, nsv = 6. Da sowohl lcp[i, psv] als auch lcp[i, nsv] gleich 0 sind, geben wir den ersten komprimierten Faktor Factor(a, 0) aus. Die nächste zu suchende Position ist k + max(len, 1) = 2. +iSAISAx[SA[i]..n]psv[i]nsv[i]0 - infinity152a02213aaaba06324aaba26435aba36541b466 - infinity