Aufgaben:Aufgabe 2.3Z: Zur LZ77-Codierung: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
(11 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 3: Zeile 3:
 
}}
 
}}
  
[[Datei:P_ID2436__Inf_Z_2_3.png|right|]]
+
[[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 Aufgabe A2.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&nbsp; <i>Sliding Window</i>, 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.
 +
* 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$.
  
:* Während beim Nachfolger LZ78 sukzessive ein globales Wörterbuch aufgebaut wird, verwendet LZ77  ein lokales Wörterbuch.
 
  
:* Das LZ77&ndash;Verfahren arbeitet mit einem <i>Sliding Window</i>, das schrittweise über den Eingabetext verschoben wird.
+
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&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&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&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.
  
:* 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 <i>G</i> Speicherplätzen.
 
  
:* Jeder Codierschritt <i>i</i> wird durch ein Zahlentriple (<i>P</i>, <i>L</i>, <i>Z</i>) charakterisiert. Hierbei sind <i>P</i> und <i>L</i> Integergrößen und <i>Z</i> ein Character. Übertragen werden die Binärdarstellungen von <i>P</i>, <i>L</i> und <i>Z</i>.
+
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$&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$&nbsp; bezeichnet die Anzahl der Zeichen im Suchpuffer, die beginnend bei&nbsp; $P$&nbsp; mit dem aktuellen String im Vorschaupuffer übereinstimmen.
 +
* $Z$&nbsp; bezeichnet schließlich das erste Zeichen im Vorschaupuffer, das sich vom gefundenen Übereinstimmungs&ndash;String  im Suchpuffer unterscheidet.
  
:* 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>i</i> + 1.
 
  
:Die obere Grafik zeigt die Anfangsbelegung mit Puffergröße <i>G</i> = 4 zu den Zeitpunkten <i>i</i> = 1 sowie <i>i</i> = 4. Zum Zeitpunkt <i>i</i> = 1 ist der Suchpuffer leer, so dass die Coderausgabe (0, 0, <b>B</b>) 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>). Die Ausgabe für <i>i</i> = 3 lautet (0, 0, <b>R</b>), da im Suchpuffer auch jetzt keine Zeichenfolge zu finden ist, die mit <b>R</b> beginnt.
+
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)$.  
 +
*Das heißt, ein&nbsp; <i>Sliding Window</i>&nbsp; mit&nbsp; $G = 5$&nbsp; hat eher einen geringen Praxisbezug.
  
:Die Momentaufnahme zum Zeitpunkt <i>i</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 (<i>P</i>, <i>L</i>, <i>Z</i>), aber nun mit folgender Bedeutung:
 
  
:* <i>P</i> gibt die Position im (roten) Suchpuffer an, bei der die gefundene Übereinstimmung beginnt. Die jeweiligen <i>P</i>&ndash;Werte für die einzelnen Speicherplätze können der Grafik entnommen werden.
 
  
:* <i>L</i> bezeichnet die Anzahl der Zeichen im Suchpuffer, die beginnend bei <i>P</i> mit dem aktuellen String im Vorschaupuffer übereinstimmen.
 
  
:* <i>Z</i> 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 <i>G</i> ist, um so leichter findet man eine möglichst lange Übereinstimmung. In der Teilaufgabe (4) werden Sie feststellen, dass die LZ77&ndash;Codierung mit <i>G</i> = 5 ein besseres Ergebnis liefert als diejenige mit <i>G</i> = 4. Aufgrund der nachfolgenden Binärdarstellung von <i>P</i> wird man allerdings <i>G</i> stets als Zweierpotenz wählen, so dass <i>G</i> mit ld <i>P</i> Bit darstellbar ist (<i>G</i> = 8 &nbsp;&#8658;&nbsp; dreistellige Binärzahl <i>P</i>). Das heißt, ein <i>Sliding Window</i> mit <i>G</i> = 5 hat eher einen geringen Praxisbezug.
+
''Hinweise:''
 
+
*Die Aufgabe gehört zum  Kapitel&nbsp; [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch|Komprimierung nach Lempel, Ziv und Welch]].
:<b>Hinweis:</b> Die Aufgabe gehört zum Themengebiet von Kapitel 2.2.
+
*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&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 36: Zeile 45:
  
 
<quiz display=simple>
 
