Exercise 2.4Z: LZW Coding and Decoding again

Momentaufnahmen der LZW–Wörterbüchern

Die Grafik zeigt Momentaufnahmen des Wörterbuchs, das während der LZW–Codierung der Eingangssymbolfolge entsteht.

Die obere Grafik gilt für Eingangssymbolfolge ABABABBAA.
Das untere Wörterbuch entsteht bei der LZW–Codierung der Sequenz ABABABABA.

In beiden Fällen wird vorausgesetzt, dass auch zu späteren Zeitpunkten keine anderen Zeichen als A und B vorkommen können.

Bei der LZW–Decodierung entstehen gleiche Wörterbücher, doch erfolgen dann die Wörterbucheinträge erst einen Schritt später. In der Teilaufgabe (3) wird gefragt, für welchen Codierschritt bzw. für welchen Decodierschritt die beiden dargestellten Momentaufnahmen gültig sind.

Bei der LZW–Codierung wird zu jedem Codierschritt $i$ ein Index $I$ ausgewählt und (binär) übertragen. Das Zeichenpaar AB wird bei den beiden Wörterbüchern durch den Index $I = 2$ dargestellt. Wir betrachten hier den Index $I$ als Dezimalzahl und lassen bei dieser Aufgabe die Binärdarstellung außer Betracht.

Bei der LZW–Decodierung wird in gleicher Weise mit Hilfe des Wörterbuchs aus jedem Index $I$ ein Zeichen bzw. eine Zeichenfolge generiert, zum Beispiel führt $I = 1$ zum Zeichen B und $I = 2$ zum Zeichenpaar AB.

Wird tatsächlich ein Wörterbucheintrag mit dem gewünschten Index $I$ gefunden, so läuft die Decodierung problemlos ab. Dies ist aber nicht immer so:

Wird bei der Codierung beim Schritt $i$ ein neuer Index $I$ eingetragen und ist dieses $I$ gleichzeitig das Codierergebnis des Schrittes, so ist dieser Index beim Decodierschritt $i$ im Wörterbuch noch nicht belegt. Der Grund hierfür ist, dass beim Decoder die Einträge um einen Schritt später erfolgen als beim Coder.
Bei binärer Eingangsfolge $($alle Zeichen seien A oder B$)$ ist bei der LZW–Decodierung genau immer dann eine Sonderregelung anzuwenden, wenn im Codierschritt $i$ der Eintrag mit dem Index $I = i$ vorgenommen wurde.

Diese Sonderregelung soll an einem Beispiel veranschaulicht werden:

Zum Schritt $i$ gibt es keinen zum Index $I$ passenden Eintrag im Decoder–Wörterbuch.
Wir nehmen an, dass beim vorherigen Schritt $(i- 1)$ das Decodierergebnis ABBABA war.
Dann ergänzt man diese Zeichenfolge um das erste Zeichen der Folge. Hier: ABBABAA.
Anschließend trägt man die Sequenz ABBABAA in das Wörterbuch unter dem Index $I$ ein.

Hinweise:

Die Aufgabe gehört zum Kapitel Komprimierung nach Lempel, Ziv und Welch.
Insbesondere wird Bezug genommen auf die Seiten

LZ77 – die Grundform der Lempel-Ziv-Algorithmen,

Lempel-Ziv-Codierung mit variabler Indexbitlänge,

Decodierung des LZW-Agorithmus.

Beachten Sie zudem bei der Lösung dieser Aufgabe, dass beim LZW–Algorithmus nicht von einem leeren Wörterbuch ausgegangen wird.
Vielmehr beinhalten die Indizes $I = 0$ bis $I = M- 1$ alle $M$ zulässigen Zeichen des Alphabets.

Fragebogen

$I_1 \ = \ $

$I_2 \ = \ $

$I_3 \ = \ $

$I_4 \ = \ $

$I_5 \ = \ $

$I_4 \ = \ $

$I_5 \ = \ $

$\text{Codierung:} \ \ i \ = \ $

$\text{Decodierung:} \ \ i \ = \ $

	Bei der Decodierung von ABABABBAA im Schritt $i = 4$.
	Bei der Decodierung von ABABABABA im Schritt $i = 4$.
	Bei der Decodierung von ABABABABA im Schritt $i = 5$.

