View source for Aufgaben:Exercise 2.4Z: LZW Coding and Decoding again


{{quiz-Header|Buchseite=Informationstheorie/Komprimierung nach Lempel, Ziv und Welch
}}

[[File:P_ID2437__Inf_Z_2_4.png|right|]]
:Die obere Grafik zeigt eine Momentaufnahme des Wörterbuchs, das während der LZW&ndash;Codierung der Eingangssymbolfolge <b>ABABABBAA</b> entsteht. Das untere Wörterbuch entsteht bei der LZW&ndash;Codierung der Sequenz <b>ABABABABA</b>. In beiden Fällen wird vorausgesetzt, dass keine andere Zeichen als <b>A</b> und <b>B</b> vorkommen.

:Gleiche Wörterbücher entstehen bei der LZW&ndash;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&ndash;Codierung wird zu jedem Codierschritt <i>i</i> ein Index <i>I</i> ausgewählt und (binär) übertragen. Das Zeichenpaar <b>AB</b> wird bei den beiden Wörterbüchern durch den Index <i>I</i> = 2 dargestellt. Wir betrachten hier den Index <i>I</i> als Dezimalzahl und lassen bei dieser Aufgabe die Binärdarstellung außer Betracht.

:Bei der LZW&ndash;Decodierung wird in gleicher Weise mit Hilfe des Wörterbuchs aus jedem Index <i>I</i> ein Zeichen bzw. eine Zeichenfolge generiert, zum Beispiel führt <i>I</i> = 1 zum Zeichen <b>B</b> und <i>I</i> = 2 zum Zeichenpaar <b>AB</b>.

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

:* Wird bei der Codierung beim Schritt <i>i</i> ein neuer Index <i>I</i> eingetragen und ist dieses <i>I</i> gleichzeitig das Codierergebnis des Schrittes, so ist dieser Index beim Decodierschritt <i>i</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 <b>A</b> oder <b>B</b>) ist bei der LZW&ndash;Decodierung genau immer dann eine Sonderregelung anzuwenden, wenn im Codierschritt <i>i</i> der Eintrag mit dem Index <i>I</i> = <i>i</i> vorgenommen wurde.

:Diese Sonderregelung soll an einem Beispiel veranschaulicht werden:

:* Zum Schritt <i>i</i> gibt es keinen zum Index <i>I</i> passenden  Eintrag im Decoder&ndash;Wörterbuch.

:* Wir nehmen an, dass das Decodierergebnis beim vorherigen Schritt (<i>i</i> &ndash; 1) <b>ABBABA</b> war.

:* Dann ergänzt man diese Zeichenfolge um das erste Zeichen der Folge. Hier: <b>ABBABAA</b>.

:* Anschließend trägt man die Sequenz <b>ABBABAA</b> in das Wörterbuch unter dem Index <i>I</i> ein.

:<b>Hinweis:</b> Die Aufgabe gehört zum Themengebiet von Kapitel 2.2. Beachten Sie bei der Lösung dieser Aufgabe, dass beim LZW&ndash;Algorithmus nicht von einem leeren Wörterbuch ausgegangen wird. Vielmehr beinhalten die Indizes <i>I</i> = 0 bis <i>I</i> = <i>M</i>&ndash;1 alle <i>M</i> zulässigen Zeichen.

===Fragebogen===

<quiz display=simple>
{Codieren Sie die Eingangsfolge <b>ABABABBAA</b>. Welche Indizes ergeben sich zu den Schritten <i>i</i> = 1, ... , 5?
|type="{}"}
<b>ABABABBAA</b>$,i = 1:\ I$ = { 0 3% }
$i = 2:\ I$ = { 1 3% }
$i = 3:\ I$ = { 2 3% }
$i = 4:\ I$ = { 2 3% }
$i = 5:\ I$ = { 3 3% }


{Codieren Sie nun die Eingangsfolge <b>ABABABABA</b>. Geben Sie die Indizes zu den Schritten <i>i</i> = 4 und <i>i</i> = 5 an.
|type="{}"}
<b>ABABABBAA</b> $i = 4:\ I$ = { 4 3% }
$i = 5:\ I$ = { 3 3% }


{Für welchen Schritt (<i>i</i>) gilt die Momentaufnahme des auf der Angabenseite dargestellten Wörterbuchs bezüglich
|type="{}"}
$Codierung:\ i$ = { 4 3% }
$Decodierung:\ i$ = { 5 3% }


{Wann muss man auf die Decodier&ndash;Sonderfallregelung zurückgreifen?
|type="[]"}
- Bei der Decodierung von <b>ABABABBAA</b> im Schritt <i>i</i> = 4.
+ Bei der Decodierung von <b>ABABABABA</b> im Schritt <i>i</i> = 4.
- Bei der Decodierung von <b>ABABABABA</b> im Schritt <i>i</i> = 5.



</quiz>

