Aufgaben:Aufgabe 2.4: Zum LZW-Algorithmus: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
K (Guenter verschob die Seite 2.4 LZW-Algorithmus nach 2.4 Zum LZW-Algorithmus)
(12 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 3: Zeile 3:
 
}}
 
}}
  
[[Datei:P_ID2440__Inf_A_2_4.png|right|]]
+
[[Datei:P_ID2440__Inf_A_2_4.png|right|frame|LZW–Wörterbuch für Codierung/Decodierung]]
:Der Komprimierungsalgorithmus LZW - benannt nach den Erfindern Abraham Lempel, Jacob Ziv und Terry Welch- arbeitet ebenso wie LZ78 mit einem globalen Wörterbuch. Dieses ist hier zu Beginn mit allen möglichen Zeichen &ndash; im Beispiel <b>A</b>, <b>B</b>, <b>C</b> und <b>D</b> &ndash; vorbelegt und wird während der Codierung sukzessive erweitert.
+
Der Komprimierungsalgorithmus &bdquo;LZW &rdquo; &ndash; benannt nach den Erfindern&nbsp;  [https://de.wikipedia.org/wiki/Abraham_Lempel Abraham Lempel],&nbsp; [https://de.wikipedia.org/wiki/Jacob_Ziv Jacob Ziv]&nbsp;  und&nbsp;  [https://de.wikipedia.org/wiki/Terry_Welch Terry Welch]&nbsp; &ndash; arbeitet ebenso wie &bdquo;LZ78 &rdquo; mit einem globalen Wörterbuch.&nbsp; Dieses ist hier zu Beginn mit allen möglichen Zeichen &ndash; im Beispiel&nbsp; <b>A</b>,&nbsp; <b>B</b>,&nbsp; <b>C</b>,&nbsp; <b>D</b>&nbsp; &ndash; vorbelegt und wird während der Codierung sukzessive erweitert.
  
:Bei der Decodierung entsteht genau das gleiche Wörterbuch, nur erfolgt der gleiche Eintrag mit dem Index <i>I</i> einen Schritt später als während der Codierung. Zur Bezeichnung der Decodierschritte verwenden wir hier die Laufvariable <i>i</i>.
+
Bei der Decodierung entsteht genau das gleiche Wörterbuch, nur erfolgt der gleiche Eintrag mit dem Index&nbsp; $I$&nbsp; einen Schritt später als während der Codierung.&nbsp; Zur Bezeichnung der Decodierschritte verwenden wir hier die Laufvariable&nbsp; $i$.
  
:Hier noch einige Hinweise zur LZW&ndash;Codierung und &ndash;Decodierung:
+
Hier noch einige Hinweise zur LZW&ndash;Codierung und &ndash;Decodierung:
 +
*Bei der Codierung wird zu jedem Zeitpunkt&nbsp; $i$&nbsp; im Wörterbuch nach einer möglichst langen Zeichenkette gesucht, die mit dem aktuell anliegenden Eingabe&ndash;String übereinstimmt.
 +
*Der gefundene Wörterbuchindex&nbsp; $I_i$&nbsp; wird stets in Binärform übertragen.&nbsp; Gleichzeitig wird ins Wörterbuch unter dem nächsten freien Index&nbsp; $W(I_i) + Z$&nbsp; eingetragen.
 +
*Hierbei bezeichner&nbsp; $W(I_i)$&nbsp; ein Zeichen oder eine Zeichenfolge, und&nbsp; $Z$&nbsp; ist das erste Zeichen des anstehenden Eingabe&ndash;Strings&nbsp; (also ebenfalls ein Character), das in&nbsp; $W(I_i)$&nbsp; nicht mehr berücksichtigt ist.
 +
*Bei&nbsp; $M = 4$&nbsp; möglichen Zeichen wird der erste Index&nbsp; $I_1$&nbsp; mit zwei Bit übertragen, die Indizes&nbsp; $I_2$,&nbsp;... ,&nbsp;$I_5$&nbsp; mit drei Bit, die nächsten acht Indizes mit vier Bit, danach 16 Indizes mit fünf Bit usw. Die Begründung für diese bitsparende Maßnahme finden Sie in der Musterlösung zu dieser Aufgabe.
  
:<ul class="liste_ohne"><li>Bei der Codierung wird zu jedem Zeitpunkt <i>i</i> im Wörterbuch nach einer möglichst langen Zeichenkette gesucht, die mit dem aktuell anliegenden Eingabe&ndash;String übereinstimmt.
 
  
:<ul class="liste_ohne"><li>Der gefundene Wörterbuchindex <i>I<sub>i</sub></i> wird stets in Binärform übertragen. Gleichzeitig wird ins Wörterbuch unter dem nächsten freien Index <i>W</i>(<i>I<sub>i</sub></i>) + <i>Z</i> eingetragen.
+
Nach der Codierung in der hier beschriebenen Weise über&nbsp; $16$&nbsp; Codierschritte ergibt sich die folgende Binärfolge der Länge&nbsp; $N_{\rm Bit} = 61$:
 +
:$$\boldsymbol{\rm 00 \ 000 \ 001 \ 010 \ 100 \ 0001 \ 1000 \ 0111 \ 0001 \ 0001 \ 0011 \ 1011 \ 1011 \ 01101 \ 00011 \  01001}\hspace{0.05cm}.$$
  
:<ul class="liste_ohne"><li>Hierbei bezeichner <i>W</i>(<i>I<sub>i</sub></i>) ein Zeichen oder eine Zeichenfolge, und <i>Z</i> ist das erste Zeichen des anstehenden Eingabe&ndash;Strings (also ebenfalls ein Character), das in <i>W</i>(<i>I<sub>i</sub></i>) nicht mehr berücksichtigt ist.
+
Aufgabe des Decoders&nbsp; (genauer gesagt:&nbsp; Ihre Aufgabe)&nbsp; ist es nun,
 +
* aus dieser Binärsequenz die Indizes&nbsp; $I_1$, ... , $I_{16}$&nbsp; zu rekonstruieren, wobei die unterschiedliche Bitanzahl zu berücksichtigen ist&nbsp; (Beschreibung der 16 Decodierergebnisse durch Dezimalzahlen),
 +
* anschließend aus dem Wörterbuch entsprechend den Indizes die zugehörigen Zeichen bzw. Zeichenfolgen auszulesen und schließlich &ndash; mit einem Schritt Verzögerung &ndash; den neuen Wörterbucheintrag zu generieren.
  
:<ul class="liste_ohne"><li>Bei <i>M</i> = 4 möglichen Zeichen wird der erste Index <i>I</i><sub>1</sub> mit 2 Bit übertragen, die Indizes <i>I</i><sub>2</sub>,&nbsp;...,&nbsp;<i>I</i><sub>5</sub> mit 3 Bit, die nächsten 8 Indizes mit 4 Bit, danach 16 Indizes mit 5 Bit usw. Die Begründung für diese bitsparende Maßnahme finden Sie in der Musterlösung zur Aufgabe.
 
  
:Nach der Codierung in der hier beschriebenen Art und Weise über 16 Codierschritte ergibt sich die folgende Binärfolge der Länge <i>N</i><sub>Bit</sub> = 61:
 
:$$\boldsymbol{\rm 00 000 001 010 100 0001 1000 0111 0001 0001 0011 1011 1011 01101 00011 01001}\hspace{0.05cm}.$$
 
:Aufgabe des Decoders (genauer gesagt: Ihre Aufgabe) ist es nun,
 
  
:* aus dieser Binärsequenz die Indizes <i>I</i><sub>1</sub>, ... , <i>I</i><sub>16</sub> zu rekonstruieren, wobei die unterschiedliche Bitanzahl zu berücksichtigen ist (Beschreibung der 16 Decodierergebnisse durch Dezimalzahlen),
 
  
:* anschließend aus dem Wörterbuch entsprechend den Indizes die zugehörigen Zeichen bzw. Zeichenfolgen auszulesen und schließlich &ndash; mit einem Schritt Verzögerung &ndash; den neuen Wörterbucheintrag zu generieren.
 
  
:<b>Hinweis:</b> Die Aufgabe bezieht sich auf das Kapitel 2.2.
+
 
 +
 
 +
 
 +
''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&nbsp;
 +
:: [[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]].
 +
 +
*Die&nbsp; [[Aufgaben:Aufgabe_2.3:_Zur_LZ78-Komprimierung|Aufgabe 2.3]]&nbsp; sowie die&nbsp; [[Aufgaben:Aufgabe_2.3Z:_Zur_LZ77-Codierung|Aufgabe 2.3Z]]&nbsp; behandeln andere LZ-Verfahren in ähnlicher Weise.
 +
 
  
  
Zeile 32: Zeile 43:
  
 
<quiz display=simple>
 
<quiz display=simple>
{Welche Indizes stehen zu den ersten vier Schritten zur Decodierung an? Geben Sie alle <i>I</i> als Dezimalzahlen ein.
+
{Welche Indizes stehen zu den ersten vier Schritten&nbsp; $i=1$, ... , $i=4$&nbsp; zur Decodierung an?&nbsp; Geben Sie alle&nbsp; $I_i = I(i)$&nbsp; als Dezimalzahlen ein.
 
|type="{}"}
 
|type="{}"}
$i = 1:\ I_1$ = { 0 3% }
+
$I_1 \ = \ $ { 0. }
$i = 2:\ I_2$ = { 0 3% }
+
$I_2 \ = \ $ { 0. }
$i = 3:\ I_3$ = { 1 3% }
+
$I_3 \ = \ $ { 1 }
$i = 4:\ I_4$ = { 2 3% }
+
$I_4 \ = \ $ { 2 }
  
  
{Setzen Sie die Unterteilung des Decoder&ndash;Eingabestrings bis zum Ende fort. Welche Indizes ergeben sich bei den aufgeführten Decodierschritten?
+
{Setzen Sie die Unterteilung des Decoder&ndash;Eingabestrings bis zum Ende fort.&nbsp; Welche Indizes ergeben sich bei den Decodierschritten&nbsp; $i=5$, ... , $i=8$?
 
|type="{}"}
 
|type="{}"}
$i = 5:\ I_5$ = { 4 3% }
+
$I_5 \ = \ $ { 4 }
$i = 6:\ I_6$ = { 1 3% }
+
$I_6 \ = \ $ { 1 }
$i = 7:\ I_7$ = { 8 3% }
+
$I_7 \ = \ $ { 8 }
$i = 8:\ I_8$ = { 7 3% }
+
$I_8 \ = \ $ { 7 }
  
  
{Wie lautet der Ausgabe&ndash;String nach <i>i</i> = 16 Decodierschritten?
+
 
|type="[]"}
+
{Wie lautet der Ausgabe&ndash;String nach&nbsp; $i = 16$&nbsp; Decodierschritten?
 +
|type="()"}
 
- <b>AABCAABAABCAABCABBDBBDCDBA</b>,
 
- <b>AABCAABAABCAABCABBDBBDCDBA</b>,
 
+ <b>AABCAABAABCABBDCABCABBDDBA</b>,
 
+ <b>AABCAABAABCABBDCABCABBDDBA</b>,
Zeile 55: Zeile 67:
  
  
{Der nächste Index lautet: <i>I</i><sub>17</sub> = 10010 (binär) = 18 (dezimal). Welche der folgenden Aussagen treffen zu?
+
{Der nächste Index lautet: &nbsp; $I_{17} = 10010$ (binär) $= 18$ (dezimal).&nbsp; Welche der folgenden Aussagen treffen zu?
 
|type="[]"}
 
|type="[]"}
+ Die Decoderausgabe zum Schritt <i>i</i> = 17 lautet <b>DB</b>.
+
+ Die Decoderausgabe zum Schritt&nbsp; $i = 17$&nbsp; lautet&nbsp; <b>DB</b>.
- Die Decoderausgabe zum Schritt <i>i</i> = 17 lautet <b>BAD</b>.
+
- Die Decoderausgabe zum Schritt&nbsp; $i = 17$&nbsp; lautet&nbsp; <b>BAD</b>.
- Neuer Wörterbucheintrag <b>DB</b> in die Zeile <i>I</i> = 19.
+
- Neuer Wörterbucheintrag&nbsp; <b>DB</b>&nbsp; in die Zeile&nbsp; $I = 19$.
+ Neuer Wörterbucheintrag <b>BAD</b> in die Zeile <i>I</i> = 19.
+
+ Neuer Wörterbucheintrag&nbsp; <b>BAD</b>&nbsp; in die Zeile&nbsp; $I = 19$.
  
  
{Der Decoder&ndash;Eingabestring besteht aus <i>N</i><sub>Bit</sub> = 300 Binärzeichen (Bit). Welche der folgenden Aussagen sind dann sicher zutreffend?
+
{Der Decoder&ndash;Eingabestring bestehe aus&nbsp; $N_{\rm Bit} = 300$&nbsp; Binärzeichen (Bit).&nbsp; Welche der folgenden Aussagen sind dann sicher zutreffend?
 
|type="[]"}
 
|type="[]"}
+ Übertragen wurden 58 LZW&ndash;Phrasen mit variabler Bitlänge.
+
+ Übertragen wurden&nbsp; $58$&nbsp; LZW&ndash;Phrasen mit variabler Bitlänge.
 
- Mit einheitlicher Indexbitlänge wären weniger Bit erforderlich.
 
- Mit einheitlicher Indexbitlänge wären weniger Bit erforderlich.
- Übertragen wurde eine Datei mit <i>N</i>&nbsp;=&nbsp;150 Quaternärzeichen.
+
- Übertragen wurde eine Datei mit&nbsp; $N =150$&nbsp; Quaternärzeichen.
  
  
Zeile 75: Zeile 87:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
:<b>1.</b>&nbsp;&nbsp;Bei der LZW&ndash;Codierung des ersten Zeichens (<i>i</i> = 1) sind nur die vier Indizes <i>I</i> = 0, ... , <i>I</i> = 3 möglich, für die bereits zum Schritt <i>i</i> = 0 (Vorbelegung) ein Wörterbucheintrag vorgenommen wurde. Deshalb genügt es hier, den Index mit zwei Bit zu übertragen.
+
'''(1)'''&nbsp; Bei der LZW&ndash;Codierung des ersten Zeichens&nbsp; $(i = 1)$&nbsp; sind nur die vier Indizes&nbsp; $I = 0$, ... , $I = 3$&nbsp; möglich, für die bereits zum Schritt&nbsp; $i = 0$&nbsp; (Vorbelegung) ein Wörterbucheintrag vorgenommen wurde. Deshalb genügt es hier, den Index mit zwei Bit zu übertragen.
  
:Bereits zum Schritt <i>i</i> = 2 werden dagegen drei Bit benötigt. Hätte die Eingangsfolge mit <b>AAA</b> begonnen, so hätte die LZW&ndash;Codierung <i>I</i><sub>2</sub> = <i>I</i>(<i>i</i> = 2) den Dezimalwert 4 ergeben. Dieser ist nicht mehr mit zwei Bit darstellbar und muss mit drei Bit codiert werden, ebenso wie <i>I</i><sub>3</sub>, <i>I</i><sub>4</sub> und <i>I</i><sub>5</sub>.
+
*Bereits zum Schritt&nbsp; $i = 2$&nbsp; werden dagegen drei Bit benötigt. Hätte die Eingangsfolge mit&nbsp; <b>AAA</b>&nbsp; begonnen, so hätte die LZW&ndash;Codierung&nbsp; $I_2 = I(i = 2)$&nbsp; den Dezimalwert&nbsp; $4$&nbsp; ergeben. Dieser ist nicht mehr mit zwei Bit darstellbar und muss mit drei Bit codiert werden, ebenso wie&nbsp; $I_3$,&nbsp; $I_4$&nbsp; und&nbsp; $I_5$.
  
:Der vorgegebene Eingabestring
+
*Der vorgegebene Eingabestring
 
:$$\boldsymbol{\rm 00 000 001 010 100 0001}\hspace{0.05cm}...$$
 
:$$\boldsymbol{\rm 00 000 001 010 100 0001}\hspace{0.05cm}...$$
 
:ist deshalb vom Decoder wie folgt aufzuteilen:
 
:ist deshalb vom Decoder wie folgt aufzuteilen:
 
:$$\boldsymbol{\rm 00 | 000 |001 |010 |100 |0001|}\hspace{0.05cm}...$$
 
:$$\boldsymbol{\rm 00 | 000 |001 |010 |100 |0001|}\hspace{0.05cm}...$$
:Die Decoderergebnisse der ersten vier Schritte lauten somit:
 
  
:* <u><i>i</i> = 1:</u>&nbsp;&nbsp; <i>I</i> = <b>00</b> (binär) &nbsp;&nbsp; &nbsp;<u> = 0</u> (dezimal) &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <b>A</b>,
+
*Die Decoderergebnisse der ersten vier Schritte lauten somit:
 +
:* $I_1 =$ <b>00</b> (binär) &nbsp;&nbsp; &nbsp;<u> = 0</u> (dezimal) &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <b>A</b>,
 +
:* $I_2 =$ <b>000</b> (binär) &nbsp;&nbsp;<u> = 0</u> (dezimal) &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <b>A</b>,
 +
:* $I_3 =$ <b>001</b> (binär) &nbsp;&nbsp;<u> = 1</u> (dezimal) &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <b>B</b>,
 +
:* $I_4 =$ <b>010</b> (binär) &nbsp;&nbsp;<u> = 2</u> (dezimal) &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <b>C</b>.
  
:* <u><i>i</i> = 2:</u>&nbsp;&nbsp; <i>I</i> = <b>000</b> (binär) &nbsp;&nbsp;<u> = 0</u> (dezimal) &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <b>A</b>,
 
  
:* <u><i>i</i> = 3:</u>&nbsp;&nbsp; <i>I</i> = <b>001</b> (binär) &nbsp;&nbsp;<u> = 1</u> (dezimal) &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <b>B</b>,
+
'''(2)'''&nbsp; Berücksichtigt man, dass
 +
* für&nbsp; $i = 1$&nbsp; zwei Bit verwendet werden,
 +
* für&nbsp; $2 &#8804; i &#8804; 5$&nbsp; drei Bit,
 +
* für&nbsp; $6 &#8804; i &#8804; 19$&nbsp; vier Bit,
 +
* für&nbsp; $14 &#8804; i &#8804; 29$&nbsp; fünf Bit,
  
:* <u><i>i</i> = 4:</u>&nbsp;&nbsp; <i>I</i> = <b>010</b> (binär) &nbsp;&nbsp;<u> = 2</u> (dezimal) &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <b>C</b>.
 
  
:<b>2.</b>&nbsp;&nbsp;Berücksichtigt man, dass
+
so kommt man vom &bdquo;kontinuierlichen Decoder&ndash;Eingangsstring&rdquo;
 
+
:$$\boldsymbol{\rm 00 000 001 010 100 0001 1000 0111 0001 0001 0011 1011 1011 01101 00011 01001}$$
:* für <i>i</i> = 1 zwei Bit verwendet werden,
 
  
:* für 2 &#8804; <i>i</i> &#8804; 5 drei Bit,
+
zum &bdquo;eingeteilten Decoder&ndash;Eingabestring&rdquo; $($bezeichnet mit&nbsp;  $I_1$, ... ,&nbsp; $I_{16})$:
 
+
:$$\boldsymbol{\rm 00 |000 |001 |010 |100 |0001 |1000 |0111 | 0001 |0001 |0011  |1011 |1011 |01101 |00011 |01001}
:* für 6 &#8804; <i>i</i> &#8804; 19 vier Bit,
 
 
 
:* für 14 &#8804; <i>i</i> &#8804; 29 fünf Bit,
 
 
 
:so kommt man vom &bdquo;kontinuierlichen Decoder&ndash;Eingangsstring&rdquo;
 
:$$\boldsymbol{\rm 00 000 001 010 100 0001 1000 0111 0001 0001 0011 1011 1011 01101 00011 01001}$$
 
:zum &bdquo;eingeteilten Decoder&ndash;Eingabestring&rdquo; (erste Zeile <i>I</i><sub>1</sub>, ... , <i>I</i><sub>8</sub>, in der zweiten Zeile <i>I</i><sub>9</sub>, ... , <i>I</i><sub>16</sub>):
 
:$$\boldsymbol{\rm 00 |000 |001 |010 |100 |0001 |1000 |0111 | }$$
 
:$$\boldsymbol{\rm 0001 |0001 |0011  |1011 |1011 |01101 |00011 |01001}
 
 
\hspace{0.1cm}.$$
 
\hspace{0.1cm}.$$
:Damit lauten die gesuchten Ergebnisse für die Decodierschritte <i>i</i> = 5, ... , <i>i</i> = 8:
 
 
:* <u><i>i</i> = 5</u>:&nbsp;&nbsp; <i>I</i> = <b>100</b> (binär) &nbsp; &nbsp;&nbsp;<u> = 4</u> (dezimal) &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <b>AA</b>,
 
 
:* <u><i>i</i> = 6</u>:&nbsp;&nbsp; <i>I</i> = <b>0001</b> (binär) &nbsp;&nbsp;<u> = 1</u> (dezimal) &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <b>B</b>,
 
 
:* <u><i>i</i> = 7</u>:&nbsp;&nbsp; <i>I</i> = <b>1000</b> (binär) &nbsp;&nbsp;<u> = 8</u> (dezimal) &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <b>AAB</b>,
 
 
:* <u><i>i</i> = 8:</u>&nbsp;&nbsp; <i>I</i> = <b>0111</b> (binär) &nbsp;&nbsp;<u> = 7</u> (dezimal) &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <b>CA</b>.
 
  
:<b>3.</b>&nbsp;&nbsp;Richtig ist <u>Aussage 2</u>. Man erhält folgende Decodierergebnisse (in verkürzter Form):
+
Damit lauten die gesuchten Ergebnisse für die Decodierschritte&nbsp; $i = 5$, ... ,&nbsp; $i = 8$:
 +
* $I_5 =$ <b>100</b> (binär) &nbsp; &nbsp;&nbsp;<u> = 4</u> (dezimal) &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <b>AA</b>,
 +
* $I_6 =$ <b>0001</b> (binär) &nbsp;&nbsp;<u> = 1</u> (dezimal) &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <b>B</b>,
 +
* $I_7 =$ <b>1000</b> (binär) &nbsp;&nbsp;<u> = 8</u> (dezimal) &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <b>AAB</b>,
 +
* $I_8 =$ <b>0111</b> (binär) &nbsp;&nbsp;<u> = 7</u> (dezimal) &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <b>CA</b>.
  
:<i>I</i><sub>9</sub> = 1 &nbsp;&nbsp;&#8658;&nbsp;&nbsp <b>B</b>,&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <i>I</i><sub>10</sub> = 1 &nbsp;&nbsp;&#8658;&nbsp;&nbsp;<b>B</b>,&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp; <i>I</i><sub>11</sub> = 3 &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <b>D</b>,&nbsp;&nbsp;&nbsp;&nbsp; <i>I</i><sub>12</sub> = 11 &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <b>CAB</b>,
 
  
:<i>I</i><sub>13</sub> = 11 &nbsp;&nbsp;&#8658;&nbsp;&nbsp <b>CAB</b>,&nbsp;&nbsp;&nbsp;&nbsp; <i>I</i><sub>14</sub> = 13 &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <b>BD</b>,&nbsp;&nbsp;&nbsp;&nbsp; <i>I</i><sub>15</sub> = 3 &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <b>D</b>,&nbsp;&nbsp;&nbsp;&nbsp; <i>I</i><sub>16</sub> = 9 &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <b>BA</b>.
+
'''(3)'''&nbsp; Richtig is tdie  <u>Aussage 2</u>.  
 +
*Man erhält folgende Decodierergebnisse (in verkürzter Form):
  
:<b>4.</b>&nbsp;&nbsp;Richtig sind die <u>Aussagen 1 und 4</u>, weil:
+
::&nbsp;&nbsp;$I_{9} = 1$ &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <b>B</b>, $\hspace{0.5cm}I_{10} = 1$ &nbsp;&nbsp;&#8658;&nbsp;&nbsp;<b>B</b>,$\hspace{0.5cm}I_{11} = 3$ &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <b>D</b>,$\hspace{0.5cm}I_{12} = 11$ &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <b>CAB</b>,
  
:* Der neu ankommende Index ist 18 (dezimal) und im Wörterbuch wird unter dem Index <i>I</i> = 18 der Eintrag <b>DB</b> gefunden.
+
::&nbsp;&nbsp;$I_{13} = 11$ &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <b>CAB</b>,$\hspace{0.5cm}I_{14} = 13$ &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <b>BD</b>,$\hspace{0.5cm}I_{15} = 3$ &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <b>D</b>,$\hspace{0.5cm}I_{16} = 9$ &nbsp;&nbsp;&#8658;&nbsp;&nbsp; <b>BA</b>.
  
:* Zum Decodierschritt <i>i</i> = 17 wird in das Wörterbuch die Zeile <i>I</i> = 19 eingetragen. Der Eintrag <b>BAD</b> setzt sich zusammen aus dem Decodierergebnis aus Schritt <i>i</i> = 16 (<b>BA</b>) und dem ersten Zeichen (<b>D</b>) des neuen Ergebnisses <b>DB</b>.
 
  
:<b>5.</b>&nbsp;&nbsp;Richtig ist hier nur die <u>Aussage 1</u>:
 
  
:* Für die erste Phrase genügen zwei Bit.
+
'''(4)'''&nbsp; Richtig sind die <u>Aussagen 1 und 4</u>. Begründung:
  
:* Für die Phrasen <i>I</i><sub>2</sub>, ... , <i>I</i><sub>5</sub> benötigt man drei Bit.
+
* Der neu ankommende Index ist&nbsp; $18$&nbsp; (dezimal) und im Wörterbuch wird unter dem Index&nbsp; $I = 18$&nbsp; der Eintrag&nbsp; <b>DB</b>&nbsp; gefunden.
 +
* Zum Decodierschritt&nbsp; $i = 17$&nbsp; wird in das Wörterbuch die Zeile&nbsp; $I = 19$&nbsp; eingetragen.
 +
*Der Eintrag&nbsp; <b>BAD</b>&nbsp; setzt sich zusammen aus dem Decodierergebnis aus Schritt&nbsp; $i = 16$&nbsp; $($<b>BA</b>$)$&nbsp; und dem ersten Zeichen&nbsp; $($<b>D</b>$)$&nbsp; des neuen Ergebnisses&nbsp; <b>DB</b>.
  
:* Für die Phrasen <i>I</i><sub>6</sub>, ... , <i>I</i><sub>13</sub> benötigt man vier Bit.
 
  
:* Für die Phrasen <i>I</i><sub>14</sub>, ... , <i>I</i><sub>29</sub> benötigt man fünf Bit.
 
  
:* Für die Phrasen <i>I</i><sub>30</sub>, ... , <i>I</i><sub>58</sub> benötigt man sechs Bit.
+
'''(5)'''&nbsp; Richtig ist hier nur die <u>Aussage 1</u>:
 +
* Für die erste Phrase genügen zwei Bit.
 +
* Für die Phrasen&nbsp; $I_2$, ... , $I_5$&nbsp; benötigt man drei Bit.
 +
* Für die Phrasen&nbsp; $I_6$, ... , $I_{13}$&nbsp; benötigt man vier Bit.
 +
* Für die Phrasen&nbsp; $I_{14}$, ... , $I_{29}$&nbsp; benötigt man fünf Bit.
 +
* Für die Phrasen&nbsp; $I_{30}$, ... , $I_{58}$&nbsp; benötigt man sechs Bit.
  
:Damit erhält man für die gesamte Bitanzahl:
+
*Damit erhält man für die gesamte Bitanzahl:
 
:$$N_{\rm Bit} = 1 \cdot 2 + 4 \cdot 3 + 8 \cdot 4 + 16 \cdot 5 + 29 \cdot 6 = 300 \hspace{0.05cm}.$$
 
:$$N_{\rm Bit} = 1 \cdot 2 + 4 \cdot 3 + 8 \cdot 4 + 16 \cdot 5 + 29 \cdot 6 = 300 \hspace{0.05cm}.$$
:Mit einheitlicher Bitlänge (6 Bit für jeden Index) wären 58 &middot; 6 = 348 Bit (also mehr) erforderlich &#8658; Aussage 2 ist prinzipiell falsch. Nun zur Aussage 3:
 
  
:* Bei der uncodierten Übertragung von <i>N</i> = 150 Zeichen aus der Symbolmenge {<b>A</b>, <b>B</b>, <b>C</b>,  <b>D</b>} würde man genau 300 Bit benötigen. Mit LZW benötigt man sicher mehr Bit, wenn die Quelle redundanzfrei ist (Zeichen gleichwahrscheinlich und statistisch unabhängig).
+
*Mit einheitlicher Bitlänge (sechs Bit für jeden Index) wären&nbsp; $58 &middot; 6 = 348$&nbsp; Bit (also mehr) erforderlich &nbsp; &#8658; &nbsp; die Aussage 2 ist prinzipiell falsch.  
  
:* Bei redundanter Quelle mit (beispielsweise) <i>H</i> = 1.6 Bit/Quellensymbol kann man die Bitanzahl auf <i>N</i><sub>Bit</sub>&nbsp;=&nbsp;<i>N</i>&nbsp;&middot;&nbsp;<i>H</i> begrenzen, vorausgesetzt, es handelt sich um eine sehr große Datei (<i>N</i> &#8594; &#8734;).
 
  
:* Bei einer eher kleinen Datei &ndash; wie hier lediglich mit <i>N</i> = 150 Bit &ndash; ist keine Aussage möglich, ob die Bitanzahl <i>N</i><sub>Bit</sub> kleiner, gleich oder größer als 150 &middot; 1.6 = 240 sein wird. Auch <i>N</i><sub>Bit</sub> > 300 ist durchaus möglich. Dann sollte man auf die &bdquo;LZ&ndash;Komprimierung&rdquo; besser verzichten.
+
Nun zur dritten Aussage, die ebenfalls nicht zutrifft:
 +
* Bei der uncodierten Übertragung von&nbsp; $N = 150$&nbsp; Zeichen aus der Symbolmenge&nbsp; $\{$ <b>A</b>, \ <b>B</b>, \ <b>C</b>, \  <b>D</b> $\}$&nbsp; würde man genau&nbsp; $300$&nbsp; Bit benötigen. Mit LZW benötigt man sicher mehr Bit, wenn die Quelle redundanzfrei ist&nbsp; (Zeichen gleichwahrscheinlich und statistisch unabhängig).
 +
* Bei redundanter Quelle mit (beispielsweise)&nbsp; $H = 1.6$ bit/Quellensymbol kann man die Bitanzahl auf&nbsp; $N_{\rm Bit} = N \cdot H$&nbsp;  begrenzen, vorausgesetzt, es handelt sich um eine sehr große Datei&nbsp; $(N \to \infty)$.
 +
* Bei einer eher kleinen Datei &ndash; wie hier lediglich mit&nbsp; $N = 150$&nbsp; Bit &ndash; ist keine Aussage möglich, ob die Bitanzahl&nbsp; $N_{\rm Bit}$&nbsp; kleiner, gleich oder größer als&nbsp; $150 &middot; 1.6 = 240$&nbsp; sein wird.  
 +
*Auch&nbsp; $N_{\rm Bit} > 300$&nbsp; ist durchaus möglich.&nbsp; Dann sollte man auf die &bdquo;Lempel&ndash;Ziv&ndash;Komprimierung&rdquo; besser verzichten.
 
{{ML-Fuß}}
 
{{ML-Fuß}}
 +
  
  
  
 
[[Category:Aufgaben zu Informationstheorie|^2.2 Verfahren von Lempel, Ziv, Welch^]]
 
[[Category:Aufgaben zu Informationstheorie|^2.2 Verfahren von Lempel, Ziv, Welch^]]

Version vom 23. Januar 2020, 17:08 Uhr

LZW–Wörterbuch für Codierung/Decodierung

Der Komprimierungsalgorithmus „LZW ” – benannt nach den Erfindern  Abraham LempelJacob Ziv  und  Terry Welch  – arbeitet ebenso wie „LZ78 ” mit einem globalen Wörterbuch.  Dieses ist hier zu Beginn mit allen möglichen Zeichen – im Beispiel  ABCD  – vorbelegt und wird während der Codierung sukzessive erweitert.

Bei der Decodierung entsteht genau das gleiche Wörterbuch, nur erfolgt der gleiche Eintrag mit dem Index  $I$  einen Schritt später als während der Codierung.  Zur Bezeichnung der Decodierschritte verwenden wir hier die Laufvariable  $i$.

Hier noch einige Hinweise zur LZW–Codierung und –Decodierung:

  • Bei der Codierung wird zu jedem Zeitpunkt  $i$  im Wörterbuch nach einer möglichst langen Zeichenkette gesucht, die mit dem aktuell anliegenden Eingabe–String übereinstimmt.
  • Der gefundene Wörterbuchindex  $I_i$  wird stets in Binärform übertragen.  Gleichzeitig wird ins Wörterbuch unter dem nächsten freien Index  $W(I_i) + Z$  eingetragen.
  • Hierbei bezeichner  $W(I_i)$  ein Zeichen oder eine Zeichenfolge, und  $Z$  ist das erste Zeichen des anstehenden Eingabe–Strings  (also ebenfalls ein Character), das in  $W(I_i)$  nicht mehr berücksichtigt ist.
  • Bei  $M = 4$  möglichen Zeichen wird der erste Index  $I_1$  mit zwei Bit übertragen, die Indizes  $I_2$, ... , $I_5$  mit drei Bit, die nächsten acht Indizes mit vier Bit, danach 16 Indizes mit fünf Bit usw. Die Begründung für diese bitsparende Maßnahme finden Sie in der Musterlösung zu dieser Aufgabe.


Nach der Codierung in der hier beschriebenen Weise über  $16$  Codierschritte ergibt sich die folgende Binärfolge der Länge  $N_{\rm Bit} = 61$:

$$\boldsymbol{\rm 00 \ 000 \ 001 \ 010 \ 100 \ 0001 \ 1000 \ 0111 \ 0001 \ 0001 \ 0011 \ 1011 \ 1011 \ 01101 \ 00011 \ 01001}\hspace{0.05cm}.$$

Aufgabe des Decoders  (genauer gesagt:  Ihre Aufgabe)  ist es nun,

  • aus dieser Binärsequenz die Indizes  $I_1$, ... , $I_{16}$  zu rekonstruieren, wobei die unterschiedliche Bitanzahl zu berücksichtigen ist  (Beschreibung der 16 Decodierergebnisse durch Dezimalzahlen),
  • anschließend aus dem Wörterbuch entsprechend den Indizes die zugehörigen Zeichen bzw. Zeichenfolgen auszulesen und schließlich – mit einem Schritt Verzögerung – den neuen Wörterbucheintrag zu generieren.





Hinweise:

LZ77 – die Grundform der Lempel-Ziv-Algorithmen,
Lempel-Ziv-Codierung mit variabler Indexbitlänge,
Decodierung des LZW-Agorithmus.


Fragebogen

1

Welche Indizes stehen zu den ersten vier Schritten  $i=1$, ... , $i=4$  zur Decodierung an?  Geben Sie alle  $I_i = I(i)$  als Dezimalzahlen ein.

$I_1 \ = \ $

$I_2 \ = \ $

$I_3 \ = \ $

$I_4 \ = \ $

2

Setzen Sie die Unterteilung des Decoder–Eingabestrings bis zum Ende fort.  Welche Indizes ergeben sich bei den Decodierschritten  $i=5$, ... , $i=8$?

$I_5 \ = \ $

$I_6 \ = \ $

$I_7 \ = \ $

$I_8 \ = \ $

3

Wie lautet der Ausgabe–String nach  $i = 16$  Decodierschritten?

AABCAABAABCAABCABBDBBDCDBA,
AABCAABAABCABBDCABCABBDDBA,
AABCAABAABCABDBBABCCDBAABDCDBA.

4

Der nächste Index lautet:   $I_{17} = 10010$ (binär) $= 18$ (dezimal).  Welche der folgenden Aussagen treffen zu?

Die Decoderausgabe zum Schritt  $i = 17$  lautet  DB.
Die Decoderausgabe zum Schritt  $i = 17$  lautet  BAD.
Neuer Wörterbucheintrag  DB  in die Zeile  $I = 19$.
Neuer Wörterbucheintrag  BAD  in die Zeile  $I = 19$.

5

Der Decoder–Eingabestring bestehe aus  $N_{\rm Bit} = 300$  Binärzeichen (Bit).  Welche der folgenden Aussagen sind dann sicher zutreffend?

Übertragen wurden  $58$  LZW–Phrasen mit variabler Bitlänge.
Mit einheitlicher Indexbitlänge wären weniger Bit erforderlich.
Übertragen wurde eine Datei mit  $N =150$  Quaternärzeichen.


Musterlösung

(1)  Bei der LZW–Codierung des ersten Zeichens  $(i = 1)$  sind nur die vier Indizes  $I = 0$, ... , $I = 3$  möglich, für die bereits zum Schritt  $i = 0$  (Vorbelegung) ein Wörterbucheintrag vorgenommen wurde. Deshalb genügt es hier, den Index mit zwei Bit zu übertragen.

  • Bereits zum Schritt  $i = 2$  werden dagegen drei Bit benötigt. Hätte die Eingangsfolge mit  AAA  begonnen, so hätte die LZW–Codierung  $I_2 = I(i = 2)$  den Dezimalwert  $4$  ergeben. Dieser ist nicht mehr mit zwei Bit darstellbar und muss mit drei Bit codiert werden, ebenso wie  $I_3$,  $I_4$  und  $I_5$.
  • Der vorgegebene Eingabestring
$$\boldsymbol{\rm 00 000 001 010 100 0001}\hspace{0.05cm}...$$
ist deshalb vom Decoder wie folgt aufzuteilen:
$$\boldsymbol{\rm 00 | 000 |001 |010 |100 |0001|}\hspace{0.05cm}...$$
  • Die Decoderergebnisse der ersten vier Schritte lauten somit:
  • $I_1 =$ 00 (binär)      = 0 (dezimal)   ⇒   A,
  • $I_2 =$ 000 (binär)    = 0 (dezimal)   ⇒   A,
  • $I_3 =$ 001 (binär)    = 1 (dezimal)   ⇒   B,
  • $I_4 =$ 010 (binär)    = 2 (dezimal)   ⇒   C.


(2)  Berücksichtigt man, dass

  • für  $i = 1$  zwei Bit verwendet werden,
  • für  $2 ≤ i ≤ 5$  drei Bit,
  • für  $6 ≤ i ≤ 19$  vier Bit,
  • für  $14 ≤ i ≤ 29$  fünf Bit,


so kommt man vom „kontinuierlichen Decoder–Eingangsstring”

$$\boldsymbol{\rm 00 000 001 010 100 0001 1000 0111 0001 0001 0011 1011 1011 01101 00011 01001}$$

zum „eingeteilten Decoder–Eingabestring” $($bezeichnet mit  $I_1$, ... ,  $I_{16})$:

$$\boldsymbol{\rm 00 |000 |001 |010 |100 |0001 |1000 |0111 | 0001 |0001 |0011 |1011 |1011 |01101 |00011 |01001} \hspace{0.1cm}.$$

Damit lauten die gesuchten Ergebnisse für die Decodierschritte  $i = 5$, ... ,  $i = 8$:

  • $I_5 =$ 100 (binär)      = 4 (dezimal)   ⇒   AA,
  • $I_6 =$ 0001 (binär)    = 1 (dezimal)   ⇒   B,
  • $I_7 =$ 1000 (binär)    = 8 (dezimal)   ⇒   AAB,
  • $I_8 =$ 0111 (binär)    = 7 (dezimal)   ⇒   CA.


(3)  Richtig is tdie Aussage 2.

  • Man erhält folgende Decodierergebnisse (in verkürzter Form):
  $I_{9} = 1$   ⇒   B, $\hspace{0.5cm}I_{10} = 1$   ⇒  B,$\hspace{0.5cm}I_{11} = 3$   ⇒   D,$\hspace{0.5cm}I_{12} = 11$   ⇒   CAB,
  $I_{13} = 11$   ⇒   CAB,$\hspace{0.5cm}I_{14} = 13$   ⇒   BD,$\hspace{0.5cm}I_{15} = 3$   ⇒   D,$\hspace{0.5cm}I_{16} = 9$   ⇒   BA.


(4)  Richtig sind die Aussagen 1 und 4. Begründung:

  • Der neu ankommende Index ist  $18$  (dezimal) und im Wörterbuch wird unter dem Index  $I = 18$  der Eintrag  DB  gefunden.
  • Zum Decodierschritt  $i = 17$  wird in das Wörterbuch die Zeile  $I = 19$  eingetragen.
  • Der Eintrag  BAD  setzt sich zusammen aus dem Decodierergebnis aus Schritt  $i = 16$  $($BA$)$  und dem ersten Zeichen  $($D$)$  des neuen Ergebnisses  DB.


(5)  Richtig ist hier nur die Aussage 1:

  • Für die erste Phrase genügen zwei Bit.
  • Für die Phrasen  $I_2$, ... , $I_5$  benötigt man drei Bit.
  • Für die Phrasen  $I_6$, ... , $I_{13}$  benötigt man vier Bit.
  • Für die Phrasen  $I_{14}$, ... , $I_{29}$  benötigt man fünf Bit.
  • Für die Phrasen  $I_{30}$, ... , $I_{58}$  benötigt man sechs Bit.
  • Damit erhält man für die gesamte Bitanzahl:
$$N_{\rm Bit} = 1 \cdot 2 + 4 \cdot 3 + 8 \cdot 4 + 16 \cdot 5 + 29 \cdot 6 = 300 \hspace{0.05cm}.$$
  • Mit einheitlicher Bitlänge (sechs Bit für jeden Index) wären  $58 · 6 = 348$  Bit (also mehr) erforderlich   ⇒   die Aussage 2 ist prinzipiell falsch.


Nun zur dritten Aussage, die ebenfalls nicht zutrifft:

  • Bei der uncodierten Übertragung von  $N = 150$  Zeichen aus der Symbolmenge  $\{$ A, \ B, \ C, \ D $\}$  würde man genau  $300$  Bit benötigen. Mit LZW benötigt man sicher mehr Bit, wenn die Quelle redundanzfrei ist  (Zeichen gleichwahrscheinlich und statistisch unabhängig).
  • Bei redundanter Quelle mit (beispielsweise)  $H = 1.6$ bit/Quellensymbol kann man die Bitanzahl auf  $N_{\rm Bit} = N \cdot H$  begrenzen, vorausgesetzt, es handelt sich um eine sehr große Datei  $(N \to \infty)$.
  • Bei einer eher kleinen Datei – wie hier lediglich mit  $N = 150$  Bit – ist keine Aussage möglich, ob die Bitanzahl  $N_{\rm Bit}$  kleiner, gleich oder größer als  $150 · 1.6 = 240$  sein wird.
  • Auch  $N_{\rm Bit} > 300$  ist durchaus möglich.  Dann sollte man auf die „Lempel–Ziv–Komprimierung” besser verzichten.