Cryptography Reference
In-Depth Information
die betreffende Zeichenkette
w
jedoch die
längste
ist (also ein bereits einge-
tragenes Muster darstellt), kann erst entschieden werden, wenn das jeweils
nächste
Zeichen
z
gelesen und mit
w
konkateniert wird. Die Zeichenkette
w
wird deshalb als
Präfix
bei der folgenden Konkatenation mit
z
verwendet.
Bevor wir den Kodierungsalgorithmus in kompakter Form notieren, wollen wir
den weiteren Ablauf anhand eines einfachen Demonstrationsbeispiels erläutern.
Beispiel 3.4.5
Es sei ein Quellenalphabet mit den Zeichen
a, b, c
gegeben.
Der Eingabestring
baacbacbaacba
soll mit dem LZW-Algorithmus kodiert wer-
den, wobei das zu erstellende Wörterbuch bereits mit
a
=1
,
b
=2
und
c
=3
vorinstalliert ist.
Lösung:
Der Kodierungsvorgang wird in folgender Tabelle dargestellt (Erläuterungen
im Textteil).
Eingabe Konkatenation Wörterbuch- Ausgabe
Präfix
z
w ◦ z
eintrag
<i>
w
a
=1
b
=2
c
=3
b
b
a
b ◦ a
ba
=4
<
2
>
a
a
a ◦ a
aa
=5
<
1
>
a
c
a ◦ c
ac
=6
<
1
>
c
b
c ◦ b
cb
=7
<
3
>
b
a
b ◦ a
ba
c
ba ◦ c
bac
=8
<
4
>
c
b
c ◦ b
cb
a
cb ◦ a
cba
=9
<
7
>
a
a
a ◦ a
aa
c
aa ◦ c
aac
=10
<
5
>
c
b
c ◦ b
cb
a
cb ◦ a
cba
−
<
9
>
Ausgabefolge:
<
2
><
1
><
1
><
3
><
4
><
7
><
5
><
9
>
