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

Maintenance script: Add English interlanguage link

2026-03-16T12:35:41Z

Add English interlanguage link

← Nächstältere Version		Version vom 16. März 2026, 14:35 Uhr
Zeile 133:		Zeile 133:

	[[Category:Aufgaben zu Informationstheorie\|^2.2 Verfahren von Lempel, Ziv, Welch^]]		[[Category:Aufgaben zu Informationstheorie\|^2.2 Verfahren von Lempel, Ziv, Welch^]]
			[[en:Aufgaben:Exercise_2.4Z:_LZW_Coding_and_Decoding_again]]

Maintenance script: Fix 1 split formula(s) (join $$...$$ across lines)

2026-02-27T13:59:35Z

Fix 1 split formula(s) (join $$...$$ across lines)

← Nächstältere Version		Version vom 27. Februar 2026, 15:59 Uhr
Zeile 116:		Zeile 116:
	*Für die Folge  <b>ABABABBAA</b>  gilt entsprechend der Teilaufgabe  '''(1)'''  stets  $I < i$.		*Für die Folge  <b>ABABABBAA</b>  gilt entsprechend der Teilaufgabe  '''(1)'''  stets  $I < i$.
	*Dagegen ergäbe sich für die Folge  <b>ABABABABA</b>  folgende Indizes:		*Dagegen ergäbe sich für die Folge  <b>ABABABABA</b>  folgende Indizes:
	:$$i = 1\hspace{-0.15cm}: \hspace{0.15cm} I = 0\hspace{0.05cm},		:$$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}. $$
	\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  <b>ABABABABA</b>:		Hier noch zusammenfassend die gesamte Decodierung von  <b>ABABABABA</b>:

Guenter am 17. Juli 2021 um 12:22 Uhr

2021-07-17T12:22:22Z

← Nächstältere Version		Version vom 17. Juli 2021, 14:22 Uhr
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  <u>LZW–Codierung</u>  der Eingangssymbolfolge entsteht.		Die Grafik zeigt Momentaufnahmen des Wörterbuchs, das während der  <u>LZW–Codierung</u>  der Eingangssymbolfolge entsteht:
	*Die obere Grafik gilt für Eingangssymbolfolge  <b>ABABABBAA</b>.		*Die obere Grafik gilt für Eingangssymbolfolge  <b>ABABABBAA</b>.
	*Das untere Wörterbuch entsteht bei der LZW–Codierung der Sequenz  <b>ABABABABA</b>.		*Das untere Wörterbuch entsteht bei der LZW–Codierung der Sequenz  <b>ABABABABA</b>.
