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

Aus LNTwww
Wechseln zu:Navigation, Suche
K (Textersetzung - „*Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.“ durch „ “)
Zeile 3: Zeile 3:
 
}}
 
}}
  
[[Datei:P_ID2436__Inf_Z_2_3.png|right|LZ77: Sliding–Window mit <i>G</i> = 4 und <i>G</i> = 5 ]]
+
[[Datei:P_ID2436__Inf_Z_2_3.png|right|frame|LZ77: &nbsp; Sliding–Window mit <i>G</i> = 4 und <i>G</i> = 5 ]]
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 [[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.
  
 
Anzumerken ist:
 
Anzumerken ist:
 
* Während beim Nachfolger &bdquo;LZ78&rdquo; sukzessive ein globales Wörterbuch aufgebaut wird, verwendet &bdquo;LZ77&rdquo;  ein lokales Wörterbuch.
 
* 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 <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 <i>G</i> Speicherplätzen.
+
* 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.
* Jeder Codierschritt <i>i&nbsp;</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>.
+
* 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$.
* 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.
+
* 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$.
  
  
Die obere Grafik zeigt die Anfangsbelegung mit der 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 mit <b>R</b> beginnende Zeichenfolge zu finden ist.
+
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>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 = 3$ lautet $(0, 0,$ <b>R</b>$)$, da im Suchpuffer auch jetzt keine mit <b>R</b> 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:
 +
* $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.
 +
* $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&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$.
 +
* 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$).
 +
*Das heißt, ein <i>Sliding Window</i> mit $G = 5$ 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 log<sub>2</sub> <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.
 
  
  
Zeile 28: Zeile 37:
 
*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 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 [[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.
+
*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 LZ-Verfahren in ähnlicher Weise.
+
*Die [[Aufgaben:2.3_Zur_LZ78-Komprimierung|Aufgabe 2.3]] sowie die [[Aufgaben:2.4_LZW-Algorithmus|Aufgabe 2.4]] 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 beim Schritt <i>i</i> = 4?
+
{Wie lautet die LZ77&ndash;Ausgabe mit $G = 4$ beim Schritt $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 beim Schritt <i>i</i> = 5?
+
{Welche Aussage gilt für die gleiche Puffergröße $G = 4$ beim Schritt $i = 5$?
 
|type="[]"}
 
|type="[]"}
 
+ Im Suchpuffer steht <b>BARA</b>.
 
+ Im Suchpuffer steht <b>BARA</b>.
 
+ Im Vorschaupuffer steht <b>&ndash;BAR</b>.
 
+ Im Vorschaupuffer steht <b>&ndash;BAR</b>.
- Die Ausgabe lautet (0, 0, <b>A</b>).
+
- Die Ausgabe lautet $(0, 0,$ <b>A</b>$)$.
  
  
{Nach welchem Schritt <i>i</i><sub>Ende</sub> ist die Codierung beendet?
+
{Nach welchem Schritt $i_{\rm Ende}$ ist die Codierung mit $G = 4$ beendet?
 
|type="{}"}
 
|type="{}"}
$G = 4\text{:}\ \ i_{\rm Ende} \ =$ { 9 }  
+
$i_{\rm Ende} \ = \ $ { 9 }  
  
  
{Nun gelte <i>G</i> = 5. Nach welchem Schritt <i>i</i><sub>Ende</sub> ist dann die Codierung  beendet?
+
{Nun gelte $G = 5$. Nach welchem Schritt $i_{\rm Ende}$ ist nun die Codierung  beendet?
 
|type="{}"}
 
|type="{}"}
$G = 5\text{:}\ \ i_{\rm Ende} \ =$ { 6 }  
+
$i_{\rm Ende} \ = \ $ { 6 }  
  
  

Version vom 24. September 2018, 13:45 Uhr

LZ77:   Sliding–Window mit G = 4 und G = 5

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 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 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$   ⇒   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

(1)  Richtig ist der Lösungsvorschlag 3. Im Vorschaupuffer steht zum betrachteten Zeitpunkt i = 4 die Zeichenfolge BARA, und im Suchpuffer 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, so dass (0, 0, ) ausgegeben wird.


(3)  Die folgende Grafik zeigt das Sliding–Window und die Coderausgabe zu den Zeitpunkten 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 = 4

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

Beispiel zum LZ77–Algorithmus mit G = 5

(5)  Richtig ist Aussage 1. Die Aussage 2 trifft dagegen nicht zu:

  • 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. Berücksichtigen Sie, 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 NI kleiner wäre als NP + NL, beispielsweise NI = 6. Das würde aber bedeuten, dass man die Wörterbuchgröße auf I = 26 = 64 begrenzen müsste. Dies reicht für große Dateien nicht aus.
  • Diese Überschlagsrechnung basiert allerdings auf einer einheitlichen Bitanzahl für den Index . Mit variabler Bitanzahl für den Index kann man etliche Bit einsparen, indem man nur mit so vielen Bit überträgt, wie es für den Codierschritt 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.