<quiz display=simple>
{Wie lautet die LZ77&ndash;Ausgabe mit <i>G</i> = 4 bei Schritt <i>i</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>),
+
- $(0, 0,$ <b>B</b>$)$,
- (2, 1, <b>A</b>),
+
- $(2, 1,$ <b>A</b>$)$,
+ (2, 3, <b>A</b>).
+
+ $(2, 3,$ <b>A</b>$)$.
  
  
{Welche Aussage gilt für die gleiche Puffergröße <i>G</i> = 4 bei Schritt <i>i</i> = 5?
+
{Welche Aussage gilt für die gleiche Puffergröße&nbsp; $G = 4$&nbsp; beim Schritt&nbsp; $i = 5$?
 
|type="[]"}
 
|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>i</i> ist die Codierung beendet?
+
{Nach welchem Schritt&nbsp; $i_{\rm Ende}$&nbsp; ist die Codierung mit&nbsp; $G = 4$&nbsp; beendet?
 
|type="{}"}
 
|type="{}"}
$G = 4:\ Nach\ i$ = { 9 3% } $Codierschritten$
+
$i_{\rm Ende} \ = \ $ { 9 }  
  
  
{Nun gelte <i>G</i> = 5. Nach welchem Schritt <i>i</i> ist dann die Codierung  beendet?
+
{Nun gelte&nbsp; $G = 5$.&nbsp; Nach welchem Schritt&nbsp; $i_{\rm Ende}$&nbsp; ist nun die Codierung  beendet?
 
|type="{}"}
 
|type="{}"}
$G = 5:\ Nach\ i$ = { 6 3% } $Codierschritten$
+
$i_{\rm Ende} \ = \ $ { 6 }  
  
  
{Welche Vorteile hat LZ78 gegenüber LZ77 bei <u>sehr großen</u> Dateien?
+
{Welche Vorteile hat LZ78 gegenüber LZ77 bei &bdquo;sehr großen&rdquo; Dateien?
 
|type="[]"}
 
|type="[]"}
 
+ Man findet häufiger bereits abgelegte Phrasen im Wörterbuch.
 
+ Man findet häufiger bereits abgelegte Phrasen im Wörterbuch.
Zeile 71: Zeile 80:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
:<b>1.</b>&nbsp;&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>:
+
[[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&nbsp; $i = 4$&nbsp; die Zeichenfolge&nbsp; <b>BARA</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}.$$
 
:$$P = 2\hspace{0.05cm},\hspace{0.2cm}L = 3\hspace{0.05cm},\hspace{0.2cm}Z = \boldsymbol{\rm A}\hspace{0.05cm}.$$
  
:<b>2.</b>&nbsp;&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.
 
  
:<b>3.</b>&nbsp;&nbsp;Die folgende Grafik zeigt das <i>Sliding&ndash;Window</i> und die Coderausgabe zu den Zeitpunkten <i>i</i> &#8805; 5. Nach <u><i>i</i> = 9</u> Codierschritten ist der Codiervorgang unter Berücksichtigung von <b>eof</b> beendet.
 
[[Datei:P_ID2438__Inf_Z_2_3c.png|center|]]
 
  
:<b>4.</b>&nbsp;&nbsp;Bei größerer Puffergröße (<i>G</i> = 5 anstelle von <i>G</i> = 4) ist die Codierung schon nach dem Codierschritt <u><i>i</i> = 6</u> abgeschlossen. Ein Vergleich der beiden Grafiken zeigt, dass sich für <i>G</i> = 5 gegenüber <i>G</i> = 4 nichts ändert bis einschließlich <i>i</i> = 5. Aufgrund des größeren Puffers lässt sich aber nun <b>BAR</b> gemeinsam mit <b>end&ndash;of&ndash;file</b> in einem einzigen Schritt codieren, während mit <i>G</i> = 4 hierfür vier Schritte notwendig waren.
+
'''(2)'''&nbsp; Richtig sind die <u>beiden ersten Lösungsvorschläge</u>:
[[Datei:P_ID2439__Inf_Z_2_3d.png|center|]]
+
*Der Bindestrich findet sich zum Zeitpunkt&nbsp; $i = 5$&nbsp; nicht im Suchpuffer.  
 +
*Ausgegeben wird&nbsp; $(0, 0,$ <b>&ndash;</b>$)$.
  
:<b>5.</b>&nbsp;&nbsp;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 <i>G</i> Zeichen vorher im Text aufgetreten sind. Dagegen sind bei LZ78 alle Phrasen im globalen Wörterbuch abgelegt. Richtig ist <u>Aussage 1</u>.
 
  
:Die Aussage 2 trifft dagegen nicht zu.
 
  
:<ul class="liste_ohne"><li>Richtig ist zwar, dass bei LZ78 nur Pärchen (<i>I</i>, <i>Z</i>) übertragen werden müssen, während bei LZ77 jeder Codierschritt durch ein Triple (<i>P</i>, <i>L</i>, <i>Z</i>) gekennzeichnet ist. Das bedeutet aber noch nicht, dass pro Codierschritt auch weniger Bit übertragen werden müssen.
+
'''(3)'''&nbsp; Die obere Grafik zeigt das&nbsp; <i>Sliding&ndash;Window</i>&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}$.
  