Zeile 11:		Zeile 11:
	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  <b>A</b>  und  <b>B</b>  vorkommen können.

	Bei der  <u>LZW–Decodierung</u>  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  <u>LZW–Decodierung</u>  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. Decodierschritt die beiden dargestellten Momentaufnahmen gültig sind.


	Bei der <u>LZW–Codierung</u> wird zu jedem Codierschritt $i$ ein Index $I$ ausgewählt und (binär) übertragen.  Das Zeichenpaar <b>AB</b> 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 <u>LZW–Codierung</u> wird zu jedem Codierschritt  $i$  ein Index  $I$  ausgewählt und (binär) übertragen.  Das Zeichenpaar  <b>AB</b>  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 <u>LZW–Decodierung</u> 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–Decodierung</u> 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>.

	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 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.		* 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  <b>A</b>  oder  <b>B</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.		* Bei binärer Eingangsfolge  $($alle Zeichen seien  <b>A</b>  oder  <b>B</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.

Guenter am 23. Januar 2020 um 16:52 Uhr

2020-01-23T16:52:35Z

← Nächstältere Version		Version vom 23. Januar 2020, 18:52 Uhr
Zeile 84:		Zeile 84:
	===Musterlösung===		===Musterlösung===
	{{ML-Kopf}}		{{ML-Kopf}}
	'''(1)'''  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)'''  Wir bezeichnen mit  $W(I)$  ein Feld (Array), welches das Wörterbuch beschreibt und dessen Elemente Character oder Zeichenfolgen beinhalten.
	* $i = 1$:   ~~  <b>A</b>    →   $\underline{I=0}$,   $W(I = 2) =$ <b>AB</b>,~~
	* $i = 2$:     <b>B</b>    →   $\underline{I=1}$,   $W(I = 3) =$ <b>BA</b>,
	* $i = 3$:     <b>AB</b> →   $\underline{I=2}$,   $W(I = 4) =$ <b>ABA</b>,
	* $i = 4$:     <b>AB</b> →   $\underline{I=2}$,   $W(I = 5) =$ <b>ABB</b>,
	* $i = 5$:     <b>BA</b> →   $\underline{I=3}$,   $W(I = 6) =$ <b>BAA</b>.

			*Die Codierung von  <b>ABABABBAA</b>  läuft dann wie folgt ab:
			:: $i = 1$:     <b>A</b>    →   $\underline{I=0}$,   $W(I = 2) =$ <b>AB</b>,
			:: $i = 2$:     <b>B</b>    →   $\underline{I=1}$,   $W(I = 3) =$ <b>BA</b>,
			:: $i = 3$:     <b>AB</b> →   $\underline{I=2}$,   $W(I = 4) =$ <b>ABA</b>,
			:: $i = 4$:     <b>AB</b> →   $\underline{I=2}$,   $W(I = 5) =$ <b>ABB</b>,
			:: $i = 5$:     <b>BA</b> →   $\underline{I=3}$,   $W(I = 6) =$ <b>BAA</b>.

	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  $($<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.


	~~'''(2)'''  Für die Schritte $i = 1$ bis $i = 3$ ändert sich nichts gegenüber der Teilaufgabe '''(1)'''. Danach gilt:~~
	* $i = 4$:     <b>ABA</b> →   $\underline{I=4}$,   $W(I = 5) =$ <b>ABAB</b>,
	* $i = 5$:     <b>BA</b> →   $\underline{I=3}$,   Codierung abgeschlossen, kein neuer Wörterbucheintrag möglich.

			'''(2)'''  Für die Schritte  $i = 1$  bis  $i = 3$  ändert sich nichts gegenüber der Teilaufgabe  '''(1)'''.
			*Danach gilt:
			:: $i = 4$:     <b>ABA</b> →   $\underline{I=4}$,   $W(I = 5) =$ <b>ABAB</b>,
			:: $i = 5$:     <b>BA</b> →   $\underline{I=3}$,   Codierung abgeschlossen, kein neuer Wörterbucheintrag möglich.


	'''(3)'''  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:   $\underline{i=5}$.		'''(3)'''  Der Vergleich mit obigen Ergebnissen zeigt:
			*Das Wörterbuch des  <u>Coders</u>  weist genau nach  $\underline{i=4}$  Codierschritten die gezeigten Einträge auf.
			*Beim  <u>Decoder</u>  ergibt sich demgegenüber eine Zeitverzögerung um einen Schritt:   $\underline{i=5}$.




	'''(4)'''  Richtig ist der <u>Lösungsvorschlag 2</u>:		'''(4)'''  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  (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.		*Bei der Decodierung findet er dann die erforderliche Zuordnung  &bdquo;Index  →  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$.		*Für die Folge  <b>ABABABBAA</b>  gilt entsprechend der Teilaufgabe  '''(1)'''  stets  $I < i$.
	*Dagegen ergäbe sich ~~bei der~~ Folge <b>ABABABABA</b> folgende Indizes:		*Dagegen ergäbe sich für die Folge  <b>ABABABABA</b>  folgende Indizes:
	:$$i = 1\hspace{-0.15cm}: \hspace{0.15cm} I = 0\hspace{0.05cm},		:$$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 = 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}. $$		\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>:

	~~Hier noch zusammenfassend die gesamte Decodierung von <b>ABABABABA</b>:~~		*Die Vorbelegung des Wörterbuchs beinhaltet  $(I=0$:  <b>A</b>$)$     und  $(I=1$:  <b>B</b>$)$.

	Die Vorbelegung des Wörterbuchs beinhaltet $I=0$: <b>A</b>     und ~~ ~~   $I=1$: <b>B</b>.

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

Guenter am 23. Januar 2020 um 16:29 Uhr

2020-01-23T16:29:01Z

← Nächstältere Version		Version vom 23. Januar 2020, 18:29 Uhr
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–Codierung der Eingangssymbolfolge entsteht.		Die Grafik zeigt Momentaufnahmen des Wörterbuchs, das während der  <u>LZW–Codierung</u>  der Eingangssymbolfolge entsteht.
	*Die obere Grafik gilt für Eingangssymbolfolge <b>ABABABBAA</b> ~~entsteht~~.		*Die obere Grafik gilt für Eingangssymbolfolge  <b>ABABABBAA</b>.
	*Das untere Wörterbuch entsteht bei der LZW–Codierung der Sequenz <b>ABABABABA</b>.		*Das untere Wörterbuch entsteht bei der LZW–Codierung der Sequenz  <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  <b>A</b>  und  <b>B</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  <u>LZW–Decodierung</u>  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 <b>AB</b> 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>B</b> ~~und~~ $I = 2$ ~~zum Zeichenpaar <b>AB</b>~~.		Bei der <u>LZW–Codierung</u> wird zu jedem Codierschritt $i$ ein Index $I$ ausgewählt und (binär) übertragen.  Das Zeichenpaar <b>AB</b> 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.

	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–Decodierung</u> 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 binärer Eingangsfolge (alle Zeichen seien <b>A</b> oder <b>B</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.
			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  <b>A</b>  oder  <b>B</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:		Diese Sonderregelung soll an einem Beispiel veranschaulicht werden:
	* Zum Schritt $i$ gibt es keinen zum Index $I$ passenden Eintrag im Decoder–Wörterbuch.		* 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 <b>ABBABA</b> war.		* Wir nehmen an, dass beim vorherigen Schritt  $(i- 1)$  das Decodierergebnis  <b>ABBABA</b>  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.  Hier:  <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  <b>ABBABAA</b>  in das Wörterbuch unter dem Index  $I$  ein.





Zeile 33:		Zeile 38:

	''Hinweise:''		''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  [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch\|Komprimierung nach Lempel, Ziv und Welch]].
	*Insbesondere wird Bezug genommen auf die Seiten		*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 – die Grundform der Lempel-Ziv-Algorithmen]],		:: [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch#LZ77_.E2.80.93_die_Grundform_der_Lempel.E2.80.93Ziv.E2.80.93Algorithmen\|LZ77 – 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]].		:: [[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–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–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.


Zeile 44:		Zeile 50:

	<quiz display=simple>		<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  <b>ABABABBAA</b>  entsprechend der <u>oberen Grafik</u>.  Welche Indizes  $I_i$  ergeben sich zu den Schritten  $i=1$, ... , $i=5$?
	\|type="{}"}		\|type="{}"}
	$I_1 \ = \ $ { 0. }		$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  <b>ABABABABA</b>  entsprechend der <u>unteren Grafik</u>.  Geben Sie die Indizes  $I_i$  zu den Schritten  $i=4$  und  $i=5$  an.
	\|type="{}"}		\|type="{}"}
	$I_4 \ = \ $ { 4 }		$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  $i$  gilt die Momentaufnahme des auf der Angabenseite dargestellten Wörterbuchs bezüglich
	\|type="{}"}		\|type="{}"}
	$\text{Codierung:} \ \ i \ = \ $ { 4 }		$\text{Codierung:} \ \ i \ = \ $ { 4 }
Zeile 68:		Zeile 74:
	{Wann muss man auf die Decodier–Sonderfallregelung zurückgreifen?		{Wann muss man auf die Decodier–Sonderfallregelung zurückgreifen?
	\|type="[]"}		\|type="[]"}
	- Bei der Decodierung von <b>ABABABBAA</b> im Schritt $i = 4$.		- Bei der Decodierung von  <b>ABABABBAA</b>  im Schritt  $i = 4$.
	+ Bei der Decodierung von <b>ABABABABA</b> im Schritt $i = 4$.		+ Bei der Decodierung von  <b>ABABABABA</b>  im Schritt  $i = 4$.
	- Bei der Decodierung von <b>ABABABABA</b> im Schritt $i = 5$.		- Bei der Decodierung von  <b>ABABABABA</b>  im Schritt  $i = 5$.

Guenter am 24. September 2018 um 16:29 Uhr

2018-09-24T16:29:00Z

← Nächstältere Version		Version vom 24. September 2018, 18:29 Uhr
Zeile 118:		Zeile 118:
	Dann gilt mit dem Wörterbuch–Array $W(I)$:		Dann gilt mit dem Wörterbuch–Array $W(I)$:
	* $i = 1$:     Decodierung $I=0$ → <b>A</b>,		* $i = 1$:     Decodierung $I=0$ → <b>A</b>,
	* $i = 2$:     Decodierung $I=1$ → <b>B</b>,     $W(I = 2) =$ <b>AB</b>,		* $i = 2$:     Decodierung $I=1$ → <b>B</b>,       $W(I = 2) =$ <b>AB</b>,
	* $i = 3$:     Decodierung $I=2$ → <b>AB</b>,     $W(I = 3) =$ <b>BA</b>,		* $i = 3$:     Decodierung $I=2$ → <b>AB</b>,     $W(I = 3) =$ <b>BA</b>,
	* $i = 4$:     Ein Eintrag mit dem Index $I = 4$ ist nicht vorhanden ⇒ '''Sonderfallregelung''': <br>Man nimmt das letzte Decodierergebnis (hier <b>AB</b>) und fügt das erste Zeichen dieser Sequenz hinten an ⇒ <b>ABA</b>. <br>Danach wird <b>ABA</b> im Wörterbuch unter dem Index $I = 4$ abgelegt.		* $i = 4$:     Ein Eintrag mit dem Index $I = 4$ ist nicht vorhanden ⇒ '''Sonderfallregelung''': <br>                  Man nimmt das letzte Decodierergebnis (hier <b>AB</b>) und fügt das erste Zeichen dieser Sequenz hinten an ⇒ <b>ABA</b>. <br>                  Danach wird <b>ABA</b> im Wörterbuch unter dem Index $I = 4$ abgelegt.
	* $i = 5$:     Decodierung $I=3$ → <b>BA</b>. '''Ende der Decoder–Eingangsfolge'''.		* $i = 5$:     Decodierung $I=3$ → <b>BA</b>.             '''Ende der Decoder–Eingangsfolge'''.
	{{ML-Fuß}}		{{ML-Fuß}}

Guenter am 24. September 2018 um 16:23 Uhr

2018-09-24T16:23:50Z

← Nächstältere Version		Version vom 24. September 2018, 18:23 Uhr
Zeile 78:		Zeile 78:
	===Musterlösung===		===Musterlösung===
	{{ML-Kopf}}		{{ML-Kopf}}
	'''(1)'''  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)'''  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>    →   ~~<u><i>~~I~~</i>~~ = 0~~</u>~~, ~~<i>~~W~~</i>~~(~~<i>~~I~~</i>~~ = 2) = <b>AB</b>,		* $i = 1$:     <b>A</b>    →   $\underline{I=0}$,   $W(I = 2) =$ <b>AB</b>,
	* ~~<i>~~i~~</i>~~ = 2: <b>B</b>    →   ~~<u><i>~~I~~</i>~~ = 1~~</u>~~, ~~<i>~~W~~</i>~~(~~<i>~~I~~</i>~~ = 3) = <b>BA</b>,		* $i = 2$:     <b>B</b>    →   $\underline{I=1}$,   $W(I = 3) =$ <b>BA</b>,
	* ~~<i>~~i~~</i>~~ = 3: <b>AB</b> →   ~~<u><i>~~I~~</i>~~ = 2~~</u>~~, ~~<i>~~W~~</i>~~(~~<i>~~I~~</i>~~ = 4) = <b>ABA</b>,		* $i = 3$:     <b>AB</b> →   $\underline{I=2}$,   $W(I = 4) =$ <b>ABA</b>,
	* ~~<i>~~i~~</i>~~ = 4: <b>AB</b> →   ~~<u><i>~~I~~</i>~~ = 2~~</u>~~, ~~<i>~~W~~</i>~~(~~<i>~~I~~</i>~~ = 5) = <b>ABB</b>,		* $i = 4$:     <b>AB</b> →   $\underline{I=2}$,   $W(I = 5) =$ <b>ABB</b>,
	* ~~<i>~~i~~</i>~~ = 5: <b>BA</b> →   ~~<u><i>~~I~~</i>~~ = 3~~</u>~~, ~~<i>~~W~~</i>~~(~~<i>~~I~~</i>~~ = 6) = <b>BAA</b>.		* $i = 5$:     <b>BA</b> →   $\underline{I=3}$,   $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.

	~~'''(2)'''  Für die Schritte <i>i</i> = 1 bis <i>i</i> = 3 ändert sich nichts gegenüber der Teilaufgabe (1). Danach gilt:~~
	* <i>i</i> = 4: <b>ABA</b> →   <u><i>I</i> = 4</u>, Wörterbuch (<i>I</i> = 5) = <b>ABAB</b>,
	* <i>i</i> = 5: <b>BA</b>    →   <u><i>I</i> = 3</u>, Codierung abgeschlossen, kein neuer Wörterbucheintrag möglich.

			'''(2)'''  Für die Schritte $i = 1$ bis $i = 3$ ändert sich nichts gegenüber der Teilaufgabe '''(1)'''. Danach gilt:
			* $i = 4$:     <b>ABA</b> →   $\underline{I=4}$,   $W(I = 5) =$ <b>ABAB</b>,
			* $i = 5$:     <b>BA</b> →   $\underline{I=3}$,   Codierung abgeschlossen, kein neuer Wörterbucheintrag möglich.



			'''(3)'''  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:   $\underline{i=5}$.

	'''(3)'''  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>.


	'''(4)'''  Richtig ist der <u>Lösungsvorschlag 2</u>:		'''(4)'''  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 → 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.		*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 <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:		*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},
			\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 $I=0$: <b>A</b>     und     $I=1$: <b>B</b>.

	~~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–Array ~~<i>~~W~~</i>~~(~~<i>~~I~~ </i>~~):		Dann gilt mit dem Wörterbuch–Array $W(I)$:
	* ~~<i>i</~~i> = 1: Decodierung ~~<i>~~I~~</i>~~ = 0 → <b>A</b>,		* $i = 1$:     Decodierung $I=0$ → <b>A</b>,
	* ~~<i>i</~~i> = 2: Decodierung ~~<i>~~I~~</i>~~ = 1 → <b>B</b>,    ~~<i>~~W~~</i>~~(~~<i>~~I~~</i>~~ = 2) = <b>AB</b>,		* $i = 2$:     Decodierung $I=1$ → <b>B</b>,     $W(I = 2) =$ <b>AB</b>,
	* ~~<i>i</~~i> = 3: Decodierung ~~<i>~~I~~</i>~~ = 2 → <b>AB</b>, ~~<i>~~W~~</i>~~(~~<i>~~I~~</i>~~ = 3) = <b>BA</b>,		* $i = 3$:     Decodierung $I=2$ → <b>AB</b>,     $W(I = 3) =$ <b>BA</b>,
	* <i~~>i</i>~~ = 4: Ein Eintrag mit dem Index ~~<i>~~I~~</i>~~ = 4 ist nicht vorhanden ⇒ Sonderfallregelung. Man nimmt das letzte Decodierergebnis (hier <b>AB</b>) und fügt das erste Zeichen dieser Sequenz hinten an ⇒ <b>ABA</b>. Danach wird <b>ABA</b> im Wörterbuch unter dem Index ~~<i>~~I~~</i>~~ = 4 abgelegt.		* $i = 4$:     Ein Eintrag mit dem Index $I = 4$ ist nicht vorhanden ⇒ '''Sonderfallregelung''': <br>Man nimmt das letzte Decodierergebnis (hier <b>AB</b>) und fügt das erste Zeichen dieser Sequenz hinten an ⇒ <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 → <b>BA</b>. Ende der ~~Decodereingangsfolge~~.		* $i = 5$:     Decodierung $I=3$ → <b>BA</b>. '''Ende der Decoder–Eingangsfolge'''.
	{{ML-Fuß}}		{{ML-Fuß}}

