Aufgaben:Aufgabe 2.3: Zur LZ78-Komprimierung - Versionsgeschichte

Guenter am 12. Juli 2021 um 13:28 Uhr

2021-07-12T13:28:45Z

Guenter am 12. Juli 2021 um 13:23 Uhr

2021-07-12T13:23:20Z

Guenter am 23. Januar 2020 um 14:33 Uhr

2020-01-23T14:33:07Z

Guenter am 23. Januar 2020 um 14:22 Uhr

2020-01-23T14:22:13Z

Guenter am 23. Januar 2020 um 14:20 Uhr

2020-01-23T14:20:18Z

Guenter am 24. September 2018 um 12:17 Uhr

2018-09-24T12:17:20Z

Guenter am 24. September 2018 um 11:48 Uhr

2018-09-24T11:48:52Z

Änderungen zeigen

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

2018-05-29T12:02:43Z

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

Guenter: Guenter verschob die Seite Aufgaben:2.3 Zur LZ78-Komprimierung nach Aufgaben:Aufgabe 2.3: Zur LZ78-Komprimierung

2018-01-03T13:57:33Z

Guenter verschob die Seite 2.3 Zur LZ78-Komprimierung nach Aufgabe 2.3: Zur LZ78-Komprimierung

Guenter am 18. Mai 2017 um 11:53 Uhr

2017-05-18T11:53:05Z

@@ Zeile 109: / Zeile 109: @@
-[[Datei:Inf_A_2_3f_version2.png|right|frame|LZ78–Codierung von&nbsp; <b>BARBARA–BAR</b>]]
+[[Datei:Inf_A_2_3f_version2.png|right|frame|LZ78–Codierung des Strings&nbsp; <b>BARBARA–BAR</b>]]
 '''(5)'''&nbsp; Der gesamte Codiervorgang ist in einer Tabelle zusammengefasst. Man erkennt:
 * Zu jedem Zeitpunkt&nbsp; $i$&nbsp; wird die bearbeitete Zeichenfolge in das Wörterbuch eingetragen.

@@ Zeile 4: / Zeile 4: @@
 [[Datei:P_ID2434__Inf_A_2_3.png|right|frame|Die LZ78&ndash;Erfinder]]