:<ul class="liste_ohne"><li>Betrachten wir beispielhaft die Puffergröße <i>G</i> = 8. Bei LZ77 muss man dann <i>P</i> mit 3 Bit und <i>L</i> mit 4 Bit dargestellen. Berücksichtigen Sie, dass die gefundene Übereinstimmung zwischen Vorschaupuffer und Suchpuffer auch im Vorschaupuffer enden darf.
 
  
:<ul class="liste_ohne"><li>Das neue Zeichen <i>Z</i> benötigt bei LZ78 genau die gleiche Bitanzahl wie bei LZ77 (nämlich 2 Bit), wenn man wie hier vom Symbolumfang <i>M</i> = 4 ausgeht). Die Aussage 2 wäre nur dann richtig, wenn <i>N</i><sub>I</sub> kleiner wäre als <i>N</i><sub>P</sub> + <i>N</i><sub>L</sub>, beispielsweise <i>N</i><sub>I</sub> = 6. Das würde aber bedeuten, dass man die Wörterbuchgröße auf <i>I</i> = 2<sup>6</sup> = 64 begrenzen müsste. Dies reicht für große Dateien nicht aus.
 
  
:<ul class="liste_ohne"><li>Diese Überschlagsrechnung basiert allerdings auf einer einheitlichen Bitanzahl für den Index <i>I</i>. Mit variabler Bitanzahl für den Index kann man etliche Bit einsparen, indem man <i>I</i> nur mit so vielen Bit überträgt, wie es für den Codierschritt <i>i</i> 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.
+
[[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&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&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&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.&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&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&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&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&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&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ß}}
 
{{ML-Fuß}}
  

Version vom 23. Januar 2020, 16:17 Uhr

Sliding–Window mit  $G = 4$  und  $G = 5$
(gültig für „LZ77”

In der  Aufgabe 2.3  sollten Sie  BARBARA–BAR  (String der Länge  $11$, vier verschiedene Zeichen)  mit dem LZ78–Algorithmus komprimieren. 

In dieser Aufgabe verwenden wir den gleichen Text zur Demonstration der LZ77–Komprimierung.  Anzumerken ist:

  • Während beim Nachfolger „LZ78” sukzessive ein globales Wörterbuch aufgebaut wird, verwendet „LZ77” ein lokales Wörterbuch.
  • Das LZ77–Verfahren arbeitet mit einem  Sliding Window, das schrittweise über den Eingabetext verschoben wird.
  • Dieses „gleitende Fenster” ist unterteilt in den  Vorschaupuffer  (in der Grafik blau hinterlegt) und den  Suchpuffer  (rote Hinterlegung).  Beide Puffer haben je eine Größe von  $G$  Speicherplätzen.
  • Jeder Codierschritt  $i$  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$.
  • Nach der Übertragung wird das  Sliding Window  um eine oder mehrere Positionen nach rechts verschoben und es beginnt der nächste Codierschritt  $i + 1$.


Die obere Grafik zeigt die Anfangsbelegung mit der Puffergröße  $G = 4$  zu den Zeitpunkten  $i = 1$  sowie  $i = 4$.

  • Zum Zeitpunkt  $i = 1$  ist der Suchpuffer leer, so dass die Coderausgabe  $(0, 0,$ B$)$  lautet.
  • Nach der Verschiebung um eine Position beinhaltet der Suchpuffer ein  B, aber keinen String, der mit  A  anfängt.  Das zweite Zahlentriple ist somit  $(0, 0,$ A$)$.
  • Die Ausgabe für  $i = 3$  lautet  $(0, 0,$ R$)$, da im Suchpuffer auch jetzt keine mit  R  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  BARA  am besten übereinstimmt.  Übertragen wird wieder ein Zahlentriple  $(P,\ L,\ Z)$, aber nun mit folgender Bedeutung:

  • $P$  gibt die Position im (roten) Suchpuffer an, bei der die Übereinstimmung beginnt.  Die  $P$–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.
  • $Z$  bezeichnet schließlich das erste Zeichen im Vorschaupuffer, das sich vom gefundenen Übereinstimmungs–String im Suchpuffer unterscheidet.


Je größer der LZ77–Parameter  $G$  ist, um so leichter findet man eine möglichst lange Übereinstimmung.  In der Teilaufgabe  (4)  werden Sie feststellen, dass die LZ77–Codierung mit  $G = 5$  ein besseres Ergebnis liefert als diejenige mit  $G = 4$.

  • Aufgrund der späteren 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$   ⇒   dreistellige Binärzahl  $P)$.
  • Das heißt, ein  Sliding Window  mit  $G = 5$  hat eher einen geringen Praxisbezug.