===Musterlösung===
{{ML-Kopf}}
:<b>1.</b>&nbsp;&nbsp;Wir bezeichnen mit <i>W</i>(<i>I</i>) ein Feld (Array), welches das Wörterbuch beschreibt und dessen Elemente Character oder Zeichenfolgen beinhalten.  Die Codierung von <b>ABABABBAA</b> läuft wie folgt ab:

:* <i>i</i> = 1: <b>A</b> &nbsp;&nbsp;&nbsp;&#8594;&nbsp;&nbsp; <u><i>I</i> = 0</u>, <i>W</i>(<i>I</i> = 2) = <b>AB</b>,

:* <i>i</i> = 2: <b>B</b> &nbsp;&nbsp;&nbsp;&#8594;&nbsp;&nbsp; <u><i>I</i> = 1</u>, <i>W</i>(<i>I</i> = 3) = <b>BA</b>,

:* <i>i</i> = 3: <b>AB</b> &#8594;&nbsp;&nbsp; <u><i>I</i> = 2</u>, <i>W</i>(<i>I</i> = 4) = <b>ABA</b>,

:* <i>i</i> = 4: <b>AB</b> &#8594;&nbsp;&nbsp; <u><i>I</i> = 2</u>, <i>W</i>(<i>I</i> = 5) = <b>ABB</b>,

:* <i>i</i> = 5: <b>BA</b> &#8594;&nbsp;&nbsp; <u><i>I</i> = 3</u>, <i>W</i>(<i>I</i> = 6) = <b>BAA</b>.

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

:<b>2.</b>&nbsp;&nbsp;Für die Schritte 1 bis 3 ändert sich nichts gegenüber der Teilaufgabe (1). Danach gilt:

:* <i>i</i> = 4: <b>ABA</b> &#8594;&nbsp;&nbsp; <u><i>I</i> = 4</u>, Wörterbuch (<i>I</i> = 5) = <b>ABAB</b>,

:* <i>i</i> = 5: <b>BA</b> &nbsp;&nbsp;&nbsp;&#8594;&nbsp;&nbsp; <u><i>I</i> = 3</u>, Codierung abgeschlossen, kein neuer Wörterbucheintrag möglich.

:<b>3.</b>&nbsp;&nbsp;Der Vergleich mit den obigen Ergebnissen zeigt, dass das Wörterbuch des Coders genau nach <u><i>i</i> = 4</u> Codierschritten die gezeigten Einträge aufweist. Beim Decoder ergibt sich demgegenüber eine Zeitverzögerung um einen Schritt: <u><i>i</i> = 5</u>.

:<b>4.</b>&nbsp;&nbsp;Die Sonderfallregelung der Decodierung ist (im vorliegenden Beispiel) dann notwendig, wenn im Codierschritt <i>i</i> der Index <i>I</i> = <i>i</i> ausgegeben wird. Bei der Decodierung findet er dann die erforderliche Zuordnung Index &#8594; Zeichenfolge nicht, da das generierte Wörterbuch zum Zeitpunkt <i>i</i> nur Einträge mit Indizes <i>I</i> < <i>i</i> enthält.

:Für die Folge <b>ABABABBAA</b> gilt entsprechend Teilaufgabe 1) stets <i>I</i> < <i>i</i>. Dagegen ergäbe sich bei der Folge <b>ABABABABA</b> 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 <u>Lösungsvorschlag 2</u>.

:Hier noch zusammenfassend die gesamte Decodierung von <b>ABABABABA</b>. Die Vorbelegung des Wörterbuchs beinhaltet <i>I</i> = 0: <b>A</b> und <i>I</i> = 1: <b>B</b>. Dann gilt mit dem Wörterbuch&ndash;Array <i>W</i>(<i>I</i>):

:* <i>i</i> = 1: Decodierung <i>I</i> = 0 &#8594; <b>A</b>,

:* <i>i</i> = 2: Decodierung <i>I</i> = 1 &#8594; <b>B</b>, &nbsp;&nbsp;&nbsp;<i>W</i>(<i>I</i> = 2) = <b>AB</b>,

:* <i>i</i> = 3: Decodierung <i>I</i> = 2 &#8594; <b>AB</b>, <i>W</i>(<i>I</i> = 3) = <b>BA</b>,

:* <i>i</i> = 4: Ein Eintrag mit dem Index <i>I</i> = 4 ist nicht vorhanden &#8658; Sonderfallregelung. Man nimmt das letzte Decodierergebnis (hier <b>AB</b>) und fügt das erste Zeichen dieser Sequenz hinten an &#8658; <b>ABA</b>. Danach wird <b>ABA</b> im Wörterbuch unter dem Index <i>I</i> = 4 abgelegt.

:* <i>i</i> = 5: Decodierung <i>I</i> = 3 &#8594; <b>BA</b>. Ende der Decodereingangsfolge.
{{ML-Fuß}}



[[Category:Aufgaben zu Informationstheorie|^2.2 Komprimierung nach Lempel, Ziv und Welch^]]