-Im Gegensatz zur Entropiecodierung nach Huffman oder nach Shannon, bei der man die Quellenstatistik (möglichst genau) kennen muss, sind solche Einschränkungen bei den von&nbsp; [https://de.wikipedia.org/wiki/Abraham_Lempel Abraham Lempel]&nbsp; und&nbsp; [https://de.wikipedia.org/wiki/Jacob_Ziv Jacob Ziv]&nbsp; entwickelten Komprimierungsverfahren nicht gegeben.&nbsp; Man spricht von ''universeller Quellencodierung''.
+Im Gegensatz zur Entropiecodierung nach Huffman oder nach Shannon, bei der man die Quellenstatistik (möglichst genau) kennen muss, sind solche Einschränkungen bei den von&nbsp; [https://de.wikipedia.org/wiki/Abraham_Lempel Abraham Lempel]&nbsp; und&nbsp; [https://de.wikipedia.org/wiki/Jacob_Ziv Jacob Ziv]&nbsp; entwickelten Komprimierungsverfahren nicht gegeben.&nbsp; Man spricht von&nbsp; '''universeller Quellencodierung'''.
-Wir betrachten in dieser Aufgabe die 1978 erstmals veröffentlichte Variante&nbsp; [LZ78].&nbsp;  Codiert werden soll der String &nbsp;<b>BARBARA&ndash;BAR</b>.
+Wir betrachten in dieser Aufgabe die 1978 erstmals veröffentlichte Variante&nbsp; ['''LZ78'''].&nbsp;  Codiert werden soll der String &nbsp;<b>BARBARA&ndash;BAR</b>.
 *Das Verfahren LZ78 arbeitet mit einem globalen Wörterbuch, das zu Beginn nur mit einem leeren Zeichen&nbsp; $(\varepsilon)$&nbsp; unter dem Index&nbsp; $I = 0$&nbsp; gefüllt ist.&nbsp; Dadurch unterscheidet sich &bdquo;LZ78&rdquo; von seinem Vorgänger &bdquo;LZ77&rdquo; (mit lokalem Wörterbuch) und auch von seinem Nachfolger &bdquo;LZW&rdquo; (Wörterbuch ist mit den möglichen Zeichen vorbelegt).
 *Wird ein Zeichen oder ein Wortfragment (mehrere Zeichen) des Eingabestrings im Wörterbuch gefunden, so wird der Index&nbsp; $I_0$&nbsp; dieses Eintrags zusammen mit dem nächsten Eingangszeichen&nbsp; $Z$&nbsp; ausgegeben.&nbsp; In jedem Schritt&nbsp; $i$&nbsp; lautet also die Ausgabe: &nbsp;  $(I_0, \ Z)$.
@@ Zeile 15: / Zeile 15: @@
 Zur Verdeutlichung ein einfaches Beispiel:
 *Zu einem gegebenen Zeitpunkt ist das Wörterbuch bis zum Index&nbsp; $I_{\rm akt }= 20$&nbsp; gefüllt.
-*Zur Codierung steht&nbsp; '''Handy'''&nbsp; an.&nbsp; Im Wörterbuch findet man unter dem Index&nbsp; $I = 11$&nbsp; den Eintrag&nbsp; <b>Ha</b>&nbsp; und unter dem Index&nbsp; $I = 16$&nbsp; den Eintrag <b>Han</b>.
+*Zur Codierung steht&nbsp; '''Handy'''&nbsp; an.&nbsp; Im Wörterbuch findet man unter dem Index&nbsp; $I = 11$&nbsp; den Eintrag&nbsp; "<b>Ha</b>"&nbsp; und unter dem Index&nbsp; $I = 16$&nbsp; den Eintrag "<b>Han</b>".
-*Somit lautet die aktuelle Coderausgabe &nbsp;  $(I_0,  Z) = (16,$ <b>d</b>$)$&nbsp; und ins Wörterbuch wird als neue Phrase eingetragen: &nbsp; $W(21) =$ <b>Hand</b>.
+*Somit lautet die aktuelle Coderausgabe &nbsp;  $(I_0,  Z) = (16,$ <b>d</b>$)$&nbsp; und ins Wörterbuch wird als neue Phrase eingetragen:
-*Nun liegt der String&nbsp; <b>y</b>&nbsp; zur Codierung an.&nbsp; Findet man hierfür keinen passenden Eintrag, so wird&nbsp; $(0,$ <b>y</b>$)$&nbsp; ausgegeben und ins Wörterbuch wird neu eingetragen: &nbsp; $W(22) = $ $\rm &epsilon;$&nbsp; +  <b>y</b> $=$ <b>y</b> .
+&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;  $W(21) =$ <b>Hand</b>.
@@ Zeile 33: / Zeile 36: @@
 *Die Aufgabe gehört zum  Kapitel&nbsp; [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch|Komprimierung nach Lempel, Ziv und Welch]].
 *Insbesondere wird auf die Seite&nbsp; [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch#Die_Lempel.E2.80.93Ziv.E2.80.93Variante_LZ78|Die Lempel-Ziv-Variante LZ78]]&nbsp; Bezug genommen.
-*Die Originalliteratur&nbsp; [LZ78]&nbsp; zu diesem Verfahren lautet: &nbsp; <br>Ziv, J.; Lempel, A.: ''Compression of Individual Sequences via Variable-Rate Coding.'' In: IEEE Transactions on Information Theory, no. 5, vol. 24, 1978, p. 530–536.
+*Die Originalliteratur&nbsp; [LZ78]&nbsp; zu diesem Verfahren lautet: &nbsp; <br>&nbsp; &nbsp; &nbsp; Ziv, J.; Lempel, A.:&nbsp; Compression of Individual Sequences via Variable-Rate Coding.&nbsp; In: IEEE Transactions on Information Theory, no. 5, vol. 24, 1978, p. 530–536.
 *Die&nbsp; [[Aufgaben:2.3Z_Zur_LZ77-Codierung|Aufgabe 2.3Z]]&nbsp; sowie die&nbsp; [[Aufgaben:Aufgabe_2.4:_Zum_LZW-Algorithmus|Aufgabe 2.4]]&nbsp; behandeln andere Lempel&ndash;Ziv-Verfahren in ähnlicher Weise.

@@ Zeile 17: / Zeile 17: @@
 *Zur Codierung steht&nbsp; '''Handy'''&nbsp; an.&nbsp; Im Wörterbuch findet man unter dem Index&nbsp; $I = 11$&nbsp; den Eintrag&nbsp; <b>Ha</b>&nbsp; und unter dem Index&nbsp; $I = 16$&nbsp; den Eintrag <b>Han</b>.
 *Somit lautet die aktuelle Coderausgabe &nbsp;  $(I_0,  Z) = (16,$ <b>d</b>$)$&nbsp; und ins Wörterbuch wird als neue Phrase eingetragen: &nbsp; $W(21) =$ <b>Hand</b>.
-*Nun liegt der String&nbsp; <b>y</b>&nbsp; zur Codierung an.&nbsp; Findet man hierfür keinen passenden Eintrag, so wird&nbsp; $(0,$ <b>y</b>$)$&nbsp; ausgegeben und ins Wörterbuch wird neu eingetragen: &nbsp; $W(22) = $ ''&epsilon;'' +  <b>y</b> $=$ <b>y</b> .
+*Nun liegt der String&nbsp; <b>y</b>&nbsp; zur Codierung an.&nbsp; Findet man hierfür keinen passenden Eintrag, so wird&nbsp; $(0,$ <b>y</b>$)$&nbsp; ausgegeben und ins Wörterbuch wird neu eingetragen: &nbsp; $W(22) = $ $\rm &epsilon;$&nbsp; +  <b>y</b> $=$ <b>y</b> .
@@ Zeile 88: / Zeile 88: @@
-'''(2)'''&nbsp; <b>&epsilon;</b> bezeichnet das leere Zeichen. Da <b>&epsilon;</b> + <b>B</b> = <b>B</b> ergibt, sind die <u>Aussagen 1 und 2</u> richtig. Aussage 3 trifft wieder für die LZW&ndash;Komprimierung zu.
 '''(3)'''&nbsp; Hier treffen <u>beide Aussagen</u> zu.
 '''(4)'''&nbsp; Richtig sind die <u>Aussagen 2 und 4</u>:
-*Im Wörterbuch wird unter dem Index $I = 1$ das Zeichen <b>B</b> gefunden.
+*Im Wörterbuch wird unter dem Index&nbsp; $I = 1$&nbsp; das Zeichen&nbsp; <b>B</b>&nbsp; gefunden.
-*Das nächste Zeichen <b>A</b> der Eingangsfolge wird angehängt: &nbsp; <b>(1, A)</b>.
+*Das nächste Zeichen&nbsp; <b>A</b>&nbsp; der Eingangsfolge wird angehängt: &nbsp; <b>(1, A)</b>.
-*Die Aussage 3 kann schon deshalb nicht stimmen, da $Z$ nur ein Zeichen sein kann und keine Zeichenfolge.
+*Die Aussage 3 kann schon deshalb nicht stimmen, da&nbsp; $Z$&nbsp; nur ein Zeichen sein kann und keine Zeichenfolge.
-:[[Datei:Inf_A_2_3f_version2.png|right|frame|LZ78–Codierung von <b>BARBARA–BAR</b>]]
+[[Datei:Inf_A_2_3f_version2.png|right|frame|LZ78–Codierung von&nbsp; <b>BARBARA–BAR</b>]]
 '''(5)'''&nbsp; Der gesamte Codiervorgang ist in einer Tabelle zusammengefasst. Man erkennt:
-* Zu jedem Zeitpunkt $i$ wird die bearbeitete Zeichenfolge in das Wörterbuch eingetragen.
+* Zu jedem Zeitpunkt&nbsp; $i$&nbsp; wird die bearbeitete Zeichenfolge in das Wörterbuch eingetragen.
-* Zum Zeitpunkt $\underline{i=7}$ ist der Codiervorgang abgeschlossen.
+* Zum Zeitpunkt&nbsp; $\underline{i=7}$&nbsp; ist der Codiervorgang abgeschlossen.
@@ Zeile 109: / Zeile 116: @@
 * ohne Codierung: &nbsp; $N = 11 \cdot 2 \hspace{0.15cm}\underline {= 22 \, \rm Bit}$,
 * mit LZ78&ndash;Codierung: &nbsp; $N = 7 \cdot (3+2) \hspace{0.15cm}\underline {= 35 \, \rm Bit}$.
 Daran erkennt man:
-* Eine jede LZ&ndash;Komprimierung macht erst bei einer größeren Datei Sinn, auch dann, wenn man glaubt, dass ein Text wie <b>BARBARA&ndash;BAR</b> dem LZ78&ndash;Algorithmus entgegenkommt.
+* Eine jede LZ&ndash;Komprimierung macht erst bei einer größeren Datei Sinn, auch dann, wenn man glaubt, dass ein Text wie&nbsp; <b>BARBARA&ndash;BAR</b>&nbsp; dem LZ78&ndash;Algorithmus entgegenkommt.
 * Mit variabler Bitanzahl für den Index entsprechend der Aufgabe 2.4 würde sich für dieses LZ78-Beispiel ergeben:
 :$$N = 1 \cdot 3 + 2 \cdot 4 + 4 \cdot 5 = 31 \,{\rm Bit}\hspace{0.05cm}.$$

← Nächstältere Version		Version vom 23. Januar 2020, 14:22 Uhr
Zeile 35:		Zeile 35:
	*Die Originalliteratur  [LZ78]  zu diesem Verfahren lautet:   <br>Ziv, J.; Lempel, A.: ''Compression of Individual Sequences via Variable-Rate Coding.'' In: IEEE Transactions on Information Theory, no. 5, vol. 24, 1978, p. 530–536.		*Die Originalliteratur  [LZ78]  zu diesem Verfahren lautet:   <br>Ziv, J.; Lempel, A.: ''Compression of Individual Sequences via Variable-Rate Coding.'' In: IEEE Transactions on Information Theory, no. 5, vol. 24, 1978, p. 530–536.

−	*Die  [[Aufgaben:2.3Z_Zur_LZ77-Codierung\|Aufgabe 2.3Z]]  sowie die  [[Aufgaben:2.~~4_LZW~~-Algorithmus\|Aufgabe 2.4]]  behandeln andere Lempel–Ziv-Verfahren in ähnlicher Weise.	+	*Die  [[Aufgaben:2.3Z_Zur_LZ77-Codierung\|Aufgabe 2.3Z]]  sowie die  [[Aufgaben:Aufgabe_2.4:_Zum_LZW-Algorithmus\|Aufgabe 2.4]]  behandeln andere Lempel–Ziv-Verfahren in ähnlicher Weise.

@@ Zeile 4: / Zeile 4: @@
 [[Datei:P_ID2434__Inf_A_2_3.png|right|frame|Die LZ78&ndash;Erfinder]]
-Im Gegensatz zur Entropiecodierung nach Huffman oder nach Shannon, bei der man die Quellenstatistik (möglichst genau) kennen muss, sind solche Einschränkungen bei den von [https://de.wikipedia.org/wiki/Abraham_Lempel Abraham Lempel] und [https://de.wikipedia.org/wiki/Jacob_Ziv Jacob Ziv] entwickelten Komprimierungsverfahren nicht gegeben. Man spricht von ''universeller Quellencodierung''.
+Im Gegensatz zur Entropiecodierung nach Huffman oder nach Shannon, bei der man die Quellenstatistik (möglichst genau) kennen muss, sind solche Einschränkungen bei den von&nbsp; [https://de.wikipedia.org/wiki/Abraham_Lempel Abraham Lempel]&nbsp; und&nbsp; [https://de.wikipedia.org/wiki/Jacob_Ziv Jacob Ziv]&nbsp; entwickelten Komprimierungsverfahren nicht gegeben.&nbsp; Man spricht von ''universeller Quellencodierung''.
-Wir betrachten in dieser Aufgabe die 1978 erstmals veröffentlichte Variante '''[LZ78]'''.  Codiert werden soll der String &nbsp;<b>BARBARA&ndash;BAR</b>.
+Wir betrachten in dieser Aufgabe die 1978 erstmals veröffentlichte Variante&nbsp; [LZ78].&nbsp;  Codiert werden soll der String &nbsp;<b>BARBARA&ndash;BAR</b>.
-*Das Verfahren LZ78 arbeitet mit einem globalen Wörterbuch, das zu Beginn nur mit einem leeren Zeichen $(\varepsilon)$ unter dem Index $I = 0$ gefüllt ist. Dadurch unterscheidet sich &bdquo;LZ78&rdquo; von seinem Vorgänger &bdquo;LZ77&rdquo; (mit lokalem Wörterbuch) und auch von seinem Nachfolger &bdquo;LZW&rdquo; (Wörterbuch ist mit den möglichen Zeichen vorbelegt).
+*Das Verfahren LZ78 arbeitet mit einem globalen Wörterbuch, das zu Beginn nur mit einem leeren Zeichen&nbsp; $(\varepsilon)$&nbsp; unter dem Index&nbsp; $I = 0$&nbsp; gefüllt ist.&nbsp; Dadurch unterscheidet sich &bdquo;LZ78&rdquo; von seinem Vorgänger &bdquo;LZ77&rdquo; (mit lokalem Wörterbuch) und auch von seinem Nachfolger &bdquo;LZW&rdquo; (Wörterbuch ist mit den möglichen Zeichen vorbelegt).
-*Wird ein Zeichen oder ein Wortfragment (mehrere Zeichen) des Eingabestrings im Wörterbuch gefunden, so wird der Index $I_0$ dieses Eintrags zusammen mit dem nächsten Eingangszeichen $Z$ ausgegeben. In jedem Schritt $i$ lautet also die Ausgabe: &nbsp;  $(I_0, \ Z)$.
+*Wird ein Zeichen oder ein Wortfragment (mehrere Zeichen) des Eingabestrings im Wörterbuch gefunden, so wird der Index&nbsp; $I_0$&nbsp; dieses Eintrags zusammen mit dem nächsten Eingangszeichen&nbsp; $Z$&nbsp; ausgegeben.&nbsp; In jedem Schritt&nbsp; $i$&nbsp; lautet also die Ausgabe: &nbsp;  $(I_0, \ Z)$.
-*Anschließend wird der neue String unter dem nächsten freien Index $I_{\rm neu}$ ins Wörterbuch eingetragen.
+*Anschließend wird der neue String unter dem nächsten freien Index&nbsp; $I_{\rm neu}$&nbsp; ins Wörterbuch eingetragen.
-*Betrachtet man das Wörterbuch als ein Feld $W[\hspace{0.05cm}I\hspace{0.05cm}]$ mit $I &ge; 0$, bei dem ein jedes Element eine Zeichenkette beliebiger Länge enthält, so gilt mit der Character&ndash;Variablen $Z$:
+*Betrachtet man das Wörterbuch als ein Feld&nbsp; $W\big[\hspace{0.05cm}I\hspace{0.05cm}\big]$&nbsp; mit&nbsp; $I &ge; 0$, bei dem ein jedes Element eine Zeichenkette beliebiger Länge enthält, so gilt mit der Character&ndash;Variablen&nbsp; $Z$:
-:$$W [\hspace{0.05cm}I_{\rm neu}\hspace{0.05cm}]  = W[\hspace{0.05cm}I_0\hspace{0.05cm}] + Z \hspace{0.05cm}. $$
+:$$W \big[\hspace{0.05cm}I_{\rm neu}\hspace{0.05cm}\big]  = W\big[\hspace{0.05cm}I_0\hspace{0.05cm}\big] + Z \hspace{0.05cm}. $$
 Zur Verdeutlichung ein einfaches Beispiel:
-*Zu einem gegebenen Zeitpunkt ist das Wörterbuch bis zum Index $I_{\rm akt }= 20$ gefüllt.
+*Zu einem gegebenen Zeitpunkt ist das Wörterbuch bis zum Index&nbsp; $I_{\rm akt }= 20$&nbsp; gefüllt.
-*Zur Codierung steht '''Handy''' an. Im Wörterbuch findet man unter dem Index $I = 11$ den Eintrag <b>Ha</b> und unter dem Index $I = 16$ den Eintrag <b>Han</b>.
+*Zur Codierung steht&nbsp; '''Handy'''&nbsp; an.&nbsp; Im Wörterbuch findet man unter dem Index&nbsp; $I = 11$&nbsp; den Eintrag&nbsp; <b>Ha</b>&nbsp; und unter dem Index&nbsp; $I = 16$&nbsp; den Eintrag <b>Han</b>.
-*Somit lautet die aktuelle Coderausgabe &nbsp;  $(I_0,  Z) = (16,$ <b>d</b>$)$ und ins Wörterbuch wird als neue Phrase eingetragen: &nbsp; $W(21) =$ <b>Hand</b>.
+*Somit lautet die aktuelle Coderausgabe &nbsp;  $(I_0,  Z) = (16,$ <b>d</b>$)$&nbsp; und ins Wörterbuch wird als neue Phrase eingetragen: &nbsp; $W(21) =$ <b>Hand</b>.
-*Nun liegt der String <b>y</b> zur Codierung an. Findet man hierfür keinen passenden Eintrag, so wird $(0,$ <b>y</b>$)$ ausgegeben und ins Wörterbuch neu eingetragen: &nbsp; $W(22) = $ <b>&epsilon;</b> +  <b>y</b> $=$ <b>y</b> .
+*Nun liegt der String&nbsp; <b>y</b>&nbsp; zur Codierung an.&nbsp; Findet man hierfür keinen passenden Eintrag, so wird&nbsp; $(0,$ <b>y</b>$)$&nbsp; ausgegeben und ins Wörterbuch wird neu eingetragen: &nbsp; $W(22) = $ ''&epsilon;'' +  <b>y</b> $=$ <b>y</b> .
@@ Zeile 29: / Zeile 31: @@
 ''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 auf die Seite [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch#Die_Lempel.E2.80.93Ziv.E2.80.93Variante_LZ78|Die Lempel-Ziv-Variante LZ78]] Bezug genommen.
+*Insbesondere wird auf die Seite&nbsp; [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch#Die_Lempel.E2.80.93Ziv.E2.80.93Variante_LZ78|Die Lempel-Ziv-Variante LZ78]]&nbsp; Bezug genommen.
-*Die Originalliteratur '''[LZ78]''' zu diesem Verfahren lautet: &nbsp; Ziv, J.; Lempel, A.: ''Compression of Individual Sequences via Variable-Rate Coding.'' In: IEEE Transactions on Information Theory, no. 5, vol. 24, 1978, p. 530–536.
+*Die Originalliteratur&nbsp; [LZ78]&nbsp; zu diesem Verfahren lautet: &nbsp; <br>Ziv, J.; Lempel, A.: ''Compression of Individual Sequences via Variable-Rate Coding.'' In: IEEE Transactions on Information Theory, no. 5, vol. 24, 1978, p. 530–536.
-*Die [[Aufgaben:2.3Z_Zur_LZ77-Codierung|Zusatzaufgabe 2.3Z]] sowie die [[Aufgaben:2.4_LZW-Algorithmus|Aufgabe 2.4]] behandeln andere Lempel&ndash;Ziv-Verfahren in ähnlicher Weise.
+*Die&nbsp; [[Aufgaben:2.3Z_Zur_LZ77-Codierung|Aufgabe 2.3Z]]&nbsp; sowie die&nbsp; [[Aufgaben:2.4_LZW-Algorithmus|Aufgabe 2.4]]&nbsp; behandeln andere Lempel&ndash;Ziv-Verfahren in ähnlicher Weise.
@@ Zeile 40: / Zeile 42: @@
 <quiz display=simple>
 {Welche Aussagen gelten für die Vorbelegung des LZ78&ndash;Wörterbuches?
-|type="[]"}
+|type="()"}
-+ Vorbelegt ist nur der Index $I = 0$ mit dem Leerzeichen (<b>&epsilon;</b>).
++ Vorbelegt ist nur der Index&nbsp; $I = 0$&nbsp; mit dem Leerzeichen&nbsp; $(\varepsilon)$.
-- Vorbelegt sind die Indizes $I = 0$ bis $I = 3$ mit den vier Zeichen '''A''', '''B''', '''R''' und '''&ndash;''' .
+- Vorbelegt sind die Indizes&nbsp; $I = 0$&nbsp; bis&nbsp; $I = 3$&nbsp; mit den vier Zeichen&nbsp; '''A''',&nbsp; '''B''',&nbsp; '''R'''&nbsp; und&nbsp; '''&ndash;''' .
-{Was geschieht im Codierschritt $i = 1$?
+{Was geschieht im Codierschritt&nbsp; $i = 1$?
 |type="[]"}
 + Die Coderausgabe lautet: &nbsp; $(0,$ <b>B</b>$)$.
@@ Zeile 52: / Zeile 54: @@
-{Welche Aussagen gelten für die Codierschritte $i = 2$ und $i = 3$?
+{Welche Aussagen gelten für die Codierschritte&nbsp; $i = 2$&nbsp; und&nbsp; $i = 3$?
 |type="[]"}
-+ Für $i = 2$ gilt: &nbsp; Ausgabe $(0,$ <b>A</b>$)$, &nbsp; Eintrag $W(I = 2) =$  <b>A</b>.
++ Für&nbsp; $i = 2$&nbsp; gilt: &nbsp; Ausgabe&nbsp; $(0,$ <b>A</b>$)$, &nbsp; Eintrag&nbsp; $W(I = 2) =$  <b>A</b>.
-+ Für $i = 3$ gilt: &nbsp; Ausgabe $(0,$ <b>R</b>$)$, &nbsp; Eintrag $W(I = 3) =$ <b>R</b>.
++ Für&nbsp; $i = 3$&nbsp; gilt: &nbsp; Ausgabe&nbsp; $(0,$ <b>R</b>$)$, &nbsp; Eintrag&nbsp; $W(I = 3) =$ <b>R</b>.
-{Welche Aussagen gelten für den Codierschritt $i = 4$?
+{Welche Aussagen gelten für den Codierschritt&nbsp; $i = 4$?
 |type="[]"}
-- Bei Schritt $i = 4$ wird <b>BAR</b> gemeinsam codiert.
+- Bei Schritt&nbsp; $i = 4$&nbsp; wird&nbsp; <b>BAR</b>&nbsp; gemeinsam codiert.
-+ Bei Schritt $i = 4$ wird <b>BA</b> gemeinsam codiert.
++ Bei Schritt&nbsp; $i = 4$&nbsp; wird&nbsp; <b>BA</b>&nbsp; gemeinsam codiert.
 - Die Coderausgabe lautet: &nbsp; $(2,$ <b>AR</b>$)$.
 + Die Coderausgabe lautet: &nbsp; $(1,$ <b>A</b>$)$.
-{Vervollständigen Sie die LZ78&ndash;Codierung. Nach welchem Codierschritt $i_{\rm Ende}$ ist <b>BARBARA&ndash;BAR</b> vollständig codiert?
+{Vervollständigen Sie die LZ78&ndash;Codierung.&nbsp; Nach welchem Codierschritt&nbsp; $i_{\rm Ende}$&nbsp; ist&nbsp; <b>BARBARA&ndash;BAR</b>&nbsp; vollständig codiert?
 |type="{}"}
 $i_{\rm Ende} \ = \ $ { 7 3% }
-{Wieviele Binärzeichen benötigt man, um  <b>BARBARA&ndash;BAR</b> zu codieren? <br>Beachten Sie die Hinweise auf der Angabenseite.
+{Wieviele Binärzeichen benötigt man, um&nbsp; <b>BARBARA&ndash;BAR</b>&nbsp; zu codieren?&nbsp; Beachten Sie die Hinweise auf der Angabenseite.
 |type="{}"}
 $\text{ohne Codierung:  }\ N \ = \ $ { 22 3% } $\ \rm Bit$

@@ Zeile 82: / Zeile 82: @@
 ===Musterlösung===
 {{ML-Kopf}}
-'''(1)'''&nbsp; Zutreffend für den LZ78&ndash;Algorithmus ist <u>Aussage 1</u>. Die Vorbelegung gemäß Aussage 2 gilt dagegen für den LZW&ndash;Algorithmus, der 1983 gemeinsam mit Terry Welch veröffentlicht wurde.
+'''(1)'''&nbsp; Zutreffend für den LZ78&ndash;Algorithmus ist <u>Aussage 1</u>:
 '''(2)'''&nbsp; <b>&epsilon;</b> bezeichnet das leere Zeichen. Da <b>&epsilon;</b> + <b>B</b> = <b>B</b> ergibt, sind die <u>Aussagen 1 und 2</u> richtig. Aussage 3 trifft wieder für die LZW&ndash;Komprimierung zu.
 '''(3)'''&nbsp; Hier treffen <u>beide Aussagen</u> zu.
 '''(4)'''&nbsp; Richtig sind die <u>Aussagen 2 und 4</u>:
-*Im Wörterbuch wird unter dem Index <i>I</i> = 1 das Zeichen <b>B</b> gefunden.
+*Im Wörterbuch wird unter dem Index $I = 1$ das Zeichen <b>B</b> gefunden.
-*Das nächste Zeichen <b>A</b> der Eingangsfolge wird angehängt: (1, <b>A</b>).
+*Das nächste Zeichen <b>A</b> der Eingangsfolge wird angehängt: &nbsp; <b>(1, A)</b>.
-*Die Aussage 3 kann schon deshalb nicht stimmen, da <i>Z</i> nur ein Zeichen sein kann und keine Zeichenfolge.
+*Die Aussage 3 kann schon deshalb nicht stimmen, da $Z$ nur ein Zeichen sein kann und keine Zeichenfolge.
 :[[Datei:Inf_A_2_3f_version2.png|right|LZ78–Codierung von <b>BARBARA–BAR</b>]]
 '''(5)'''&nbsp; Der gesamte Codiervorgang ist in einer Tabelle zusammengefasst. Man erkennt:
-* Zu jedem Zeitpunkt <i>i</i> wird die bearbeitete Zeichenfolge in das Wörterbuch eingetragen.
+* Zu jedem Zeitpunkt $i$ wird die bearbeitete Zeichenfolge in das Wörterbuch eingetragen.
-* Zum Zeitpunkt <u><i>i</i> = 7</u> ist der Codiervorgang abgeschlossen.
+* Zum Zeitpunkt $\underline{i=7}$ ist der Codiervorgang abgeschlossen.
-<br><br><br><br><br><br>
 '''(6)'''&nbsp; Stellt man alle Indizes mit drei Bit dar und die vier Zeichen (Character) mit je zwei Bit, so kommt man zu folgenden Ergebnissen:
-* ohne Codierung: $N = 11 \cdot 2 \hspace{0.15cm}\underline {= 22 \, \rm Bit}$,
+* ohne Codierung: &nbsp; $N = 11 \cdot 2 \hspace{0.15cm}\underline {= 22 \, \rm Bit}$,
-* mit LZ78&ndash;Codierung: $N = 7 \cdot (3+2) \hspace{0.15cm}\underline {= 35 \, \rm Bit}$.
+* mit LZ78&ndash;Codierung: &nbsp; $N = 7 \cdot (3+2) \hspace{0.15cm}\underline {= 35 \, \rm Bit}$.
 Daran erkennt man:

@@ Zeile 28: / Zeile 28: @@
 *Insbesondere wird auf die Seite [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch#Die_Lempel.E2.80.93Ziv.E2.80.93Variante_LZ78|Die Lempel-Ziv-Variante LZ78]] Bezug genommen.
 *Die Originalliteratur [LZ78] zu diesem Verfahren lautet: Ziv, J.; Lempel, A.: ''Compression of Individual Sequences via Variable-Rate Coding.'' In: IEEE Transactions on Information Theory, no. 5, vol. 24, 1978, p. 530–536.
-*Sollte die Eingabe des Zahlenwertes &bdquo;0&rdquo; erforderlich sein, so geben Sie bitte &bdquo;0.&rdquo; ein.
 *Die [[Aufgaben:2.3Z_Zur_LZ77-Codierung|Zusatzaufgabe 2.3Z]] sowie die [[Aufgaben:2.4_LZW-Algorithmus|Aufgabe 2.4]] behandeln andere LZ-Verfahren in ähnlicher Weise.