LZ77

LZ77 (Lempel-Ziv 77) 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 $x$ ist eine Zerlegung in nicht-leere Zeichenketten $w_{1},w_{2},\ldots ,w_{k}$, sodass

• $x=w_{1}w_{2}\cdots w_{k}$ und
• für jedes $w_{j}$ mit $1\leq j\leq k$ gilt:
  • $w_{j}$ ist ein neuer Buchstabe $\alpha$, der nicht in $w_{1}\cdots w_{j-1}$ auftaucht oder
  • $w_{j}$ ist die längste Zeichenkette, die mindestens zweimal in $w_{1}\cdots w_{j}$ auftaucht.

Die einzelnen Zeichenketten $w_{j}$ werden als Faktoren oder Phrasen bezeichnet.

Aus der Definition ist direkt ableitbar, dass $w_{1}=x[1]$ ist. Dabei bezeichnet $x[i\dots j]$ die Zeichenkette $x$, die von der Position $i$ an alle Zeichen aus $x$ bis einschließlich zur Position $j$ enthält. $x[i]$ ist die abkürzende Schreibweise für die Zeichenkette $x[i\dots i]$.

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.

sliding window

) 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 $w_{j}$ hat die Form $(pos,len,\lambda )$, wobei

• $pos$ die Position des vorherigen Vorkommens von $w_{j}$ in $x$ angibt (bzw. $0$, falls kein vorheriges Vorkommen in $x$ existiert),
• $len$ die Länge des vorherigen Vorkommens von $w_{j}$ ist (bzw. 0, falls $w_{j}$ ein neues Zeichen ist)
• und $\lambda$ der Mismatch-Buchstabe ist, d. h. für $j\leq k$ ist $\lambda =x[|w_{1}w_{2}\cdots w_{j-1}|+len+1]$.

Dabei ist zu beachten, dass bei Verwendung eines Puffers für das Wörterbuch die Position $pos$ 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 $(0,0,\lambda )$ 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 Fenster

Zeile

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

$\Longrightarrow$  (0, 0, a )

2

leer

a

a

c

a

a

c

a

b

c

a

b

$\Longrightarrow$  (1, 1, c )

3

leer

a

a

c

a

a

c

a

b

c

a

b

a

a

$\Longrightarrow$  (3, 4, b )

4

leer

a

a

c

a

a

c

a

b

c

a

b

a

a

a

c

Ende

$\Longrightarrow$  (3, 3, a )

5

a

a

c

a

a

c

a

b

c

a

b

a

a

a

c

Ende

