LZW

Das LZW verfahren ist eine Weiterentwicklung des LZ78 Verfahren und wurde 1984 von Terry Welch patentiert. Das Verfahren beruht darauf, dass es bei der Ausgabe nur noch Indizes des Wörterbuchs ausgibt, und keine Zeichen mehr enthalten sind.

Zu Beginn werden alle möglichen Zeichen der länge 1 im Wörterbuch explizit untergebracht. Bei der Kompression wird eine möglichst lange Zeichenkette im Wörterbuch gesucht und als Index ausgegeben. Diese Zeichenkette wird mit dem nächsten nicht passenden Zeichen als neue Zeichenkette in das Wörterbuch übernommen.

LZW Beispiel

Die zu komprimierende Zeichenfolge:

Stelle	1	2	3	4	5	6	7	8	9
Zeichen	a	b	b	a	b	a	b	a	c

Im Wörterbuch bereits enthalten: 1:a, 2:b, 3:c

Zur Kodierung:

Stelle	Wörterbuch	Code
1	4:ab	(1)
2	5:bb	(2)
3	6:ba	(2)
4	7:aba	(4)
6	8:abac	(7)
9	-	(3)

Zur Dekompression:

Dekompression ( im Wörterbuch steht bereits 1:a, 2:b, 3:c)

Stelle	Eingabe	Wörterbuch	Ausgabe
1	(1)	1:a	a
2	(2)	4:ab	b
3	(2)	5:bb	b
4	(4)	6:ba	ab
5	(7)	7:aba	ab+a
6	(3)	8:abac	c

³
[Kow04]

Anwendungsgebiete: Unix Programm ''compress'', GIF (Graphic Image Format)

Die LZ-Verfahren sind bei der verlustfreien Kompression anzusiedeln.