Aufgaben:Aufgabe 2.4Z: Nochmals LZW-Codierung und -Decodierung - Versionsgeschichte

Guenter am 17. Juli 2021 um 12:22 Uhr

2021-07-17T12:22:22Z

Guenter am 23. Januar 2020 um 16:52 Uhr

2020-01-23T16:52:35Z

Guenter am 23. Januar 2020 um 16:29 Uhr

2020-01-23T16:29:01Z

Guenter am 24. September 2018 um 16:29 Uhr

2018-09-24T16:29:00Z

Guenter am 24. September 2018 um 16:23 Uhr

2018-09-24T16:23:50Z

Guenter am 24. September 2018 um 15:51 Uhr

2018-09-24T15:51:13Z

Guenter am 24. September 2018 um 15:43 Uhr

2018-09-24T15:43:15Z

Mwiki-lnt: Textersetzung - „*Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.“ durch „ “

2018-05-29T12:02:44Z

Textersetzung - „*Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.“ durch „ “

Guenter: Guenter verschob die Seite Aufgaben:2.4Z Nochmals LZW-Codierung und -Decodierung nach Aufgaben:Aufgabe 2.4Z: Nochmals LZW-Codierung und -Decodierung

2018-01-03T13:58:28Z

Guenter verschob die Seite 2.4Z Nochmals LZW-Codierung und -Decodierung nach Aufgabe 2.4Z: Nochmals LZW-Codierung und -Decodierung

Guenter am 18. Mai 2017 um 11:13 Uhr

2017-05-18T11:13:57Z

@@ Zeile 3: / Zeile 3: @@
 }}
-[[Datei:P_ID2437__Inf_Z_2_4.png|right|frame|Momentaufnahmen der LZW–Wörterbüchern]]
+[[Datei:P_ID2437__Inf_Z_2_4.png|right|frame|Momentaufnahmen <br>der LZW–Wörterbücher]]
-Die Grafik zeigt Momentaufnahmen des Wörterbuchs, das während der&nbsp; <u>LZW&ndash;Codierung</u>&nbsp; der Eingangssymbolfolge entsteht.
+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>.
@@ Zeile 11: / Zeile 11: @@
 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&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.
+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. Decodierschritt die beiden dargestellten Momentaufnahmen gültig sind.
-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 der <u>LZW&ndash;Codierung</u> wird zu jedem Codierschritt&nbsp; $i$&nbsp; ein Index&nbsp; $I$&nbsp; ausgewählt und (binär) übertragen.&nbsp; Das Zeichenpaar&nbsp; <b>AB</b>&nbsp; wird bei den beiden Wörterbüchern durch den Index&nbsp; $I = 2$&nbsp; dargestellt.&nbsp; Wir betrachten hier den Index&nbsp; $I$&nbsp; als Dezimalzahl und lassen bei dieser Aufgabe die Binärdarstellung außer Betracht.
 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>.
-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  tatsächlich ein Wörterbucheintrag mit dem gewünschten Index&nbsp; $I$&nbsp; gefunden, so läuft die Decodierung problemlos ab.&nbsp; 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.

@@ Zeile 84: / Zeile 84: @@
 ===Musterlösung===
 {{ML-Kopf}}
