Aufgaben:Aufgabe 2.4Z: Nochmals LZW-Codierung und -Decodierung: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
(17 dazwischenliegende Versionen von 3 Benutzern werden nicht angezeigt)
Zeile 1: Zeile 1:
  
{{quiz-Header|Buchseite=Informationstheorie und Quellencodierung/Komprimierung nach Lempel, Ziv und Welch
+
{{quiz-Header|Buchseite=Informationstheorie/Komprimierung nach Lempel, Ziv und Welch
 
}}
 
}}
  
[[Datei:P_ID2437__Inf_Z_2_4.png|right|]]
+
[[Datei:P_ID2437__Inf_Z_2_4.png|right|frame|Momentaufnahmen der LZW–Wörterbüchern]]
: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.
+
Die Grafik zeigt Momentaufnahmen des Wörterbuchs, das während der&nbsp; <u>LZW&ndash;Codierung</u>&nbsp; der Eingangssymbolfolge entsteht.
 +
*Die obere Grafik gilt für Eingangssymbolfolge&nbsp; <b>ABABABBAA</b>.  
 +
*Das untere Wörterbuch entsteht bei der LZW&ndash;Codierung der Sequenz&nbsp; <b>ABABABABA</b>.  
  
: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.
+
In beiden Fällen wird vorausgesetzt, dass auch zu späteren Zeitpunkten keine anderen Zeichen als&nbsp; <b>A</b>&nbsp; und&nbsp; <b>B</b>&nbsp; vorkommen können.
  
: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>.
+
Bei der&nbsp; <u>LZW&ndash;Decodierung</u>&nbsp; entstehen gleiche Wörterbücher, doch erfolgen dann die Wörterbucheinträge erst einen Schritt später.&nbsp; In der Teilaufgabe&nbsp; '''(3)'''&nbsp; wird gefragt, für welchen Codierschritt bzw. für welchen Decodierschritt die beiden dargestellten Momentaufnahmen gültig sind.
  
: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 der <u>LZW&ndash;Codierung</u> wird zu jedem Codierschritt $i$ ein Index $I$ ausgewählt und (binär) übertragen.&nbsp; Das Zeichenpaar <b>AB</b> wird bei den beiden Wörterbüchern durch den Index $I = 2$ dargestellt.&nbsp; Wir betrachten hier den Index $I$ als Dezimalzahl und lassen bei dieser Aufgabe die Binärdarstellung außer Betracht.
  
:* 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:
+
Bei der <u>LZW&ndash;Decodierung</u> wird in gleicher Weise mit Hilfe des Wörterbuchs aus jedem Index&nbsp; $I$&nbsp; ein Zeichen bzw. eine Zeichenfolge generiert, zum Beispiel führt&nbsp; $I = 1$&nbsp; zum Zeichen&nbsp; <b>B</b>&nbsp; und&nbsp; $I = 2$&nbsp; zum Zeichenpaar&nbsp; <b>AB</b>.
  
:* Zum Schritt <i>i</i> gibt es keinen zum Index <i>I</i> passenden  Eintrag im Decoder&ndash;Wörterbuch.
+
Wird  tatsächlich ein Wörterbucheintrag mit dem gewünschten Index&nbsp; $I$&nbsp; gefunden, so läuft die Decodierung problemlos ab. Dies ist aber nicht immer so:
 +
* Wird bei der Codierung beim Schritt&nbsp; $i$&nbsp; ein neuer Index&nbsp; $I$&nbsp; eingetragen und ist dieses&nbsp; $I$&nbsp; gleichzeitig das Codierergebnis des Schrittes, so ist dieser Index beim Decodierschritt&nbsp; $i$&nbsp; im Wörterbuch noch nicht belegt.&nbsp; Der Grund hierfür ist, dass  beim Decoder die Einträge um einen Schritt später erfolgen als beim Coder.
 +
* Bei binärer Eingangsfolge&nbsp; $($alle Zeichen seien&nbsp; <b>A</b>&nbsp; oder&nbsp; <b>B</b>$)$&nbsp; ist bei der LZW&ndash;Decodierung genau immer dann eine Sonderregelung anzuwenden, wenn im Codierschritt&nbsp; $i$&nbsp; der Eintrag mit dem Index&nbsp; $I = i$&nbsp; vorgenommen wurde.
  
:* 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>.
+
Diese Sonderregelung soll an einem Beispiel veranschaulicht werden:
 +
* Zum Schritt&nbsp; $i$&nbsp; gibt es keinen zum Index&nbsp; $I$&nbsp; passenden  Eintrag im Decoder&ndash;Wörterbuch.
 +
