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
LZW-Dekomprimierung (1. Näherung)
code := get_bits();
v := String(code);
put_char(v);
code := get_bits();
while code # EOF-code do
w := String(code);
put_string(w);
fuege v * w[0] in Tabelle ein;
v := w;
code := get_bits()
end;
Obacht: Der Spezialfall eines Eingabestrings der Form
xwxwx muß abgefangen und gesondert behandelt werden,
da der Komprimierer unmittelbar nach Eintragen des Codes
für xwx den Code auch sendet.
Der Dekomprimierer hat ihn jedoch noch nicht eingetragen,
kann es aber nachholen.
v
Input-
w
Tabellen-
Tabellen-
Code
String
Code
a
1
b
2
c
3
1
a
2
b
ab
4
b
4
ab
ba
5
ab
3
c
abc
6
c
5
ba
cb
7
ba
8
?
Kompressionsraten für den Spiegelartikel Multimedia
spiegel.txt
16617
100 %
Huffmann
pack
spiegel.txt.z
9944
60 %
LZW
compress
spiegel.txt.Z
9120
55 %
Lempel-Ziv
gzip
spiegel.txt.gz
7765
47 %