Aufgaben:Aufgabe 2.3Z: Zur LZ77-Codierung - Versionsgeschichte

Guenter am 12. Juli 2021 um 14:07 Uhr

2021-07-12T14:07:08Z

Guenter am 12. Juli 2021 um 13:58 Uhr

2021-07-12T13:58:32Z

Guenter am 23. Januar 2020 um 15:17 Uhr

2020-01-23T15:17:13Z

Guenter am 23. Januar 2020 um 15:04 Uhr

2020-01-23T15:04:27Z

Guenter am 24. September 2018 um 14:04 Uhr

2018-09-24T14:04:41Z

Guenter am 24. September 2018 um 14:03 Uhr

2018-09-24T14:03:00Z

Guenter am 24. September 2018 um 12:49 Uhr

2018-09-24T12:49:40Z

Guenter am 24. September 2018 um 12:45 Uhr

2018-09-24T12:45:13Z

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.3Z Zur LZ77-Codierung nach Aufgaben:Aufgabe 2.3Z: Zur LZ77-Codierung

2018-01-03T13:57:49Z

Guenter verschob die Seite 2.3Z Zur LZ77-Codierung nach Aufgabe 2.3Z: Zur LZ77-Codierung

@@ Zeile 85: / Zeile 85: @@
 *Im Suchpuffer steht in den letzten drei Stellen&nbsp; <b>BAR</b>:
 :$$P = 2\hspace{0.05cm},\hspace{0.2cm}L = 3\hspace{0.05cm},\hspace{0.2cm}Z = \boldsymbol{\rm A}\hspace{0.05cm}.$$
@@ Zeile 94: / Zeile 93: @@
-'''(3)'''&nbsp; Die obere Grafik zeigt das&nbsp; <i>Sliding&ndash;Window</i>&nbsp; und die Coderausgabe zu den Zeiten&nbsp; $i>5$.
+'''(3)'''&nbsp; Die obere Grafik zeigt das&nbsp; &bdquo;Sliding&ndash;Window&rdquo;&nbsp; und die Coderausgabe zu den Zeiten&nbsp; $i>5$.
-*Nach&nbsp; $i = 9$&nbsp; Codierschritten ist der Codiervorgang unter Berücksichtigung von&nbsp; <b>eof</b>&nbsp; beendet &nbsp; &rArr; &nbsp; $\underline{i_{\rm Ende} = 9}$.
+*Nach&nbsp; $i = 9$&nbsp; Codierschritten ist der Codiervorgang unter Berücksichtigung von&nbsp; "<b>eof</b>"&nbsp; beendet &nbsp; &rArr; &nbsp; $\underline{i_{\rm Ende} = 9}$.

@@ Zeile 3: / Zeile 3: @@
 }}
