LZW-Komprimierung (Lempel/Ziv/Welch, 1984)

Ein wichtiger Bestandteil des GIF-Formates ist die LZW-Komprimierung für Zeichenketten.

Starte mit Stringtabelle, gefüllt mit characters, und fülle sie mit Verweisen auf bereits gelesene Substrings.

x := get_char();
w := x;
repeat
   x := get_char();
   if wx in Tabelle
      then w := wx
      else put_string(code(w));
           trage wx in Tabelle ein
           w := x
   endif
until x = EOF

w	Input	Output	String	Code
			a	1
			b	2
			c	3
	a
a	b	1	ab	4
b	a	2	ba	5
a	b
ab	c	4	abc	6
c	b	3	cb	7
b	a
ba	b	5	bab	8
b	a
ba	b
bab	a	8	baba	9
a	a	1	aa	10
a	a
aa	a	10	aaa	11
a	a
aa	a
aaa	a	11	aaaa	12

Entwicklung von Output und Tabelle für den Input ababcbababaaaaaaa

String
Präfix-	Erwei-
String-	terungs-
Index	character	Code
	a	1
	b	2
	c	3
1	b	4
2	a	5
4	c	6
3	b	7
5	b	8
8	a	9
1	a	10
10	a	11
11	a	12

Implementation der
Stringtabelle