Guenter am 24. September 2018 um 15:51 Uhr

2018-09-24T15:51:13Z

← Nächstältere Version		Version vom 24. September 2018, 17:51 Uhr
Zeile 44:		Zeile 44:

	<quiz display=simple>		<quiz display=simple>
	{Codieren Sie die Eingangsfolge <b>ABABABBAA</b>. Welche Indizes ~~<i>I<sub>i</sub> </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="{}"}		\|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> </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="{}"}		\|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 </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="{}"}		\|type="{}"}
	$\text{Codierung:} \ \ i \ = $ { 4 }		$\text{Codierung:} \ \ i \ = \ $ { 4 }
	$\text{Decodierung:} \ \ i \ = $ { 5 }		$\text{Decodierung:} \ \ i \ = \ $ { 5 }


	{Wann muss man auf die Decodier–Sonderfallregelung zurückgreifen?		{Wann muss man auf die Decodier–Sonderfallregelung zurückgreifen?
	\|type="[]"}		\|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$.

Guenter am 24. September 2018 um 15:43 Uhr

2018-09-24T15:43:15Z

← Nächstältere Version		Version vom 24. September 2018, 17:43 Uhr
Zeile 3:		Zeile 3:
	}}		}}

	[[Datei:P_ID2437__Inf_Z_2_4.png\|right\|Momentaufnahmen von LZW–Wörterbüchern]]		[[Datei:P_ID2437__Inf_Z_2_4.png\|right\|frame\|Momentaufnahmen von LZW–Wörterbüchern]]
	Die ~~obere~~ Grafik zeigt ~~eine Momentaufnahme~~ des Wörterbuchs, das während der LZW–Codierung der Eingangssymbolfolge <b>ABABABBAA</b> entsteht. Das untere Wörterbuch entsteht bei der LZW–Codierung der Sequenz <b>ABABABABA</b>~~. In beiden Fällen wird vorausgesetzt, dass auch zu späteren Zeitpunkten keine andere Zeichen als <b>A</b> und <b>B</b> vorkommen können~~.		Die Grafik zeigt Momentaufnahmen des Wörterbuchs, das während der LZW–Codierung der Eingangssymbolfolge entsteht.
			*Die obere Grafik gilt für Eingangssymbolfolge <b>ABABABBAA</b> entsteht.
			*Das untere Wörterbuch entsteht bei der LZW–Codierung der Sequenz <b>ABABABABA</b>.

	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>~~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 <b>A</b> und <b>B</b> vorkommen können.

	Bei der LZW–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 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.

	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:		Bei der LZW–Codierung wird zu jedem Codierschritt $i$ ein Index $I$ ausgewählt und (binär) übertragen. Das Zeichenpaar <b>AB</b> 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.
	* 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–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.		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>B</b> und $I = 2$ zum Zeichenpaar <b>AB</b>.

			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 binärer Eingangsfolge (alle Zeichen seien <b>A</b> oder <b>B</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:		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–Wörterbuch.		* 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>i</~~i~~> –~~ 1) <b>ABBABA</b> war.		* Wir nehmen an, dass beim vorherigen Schritt $(i- 1)$ das Decodierergebnis <b>ABBABA</b> 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. 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.		* Anschließend trägt man die Sequenz <b>ABBABAA</b> in das Wörterbuch unter dem Index $I$ ein.





	''Hinweise:''		''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 [[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 – 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]].		*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 – die Grundform der Lempel-Ziv-Algorithmen]],
	*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>~~I~~</i>~~ = 0 bis ~~<i>~~I~~</i>~~ = ~~<i>~~M~~</i> –~~ 1 alle ~~<i>~~M~~</i>~~ zulässigen Zeichen des Alphabets.		:: [[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]].
			*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.

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 „ “

← Nächstältere Version		Version vom 29. Mai 2018, 14:02 Uhr
Zeile 27:		Zeile 27:
	*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 [[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 – 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]].		*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 – 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” erforderlich sein, so geben Sie bitte &bdquo;0.” ein.
	*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>I</i> = 0 bis <i>I</i> = <i>M</i> – 1 alle <i>M</i> zulässigen Zeichen des Alphabets.		*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>I</i> = 0 bis <i>I</i> = <i>M</i> – 1 alle <i>M</i> zulässigen Zeichen des Alphabets.