Hinweise:


Fragebogen

1

Wie lautet die LZ77–Ausgabe mit  $G = 4$  beim Schritt  $i = 4$?

$(0, 0,$ B$)$,
$(2, 1,$ A$)$,
$(2, 3,$ A$)$.

2

Welche Aussage gilt für die gleiche Puffergröße  $G = 4$  beim Schritt  $i = 5$?

Im Suchpuffer steht  BARA.
Im Vorschaupuffer steht  –BAR.
Die Ausgabe lautet  $(0, 0,$ A$)$.

3

Nach welchem Schritt  $i_{\rm Ende}$  ist die Codierung mit  $G = 4$  beendet?

$i_{\rm Ende} \ = \ $

4

Nun gelte  $G = 5$.  Nach welchem Schritt  $i_{\rm Ende}$  ist nun die Codierung beendet?

$i_{\rm Ende} \ = \ $

5

Welche Vorteile hat LZ78 gegenüber LZ77 bei „sehr großen” Dateien?

Man findet häufiger bereits abgelegte Phrasen im Wörterbuch.
Pro Codierschritt müssen weniger Bit übertragen werden.


Musterlösung

Beispiel zum LZ77–Algorithmus mit  $G = 4$

(1)  Richtig ist der Lösungsvorschlag 3.

  • Im Vorschaupuffer steht zum betrachteten Zeitpunkt  $i = 4$  die Zeichenfolge  BARA.
  • Im Suchpuffer steht in den letzten drei Stellen  BAR:
$$P = 2\hspace{0.05cm},\hspace{0.2cm}L = 3\hspace{0.05cm},\hspace{0.2cm}Z = \boldsymbol{\rm A}\hspace{0.05cm}.$$


(2)  Richtig sind die beiden ersten Lösungsvorschläge:

  • Der Bindestrich findet sich zum Zeitpunkt  $i = 5$  nicht im Suchpuffer.
  • Ausgegeben wird  $(0, 0,$ $)$.


(3)  Die obere Grafik zeigt das  Sliding–Window  und die Coderausgabe zu den Zeiten  $i>5$.

  • Nach  $i = 9$  Codierschritten ist der Codiervorgang unter Berücksichtigung von  eof  beendet   ⇒   $\underline{i_{\rm Ende} = 9}$.


Beispiel zum LZ77–Algorithmus mit  $G = 5$

(4)  Bei größerer Puffergröße  $(G = 5$  anstelle von  $G = 4)$  ist die Codierung schon nach dem 6. Codierschritt abgeschlossen   ⇒   $\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.
  • Aufgrund des größeren Puffers lässt sich aber nun  BAR  gemeinsam mit  eof  (end-of-file) in einem einzigen Schritt codieren, während mit  $G = 4$  hierfür vier Schritte notwendig waren.


(5)  Richtig ist nur die Aussage 1.

  • 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.
  • 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.
  • Betrachten wir beispielhaft die Puffergröße  $G = 8$.  Bei LZ77 muss man dann  $P$  mit drei Bit und  $L$  mit vier Bit dargestellen.  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.
  • 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.
  • 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.
  • Prinzipiell ändert das aber nichts an der Beschränkung der Wörterbuchgröße, was bei großen Dateien stets zu Problemen führen wird.