Musterlösung

Solution

(1) Wir bezeichnen mit $W(I)$ ein Feld (Array), welches das Wörterbuch beschreibt und dessen Elemente Character oder Zeichenfolgen beinhalten. Die Codierung von ABABABBAA läuft wie folgt ab:

$i = 1$: A → $\underline{I=0}$, $W(I = 2) =$ AB,
$i = 2$: B → $\underline{I=1}$, $W(I = 3) =$ BA,
$i = 3$: AB → $\underline{I=2}$, $W(I = 4) =$ ABA,
$i = 4$: AB → $\underline{I=2}$, $W(I = 5) =$ ABB,
$i = 5$: BA → $\underline{I=3}$, $W(I = 6) =$ BAA.

Es ist anzumerken, dass das letzte Zeichen (A) des Eingabestrings ABABABBAA zum Zeitpunkt $i = 5$ zwar bereits beim Wörterbucheintrag berücksichtigt ist, aber noch nicht codiert wurde.

(2) Für die Schritte $i = 1$ bis $i = 3$ ändert sich nichts gegenüber der Teilaufgabe (1). Danach gilt:

$i = 4$: ABA → $\underline{I=4}$, $W(I = 5) =$ ABAB,
$i = 5$: BA → $\underline{I=3}$, Codierung abgeschlossen, kein neuer Wörterbucheintrag möglich.

(3) Der Vergleich mit den obigen Ergebnissen zeigt, dass das Wörterbuch des Coders genau nach $\underline{i=4}$ Codierschritten die gezeigten Einträge aufweist.

Beim Decoder ergibt sich demgegenüber eine Zeitverzögerung um einen Schritt: $\underline{i=5}$.

(4) Richtig ist der Lösungsvorschlag 2:

Die Sonderfallregelung der Decodierung ist (im vorliegenden Beispiel) dann notwendig, wenn im Codierschritt $i$ der Index $I =i$ ausgegeben wird.
Bei der Decodierung findet er dann die erforderliche Zuordnung Index → Zeichenfolge nicht, da das generierte Wörterbuch zum Zeitpunkt $i$ nur Einträge mit Indizes $I < i$ enthält.
Für die Folge ABABABBAA gilt entsprechend Teilaufgabe (1) stets $I < i$.
Dagegen ergäbe sich bei der Folge ABABABABA folgende Indizes:

$$i = 1\hspace{-0.15cm}: \hspace{0.15cm} I = 0\hspace{0.05cm}, \hspace{0.5cm}i = 2\hspace{-0.15cm}: \hspace{0.15cm}I = 1\hspace{0.05cm}, \hspace{0.5cm}i = 3\hspace{-0.15cm}: \hspace{0.15cm}I = 2\hspace{0.05cm}, \hspace{0.5cm}\underline{i = 4\hspace{-0.15cm}: \hspace{0.15cm}I = 4}\hspace{0.05cm}, \hspace{0.5cm}i = 5\hspace{-0.15cm}: \hspace{0.15cm}I = 3\hspace{0.05cm}. $$

Hier noch zusammenfassend die gesamte Decodierung von ABABABABA:

Die Vorbelegung des Wörterbuchs beinhaltet $I=0$: A und $I=1$: B.

Dann gilt mit dem Wörterbuch–Array $W(I)$:

$i = 1$: Decodierung $I=0$ → A,
$i = 2$: Decodierung $I=1$ → B, $W(I = 2) =$ AB,
$i = 3$: Decodierung $I=2$ → AB, $W(I = 3) =$ BA,
$i = 4$: Ein Eintrag mit dem Index $I = 4$ ist nicht vorhanden ⇒ Sonderfallregelung:
Man nimmt das letzte Decodierergebnis (hier AB) und fügt das erste Zeichen dieser Sequenz hinten an ⇒ ABA.
Danach wird ABA im Wörterbuch unter dem Index $I = 4$ abgelegt.
$i = 5$: Decodierung $I=3$ → BA. Ende der Decoder–Eingangsfolge.