-[[Datei:P_ID2436__Inf_Z_2_3.png|right|frame|Sliding–Window mit&nbsp; $G = 4$&nbsp; und&nbsp; $G = 5$<br>(gültig für &bdquo;LZ77&rdquo;]]
+[[Datei:P_ID2436__Inf_Z_2_3.png|right|frame|Sliding–Window mit&nbsp; $G = 4$&nbsp; und&nbsp; $G = 5$<br>(gültig für &bdquo;LZ77&rdquo;)]]
-In der&nbsp; [[Aufgaben:2.3_Zur_LZ78-Komprimierung|Aufgabe 2.3]]&nbsp; sollten Sie&nbsp; <b>BARBARA&ndash;BAR</b>&nbsp; (String der Länge&nbsp; $11$, vier verschiedene Zeichen)&nbsp; mit dem LZ78&ndash;Algorithmus komprimieren.&nbsp;
+In der&nbsp; [[Aufgaben:2.3_Zur_LZ78-Komprimierung|Aufgabe 2.3]]&nbsp; sollten Sie&nbsp; "<b>BARBARA&ndash;BAR"</b>&nbsp; (String der Länge&nbsp; $11$, vier verschiedene Zeichen)&nbsp; mit dem LZ78&ndash;Algorithmus komprimieren.&nbsp;
 In dieser Aufgabe verwenden wir den gleichen Text zur Demonstration der LZ77&ndash;Komprimierung.&nbsp; Anzumerken ist:
 * Während beim Nachfolger &bdquo;LZ78&rdquo; sukzessive ein globales Wörterbuch aufgebaut wird, verwendet &bdquo;LZ77&rdquo;   ein lokales Wörterbuch.
-* Das LZ77&ndash;Verfahren arbeitet mit einem&nbsp; <i>Sliding Window</i>, das schrittweise über den Eingabetext verschoben wird.
+* Das LZ77&ndash;Verfahren arbeitet mit einem&nbsp; &bdquo;Sliding Window&rdquo;, das schrittweise über den Eingabetext verschoben wird.
-* Dieses &bdquo;gleitende Fenster&rdquo; ist unterteilt in den&nbsp; ''Vorschaupuffer''&nbsp; (in der Grafik blau hinterlegt) und den&nbsp; ''Suchpuffer''&nbsp; (rote Hinterlegung).&nbsp; Beide Puffer haben je eine Größe von&nbsp; $G$&nbsp; Speicherplätzen.
+* Dieses &bdquo;gleitende Fenster&rdquo; ist unterteilt in den&nbsp; &bdquo;Vorschaupuffer&rdquo;&nbsp; (in der Grafik blau hinterlegt) und den&nbsp; &bdquo;Suchpuffer&rdquo;&nbsp; (rote Hinterlegung).&nbsp; Beide Puffer haben je eine Größe von&nbsp; $G$&nbsp; Speicherplätzen.
 * Jeder Codierschritt&nbsp; $i$&nbsp; wird durch ein Zahlentriple&nbsp; $(P,\ L,\ Z)$&nbsp; charakterisiert.&nbsp; Hierbei sind&nbsp; $P$&nbsp; und&nbsp; $L$&nbsp; Integergrößen und&nbsp; $Z$&nbsp; ein Character.&nbsp; Übertragen werden die Binärdarstellungen von&nbsp; $P$,&nbsp; $L$&nbsp; und&nbsp; $Z$.
-* Nach der Übertragung wird das&nbsp; <i>Sliding Window</i>&nbsp; um eine oder mehrere Positionen nach rechts verschoben und es beginnt der nächste Codierschritt&nbsp; $i + 1$.
+* Nach der Übertragung wird das&nbsp; &bdquo;Sliding Window&rdquo;&nbsp; um eine oder mehrere Positionen nach rechts verschoben und es beginnt der nächste Codierschritt&nbsp; $i + 1$.
@@ Zeile 27: / Zeile 27: @@
 Je größer der LZ77&ndash;Parameter&nbsp; $G$&nbsp; ist, um so leichter findet man eine möglichst lange Übereinstimmung.&nbsp; In der Teilaufgabe&nbsp; '''(4)'''&nbsp; werden Sie feststellen, dass die LZ77&ndash;Codierung mit&nbsp; $G = 5$&nbsp; ein besseres Ergebnis liefert als diejenige mit&nbsp; $G = 4$.
-* Aufgrund der späteren Binärdarstellung von&nbsp; $P$ wird&nbsp; man allerdings&nbsp; $G$&nbsp; stets als Zweierpotenz wählen, so dass&nbsp; $G$&nbsp; mit&nbsp; $\log_2 \ P$&nbsp; Bit darstellbar ist&nbsp; $(G = 8$ &nbsp; &#8658; &nbsp; dreistellige Binärzahl&nbsp; $P)$.
+* Aufgrund der späteren Binärdarstellung von&nbsp; $P$ wird&nbsp; man allerdings&nbsp; $G$&nbsp; stets als Zweierpotenz wählen, so dass&nbsp; $G$&nbsp; mit&nbsp; $\log_2 \ P$&nbsp; Bit darstellbar ist&nbsp; <br>$(G = 8$ &nbsp; &#8658; &nbsp; dreistellige Binärzahl&nbsp; $P)$.
-*Das heißt, ein&nbsp; <i>Sliding Window</i>&nbsp; mit&nbsp; $G = 5$&nbsp; hat eher einen geringen Praxisbezug.
+*Das heißt, ein&nbsp; &bdquo;Sliding Window&rdquo;&nbsp; mit&nbsp; $G = 5$&nbsp; hat eher einen geringen Praxisbezug.
@@ Zeile 37: / Zeile 37: @@
 *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#LZ77_.E2.80.93_die_Grundform_der_Lempel.E2.80.93Ziv.E2.80.93Algorithmen|LZ77 &ndash; die Grundform der Lempel-Ziv-Algorithmen]]&nbsp; Bezug genommen.
-*Die Originalliteratur&nbsp; [LZ77]&nbsp; zu diesem Verfahren lautet: <br>Ziv, J.; Lempel, A.: ''A Universal Algorithm for Sequential Data Compression.'' In: IEEE Transactions on Information Theory, no. 3, vol. 23, 1977, p. 337–343.
+*Die Originalliteratur&nbsp; [LZ77]&nbsp; zu diesem Verfahren lautet: <br>Ziv, J.; Lempel, A.:&nbsp; A Universal Algorithm for Sequential Data Compression.&nbsp; In: IEEE Transactions on Information Theory, no. 3, vol. 23, 1977, p. 337–343.
 *Die&nbsp; [[Aufgaben:2.3_Zur_LZ78-Komprimierung|Aufgabe 2.3]]&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 80: / Zeile 80: @@
 ===Musterlösung===
 {{ML-Kopf}}
-[[Datei:P_ID2438__Inf_Z_2_3c.png|right|frame|Beispiel zum LZ77–Algorithmus mit $G = 4$]]
+[[Datei:P_ID2438__Inf_Z_2_3c.png|right|frame|Beispiel zum LZ77–Algorithmus mit&nbsp; $G = 4$]]
 '''(1)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 3</u>.
-*Im Vorschaupuffer steht zum betrachteten Zeitpunkt $i = 4$ die Zeichenfolge <b>BARA</b>.
+*Im Vorschaupuffer steht zum betrachteten Zeitpunkt&nbsp; $i = 4$&nbsp; die Zeichenfolge&nbsp; <b>BARA</b>.
-*Im Suchpuffer steht in den letzten drei Stellen <b>BAR</b>:
+*Im Suchpuffer steht in den letzten drei Stellen&nbsp; <b>BAR</b>:
 :$$P = 2\hspace{0.05cm},\hspace{0.2cm}L = 3\hspace{0.05cm},\hspace{0.2cm}Z = \boldsymbol{\rm A}\hspace{0.05cm}.$$
 '''(2)'''&nbsp; Richtig sind die <u>beiden ersten Lösungsvorschläge</u>:
-*Der Bindestrich findet sich zum Zeitpunkt $i = 5$ nicht im Suchpuffer.
+*Der Bindestrich findet sich zum Zeitpunkt&nbsp; $i = 5$&nbsp; nicht im Suchpuffer.
-*Ausgegeben wird $(0, 0,$ <b>&ndash;</b>$)$.
+*Ausgegeben wird&nbsp; $(0, 0,$ <b>&ndash;</b>$)$.
-[[Datei:P_ID2439__Inf_Z_2_3d.png|right|frame|Beispiel zum LZ77–Algorithmus mit $G = 5$]]
+[[Datei:P_ID2439__Inf_Z_2_3d.png|right|frame|Beispiel zum LZ77–Algorithmus mit&nbsp; $G = 5$]]
-'''(4)'''&nbsp; Bei größerer Puffergröße ($G = 5$ anstelle von $G = 4$) ist die Codierung schon nach dem 6. Codierschritt  abgeschlossen &nbsp; &rArr; &nbsp; $\underline{i_{\rm Ende} = 6}$.
+'''(4)'''&nbsp; Bei größerer Puffergröße&nbsp; $(G = 5$&nbsp; anstelle von&nbsp; $G = 4)$&nbsp; ist die Codierung schon nach dem 6. Codierschritt  abgeschlossen &nbsp; &rArr; &nbsp; $\underline{i_{\rm Ende} = 6}$.
-*Ein Vergleich der beiden Grafiken zeigt, dass sich für $G = 5$ gegenüber $G = 4$ bis einschließlich $i = 5$  nichts ändert.
+*Ein Vergleich der beiden Grafiken zeigt, dass sich für&nbsp; $G = 5$&nbsp; gegenüber&nbsp; $G = 4$&nbsp; bis einschließlich&nbsp; $i = 5$&nbsp;  nichts ändert.
-*Aufgrund des größeren Puffers lässt sich aber nun <b>BAR</b> gemeinsam mit <b>eof</b> (end-of-file) in einem einzigen Schritt codieren, während mit $G = 4$ hierfür vier Schritte notwendig waren.
+*Aufgrund des größeren Puffers lässt sich aber nun&nbsp; <b>BAR</b>&nbsp; gemeinsam mit&nbsp; <b>eof</b>&nbsp; (end-of-file) in einem einzigen Schritt codieren, während mit&nbsp; $G = 4$&nbsp; hierfür vier Schritte notwendig waren.
 <br clear=all>
 '''(5)'''&nbsp; Richtig ist nur die  <u>Aussage 1</u>.
-*Ein Nachteil von LZ77 ist das lokale Wörterbuch. Eigentlich schon bekannte Phrasen können nicht für die Datenkomprimierung verwendet werden, wenn sie mehr als $G$ Zeichen vorher im Text aufgetreten sind. Dagegen sind bei LZ78 alle Phrasen im globalen Wörterbuch abgelegt.
+*Ein Nachteil von LZ77 ist das lokale Wörterbuch.&nbsp; Eigentlich schon bekannte Phrasen können nicht für die Datenkomprimierung verwendet werden, wenn sie mehr als&nbsp; $G$&nbsp; Zeichen vorher im Text aufgetreten sind.&nbsp; Dagegen sind bei LZ78 alle Phrasen im globalen Wörterbuch abgelegt.
-*Richtig ist zwar, dass bei LZ78 nur Pärchen $(I, Z)$ übertragen werden müssen, während bei LZ77 jeder Codierschritt durch ein Triple $(P, L, Z)$ gekennzeichnet ist. Das bedeutet aber noch nicht, dass pro Codierschritt auch weniger Bit übertragen werden müssen.
+*Richtig ist zwar, dass bei LZ78 nur Pärchen&nbsp; $(I, \ Z)$&nbsp; übertragen werden müssen, während bei LZ77 jeder Codierschritt durch ein Triple&nbsp; $(P, \ L, \ Z)$&nbsp; gekennzeichnet ist.&nbsp; Das bedeutet aber noch nicht, dass pro Codierschritt auch weniger Bit übertragen werden müssen.
-*Betrachten wir beispielhaft die Puffergröße $G = 8$. Bei LZ77 muss man dann $P$ mit drei Bit und $L$ mit vier Bit dargestellen. Berücksichtigen Sie, dass die gefundene Übereinstimmung zwischen Vorschaupuffer und Suchpuffer auch im Vorschaupuffer enden darf.
+*Betrachten wir beispielhaft die Puffergröße&nbsp; $G = 8$.&nbsp; Bei LZ77 muss man dann&nbsp; $P$&nbsp; mit drei Bit und&nbsp; $L$&nbsp; mit vier Bit dargestellen.&nbsp; Beachten Sie bitte, dass die gefundene Übereinstimmung zwischen Vorschaupuffer und Suchpuffer auch im Vorschaupuffer enden darf.
-*Das neue Zeichen $Z$ benötigt bei LZ78 genau die gleiche Bitanzahl wie bei LZ77 (nämlich zwei Bit), wenn man wie hier vom Symbolumfang $M = 4$ ausgeht.
+*Das neue Zeichen&nbsp; $Z$&nbsp; benötigt bei LZ78 genau die gleiche Bitanzahl wie bei LZ77 (nämlich zwei Bit), wenn man wie hier vom Symbolumfang&nbsp; $M = 4$&nbsp; ausgeht.
-*Die Aussage 2 wäre nur dann richtig, wenn $N_{\rm I}$ kleiner wäre als $N_{\rm P}+ N_{\rm L}$, beispielsweise $N_{\rm I} = 6$. Das würde aber bedeuten, dass man die Wörterbuchgröße auf $I = 2^6 = 64$ begrenzen müsste. Dies reicht für große Dateien nicht aus.
+*Die Aussage 2 wäre nur dann richtig, wenn&nbsp; $N_{\rm I}$&nbsp; kleiner wäre als&nbsp; $N_{\rm P}+ N_{\rm L}$, beispielsweise&nbsp; $N_{\rm I} = 6$. Das würde aber bedeuten, dass man die Wörterbuchgröße auf&nbsp; $I = 2^6 = 64$&nbsp; begrenzen müsste.&nbsp; Dies reicht für große Dateien nicht aus.
-*Unsere Überschlagsrechnung basiert allerdings auf einer einheitlichen Bitanzahl für den Index $I$. Mit variabler Bitanzahl für den Index kann man etliche Bit einsparen, indem man $I$ nur mit so vielen Bit überträgt, wie es für den Codierschritt $i$ erforderlich ist.
+*Unsere Überschlagsrechnung basiert allerdings auf einer einheitlichen Bitanzahl für den Index&nbsp; $I$.&nbsp; Mit variabler Bitanzahl für den Index kann man etliche Bit einsparen, indem man&nbsp; $I$&nbsp; nur mit so vielen Bit überträgt, wie es für den Codierschritt&nbsp; $i$&nbsp; erforderlich ist.
 *Prinzipiell ändert das aber nichts an der Beschränkung der Wörterbuchgröße, was bei großen Dateien stets zu Problemen führen wird.
 {{ML-Fuß}}

@@ Zeile 3: / Zeile 3: @@
 }}
-[[Datei:P_ID2436__Inf_Z_2_3.png|right|frame|Sliding–Window mit $G = 4$ und $G = 5$ bei LZ77]]
+[[Datei:P_ID2436__Inf_Z_2_3.png|right|frame|Sliding–Window mit&nbsp; $G = 4$&nbsp; und&nbsp; $G = 5$<br>(gültig für &bdquo;LZ77&rdquo;]]
-In der [[Aufgaben:2.3_Zur_LZ78-Komprimierung|Aufgabe 2.3]] sollten Sie <b>BARBARA&ndash;BAR</b> (String der Länge $11$, vier verschiedene Zeichen) mit dem LZ78&ndash;Algorithmus komprimieren. In dieser Aufgabe verwenden wir den gleichen Text zur Demonstration der LZ77&ndash;Komprimierung.
+In der&nbsp; [[Aufgaben:2.3_Zur_LZ78-Komprimierung|Aufgabe 2.3]]&nbsp; sollten Sie&nbsp; <b>BARBARA&ndash;BAR</b>&nbsp; (String der Länge&nbsp; $11$, vier verschiedene Zeichen)&nbsp; mit dem LZ78&ndash;Algorithmus komprimieren.&nbsp;
-Anzumerken ist:
+In dieser Aufgabe verwenden wir den gleichen Text zur Demonstration der LZ77&ndash;Komprimierung.&nbsp; Anzumerken ist:
 * Während beim Nachfolger &bdquo;LZ78&rdquo; sukzessive ein globales Wörterbuch aufgebaut wird, verwendet &bdquo;LZ77&rdquo;   ein lokales Wörterbuch.
-* Das LZ77&ndash;Verfahren arbeitet mit einem <i>Sliding Window</i>, das schrittweise über den Eingabetext verschoben wird.
+* Das LZ77&ndash;Verfahren arbeitet mit einem&nbsp; <i>Sliding Window</i>, das schrittweise über den Eingabetext verschoben wird.
-* Dieses &bdquo;gleitende Fenster&rdquo; ist unterteilt in den Vorschaupuffer (in der Grafik blau hinterlegt) und den Suchpuffer (rote Hinterlegung). Beide Puffer haben eine Größe von $G$ Speicherplätzen.
+* Dieses &bdquo;gleitende Fenster&rdquo; ist unterteilt in den&nbsp; ''Vorschaupuffer''&nbsp; (in der Grafik blau hinterlegt) und den&nbsp; ''Suchpuffer''&nbsp; (rote Hinterlegung).&nbsp; Beide Puffer haben je eine Größe von&nbsp; $G$&nbsp; Speicherplätzen.
-* Jeder Codierschritt $i$&nbsp; wird durch ein Zahlentriple $(P,\ L,\ Z)$ charakterisiert. Hierbei sind $P$ und $L$ Integergrößen und $Z$ ein Character. Übertragen werden die Binärdarstellungen von $P$, $L$ und $Z$.
+* Jeder Codierschritt&nbsp; $i$&nbsp; wird durch ein Zahlentriple&nbsp; $(P,\ L,\ Z)$&nbsp; charakterisiert.&nbsp; Hierbei sind&nbsp; $P$&nbsp; und&nbsp; $L$&nbsp; Integergrößen und&nbsp; $Z$&nbsp; ein Character.&nbsp; Übertragen werden die Binärdarstellungen von&nbsp; $P$,&nbsp; $L$&nbsp; und&nbsp; $Z$.
-* Nach der Übertragung wird das <i>Sliding Window</i> um eine oder mehrere Positionen nach rechts verschoben und es beginnt der nächste Codierschritt $i + 1$.
+* Nach der Übertragung wird das&nbsp; <i>Sliding Window</i>&nbsp; um eine oder mehrere Positionen nach rechts verschoben und es beginnt der nächste Codierschritt&nbsp; $i + 1$.
-Die obere Grafik zeigt die Anfangsbelegung mit der Puffergröße $G = 4$ zu den Zeitpunkten $i = 1$ sowie $i = 4$.
+Die obere Grafik zeigt die Anfangsbelegung mit der Puffergröße&nbsp; $G = 4$&nbsp; zu den Zeitpunkten&nbsp; $i = 1$&nbsp; sowie&nbsp; $i = 4$.
-*Zum Zeitpunkt $i = 1$ ist der Suchpuffer leer, so dass die Coderausgabe $(0, 0,$ <b>B</b>$)$ lautet.
+*Zum Zeitpunkt&nbsp; $i = 1$&nbsp; ist der Suchpuffer leer, so dass die Coderausgabe&nbsp; $(0, 0,$ <b>B</b>$)$&nbsp; lautet.
-*Nach der Verschiebung um eine Position beinhaltet der Suchpuffer ein <b>B</b>, aber keinen String, der mit <b>A</b> anfängt. Das zweite Zahlentriple ist somit $(0, 0,$ <b>A</b>$)$.
+*Nach der Verschiebung um eine Position beinhaltet der Suchpuffer ein&nbsp; <b>B</b>, aber keinen String, der mit&nbsp; <b>A</b>&nbsp; anfängt.&nbsp; Das zweite Zahlentriple ist somit&nbsp; $(0, 0,$ <b>A</b>$)$.
-*Die Ausgabe für $i = 3$ lautet $(0, 0,$ <b>R</b>$)$, da im Suchpuffer auch jetzt keine mit <b>R</b> beginnende Zeichenfolge zu finden ist.
+*Die Ausgabe für&nbsp; $i = 3$&nbsp; lautet&nbsp; $(0, 0,$ <b>R</b>$)$, da im Suchpuffer auch jetzt keine mit&nbsp; <b>R</b>&nbsp; beginnende Zeichenfolge zu finden ist.
-Die Momentaufnahme zum Zeitpunkt $i = 4$ ist ebenfalls in der Grafik angegeben. Gesucht ist nun die Zeichenfolge im Suchpuffer, die mit dem Vorschautext <b>BARA</b> am besten übereinstimmt. Übertragen wird wieder ein Zahlentriple $(P,\ L,\ Z)$, aber nun mit folgender Bedeutung:
+Die Momentaufnahme zum Zeitpunkt&nbsp; $i = 4$&nbsp; ist ebenfalls in der Grafik angegeben.&nbsp; Gesucht ist nun die Zeichenfolge im Suchpuffer, die mit dem Vorschautext&nbsp; <b>BARA</b>&nbsp; am besten übereinstimmt.&nbsp; Übertragen wird wieder ein Zahlentriple&nbsp; $(P,\ L,\ Z)$, aber nun mit folgender Bedeutung:
-* $P$ gibt die Position im (roten) Suchpuffer an, bei der die Übereinstimmung beginnt. Die $P$&ndash;Werte der einzelnen Speicherplätze kann man der Grafik entnehmen.
+* $P$&nbsp; gibt die Position im (roten) Suchpuffer an, bei der die Übereinstimmung beginnt.&nbsp; Die&nbsp; $P$&ndash;Werte der einzelnen Speicherplätze kann man der Grafik entnehmen.
-* $L$ bezeichnet die Anzahl der Zeichen im Suchpuffer, die beginnend bei $P$ mit dem aktuellen String im Vorschaupuffer übereinstimmen.
+* $L$&nbsp; bezeichnet die Anzahl der Zeichen im Suchpuffer, die beginnend bei&nbsp; $P$&nbsp; mit dem aktuellen String im Vorschaupuffer übereinstimmen.
-* $Z$ bezeichnet schließlich das erste Zeichen im Vorschaupuffer, das sich vom gefundenen Übereinstimmungs&ndash;String  im Suchpuffer unterscheidet.
+* $Z$&nbsp; bezeichnet schließlich das erste Zeichen im Vorschaupuffer, das sich vom gefundenen Übereinstimmungs&ndash;String  im Suchpuffer unterscheidet.
-Je größer der LZ77&ndash;Parameter $G$ ist, um so leichter findet man eine möglichst lange Übereinstimmung. In der Teilaufgabe '''(4)''' werden Sie feststellen, dass die LZ77&ndash;Codierung mit $G = 5$ ein besseres Ergebnis liefert als diejenige mit $G = 4$.
+Je größer der LZ77&ndash;Parameter&nbsp; $G$&nbsp; ist, um so leichter findet man eine möglichst lange Übereinstimmung.&nbsp; In der Teilaufgabe&nbsp; '''(4)'''&nbsp; werden Sie feststellen, dass die LZ77&ndash;Codierung mit&nbsp; $G = 5$&nbsp; ein besseres Ergebnis liefert als diejenige mit&nbsp; $G = 4$.
-* Aufgrund der nachfolgenden Binärdarstellung von $P$ wird man allerdings $G$ stets als Zweierpotenz wählen, so dass $G$ mit $\log_2 \ P$ Bit darstellbar ist ($G = 8$ &nbsp; &#8658; &nbsp; dreistellige Binärzahl $P$).
+* Aufgrund der späteren Binärdarstellung von&nbsp; $P$ wird&nbsp; man allerdings&nbsp; $G$&nbsp; stets als Zweierpotenz wählen, so dass&nbsp; $G$&nbsp; mit&nbsp; $\log_2 \ P$&nbsp; Bit darstellbar ist&nbsp; $(G = 8$ &nbsp; &#8658; &nbsp; dreistellige Binärzahl&nbsp; $P)$.
-*Das heißt, ein <i>Sliding Window</i> mit $G = 5$ hat eher einen geringen Praxisbezug.
+*Das heißt, ein&nbsp; <i>Sliding Window</i>&nbsp; mit&nbsp; $G = 5$&nbsp; hat eher einen geringen Praxisbezug.
@@ Zeile 35: / Zeile 35: @@
 ''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#LZ77_.E2.80.93_die_Grundform_der_Lempel.E2.80.93Ziv.E2.80.93Algorithmen|LZ77 &ndash; die Grundform der Lempel-Ziv-Algorithmen]] Bezug genommen.
+*Insbesondere wird auf die Seite&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]]&nbsp; Bezug genommen.
-*Die Originalliteratur '''[LZ77]''' zu diesem Verfahren lautet: Ziv, J.; Lempel, A.: ''A Universal Algorithm for Sequential Data Compression.'' In: IEEE Transactions on Information Theory, no. 3, vol. 23, 1977, p. 337–343.
+*Die Originalliteratur&nbsp; [LZ77]&nbsp; zu diesem Verfahren lautet: <br>Ziv, J.; Lempel, A.: ''A Universal Algorithm for Sequential Data Compression.'' In: IEEE Transactions on Information Theory, no. 3, vol. 23, 1977, p. 337–343.
-*Die [[Aufgaben:2.3_Zur_LZ78-Komprimierung|Aufgabe 2.3]] sowie die [[Aufgaben:Aufgabe_2.4:_Zum_LZW-Algorithmus|Aufgabe 2.4]] behandeln andere Lempel&ndash;Ziv-Verfahren in ähnlicher Weise.
+*Die&nbsp; [[Aufgaben:2.3_Zur_LZ78-Komprimierung|Aufgabe 2.3]]&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 45: / Zeile 45: @@
 <quiz display=simple>
-{Wie lautet die LZ77&ndash;Ausgabe mit $G = 4$ beim Schritt $i = 4$?
+{Wie lautet die LZ77&ndash;Ausgabe mit&nbsp; $G = 4$&nbsp; beim Schritt&nbsp; $i = 4$?
-|type="[]"}
+|type="()"}
 - $(0, 0,$ <b>B</b>$)$,
 - $(2, 1,$ <b>A</b>$)$,
@@ Zeile 52: / Zeile 52: @@
-{Welche Aussage gilt für die gleiche Puffergröße $G = 4$ beim Schritt $i = 5$?
+{Welche Aussage gilt für die gleiche Puffergröße&nbsp; $G = 4$&nbsp; beim Schritt&nbsp; $i = 5$?
 |type="[]"}
-+ Im Suchpuffer steht <b>BARA</b>.
++ Im Suchpuffer steht&nbsp; <b>BARA</b>.
-+ Im Vorschaupuffer steht <b>&ndash;BAR</b>.
++ Im Vorschaupuffer steht&nbsp; <b>&ndash;BAR</b>.
-- Die Ausgabe lautet $(0, 0,$ <b>A</b>$)$.
+- Die Ausgabe lautet&nbsp; $(0, 0,$ <b>A</b>$)$.
-{Nach welchem Schritt $i_{\rm Ende}$ ist die Codierung mit $G = 4$ beendet?
+{Nach welchem Schritt&nbsp; $i_{\rm Ende}$&nbsp; ist die Codierung mit&nbsp; $G = 4$&nbsp; beendet?
 |type="{}"}
 $i_{\rm Ende} \ = \ $ { 9 }
-{Nun gelte $G = 5$. Nach welchem Schritt $i_{\rm Ende}$ ist nun die Codierung  beendet?
+{Nun gelte&nbsp; $G = 5$.&nbsp; Nach welchem Schritt&nbsp; $i_{\rm Ende}$&nbsp; ist nun die Codierung  beendet?
 |type="{}"}
 $i_{\rm Ende} \ = \ $ { 6 }

← Nächstältere Version		Version vom 24. September 2018, 14:04 Uhr
Zeile 39:		Zeile 39:
	*Die Originalliteratur '''[LZ77]''' zu diesem Verfahren lautet: Ziv, J.; Lempel, A.: ''A Universal Algorithm for Sequential Data Compression.'' In: IEEE Transactions on Information Theory, no. 3, vol. 23, 1977, p. 337–343.		*Die Originalliteratur '''[LZ77]''' zu diesem Verfahren lautet: Ziv, J.; Lempel, A.: ''A Universal Algorithm for Sequential Data Compression.'' In: IEEE Transactions on Information Theory, no. 3, vol. 23, 1977, p. 337–343.

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

@@ Zeile 80: / Zeile 80: @@
 ===Musterlösung===
 {{ML-Kopf}}
-'''(1)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 3</u>. Im Vorschaupuffer steht zum betrachteten Zeitpunkt <i>i</i> = 4 die Zeichenfolge <b>BARA</b>, und im Suchpuffer in den letzten drei Stellen <b>BAR</b>:
+'''(1)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 3</u>.
 :$$P = 2\hspace{0.05cm},\hspace{0.2cm}L = 3\hspace{0.05cm},\hspace{0.2cm}Z = \boldsymbol{\rm A}\hspace{0.05cm}.$$
-'''(2)'''&nbsp; Richtig sind die <u>beiden ersten Lösungsvorschläge</u>. Der Bindestrich findet sich zum Zeitpunkt <i>i</i> = 5 nicht im Suchpuffer, so dass (0, 0, <b>&ndash;</b>) ausgegeben wird.
 '''(3)'''&nbsp; Die folgende Grafik zeigt das <i>Sliding&ndash;Window</i> und die Coderausgabe zu den Zeitpunkten <i>i</i> &#8805; 5. Nach <i>i</i> = 9 Codierschritten ist der Codiervorgang unter Berücksichtigung von <b>eof</b> beendet &nbsp; &rArr; &nbsp; $\underline{i_{\rm Ende} = 9}$.
-[[Datei:P_ID2438__Inf_Z_2_3c.png|Beispiel zum LZ77–Algorithmus mit <i>G</i> = 4]]
+[[Datei:P_ID2438__Inf_Z_2_3c.png|frame|Beispiel zum LZ77–Algorithmus mit <i>G</i> = 4]]
 '''(4)'''&nbsp; Bei größerer Puffergröße (<i>G</i> = 5 anstelle von <i>G</i> = 4) ist die Codierung schon nach dem 6. Codierschritt  abgeschlossen &nbsp; &rArr; &nbsp; $\underline{i_{\rm Ende} = 6}$.

@@ Zeile 29: / Zeile 29: @@
 *Insbesondere wird auf die Seite [[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]] Bezug genommen.
 *Die Originalliteratur [LZ77] zu diesem Verfahren lautet: Ziv, J.; Lempel, A.: ''A Universal Algorithm for Sequential Data Compression.'' In: IEEE Transactions on Information Theory, no. 3, vol. 23, 1977, p. 337–343.
-*Sollte die Eingabe des Zahlenwertes &bdquo;0&rdquo; erforderlich sein, so geben Sie bitte &bdquo;0.&rdquo; ein.
 *Die [[Aufgaben:2.3_Zur_LZ78-Komprimierung|Aufgabe 2.3]] sowie die [[Aufgaben:2.4_LZW-Algorithmus|Aufgabe 2.4]] behandeln andere LZ-Verfahren in ähnlicher Weise.