Cryptography Reference
In-Depth Information
Nachdem wir uns mit dem grundsätzlichen Ablauf des LZW-Verfahrens ver-
traut gemacht haben, soll noch ein kurzer Blick auf die praktische Realisier-
barkeit folgen. Dabei erkennt man schnell, dass das Wörterbuch eine kritische
Stelle im System darstellt. Einerseits kann das ständige Durchmustern der ma-
ximal 4096 Eintragungen zum Problem werden, wenn nicht ein sehr effektiver
Suchalgorithmus zur Verfügung steht. Andererseits kann es problematisch wer-
den, wenn die Kapazität des Wörterbuchs nicht ausreichend ist.
3
Dann könnte
es zur drastischen Verschlechterung der Datenkompression führen. In der Pra-
xis sind diese Probleme heute weitgehend beherrschbar.
Betrachtungen zur
Koderedundanz
und
Datenkompression
Die bisherigen Berechnungen zur Quellenkodierung (s. Abschn. 3.3) auf der
Grundlage der Quellenstatistik konnten bereits
vor
der eigentlichen Kodierung
vorgenommen werden. Dafür reichte die Kenntnis der Auftrittswahrscheinlich-
keiten und ggf. der Übergangswahrscheinlichkeiten einer MARKOW-Kette ers-
ter Ordnung aus.
Bei der LZW-Kodierung werden entsprechend den statistischen Bindungen un-
terschiedlich viele Quellenzeichen auf ein Kodewort abgebildet. Die mittlere
Kodewortlänge
l
m
(auf ein Quellenzeichen bezogen) kann durch eine Mittel-
wertbildung der Ausgabefolge gewonnen werden, denn jedem 12stelligen Kode-
wort ist eine Zeichenkette zugeordnet.
Ein größeres Problem bei der Berechnung der Koderedundanz nach Gl. (3.4)
stellt die Bestimmung der mittleren Quellenentropie
H
m
dar. Da nicht einzelne
Textzeichen sondern Zeichenketten kodiert werden, ist
H
m
für eine MARKOW-
Kette höherer Ordnung (die mindestens der zu erwartenden mittleren Zeichen-
kettenlänge entsprechen sollte) zu berechnen. Dies geht über den hier gegebe-
nen Rahmen hinaus, und deshalb werden wir uns auch nicht weiter mit der
Redundanz von LZW-Kodes befassen.
Weitaus einfacher zu bestimmen und praktisch relevanter ist dagegen die
Kom-
pressionsrate
: Darunter wollen wir den Quotienten
R
C
aus Anzahl der Aus-
gabebits und Anzahl der Eingabebits verstehen:
4
Wir gehen davon aus, dass
n
e
8-
Bit
-Zeichen eingegeben und
n
a
12-
Bit
-Zeichen ausgegeben werden. Dann
ergibt sich
n
a
n
e
.
R
C
=1
,
5
(3.12)
3
Die Menge der einzutragenden Muster hängt wesentlich vom Charakter des Eingabetextes,
seiner Homogenität ab.
4
In der Literatur sind auch andere Bewertungsmaße für die Datenkompression zu finden.