-'''(1)'''&nbsp; Wir bezeichnen mit $W(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;
-Es ist anzumerken, dass das letzte Zeichen (<b>A</b>) des Eingabestrings <b>ABABABBAA</b> zum Zeitpunkt $i = 5$ zwar bereits beim Wörterbucheintrag berücksichtigt ist, aber noch nicht codiert wurde.
+*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.
-'''(3)'''&nbsp; Der Vergleich mit den obigen Ergebnissen zeigt, dass das Wörterbuch des <u>Coders</u> genau nach $\underline{i=4}$ Codierschritten die gezeigten Einträge aufweist.
-*Beim <u>Decoder</u> ergibt sich demgegenüber eine Zeitverzögerung um einen Schritt: &nbsp; $\underline{i=5}$.
+'''(3)'''&nbsp; Der Vergleich mit obigen Ergebnissen zeigt:
 '''(4)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 2</u>:
-*Die Sonderfallregelung der Decodierung ist (im vorliegenden Beispiel) dann notwendig, wenn im Codierschritt $i$ der Index $I =i$ ausgegeben wird.
+*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 Index &#8594; Zeichenfolge nicht, da das generierte Wörterbuch zum Zeitpunkt $i$ nur Einträge mit Indizes $I < i$ enthält.
+*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 <b>ABABABBAA</b> gilt entsprechend Teilaufgabe '''(1)''' stets $I < i$.
+*Für die Folge&nbsp; <b>ABABABBAA</b>&nbsp; gilt entsprechend der  Teilaufgabe&nbsp; '''(1)'''&nbsp; stets&nbsp; $I < i$.
-*Dagegen ergäbe sich bei der Folge <b>ABABABABA</b> folgende Indizes:
+*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},
@@ Zeile 117: / Zeile 122: @@
 \hspace{0.5cm}i = 5\hspace{-0.15cm}: \hspace{0.15cm}I = 3\hspace{0.05cm}.  $$
-Hier noch zusammenfassend die gesamte Decodierung von <b>ABABABABA</b>:
+*Die Vorbelegung des Wörterbuchs beinhaltet&nbsp; $(I=0$:&nbsp; <b>A</b>$)$ &nbsp; &nbsp; und&nbsp; $(I=1$:&nbsp; <b>B</b>$)$.
-Dann gilt mit dem Wörterbuch&ndash;Array $W(I)$:
+*Dann gilt mit dem Wörterbuch&ndash;Array&nbsp; $W(I)$:
-* $i = 1$: &nbsp; &nbsp; Decodierung $I=0$ &#8594; <b>A</b>,
+:: $i = 1$: &nbsp; &nbsp; Decodierung &nbsp; $I=0$ &nbsp; &#8594; &nbsp; <b>A</b>,
-* $i = 2$: &nbsp; &nbsp; Decodierung $I=1$ &#8594; <b>B</b>, &nbsp; &nbsp; &nbsp; $W(I = 2) =$ <b>AB</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 $I=2$ &#8594; <b>AB</b>, &nbsp;&nbsp;&nbsp; $W(I = 3) =$ <b>BA</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 $I = 4$ ist nicht vorhanden &#8658; '''Sonderfallregelung''': <br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Man nimmt das letzte Decodierergebnis (hier <b>AB</b>) und fügt das erste Zeichen dieser Sequenz hinten an &#8658; <b>ABA</b>. <br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Danach wird <b>ABA</b> im Wörterbuch unter dem Index $I = 4$ abgelegt.
+:: $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 $I=3$ &#8594; <b>BA</b>. &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;  '''Ende der Decoder&ndash;Eingangsfolge'''.
+:: $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ß}}

@@ Zeile 3: / Zeile 3: @@
 }}
-[[Datei:P_ID2437__Inf_Z_2_4.png|right|frame|Momentaufnahmen von LZW–Wörterbüchern]]
+[[Datei:P_ID2437__Inf_Z_2_4.png|right|frame|Momentaufnahmen der LZW–Wörterbüchern]]
-Die Grafik zeigt Momentaufnahmen des Wörterbuchs, das während der LZW&ndash;Codierung der Eingangssymbolfolge entsteht.
+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 <b>ABABABBAA</b> entsteht.
+*Die obere Grafik gilt für Eingangssymbolfolge&nbsp; <b>ABABABBAA</b>.
-*Das untere Wörterbuch entsteht bei der LZW&ndash;Codierung der Sequenz <b>ABABABABA</b>.
+*Das untere Wörterbuch entsteht bei der LZW&ndash;Codierung der Sequenz&nbsp; <b>ABABABABA</b>.
-In beiden Fällen wird vorausgesetzt, dass auch zu späteren Zeitpunkten keine anderen Zeichen als <b>A</b> und <b>B</b> vorkommen können.
+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 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&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.
-Bei der LZW&ndash;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>B</b> und $I = 2$ zum Zeichenpaar <b>AB</b>.
+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.
 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 als beim Coder.
+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>.
 * 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$ 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&ndash;Wörterbuch.
+* 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 $(i- 1)$ das Decodierergebnis <b>ABBABA</b> war.
+* 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. Hier: <b>ABBABAA</b>.
+* 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 <b>ABBABAA</b> in das Wörterbuch unter dem Index $I$ ein.
+* Anschließend trägt man die Sequenz&nbsp; <b>ABBABAA</b>&nbsp; in das Wörterbuch unter dem Index&nbsp; $I$&nbsp; ein.
@@ Zeile 33: / Zeile 38: @@
 ''Hinweise:''
-*Die Aufgabe gehört zum  Kapitel [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch|Komprimierung nach Lempel, Ziv und Welch]].
+*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]] sowie
+:: [[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 $I = 0$ bis $I = M- 1$ alle $M$ zulässigen Zeichen des Alphabets.
+*Beachten Sie zudem bei der Lösung dieser Aufgabe, dass beim LZW&ndash;Algorithmus nicht von einem leeren Wörterbuch ausgegangen wird.
@@ Zeile 44: / Zeile 50: @@
 <quiz display=simple>
-{Codieren Sie die Eingangsfolge <b>ABABABBAA</b> entsprechend der oberen Grafik. <br>Welche Indizes $I_i$ ergeben sich zu den Schritten $i=1$, ... , $i=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="{}"}
 $I_1 \ = \ $ { 0. }
@@ Zeile 54: / Zeile 60: @@
-{Codieren Sie nun die Eingangsfolge <b>ABABABABA</b> entsprechend der unteren Grafik. <br>Geben Sie die Indizes $I_i$ zu den Schritten $i=4$ und $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="{}"}
 $I_4 \ = \ $ { 4 }
@@ Zeile 60: / Zeile 66: @@
-{Für welchen Schritt $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="{}"}
 $\text{Codierung:} \ \ i \ = \ $ { 4 }
@@ Zeile 68: / Zeile 74: @@
 {Wann muss man auf die Decodier&ndash;Sonderfallregelung zurückgreifen?
 |type="[]"}
-- Bei der Decodierung von <b>ABABABBAA</b> im Schritt $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 = 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 = 5$.
+- Bei der Decodierung von&nbsp; <b>ABABABABA</b>&nbsp; im Schritt&nbsp; $i = 5$.

@@ Zeile 118: / Zeile 118: @@
 Dann gilt mit dem Wörterbuch&ndash;Array $W(I)$:
 * $i = 1$: &nbsp; &nbsp; Decodierung $I=0$ &#8594; <b>A</b>,
-* $i = 2$: &nbsp; &nbsp; Decodierung $I=1$ &#8594; <b>B</b>, &nbsp;&nbsp;&nbsp; $W(I = 2) =$ <b>AB</b>,
+* $i = 2$: &nbsp; &nbsp; Decodierung $I=1$ &#8594; <b>B</b>, &nbsp; &nbsp; &nbsp; $W(I = 2) =$ <b>AB</b>,
 * $i = 3$: &nbsp; &nbsp; Decodierung $I=2$ &#8594; <b>AB</b>, &nbsp;&nbsp;&nbsp; $W(I = 3) =$ <b>BA</b>,
-* $i = 4$: &nbsp; &nbsp; Ein Eintrag mit dem Index $I = 4$ ist nicht vorhanden &#8658; '''Sonderfallregelung''': <br>Man nimmt das letzte Decodierergebnis (hier <b>AB</b>) und fügt das erste Zeichen dieser Sequenz hinten an &#8658; <b>ABA</b>. <br>Danach wird <b>ABA</b> im Wörterbuch unter dem Index $I = 4$ abgelegt.
+* $i = 4$: &nbsp; &nbsp; Ein Eintrag mit dem Index $I = 4$ ist nicht vorhanden &#8658; '''Sonderfallregelung''': <br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Man nimmt das letzte Decodierergebnis (hier <b>AB</b>) und fügt das erste Zeichen dieser Sequenz hinten an &#8658; <b>ABA</b>. <br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Danach wird <b>ABA</b> im Wörterbuch unter dem Index $I = 4$ abgelegt.
-* $i = 5$: &nbsp; &nbsp; Decodierung $I=3$ &#8594; <b>BA</b>. '''Ende der Decoder&ndash;Eingangsfolge'''.
+* $i = 5$: &nbsp; &nbsp; Decodierung $I=3$ &#8594; <b>BA</b>. &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;  '''Ende der Decoder&ndash;Eingangsfolge'''.
 {{ML-Fuß}}

@@ Zeile 78: / Zeile 78: @@
 ===Musterlösung===
 {{ML-Kopf}}
-'''(1)'''&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 $W(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 = 1$: &nbsp; &nbsp; <b>A</b> &nbsp;&nbsp;&nbsp;&#8594;&nbsp;&nbsp; $\underline{I=0}$, &nbsp; $W(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 = 2$: &nbsp; &nbsp; <b>B</b> &nbsp;&nbsp;&nbsp;&#8594;&nbsp;&nbsp; $\underline{I=1}$, &nbsp; $W(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 = 3$: &nbsp; &nbsp; <b>AB</b> &#8594;&nbsp;&nbsp; $\underline{I=2}$, &nbsp; $W(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 = 4$: &nbsp; &nbsp; <b>AB</b> &#8594;&nbsp;&nbsp; $\underline{I=2}$, &nbsp; $W(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>.
+* $i = 5$: &nbsp; &nbsp; <b>BA</b> &#8594;&nbsp;&nbsp; $\underline{I=3}$, &nbsp; $W(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.
+Es ist anzumerken, dass das letzte Zeichen (<b>A</b>) des Eingabestrings <b>ABABABBAA</b> zum Zeitpunkt $i = 5$ zwar bereits beim Wörterbucheintrag berücksichtigt ist, aber noch nicht codiert wurde.
 '''(4)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 2</u>:
-*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.
+*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 &#8594; Zeichenfolge nicht, da das generierte Wörterbuch zum Zeitpunkt <i>i&nbsp;</i> nur Einträge mit Indizes <i>I&nbsp;</i> < <i>i&nbsp;</i> enthält.
+*Bei der Decodierung findet er dann die erforderliche Zuordnung Index &#8594; Zeichenfolge nicht, da das generierte Wörterbuch zum Zeitpunkt $i$ nur Einträge mit Indizes $I < i$ enthält.
-*Für die Folge <b>ABABABBAA</b> gilt entsprechend Teilaufgabe (1) stets <i>I&nbsp;</i> < <i>i&nbsp;</i>. Dagegen ergäbe sich bei der Folge <b>ABABABABA</b> folgende Indizes:
+*Für die Folge <b>ABABABBAA</b> gilt entsprechend Teilaufgabe '''(1)''' stets $I < i$.
-:$$i = 1\hspace{-0.15cm}: I = 0\hspace{0.05cm},
+*Dagegen ergäbe sich bei der Folge <b>ABABABABA</b> folgende Indizes:
-\hspace{0.2cm}i = 2\hspace{-0.15cm}: I = 1\hspace{0.05cm},
+:$$i = 1\hspace{-0.15cm}: \hspace{0.15cm} I = 0\hspace{0.05cm},
-\hspace{0.2cm}i = 3\hspace{-0.15cm}: I = 2\hspace{0.05cm},
+\hspace{0.5cm}i = 2\hspace{-0.15cm}: \hspace{0.15cm}I = 1\hspace{0.05cm},
-\hspace{0.2cm}\underline{i = 4\hspace{-0.15cm}: I = 4}\hspace{0.05cm},
+\hspace{0.5cm}i = 3\hspace{-0.15cm}: \hspace{0.15cm}I = 2\hspace{0.05cm},
-\hspace{0.2cm}i = 5\hspace{-0.15cm}: I = 3\hspace{0.05cm}.  $$
+\hspace{0.5cm}\underline{i = 4\hspace{-0.15cm}: \hspace{0.15cm}I = 4}\hspace{0.05cm},
-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&nbsp;</i>):
+Dann gilt mit dem Wörterbuch&ndash;Array $W(I)$:
-* <i>i</i> = 1: Decodierung <i>I</i> = 0 &#8594; <b>A</b>,
+* $i = 1$: &nbsp; &nbsp; Decodierung $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 = 2$: &nbsp; &nbsp; Decodierung $I=1$ &#8594; <b>B</b>, &nbsp;&nbsp;&nbsp; $W(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 = 3$: &nbsp; &nbsp; Decodierung $I=2$ &#8594; <b>AB</b>, &nbsp;&nbsp;&nbsp; $W(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 = 4$: &nbsp; &nbsp; Ein Eintrag mit dem Index $I = 4$ ist nicht vorhanden &#8658; '''Sonderfallregelung''': <br>Man nimmt das letzte Decodierergebnis (hier <b>AB</b>) und fügt das erste Zeichen dieser Sequenz hinten an &#8658; <b>ABA</b>. <br>Danach wird <b>ABA</b> im Wörterbuch unter dem Index $I = 4$ abgelegt.
-* <i>i</i> = 5: Decodierung <i>I</i> = 3 &#8594; <b>BA</b>. Ende der Decodereingangsfolge.
+* $i = 5$: &nbsp; &nbsp; Decodierung $I=3$ &#8594; <b>BA</b>. '''Ende der Decoder&ndash;Eingangsfolge'''.
 {{ML-Fuß}}

