Aufgaben:Exercise 2.4Z: LZW Coding and Decoding again

• Return to book

Die obere Grafik zeigt eine Momentaufnahme des Wörterbuchs, das während der LZW–Codierung der Eingangssymbolfolge ABABABBAA entsteht. Das untere Wörterbuch entsteht bei der LZW–Codierung der Sequenz ABABABABA. In beiden Fällen wird vorausgesetzt, dass keine andere Zeichen als A und B vorkommen.

Gleiche Wörterbücher entstehen bei der LZW–Decodierung, 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 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 dafür ist, dass beim Decoder die Einträge um einen Schritt später erfolgen.

• 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 das Decodierergebnis beim vorherigen Schritt (i – 1) 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.

Hinweis: Die Aufgabe gehört zum Themengebiet von Kapitel 2.2. Beachten Sie 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.

Fragebogen

1

Codieren Sie die Eingangsfolge ABABABBAA. Welche Indizes ergeben sich zu den Schritten i = 1, ... , 5?

ABABABBAA$,i = 1:\ I$ =

$i = 2:\ I$ =

$i = 3:\ I$ =

$i = 4:\ I$ =

$i = 5:\ I$ =

2

Codieren Sie nun die Eingangsfolge ABABABABA. Geben Sie die Indizes zu den Schritten i = 4 und i = 5 an.

ABABABBAA $i = 4:\ I$ =

$i = 5:\ I$ =

3

Für welchen Schritt (i) gilt die Momentaufnahme des auf der Angabenseite dargestellten Wörterbuchs bezüglich

$Codierung:\ i$ =

$Decodierung:\ i$ =

4

Wann muss man auf die Decodier–Sonderfallregelung zurückgreifen?

	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    →   I = 0, W(I = 2) = AB,

• i = 2: B    →   I = 1, W(I = 3) = BA,

• i = 3: AB →   I = 2, W(I = 4) = ABA,

• i = 4: AB →   I = 2, W(I = 5) = ABB,

• i = 5: BA →   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 1 bis 3 ändert sich nichts gegenüber der Teilaufgabe (1). Danach gilt:

• i = 4: ABA →   I = 4, Wörterbuch (I = 5) = ABAB,

• i = 5: BA    →   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 i = 4 Codierschritten die gezeigten Einträge aufweist. Beim Decoder ergibt sich demgegenüber eine Zeitverzögerung um einen Schritt: i = 5.

4.  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}: I = 0\hspace{0.05cm}, \hspace{0.2cm}i = 2\hspace{-0.15cm}: I = 1\hspace{0.05cm}, \hspace{0.2cm}i = 3\hspace{-0.15cm}: I = 2\hspace{0.05cm}, \hspace{0.2cm}\underline{i = 4\hspace{-0.15cm}: I = 4}\hspace{0.05cm}, \hspace{0.2cm}i = 5\hspace{-0.15cm}: I = 3\hspace{0.05cm}. $$

Richtig ist dementsprechend der Lösungsvorschlag 2.

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 Decodereingangsfolge.