$\Longrightarrow$  (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

Die Laufzeit des Algorithmus wird mit $\Theta (n)$ angegeben, da der Text bei der Kompression nur einmal durchlaufen wird. 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 $\Theta (n)$.

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

$\Longrightarrow$  (0, 0, a )

leer

a

2

$\Longrightarrow$  (1, 1, c )

leer

a

a

c

3

$\Longrightarrow$  (3, 4, b )

leer

a

a

c

a

a

c

a

b

4

$\Longrightarrow$  (3, 3, a )

leer

a

a

c

a

a

c

a

b

c

a

b

a

5

$\Longrightarrow$  (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 $x$ bezeichne $SA$ das Suffixarray und $ISA$ das inverse Suffixarray von $x$, d. h. es ist $ISA[i]=j$ genau dann, wenn $SA[j]=i$. Zudem bezeichne $lcp(i,j)$ die Länge des längsten gemeinsamen Präfixes der Zeichenketten $x[SA[i]..n]$ und $x[SA[j]..n]$, wobei $n=|x|$ ist.

Die Berechnung nutzt aus, dass für einen Faktor $w_{j}$ von $x$ mit $|w_{j}|>1$ für die Bestimmung der Position $pos$ des Tupels nur die Textpositionen $SA[NSV[ISA[j]]]$ und $SA[PSV[ISA[j]]]$ betrachtet werden müssen. Dabei ist $NSV[j]=min\{i\in \{j+1,\ldots ,n\}\,|\,SA[i]<SA[j]\}$ (NSV steht für next smaller value) und $PSV[j]=max\{i\in \{1,\ldots ,j-1\}\,|\,SA[i]<SA[j]\}$ (PSV steht für previous smaller value).

Pseudocode

Der Algorithmus LZ_Factor(i, psv, nsv) liefert als Rückgabe die Startposition des nächstens Faktors

 Algorithmus LZ_Factor(i, psv, nsv):
     if lcp(i, psv) > lcp(i, nsv); then
         (pos, len) <- (psv, lcp(i, psv))
     else
         (pos, len) <- (nsv, lcp(i, nsv))
     end if
     if len = 0; then
         pos <- i
     end if
     if i + len > n; then
         print factor(pos, len, 'Ende')
     else
         print factor(pos, len, x[i+len])
     end if
     return i + max(len, 1)

Die beiden Arrays $NSV$ und $PSV$ können aus dem Suffixarray $SA$ in Linearzeit berechnet werden:

 for i <- 2 to n+1; do
     j <- i-1
     while defined(j) and SA[i] < SA[j]; do
         NSV[j] <- i
         j <- PSV[j]
     end while
     PSV[i] <- j
 end for

Abschließend folgt der Algorithmus zur Berechnung der LZ77-Faktorisierung für die Zeichenkette $x$

 Berechne SA, ISA, NSV und PSV für x
 k <- 1
 while k <= n; do
     psv <- SA[PSV[ISA[k]]]
     nsv <- SA[NSV[ISA[k]]]
     k <- LZ_Factor(k, psv, nsv)
 end while

Laufzeitanalyse

Die Berechnung der LZ77-Faktorisierung eines Strings ist mit dem Algorithmus in ${\mathcal {O}}(n)$ Zeit möglich, wobei $n=|x|$ die Länge der Eingabezeichenkette $x$ ist. Die Methode LZ_Factor benötigt ${\mathcal {O}}(1)$ Zeit, wenn die Berechnung von $lcp(i,j)$ über Range Minimum Queries realisiert wird. Die Berechnung der Arrays $NSV$ und $PSV$ ist in ${\mathcal {O}}(n)$ Zeit möglich, sodass der gesamte Algorithmus zur Berechnung ${\mathcal {O}}(n)$ Zeit benötigt (dies setzt eine Linearzeitkonstruktion des Suffixarrays voraus).

Vergleich verschiedener Implementierungen

Zur Berechnung der LZ77-Kompression einer Zeichenkette gibt es verschiedene Implementierungen, die sich in der Laufzeit und im Speicherbedarf unterscheiden. Für den Vergleich wird die LZ-Faktorisierung auf der kompletten Zeichenkette $x$ mit der Länge $|x|=n$ betrachtet. Die Analyse des Speicherbedarfs orientiert sich an der Speicherung in 32- oder 64-Bit-Worten. Dabei belege ein Buchstabe des Alphabets $\Sigma$ ein Viertel eines Speicherwortes und ein Integer ein ganzes Speicherwort.

In der folgenden Tabelle sind einige Implementierungen zur Berechnung der LZ77-Faktorisierung mit ihrer Laufzeit, ihrem Speicherbedarf und den verwendeten Datenstrukturen aufgelistet.

Algorithmus von	Worst-Case- Laufzeit	Speicherbedarf in Wörtern	Verwendete Datenstrukturen	Bemerkungen
Abouelhoda et al.	$\Theta (n)$	$4.25n+$	Suffixarray, LCP-Array	–
Chen et al.	$\Theta (n)$	$4.25n+$	Suffixarray, LCP-Array	–
Chen et al.	$\Theta (n)$	$3.25n+$	Suffixarray, LCP-Array	Positions-Array überschreibt Suffix-Array
Chen et al.	$\Theta (n)$	$3.25n$	Suffixarray, LCP-Array	Positions-Array überschreibt Suffix-Array
Crochemore und Ilie	$\Theta (n)$	$3.25n$	Suffixarray, LCP-Array, LPF-Array	LZ77-Ausgabe erfordert keinen zusätzlichen Platz
Crochemore und Ilie	$\Theta (n)$	$3n+$	Suffixarray, LCP-Array, LPF-Array	LZ77-Ausgabe erfordert keinen zusätzlichen Platz, kein Zugriff auf die Zeichenkette $x$ für die LZ77-Kompression notwendig

Einige der in der Tabelle aufgeführten Algorithmen verwenden das LPF-Array (LPF steht für Longest Previous Factor). Das LPF-Array ist wie folgt definiert: Für jede Position $i$ der Zeichenkette $x$ ist $LPF[i]$ definiert als Länge des längsten Faktors von $x$, der an der Position $i$ beginnt und vor der Position $i$ in $x$ auftaucht, d. h. $LPF[i]=max(\{0\}\cup \{l\,|\,x[i\dots i+l-1]{\text{ ist ein Faktor von }}x[1\dots i+l-2]\})$. Aus dem LPF-Array kann die LZ77-Faktorisierung einer Zeichenkette in linearer Zeit berechnet werden. Das LPF-Array kann unter anderem mit den oben aufgeführten NSV und PSV-Arrays berechnet werden, denn es gilt: $LPF[i]=max(lcp(i,SA[NSV[ISA[i]]]),lcp(i,SA[PSV[ISA[i]]]))$

Für die Implementierung einiger der in der Tabelle aufgeführten Algorithmen wird ein Stapelspeicher $S$ verwendet, welcher zusätzlichen Speicher benötigt. In der Tabelle ist die Verwendung eines Stacks durch ein an den Speicherbedarf angehängtes $+$ dargestellt. Die Größe des Stapelspeichers ist begrenzt durch $|S|=n$ - dies ist der Fall, wenn die Zeichenkette die Form $x=\alpha ^{n}$ mit $\alpha \in \Sigma$ aufweist. Erwartet ist $|S|\in O(\log _{|\Sigma |}n)$.

Verwendung

Heute wird die LZ77-Kompression u. a. noch auf dem Game Boy Advance, dem AutoCAD DWG Format und weiteren eingebetteten Systemen verwendet. Mit der Huffman-Kodierung kombiniert wird LZ77 in dem vielbenutzten Deflate-Algorithmus verwendet, welcher wiederum von sehr bekannten Komprimierungsprogrammen sowie dem Grafikformat PNG genutzt wird. Dass LZ77 mit keinerlei Patenten belegt ist, dürfte wohl der Grund sein, dass das Verfahren heute immer noch dem ein Jahr später veröffentlichten Nachfolger LZ78 vorgezogen wird, der bis ins Jahr 2004 mancherorts in Teilen patentiert war.

In der algorithmischen Verarbeitung von Zeichenketten wird die LZ77-Faktorisierung für die Berechnung von Regelmäßigkeiten in Strings eingesetzt. Dabei wird stets die Faktorisierung auf dem gesamten String betrachtet und nicht nur innerhalb des gleitenden Fensters. Zudem kann die Ausgabe vereinfacht werden, da der ursprüngliche String in den Anwendungen vorliegt und nicht rekonstruiert werden muss. Eine Auswahl von Problemstellungen, bei denen die LZ77-Faktorisierung verwendet werden kann, findet sich in der folgenden Auflistung:

• Bestimmung von Wiederholungen in Zeichenketten In einer Zeichenkette $x$ wird nach nicht-leeren Teilzeichenketten der Form $uu$ (im engl. als tandem repeat oder square bezeichnet) gesucht.
• Zeichenketten mit Wiederholungen mit Lücken (engl.:
  gaps
  ) fester Größe: In einer Zeichenkette $x$ werden alle nicht-leeren Teilzeichenketten der Form $uvu$ mit $|u|>0$ und $|v|=r$ für ein gegebenes $r$ gesucht.
• Maximale Periodizitäten in Zeichenketten: In einer Zeichenkette $x$ wird eine maximale Periodizität gesucht.
  • Eine Periodizität in einer Zeichenkette $x$ ist eine nicht-leerer Zeichenkette der Form $p^{m}q$, wobei $m\geq 2$ und $q$ ein Präfix von $p$ ist. Dabei ist $|p|$ die Periodenlänge.
  • Ein Vorkommen der Periodizität $x[i\dots j]$ mit einer Periodenlänge $k$ ist maximal, wenn
    1. $i=1$ ist oder $x[i-1\dots j]$ keine Periodizität mit Periodenlänge $k$ ist und
    2. $j=|x|$ ist oder $x[i\dots j+1]$ keine Periodizität mit Periodenlänge $k$ ist.

Geschichte

Die Kompressionsgüte ist direkt von der Größe des Lexikons abhängig. Um gute Kompressionsraten zu erhalten, muss das gleitende Fenster daher eine gewisse Mindestgröße erreichen. Da im Algorithmus der zu komprimierende Text mit jedem Eintrag im Lexikon verglichen werden muss (siehe Abschnitt Algorithmus), steigt die zum Komprimieren benötigte Zeit mit der Größe des Fensters linear an. Der LZ77-Algorithmus in Reinform fand daher zunächst wenig Beachtung. James Storer und Thomas Szymanski verbesserten 1982 einige Probleme in dem nun Lempel-Ziv-Storer-Szymanski (LZSS) genannten Algorithmus, der auch von Phil Katz für den weit verbreiteten Deflate-Algorithmus verwertet wurde. Der Vergleich des zu komprimierenden Textes mit allen Einträgen im Lexikon entfällt bei einer effizienten Implementierung wie im Abschnitt zur effizienten Konstruktion, wo immer nur der Vergleich mit maximal zwei Einträgen aus dem Lexikon notwendig ist.

In Reduced Offset Lempel Ziv (ROLZ, auch Lempel Ziv Ross Williams, von Ross Williams, 1991) und dem Lempel-Ziv-Markow-Algorithmus (LZMA, von Igor Pavlov, 1998) fand er bekanntere, moderne Nachfolger.

Verwandte Algorithmen

• Lempel-Ziv-Welch-Algorithmus, wörterbuchbasierte Kompression, häufig bei Grafikdaten verwendet
• LZX-Algorithmus, Weiterentwicklung des LZ77-Algorithmus

Literatur

• Mark Nelson, Jean-Loup Gailly: The Data Compression Book. 2. Auflage. M&T Books, New York 1996, ISBN 1-55851-434-1
• Anisa 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
• Annette Leßmöllmann: Im Fadenkreuz des Zippers – Komprimierungsprogramme können den Autor eines Textes enttarnen, obwohl sie kein einziges Wort verstehen. In: Die Zeit, Nr. 12/2002, S. 45

Weblinks

Wikibooks: Datenkompression - LZ77 - Lempel, Ziv 1977 – Lern- und Lehrmaterialien