* Wir nehmen an, dass beim vorherigen Schritt&nbsp; $(i- 1)$&nbsp; das Decodierergebnis&nbsp; <b>ABBABA</b>&nbsp; war.
 +
* Dann ergänzt man diese Zeichenfolge um das erste Zeichen der Folge.&nbsp; Hier:&nbsp; <b>ABBABAA</b>.
 +
* Anschließend trägt man die Sequenz&nbsp; <b>ABBABAA</b>&nbsp; in das Wörterbuch unter dem Index&nbsp; $I$&nbsp; ein.
  
:* 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.
+
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
''Hinweise:''
 +
*Die Aufgabe gehört zum Kapitel&nbsp; [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch|Komprimierung nach Lempel, Ziv und Welch]].
 +
*Insbesondere wird  Bezug genommen auf die Seiten
 +
:: [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch#LZ77_.E2.80.93_die_Grundform_der_Lempel.E2.80.93Ziv.E2.80.93Algorithmen|LZ77 &ndash; die Grundform der Lempel-Ziv-Algorithmen]],
 +
:: [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch#Lempel.E2.80.93Ziv.E2.80.93Codierung_mit_variabler_Indexbitl.C3.A4nge|Lempel-Ziv-Codierung mit variabler Indexbitlänge]],
 +
:: [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch#Decodierung_des_LZW.E2.80.93Algorithmus|Decodierung des LZW-Agorithmus]].
 +
*Beachten Sie zudem bei der Lösung dieser Aufgabe, dass beim LZW&ndash;Algorithmus nicht von einem leeren Wörterbuch ausgegangen wird.  
 +
*Vielmehr beinhalten die Indizes&nbsp; $I = 0$&nbsp; bis&nbsp; $I = M- 1$&nbsp; alle&nbsp; $M$&nbsp; zulässigen Zeichen des Alphabets.
 +
 
  
 
===Fragebogen===
 
===Fragebogen===
  
 
<quiz display=simple>
 
<quiz display=simple>
{Codieren Sie die Eingangsfolge <b>ABABABBAA</b>. Welche Indizes ergeben sich zu den Schritten <i>i</i> = 1, ... , 5?
+
{Codieren Sie die Eingangsfolge&nbsp; <b>ABABABBAA</b>&nbsp; entsprechend der <u>oberen Grafik</u>.&nbsp; Welche Indizes&nbsp; $I_i$&nbsp; ergeben sich zu den Schritten&nbsp; $i=1$, ... , $i=5$?
 
|type="{}"}
 
|type="{}"}
<b>ABABABBAA</b>$,i = 1:\ I$ = { 0 3% }
+
$I_1 \ = \ $ { 0. }
$i = 2:\ I$ = { 1 3% }
+
$I_2 \ = \ $ { 1 }
$i = 3:\ I$ = { 2 3% }
+
$I_3 \ = \ $ { 2 }
$i = 4:\ I$ = { 2 3% }
+
$I_4 \ = \ $ { 2 }
$i = 5:\ I$ = { 3 3% }
+
$I_5 \ = \ $ { 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.
+
 
 +
{Codieren Sie nun die Eingangsfolge&nbsp; <b>ABABABABA</b>&nbsp; entsprechend der <u>unteren Grafik</u>.&nbsp; Geben Sie die Indizes&nbsp; $I_i$&nbsp; zu den Schritten&nbsp; $i=4$&nbsp; und&nbsp; $i=5$&nbsp; an.
 
|type="{}"}
 
|type="{}"}
<b>ABABABBAA</b> $i = 4:\ I$ = { 4 3% }
+
$I_4 \ = \ $ { 4 }
$i = 5:\ I$ = { 3 3% }
+
$I_5 \ = \ $ { 3 }
  
  
{Für welchen Schritt (<i>i</i>) gilt die Momentaufnahme des auf der Angabenseite dargestellten Wörterbuchs bezüglich
+
{Für welchen Schritt&nbsp; $i$&nbsp; gilt die Momentaufnahme des auf der Angabenseite dargestellten Wörterbuchs bezüglich
 
|type="{}"}
 
|type="{}"}
$Codierung:\ i$ = { 4 3% }
+
$\text{Codierung:} \ \ i \ = \ $ { 4 }
$Decodierung:\ i$ = { 5 3% }
+
$\text{Decodierung:} \ \ i \ = \ $ { 5 }
  
  
 
{Wann muss man auf die Decodier&ndash;Sonderfallregelung zurückgreifen?
 
{Wann muss man auf die Decodier&ndash;Sonderfallregelung zurückgreifen?
 
|type="[]"}
 
|type="[]"}
- Bei der Decodierung von <b>ABABABBAA</b> im Schritt <i>i</i> = 4.
+
- Bei der Decodierung von&nbsp; <b>ABABABBAA</b>&nbsp; im Schritt&nbsp; $i = 4$.
+ Bei der Decodierung von <b>ABABABABA</b> im Schritt <i>i</i> = 4.
+
+ Bei der Decodierung von&nbsp; <b>ABABABABA</b>&nbsp; im Schritt&nbsp; $i = 4$.
- Bei der Decodierung von <b>ABABABABA</b> im Schritt <i>i</i> = 5.
+
- Bei der Decodierung von&nbsp; <b>ABABABABA</b>&nbsp; im Schritt&nbsp; $i = 5$.
  
  
Zeile 66: Zeile 84:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{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:
+
'''(1)'''&nbsp; Wir bezeichnen mit&nbsp; $W(I)$&nbsp; ein Feld (Array), welches das Wörterbuch beschreibt und dessen Elemente Character oder Zeichenfolgen beinhalten.&nbsp;
 
 
:* <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>,
+
*Die Codierung von&nbsp; <b>ABABABBAA</b>&nbsp; läuft dann wie folgt ab:
 +
:: $i = 1$: &nbsp; &nbsp; <b>A</b> &nbsp;&nbsp;&nbsp;&#8594;&nbsp;&nbsp; $\underline{I=0}$, &nbsp; $W(I = 2) =$ <b>AB</b>,
 +
:: $i = 2$: &nbsp; &nbsp; <b>B</b> &nbsp;&nbsp;&nbsp;&#8594;&nbsp;&nbsp; $\underline{I=1}$, &nbsp; $W(I = 3) =$ <b>BA</b>,
 +
:: $i = 3$: &nbsp; &nbsp; <b>AB</b> &#8594;&nbsp;&nbsp; $\underline{I=2}$, &nbsp; $W(I = 4) =$ <b>ABA</b>,
 +
:: $i = 4$: &nbsp; &nbsp; <b>AB</b> &#8594;&nbsp;&nbsp; $\underline{I=2}$, &nbsp; $W(I = 5) =$ <b>ABB</b>,
 +
:: $i = 5$: &nbsp; &nbsp; <b>BA</b> &#8594;&nbsp;&nbsp; $\underline{I=3}$, &nbsp; $W(I = 6) =$ <b>BAA</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&nbsp; $($<b>A</b>$)$&nbsp; des Eingabestrings&nbsp; <b>ABABABBAA</b>&nbsp; zum Zeitpunkt&nbsp; $i = 5$&nbsp; zwar bereits beim Wörterbucheintrag berücksichtigt ist, aber noch nicht codiert wurde.
  
: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>,
+
'''(2)'''&nbsp; Für die Schritte&nbsp; $i = 1$&nbsp; bis&nbsp; $i = 3$&nbsp; ändert sich nichts gegenüber der Teilaufgabe&nbsp; '''(1)'''.
 +
*Danach gilt:
 +
:: $i = 4$: &nbsp; &nbsp; <b>ABA</b> &#8594;&nbsp;&nbsp; $\underline{I=4}$, &nbsp; $W(I = 5) =$ <b>ABAB</b>,
 +
:: $i = 5$: &nbsp; &nbsp; <b>BA</b> &#8594;&nbsp;&nbsp; $\underline{I=3}$, &nbsp; Codierung abgeschlossen, kein neuer Wörterbucheintrag möglich.
  
:* <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.
+
'''(3)'''&nbsp; Der Vergleich mit obigen Ergebnissen zeigt:  
 +
*Das Wörterbuch des&nbsp; <u>Coders</u>&nbsp; weist genau nach&nbsp; $\underline{i=4}$&nbsp; Codierschritten die gezeigten Einträge auf.  
 +
*Beim&nbsp; <u>Decoder</u>&nbsp; ergibt sich demgegenüber eine Zeitverzögerung um einen Schritt: &nbsp; $\underline{i=5}$.
  
: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>,
+
'''(4)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 2</u>:
 +
*Die Sonderfallregelung der Decodierung ist&nbsp; (im vorliegenden Beispiel)&nbsp; dann notwendig, wenn im Codierschritt&nbsp; $i$&nbsp; der Index&nbsp; $I =i$&nbsp; ausgegeben wird.
 +
*Bei der Decodierung findet er dann die erforderliche Zuordnung&nbsp; &bdquo;Index&nbsp; &#8594;&nbsp; Zeichenfolge&rdquo;&nbsp; nicht, da das generierte Wörterbuch zum Zeitpunkt&nbsp; $i$&nbsp; nur Einträge mit Indizes&nbsp; $I < i$&nbsp; enthält.
 +
*Für die Folge&nbsp; <b>ABABABBAA</b>&nbsp; gilt entsprechend der  Teilaufgabe&nbsp; '''(1)'''&nbsp; stets&nbsp; $I < i$.
 +
*Dagegen ergäbe sich für die Folge&nbsp; <b>ABABABABA</b>&nbsp; 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}.  $$
  
:* <i>i</i> = 3: Decodierung <i>I</i> = 2 &#8594; <b>AB</b>, <i>W</i>(<i>I</i> = 3) = <b>BA</b>,
+
Hier noch zusammenfassend die gesamte Decodierung von&nbsp; <b>ABABABABA</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.
+
*Die Vorbelegung des Wörterbuchs beinhaltet&nbsp; $(I=0$:&nbsp; <b>A</b>$)$ &nbsp; &nbsp; und&nbsp; $(I=1$:&nbsp; <b>B</b>$)$.  
  
:* <i>i</i> = 5: Decodierung <i>I</i> = 3 &#8594; <b>BA</b>. Ende der Decodereingangsfolge.
+
*Dann gilt mit dem Wörterbuch&ndash;Array&nbsp; $W(I)$:
 +
:: $i = 1$: &nbsp; &nbsp; Decodierung &nbsp; $I=0$ &nbsp; &#8594; &nbsp; <b>A</b>,
 +
:: $i = 2$: &nbsp; &nbsp; Decodierung &nbsp; $I=1$ &nbsp; &#8594; &nbsp; <b>B</b>, &nbsp; &nbsp; &nbsp; $W(I = 2) =$ <b>AB</b>,
 +
:: $i = 3$: &nbsp; &nbsp; Decodierung &nbsp; $I=2$ &nbsp; &#8594; &nbsp; <b>AB</b>, &nbsp;&nbsp;&nbsp; $W(I = 3) =$ <b>BA</b>,
 +
:: $i = 4$: &nbsp; &nbsp; Ein Eintrag mit dem Index&nbsp; $I = 4$&nbsp; ist nicht vorhanden &nbsp; &#8658; &nbsp; '''Sonderfallregelung''': <br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Man nimmt das letzte Decodierergebnis&nbsp; $($hier&nbsp; <b>AB</b>$)$ und fügt das erste Zeichen dieser Sequenz hinten an &nbsp; &#8658; &nbsp; <b>ABA</b>. <br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Danach wird&nbsp; <b>ABA</b>&nbsp; im Wörterbuch unter dem&nbsp; Index&nbsp; $I = 4$&nbsp; abgelegt.
 +
:: $i = 5$: &nbsp; &nbsp; Decodierung &nbsp; $I=3$ &nbsp; &#8594; &nbsp; <b>BA</b>. &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;  '''Ende der Decoder&ndash;Eingangsfolge'''.
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  
  
  
[[Category:Aufgaben zu Informationstheorie und Quellencodierung|^2.2 Komprimierung nach Lempel, Ziv und Welch^]]
+
[[Category:Aufgaben zu Informationstheorie|^2.2 Verfahren von Lempel, Ziv, Welch^]]

Version vom 23. Januar 2020, 17:52 Uhr

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:

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

1

Codieren Sie die Eingangsfolge  ABABABBAA  entsprechend der oberen Grafik.  Welche Indizes  $I_i$  ergeben sich zu den Schritten  $i=1$, ... , $i=5$?

$I_1 \ = \ $

$I_2 \ = \ $

$I_3 \ = \ $

$I_4 \ = \ $

$I_5 \ = \ $

2

Codieren Sie nun die Eingangsfolge  ABABABABA  entsprechend der unteren Grafik.  Geben Sie die Indizes  $I_i$  zu den Schritten  $i=4$  und  $i=5$  an.

$I_4 \ = \ $

$I_5 \ = \ $

3

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

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

$\text{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

(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 dann 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 obigen Ergebnissen zeigt:

  • Das Wörterbuch des  Coders  weist genau nach  $\underline{i=4}$  Codierschritten die gezeigten Einträge auf.
  • 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 der Teilaufgabe  (1)  stets  $I < i$.
  • Dagegen ergäbe sich für die 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.