Ein wichtiger Bestandteil des GIF-Formates (siehe nächste Sektion) 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
Entwicklung von Output und Tabelle
für den Input ababcbababaaaaaaa
Implementation der
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
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
Stringtabelle