Rechnernetze

Datenkompression durch LZW

Das Verfahren LZW wurde 1984 von Terry Welch entwickelt und ist patentiert. Es basiert auf dem LZ78-Verfahren. Der Vorteil dieses Verfahrens ist, dass es schneller Daten komprimiert und darüber hinaus in der Ausgabe nur noch Indizes des Wörterbuchs, also keine Zeichen mehr auftreten.

Vor dem Start werden alle möglichen Zeichen (d.h. Zeichenketten der Länge 1) im Wörterbuch implizit untergebracht. Bei der Kompression wird zum nächsten Eingabetext eine möglichst lange Zeichenkette im Wörterbuch gesucht und als Index ausgegeben. Die Zeichenkette zusammen mit dem ersten nicht passenden Zeichen wird als neue Zeichenkette in das Wörterbuch übernommen.

Beispiel

Position

1

2

3

4

5

6

7

8

9

Zeichen

A

B

B

A

B

A

B

A

C

Kompression (im Wörterbuch steht bereits 1: A, 2: B, 3: C)

Nr.

Pos.

Wörterbuch

Ausgabe

1.

1

4: A B

(1)

2.

2

5: B B

(2)

3.

3

6: B A

(2)

4.

4

7: A B A

(4)

5.

6

8: A B A C

(7)

6.

9

-

(3)

Die Dekompression führt die analogen Schritte durch, wobei der Aufbau des Wörterbuchs immer einen Schritt später erfolgt, da für das aktuelle Wort das erste Zeichen des nächsten ausgegebenen Worts benötigt wird.

Dekompression (im Wörterbuch steht bereits 1: A, 2: B, 3: C)

Nr.

Eingabe

Wörterbuch

Ausgabe

1.

(1)

1: A

A

2.

(2)

4: A B

B

3.

(2)

5: B B

B

4.

(4)

6: B A

A B

5.

(7)

7: A B A

A B + A

6.

(3)

8: A B A C

C

Dieses führt zu Problemen, wenn das bei der Kompression zuletzt in das Wörterbuch übernommene Wort als nächstes kodiert wird.

Es liege die Zeichenfolge (A x)(A x A) vor, wobei A ein beliebiges Zeichen und x eine beliebige Zeichenfolge ist (im Beispiel ist x=B und die Zeichenfolge beginnt an Position 4).
Bei der Kompression wird Ax im Wörterbuch gefunden und nach der Regel AxA in das Wörterbuch abgelegt (weil (A x A x A) im Text vorkommt), bei der Dekompression wurde AxA aber noch nicht ins Wörterbuch übernommen.
Allerdings bedeutet dieses, dass die neue Folge gleich der vorherigen Folge plus dem ersten Zeichen der vorherigen Folge (A x + A) ist, da der nächste Eintrag ins Wörterbuch stets gleich dem vorhergehenden Eintrag plus dem ersten Zeichen des neuen Worts ist. Daher kann im Falle eines nicht vorhandenen Eintrags im Wörterbuch (7:) die Dekompression den Wert des Wörterbucheintrags leicht rekonstruieren und sowohl das neue Wort in das Wörterbuch übernehmen als auch in die Ausgabe schreiben.

Dieses Verfahren ist ähnlich effektiv wie LZ78, Varianten hierzu ändern die Größe der Indizes in der Ausgabe, indem sie diese von der Größe des Wörterbuchs abhängig machen (die monoton wächst), oder löschen alte Einträge aus dem Wörterbuch, wenn dieses zu groß wird. Dieses Verfahren wird u.a. im UNIX-Programm compress sowie im GIF-Kompressions-Format verwendet.