Cryptography Reference
In-Depth Information
Wie aus dem Ergebnis der Kodierung ersichtlich ist, werden anstelle der 13
Eingabezeichen nur 8 Kodewörter ausgegeben.
Es folgen noch einige Erläuterungen zur Tabellendarstellung (die auch über-
sprungen werden können):
Da vereinbarungsgemäß alle Quellenzeichen bereits im Wörterbuch eingetragen
sind (somit auch als bekannte Muster anzusehen sind), sucht der Algorithmus
immer nach bekannten Zeichenketten, die mindestens zwei Zeichen enthalten.
Deshalb wird das erste eingelesene Zeichen
z
=
b
als Präfix
w
mit dem nächs-
ten Zeichen
z
=
a
(in der nächsten Tabellenzeile) konkateniert. Jetzt wird
festgestellt, dass zwar
b
, aber nicht die Zeichenkette
ba
ein bekanntes Muster
ist. Also wird
ba
=4
als unbekanntes Muster ins Wörterbuch eingetragen,
Zeichen
b
bzw. sein Kodewort
<
2
>
ausgegeben und
a
als Präfix
w
=
a
für
den folgenden Kodierungsschritt gespeichert.
Betrachten wir noch die Tabellenzeile nach der Ausgabe des Kodewortes
<
3
>
:
Präfix
w
=
b
wird mit dem aktuellen
z
=
a
konkateniert. Ein Durchsuchen
des Wörterbuches zeigt, dass die gebildete Zeichenkette
ba
bereits eingetragen
ist. Um aber festzustellen, ob sie das
längste
bekannte Muster ist, muss sie
als
w
=
ba
zwischengespeichert und mit
z
=
c
zur Zeichenkette
bac
verknüpft
werden. Da
bac
kein bekanntes Muster ist, wird
bac
=8
neu eingetragen und
ba
als Kodewort
<
4
>
ausgegeben.
Nach dem Ende des Eingabestrings erfolgt noch die Ausgabe des bekannten
Musters
w
=
cba
als Kodewort
<
9
>
.
Zusammenfassend kann folgender
Kodierungsalgorithmus
angegeben wer-
den:
1. Lies erstes Zeichen
z
und setze Präfix
w
:=
z
.
2. Lies nächstes Zeichen
z
und konkateniere
w ◦ z
.
3. Stelle fest, ob Zeichenkette
wz
bereits im Wörterbuch steht,
wenn
ja
: Setze
w
:=
wz
,
wenn
nein
: 1. Trage
wz
ins Wörterbuch ein.
2. Gib
w
aus.
3. Setze
w
:=
z
.
4. Stelle fest, ob aktuelles
z
das letzte Zeichen des Eingabestrings ist,
wenn
nein
:
G e h .,
wenn
ja
:
ib
w
aus und Stopp.