@@ Zeile 44: / Zeile 44: @@
 <quiz display=simple>
-{Codieren Sie die Eingangsfolge <b>ABABABBAA</b>. Welche Indizes <i>I<sub>i</sub>&nbsp;</i> ergeben sich zu den Schritten <i>i</i> = 1, ... , 5?
+{Codieren Sie die Eingangsfolge <b>ABABABBAA</b> entsprechend der oberen Grafik. <br>Welche Indizes $I_i$ ergeben sich zu den Schritten $i=1$, ... , $i=5$?
 |type="{}"}
-$i = 1\text{:}\ \ I_1 \ = $ { 0. }
+$I_1 \ = \ $ { 0. }
-$i = 2\text{:}\ \ I_2 \ = $ { 1 }
+$I_2 \ = \  $ { 1 }
-$i = 3\text{:}\ \ I_3 \ = $ { 2 }
+$I_3 \ = \  $ { 2 }
-$i = 4\text{:}\ \ I_4 \ = $ { 2 }
+$I_4 \ = \  $ { 2 }
-$i = 5\text{:}\ \ I_5 \ = $ { 3 }
+$I_5 \ = \  $ { 3 }
-{Codieren Sie nun die Eingangsfolge <b>ABABABABA</b>. Geben Sie die Indizes <i>I<sub>i</sub>&nbsp;</i> zu den Schritten <i>i</i> = 4 und <i>i</i> = 5 an.
+{Codieren Sie nun die Eingangsfolge <b>ABABABABA</b> entsprechend der unteren Grafik. <br>Geben Sie die Indizes $I_i$ zu den Schritten $i=4$ und $i=5$ an.
 |type="{}"}
-$i = 4\text{:}\ \ I_4 \ = $ { 4 }
+$I_4 \ = \ $ { 4 }
-$i = 5\text{:}\ \ I_5 \ = $ { 3 }
+$I_5 \ = \ $ { 3 }
-{Für welchen Schritt <i>i&nbsp;</i> gilt die Momentaufnahme des auf der Angabenseite dargestellten Wörterbuchs bezüglich
+{Für welchen Schritt $i$ gilt die Momentaufnahme des auf der Angabenseite dargestellten Wörterbuchs bezüglich
 |type="{}"}
-$\text{Codierung:} \ \ i \ = $ { 4 }
+$\text{Codierung:} \ \ i \ = \ $ { 4 }
-$\text{Decodierung:} \ \ i \ = $ { 5 }
+$\text{Decodierung:} \ \ i \ = \ $ { 5 }
 {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>ABABABBAA</b> im Schritt $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 = 4$.
-- Bei der Decodierung von <b>ABABABABA</b> im Schritt <i>i</i> = 5.
+- Bei der Decodierung von <b>ABABABABA</b> im Schritt $i = 5$.

@@ Zeile 27: / Zeile 27: @@
 *Die Aufgabe gehört zum  Kapitel [[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#Der_Lempel.E2.80.93Ziv.E2.80.93Welch.E2.80.93Algorithmus|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]] sowie [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch#Decodierung_des_LZW.E2.80.93Algorithmus|Decodierung des LZW-Agorithmus]].
-*Sollte die Eingabe des Zahlenwertes &bdquo;0&rdquo; erforderlich sein, so geben Sie bitte &bdquo;0.&rdquo; ein.
 *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 des Alphabets.

← Nächstältere Version	Version vom 3. Januar 2018, 13:58 Uhr
(kein Unterschied)