Difference between revisions of "Information Theory/Compression According to Lempel, Ziv and Welch"

From LNTwww
Line 7: Line 7:
  
  
==Statische und dynamische Wörterbuchtechniken ==  
+
==Static and dynamic dictionary techniques ==  
 
<br>
 
<br>
Viele Datenkomprimierungsverfahren verwenden Wörterbücher.&nbsp; Die Idee ist dabei die Folgende:  
+
Many data compression methods use dictionaries.&nbsp; the idea is the following:  
*Man konstruiere eine Liste der Zeichenmuster, die im Text vorkommen,  
+
*Construct a list of character patterns that occur in the text,  
*und codiere diese Muster als Indizes der Liste.  
+
*and encode these patterns as indices of the list.  
  
  
Besonders effizient ist diese Vorgehensweise, wenn sich bestimmte Muster im Text häufig wiederholen und dies bei der Codierung auch berücksichtigt wird.&nbsp; Hierbei unterscheidet man:
+
This procedure is particularly efficient if certain patterns are repeated frequently in the text and this is also taken into account in the coding.&nbsp; A distinction is made here
*Verfahren mit statischem Wörterbuch,
+
*Procedure with static dictionary,
*Verfahren mit dynamischem Wörterbuch.
+
*Procedure with dynamic dictionary.
  
  
 
<br><br>
 
<br><br>
$\text{(1) Verfahren mit statischem Wörterbuch}$
+
$\text{(1) Procedure with static dictionary}$
  
Ein statisches Wörterbuch ist nur für ganz spezielle Anwendungen sinnvoll, zum Beispiel für eine Datei der folgenden Form:
+
A static dictionary is only useful for very special applications, for example for a file of the following form:
  
[[File:P_ID2424__Inf_T_2_2_S1a.png|center|frame|Zu bearbeitende Datei in diesem Abschnitt]]
+
[[File:P_ID2424__Inf_T_2_2_S1a.png|center|frame|File to edit in this section]]
  
Beispielsweise ergibt sich mit den Zuordnungen
+
For example, the assignments result in
 
      
 
      
 
:$$"\boldsymbol{\rm 0}" \hspace{0.05cm} \mapsto \hspace{0.05cm} \boldsymbol{\rm 000000} \hspace{0.05cm},\hspace{0.15cm} ... \hspace{0.15cm},\hspace{0.05cm}
 
:$$"\boldsymbol{\rm 0}" \hspace{0.05cm} \mapsto \hspace{0.05cm} \boldsymbol{\rm 000000} \hspace{0.05cm},\hspace{0.15cm} ... \hspace{0.15cm},\hspace{0.05cm}
Line 48: Line 48:
 
"\boldsymbol{\rm ,\_\hspace{-0.03cm}\_Wohnort\hspace{-0.1cm}:\hspace{-0.05cm}\_\hspace{-0.03cm}\_}" \hspace{0.05cm} \mapsto \hspace{0.05cm} \boldsymbol{\rm 010010} \hspace{0.05cm},\hspace{0.15cm} ... \hspace{0.15cm}$$
 
"\boldsymbol{\rm ,\_\hspace{-0.03cm}\_Wohnort\hspace{-0.1cm}:\hspace{-0.05cm}\_\hspace{-0.03cm}\_}" \hspace{0.05cm} \mapsto \hspace{0.05cm} \boldsymbol{\rm 010010} \hspace{0.05cm},\hspace{0.15cm} ... \hspace{0.15cm}$$
  
für die mit jeweils sechs Bit pro Zeichen binär–quellencodierte erste Zeile des obigen Textes:
+
for the first line of the above text, binary source coded with six bits per character:
 
      
 
      
 
:$$\boldsymbol{010000} \hspace{0.15cm}\boldsymbol{100000} \hspace{0.15cm}\boldsymbol{100001} \hspace{0.15cm}\boldsymbol{100100} \hspace{0.15cm}\boldsymbol{101011} \hspace{0.3cm}
 
:$$\boldsymbol{010000} \hspace{0.15cm}\boldsymbol{100000} \hspace{0.15cm}\boldsymbol{100001} \hspace{0.15cm}\boldsymbol{100100} \hspace{0.15cm}\boldsymbol{101011} \hspace{0.3cm}
Line 73: Line 73:
  
 
{{BlaueBox|TEXT=
 
{{BlaueBox|TEXT=
$\text{Fazit:}$&nbsp;  
+
$\text{Conclusion:}$&nbsp;  
Bei dieser spezifischen Anwendung lässt sich die erste Zeile mit&nbsp; $14 · 6 = 84$&nbsp; Bit darstellen.  
+
In this specific application the first line can be displayed with&nbsp; $14 \cdot 6 = 84$&nbsp; Bit.  
*Dagegen würde man bei herkömmlicher Binärcodierung&nbsp; $39 · 7 = 273$&nbsp; Bit benötigen, weil:  
+
*In contrast, conventional binary coding would require&nbsp; $39 \cdot 7 = 273$&nbsp; bits since:  
*Aufgrund der Kleinbuchstaben im Text reichen hier sechs Bit pro Zeichen nicht aus.  
+
*Because of the lowercase letters in the text, six bits per character are not sufficient here.  
*Für den gesamten Text ergeben sich&nbsp; $103 · 6 = 618$&nbsp; Bit gegenüber&nbsp; $196 · 7 = 1372$&nbsp; Bit.  
+
*For the entire text, this results in&nbsp; $103 \cdot 6 = 618$&nbsp; Bit versus&nbsp; $196 \cdot 7 = 1372$&nbsp; Bit.  
*Allerdings muss die Codetabelle auch dem Empfänger bekannt sein.}}
+
*However, the code table must also be known to the recipient.}}
  
  
 
<br><br>
 
<br><br>
$\text{(2) Verfahren mit dynamischem Wörterbuch}$
+
$\text{(2) Procedure with dynamic dictionary}$
  
Alle relevanten Komprimierungsverfahren arbeiten allerdings nicht mit statischem Wörterbuch, sondern mit ''dynamischen Wörterbüchern'', die erst während der Codierung sukzessive entstehen:
+
Nevertheless, all relevant compression methods do not work with static dictionaries, but with ''dynamic dictionaries'', which are created successively only during the coding:
*Solche Verfahren sind flexibel einsetzbar und müssen nicht an die Anwendung adaptiert werden.&nbsp; Man spricht von ''universellen Quellencodierverfahren''.
+
*Such procedures are flexible and do not have to be adapted to the application &nbsp; One speaks of ''universal source coding procedures''.
*Dann genügt ein einziger Durchlauf, während bei statischem Wörterbuch die Datei vor dem Codiervorgang erst analysiert werden muss.
+
*A single pass is sufficient, whereas with a static dictionary the file must first be analyzed before the encoding process.
*An der Sinke wird das dynamische Wörterbuch in gleicher Weise generiert wie bei der Quelle.&nbsp; Damit entfällt die Übertragung des Wörterbuchs.
+
*At the sink, the dynamic dictionary is generated in the same way as for the source .&nbsp; this eliminates the need to transfer the dictionary.
  
  
[[File:P_ID2926__Inf_T_2_2_S1b_neu.png|frame|Auszug aus dem Hexdump eines natürlichen Bildes im BMP–Format]]
+
[[File:P_ID2926__Inf_T_2_2_S1b_neu.png|frame|Extract from the hexdump of a natural image in BMP format]].
 
{{GraueBox|TEXT=
 
{{GraueBox|TEXT=
$\text{Beispiel 1:}$&nbsp;  
+
$\text{Example 1:}$&nbsp;  
Die Grafik zeigt einen kleinen Ausschnitt von&nbsp; $80$&nbsp; Byte einer&nbsp; [[Digital_Signal_Transmission/Anwendungen_bei_Multimedia–Dateien#Bilder_im_BMP.E2.80.93Format_.281.29|BMP–Datei]]&nbsp; in Hexadezimaldarstellung.&nbsp; Es handelt sich um die unkomprimierte Darstellung eines natürlichen Bildes.
+
The graphic shows a small section of&nbsp; $80$&nbsp; Byte of a&nbsp; [[Digital_Signal_Transmission/Applications for Multimedia Files#Pictures_in_BMP.E2.80.93Format_.281.29|BMP-File]]&nbsp; in hexadecimal representation.&nbsp; It is the uncompressed representation of a natural picture.
  
*Man erkennt, dass in diesem kleinen Ausschnitt einer Landschaftsaufnahme die Bytes&nbsp; $\rm FF$,&nbsp; $\rm 55$&nbsp; und&nbsp; $\rm 47$&nbsp; sehr häufig auftreten.  
+
*You can see that in this small section of a landscape image the bytes&nbsp; $\rm FF$,&nbsp; $\rm 55$&nbsp; and&nbsp; $\rm 47$&nbsp; occur very frequently.  
*Eine Datenkomprimierung ist deshalb erfolgversprechend.  
+
*Data compression is therefore promising.  
*Da aber an anderen Stellen der&nbsp; $\text{4 MByte}$–Datei oder bei anderem Bildinhalt andere Bytekombinationen dominieren, wäre hier die Verwendung eines statischen Wörterbuchs nicht zielführend.}}
+
*But since other parts of the&nbsp; $\text{4 MByte}$ file or other byte combinations dominate in other image contents, the use of a static dictionary would not be appropriate here.}}
  
  
[[File:P_ID2927__Inf_T_2_2_S1c_GANZ_neu.png|right|frame|Mögliche Codierung einer einfachen Grafik]]
+
[[File:P_ID2927__Inf_T_2_2_S1c_GANZ_neu.png|right|frame|Possible encoding of a simple graphic]]
 
{{GraueBox|TEXT=
 
{{GraueBox|TEXT=
$\text{Beispiel 2:}$&nbsp;  
+
$\text{Example 2:}$&nbsp;  
Bei einer künstlich erzeugten Grafik – zum Beispiel einem Formular – könnte man dagegen durchaus mit  statischem Wörterbuch arbeiten.  
+
For an artificially created graphic, for example a form, you could work with a static dictionary.  
  
Wir betrachten hier ein S/W–Bild mit&nbsp; $27 × 27$&nbsp; Pixeln, wobei die Zuordnung „Schwarz”  &nbsp; ⇒ &nbsp; '''0'''&nbsp; und „Weiß”  &nbsp; ⇒ &nbsp; '''1'''&nbsp; vereinbart wurde.
+
We are looking at a b/w image with&nbsp; $27 × 27$&nbsp; pixels, where the mapping "black" &nbsp; ⇒ &nbsp; '''0'''&nbsp; and "white" &nbsp; ⇒ &nbsp; '''1'''&nbsp; has been agreed upon.
  
*Oben  (schwarze Markierung) wird jede Zeile durch&nbsp; $27$&nbsp; Nullen beschrieben.
+
*At the top (black marker) each line is described by&nbsp; $27$&nbsp; zeros.
*In der Mitte (blaue Markierung) wechseln sich stets drei Nullen und drei Einsen ab.
+
*In the middle (blue marking), three zeros and three ones always alternate.
*Unten (rote Markierung) werden pro Zeile&nbsp; $25$&nbsp; Einsen durch zwei Nullen begrenzt.}}
+
*At the bottom (red mark), each line is delimited by&nbsp; $25$&nbsp; ones by two zeros.}}
  
 
 
 
 
==LZ77 – die Grundform der Lempel–Ziv–Algorithmen  ==  
+
==LZ77 - the basic form of the Lempel-Ziv-algorithms ==  
 
<br>
 
<br>
Die wichtigsten Verfahren zur Datenkomprimierung mit dynamischem Wörterbuch gehen auf&nbsp; [https://de.wikipedia.org/wiki/Abraham_Lempel Abraham Lempel]&nbsp; und&nbsp; [https://de.wikipedia.org/wiki/Jacob_Ziv Jacob Ziv]&nbsp; zurück.&nbsp; Die gesamte Lempel–Ziv–Familie&nbsp; (im Folgenden verwenden wir hierfür kurz: &nbsp; LZ–Verfahren)&nbsp; kann wie folgt charakterisiert werden:
+
The most important procedures for data compression with a dynamic dictionary go back to&nbsp; [https://en.wikipedia.org/wiki/Abraham_Lempel Abraham Lempel]&nbsp; and&nbsp; [https://en.wikipedia.org/wiki/Jacob_Ziv Jacob Ziv]&nbsp; zurück.&nbsp; The entire Lempel-Ziv family&nbsp; (in the following we will use for this briefly: &nbsp; LZ procedure)&nbsp; can be characterized as follows
*Lempel–Ziv–Verfahren nutzen die Tatsache, dass in einem Text oft ganze Wörter – oder zumindest Teile davon – mehrfach vorkommen.&nbsp; Man sammelt alle Wortfragmente, die man auch als&nbsp; ''Phrasen''&nbsp; bezeichnet, in einem ausreichend großen Wörterbuch.
+
*Lempel-Ziv methods use the fact that often whole words, or at least parts of them, occur several times in a text.&nbsp; One collects all word fragments, which are also called&nbsp; ''phrases''&nbsp; in a sufficiently large dictionary.
*Im Gegensatz zur vorher (von Shannon und Huffman) entwickelten Entropiecodierung ist hier nicht die Häufigkeit einzelner Zeichen oder Zeichenfolgen die Grundlage der Komprimierung, so dass die LZ–Verfahren auch ohne Kenntnis der Quellenstatistik angewendet werden können.
+
*Contrary to the entropy coding developed before (by Shannon and Huffman), the frequency of single characters or character strings is not the basis of the compression here, so that the LZ procedures can be applied even without knowledge of the source statistics.
*LZ–Komprimierung kommt dementsprechend mit einem einzigen Durchgang aus und auch der Quellensymbolumfang&nbsp; $M$&nbsp; und die Symbolmenge&nbsp; $\{q_μ\}$&nbsp; mit&nbsp; $μ = 1$, ... , $M$&nbsp; muss nicht bekannt sein.&nbsp; Man spricht von ''universeller Quellencodierung''&nbsp; (englisch:&nbsp; ''Universal Source Coding'').
+
*LZ compression accordingly manages with a single pass and also the source symbol range&nbsp; $M$&nbsp; and the symbol set&nbsp; $\{q_μ\}$&nbsp; with&nbsp; $μ = 1$, ... , $M$&nbsp; does not have to be known.&nbsp; This is called ''Universal Source Coding''.
  
  
Wir betrachten zunächst den Lempel–Ziv–Algorithmus in seiner ursprünglichen Form aus dem Jahre 1977, bekannt unter der Bezeichnung&nbsp; [https://de.wikipedia.org/wiki/LZ77 LZ77]:  
+
We first look at the Lempel-Ziv algorithm in its original form from 1977, known as&nbsp; [https://en.wikipedia.org/wiki/LZ77_and_LZ78#LZ77 LZ77]:  
*Dieser arbeitet mit einem Fenster, das sukzessive über den Text verschoben wird.&nbsp; Man spricht auch von einem&nbsp; ''Sliding Window''.  
+
*This works with a window that is successively moved over the text&nbsp; one also speaks of a&nbsp; ''sliding window''.  
*Die Fenstergröße&nbsp; $G$&nbsp; ist dabei ein wichtiger Parameter, der das Komprimierungsergebnis entscheidend beeinflusst.
+
*The window size&nbsp; $G$&nbsp; is an important parameter that decisively influences the compression result.
  
  
[[File:P_ID2426__Inf_T_2_2_S2a_neu.png|center|frame|Sliding–Window bei LZ77–Komprimierung]]
+
[[File:P_ID2426__Inf_T_2_2_S2a_neu.png|center|frame|Sliding window with LZ77 compression]]
  
Die Grafik zeigt eine beispielhafte Belegung des&nbsp; ''Sliding Windows''.&nbsp; Dieses ist unterteilt in
+
The graphic shows an example of the&nbsp; ''sliding windows''.&nbsp; This is divided into
*den Vorschaupuffer&nbsp; $($blaue Hinterlegung),&nbsp; und
+
*the preview buffer&nbsp; $($blue background),&nbsp; and
*den Suchpuffer&nbsp; $($rote Hinterlegung, mit den  Positionen&nbsp; $P = 0$, ... , $7$ &nbsp; ⇒ &nbsp; Fenstergröße&nbsp;   $G = 8)$.
+
*the search buffer&nbsp; $($red background, with the positions&nbsp; $P = 0$, ... , $7$ &nbsp; ⇒ &nbsp; window size&nbsp; $G = 8)$.
  
  
Der bearbeitete Text umfasst die vier Worte&nbsp; '''Miss''',&nbsp; '''Mission''',&nbsp; '''Mississippi'''&nbsp; und&nbsp; '''Mistral''', jeweils getrennt durch einen Bindestrich.&nbsp; Zum betrachteten Zeitpunkt steht im Vorschaupuffer&nbsp; '''Mississi'''.
+
The edited text consists of the four words&nbsp; '''Miss''',&nbsp; '''Mission'''',&nbsp; '''Mississippi''''&nbsp; and&nbsp; '''Mistral'''', each separated by a hyphen.&nbsp; At the time in question the preview buffer contains&nbsp; '''Mississi'''.
*Gesucht wird nun im Suchpuffer die beste Übereinstimmung &nbsp; ⇒ &nbsp; die Zeichenfolge mit der maximalen Übereinstimmungslänge&nbsp; $L$.&nbsp; Diese ergibt sich für die Position&nbsp; $P = 7$&nbsp; und die Länge&nbsp; $L = 5$&nbsp; zu&nbsp; '''Missi'''.
+
*Search now in the search buffer for the best match &nbsp; ⇒ &nbsp; the string with the maximum match length&nbsp; $L$.&nbsp; This is the result for the position&nbsp; $P = 7$&nbsp; and the length&nbsp; $L = 5$&nbsp; to&nbsp; '''Missi'''.
*Dieser Schritt wird dann durch das ''Triple''&nbsp; $(7,&nbsp; 5,&nbsp; $ '''s'''$)$&nbsp; ausgedrückt  &nbsp; ⇒ &nbsp; allgemein&nbsp; $(P, \ L, \ Z)$, wobei&nbsp; $Z =$&nbsp;'''s'''&nbsp; dasjenige  Zeichen angibt, das nicht mehr mit der gefundenen Zeichenfolge im Suchpuffer übereinstimmt.
+
*This step is then expressed by the ''triple''&nbsp; $(7,&nbsp; 5,&nbsp; $ '''s'''$)$&nbsp; expressed &nbsp; ⇒ &nbsp; general&nbsp; $(P, \ L, \ Z)$, where&nbsp; $Z =$&nbsp;'''s'''&nbsp; specifies the character that no longer matches the string found in the search buffer.
*Anschließend wird das Fenster um&nbsp; $L + 1 = 6$&nbsp; Zeichen nach rechts verschoben.&nbsp; Im Vorschaupuffer steht nun&nbsp; '''sippi–Mi''',&nbsp; im Suchpuffer&nbsp; '''n–Missis'''&nbsp; und die Codierung ergibt das Triple&nbsp; $(2, 2,$&nbsp; '''p'''$)$.
+
*At the end the window is moved by&nbsp; $L + 1 = 6$&nbsp; character is moved to the right.&nbsp; In the preview buffer there is now&nbsp; '''sippi-Mi'',&nbsp; in the search buffer&nbsp; '''n-Missis'''&nbsp; and the encoding gives the triple&nbsp; $(2, 2,$&nbsp; '''p'''$)$.
  
  
Im folgenden Beispiel wird der LZ77–Codier&ndash;Algorithmen genauer beschrieben.&nbsp; Die Decodierung läuft in vergleichbarer Weise ab.
+
In the following example the LZ77-coding algorithms are described in more detail.&nbsp; The decoding runs in a similar way.
 
 
 
 
 
{{GraueBox|TEXT=
 
{{GraueBox|TEXT=
$\text{Beispiel 3:}$&nbsp;  
+
$\text{Example 3:}$&nbsp;  
Wir betrachten die LZ77–Codierung des Strings&nbsp; '''ABABCBCBAABCABe'''&nbsp; entsprechend der folgenden Grafik.&nbsp; Die Eingangsfolge hat die Länge $N = 15$.&nbsp;  
+
We consider the LZ77 encoding of the string&nbsp; '''ABABCBCBAABCABe'''&nbsp; according to the following graphic.&nbsp; The input sequence has the length $N = 15$.&nbsp;  
  
Weiter wird vorausgesetzt:
+
Further is assumed:
*Für die Zeichen gelte&nbsp; $Z ∈ \{$ '''A''',&nbsp; '''B''',&nbsp; '''C''',&nbsp; '''e''' $\}$,&nbsp; wobei&nbsp; '''e'''&nbsp; dem&nbsp; ''end–of–file''&nbsp; (Ende des Eingabe–Strings) entspricht,
+
*For the characters apply&nbsp; $Z ∈ \{$ '''A''',&nbsp; '''B''',&nbsp; '''C''',&nbsp; '''e''' $\}$,&nbsp; where&nbsp; '''e'''&nbsp; corresponds to the&nbsp; ''end-of-file''&nbsp; (end of the input string)
*Die Größe von Vorschau– und Suchpuffer sind jeweils&nbsp; $G = 4$ &nbsp; ⇒ &nbsp; Position&nbsp; $P ∈ {0, 1, 2, 3}$.
+
*The size of the preview and search buffer are&nbsp; $G = 4$ &nbsp; ⇒ &nbsp; Position&nbsp; $P ∈ {0, 1, 2, 3}$.
  
[[File:P_ID2427__Inf_T_2_2_S2b_neu.png|frame|Zur Verdeutlichung der LZ77–Codierung]]
+
[[File:P_ID2427__Inf_T_2_2_S2b_neu.png|frame|To illustrate the LZ77 encoding]]
 
<br>
 
<br>
<u>Darstellung des Codiervorgangs</u>:
+
<u>Display of the encoding process</u>:
  
<u>Schritt 1 und 2</u>: &nbsp; Es werden die Zeichen&nbsp; '''A'''&nbsp; und&nbsp; '''B'''&nbsp; durch die Triple&nbsp; $(0, 0,&nbsp; $ '''A'''$)$&nbsp; und&nbsp; $(0, 0,&nbsp; $ '''B'''$)$ codiert, da diese im Suchpuffer noch nicht abgelegt sind.&nbsp; Dann Verschiebung des Sliding Window jeweils um 1.
+
<u>Step 1 and 2</u>: &nbsp; The characters&nbsp; '''A'''&nbsp; and&nbsp; '''B'''&nbsp; are encoded by the triple&nbsp; $(0, 0,&nbsp; $ '''A'''$)$&nbsp; and&nbsp; $(0, 0,&nbsp; $ '''B'''$)$, because they are not yet stored in the search buffer. &nbsp; Then move the Sliding Window by 1.
  
<u>Schritt 3</u>: &nbsp; '''AB'''&nbsp; wird über den Suchpuffer maskiert und gleichzeitig das noch unbekannte Zeichen&nbsp; '''C'''&nbsp; angehängt.&nbsp; Danach wird das Sliding Window um drei Positionen nach rechts verschoben.
+
<u>step 3</u>: &nbsp; '''AB'''&nbsp; is masked by the search buffer and at the same time the still unknown character&nbsp; '''C'''&nbsp; is appended.&nbsp; After that the Sliding Window is moved three positions to the right.
  
<u>Schritt 4</u>: &nbsp; Hier wird gezeigt, dass der Suchstring&nbsp; '''BCB'''&nbsp; auch im Vorschaupuffer enden darf.&nbsp; Jetzt kann das Fenster um vier Positionen verschoben werden.
+
<u>Step 4</u>: &nbsp; This shows that the search string&nbsp; '''BCB'''&nbsp; may also end in the preview buffer.&nbsp; Now the window can be moved four positions to the right.
  
<u>Schritt 5</u>: &nbsp; Es wird im Suchpuffer lediglich&nbsp; '''A'''&nbsp; gefunden und&nbsp; '''B'''&nbsp; abgehängt.&nbsp; Bei größerem Suchpuffer könnten dagegen&nbsp; '''ABC'''&nbsp; gemeinsam maskiert werden.&nbsp; Dazu müsste&nbsp; $G ≥ 7$&nbsp; sein.
+
<u>Step 5</u>: &nbsp; Only&nbsp; '''A'''&nbsp; is found in the search buffer and&nbsp; '''B'''&nbsp; is dropped.&nbsp; If the search buffer is larger, however,&nbsp; '''ABC'''&nbsp; could be masked together.&nbsp; For this purpose&nbsp; $G ≥ must be 7$&nbsp;.
  
<u>Schritt 6</u>: &nbsp; Ebenso muss das Zeichen&nbsp; '''C'''&nbsp; aufgrund des zu kleinen Puffers separat codiert werden.&nbsp; Da aber&nbsp; '''CA'''&nbsp; vorher noch nicht aufgetreten ist,&nbsp; würde hier&nbsp; $G = 7$&nbsp; die Komprimierung nicht verbessern.
+
<u>Step 6</u>: &nbsp; Likewise, the character&nbsp; '''C'''&nbsp; must be coded separately due to the buffer being too small.&nbsp; But since&nbsp; '''CA'''&nbsp; hasn't occurred before,&nbsp; would not improve the compression here&nbsp; $G = 7$&nbsp;
  
<u>Schritt 7</u>: &nbsp; Mit der Berücksichtigung des end–of–file&nbsp; ('''e''')&nbsp; gemeinsam mit&nbsp; '''AB'''&nbsp; aus dem Suchpuffer ist der Codiervorgang abgeschlossen.
+
<u>Step 7</u>: &nbsp; With the consideration of the end-of-file&nbsp; ('''e''')&nbsp; together with&nbsp; '''AB'''&nbsp; from the search buffer, the encoding process is finished.
  
  
Vor der Übertragung müssen natürlich die angegebenen Triple noch binär codiert werden.&nbsp; Dabei benötigt man im vorliegenden Beispiel für
+
Before transmission, the specified triples must of course be binary coded.&nbsp; In this example you need
*die Position&nbsp; $P ∈ \{0, 1, 2, 3\}$&nbsp; zwei Bit&nbsp; (gelbe Hinterlegung in obiger Tabelle),
+
*the position&nbsp; $P ∈ \{0, 1, 2, 3\}$&nbsp; two Bit&nbsp; (yellow background in the table above),
*die Kopierlänge&nbsp; $L$&nbsp; drei Bit&nbsp; (grün hinterlegt), so dass man auch&nbsp; $L = 7$&nbsp; noch darstellen könnte,
+
*the copy length&nbsp; $L$&nbsp; three bits&nbsp; (green background), so that one could also&nbsp; $L = 7$&nbsp; still be displayed,
*alle Zeichen jeweils zwei Bit&nbsp; (weiß hinterlegt),&nbsp; zum Beispiel&nbsp; '''A''' &#8594; '''00''',&nbsp; '''B''' &#8594; '''01''',&nbsp; '''C''' &#8594; '''10''',&nbsp; '''e''' („end–of–file”) &#8594; '''11'''.
+
*all characters are two bits&nbsp; (white background),&nbsp; for example&nbsp; '''A''' &#8594; '''00''',&nbsp; '''B''' &#8594; '''01''',&nbsp; '''C''' &#8594; '''10''',&nbsp; '''e''' ("end-of-file") &#8594; '''11'''.
  
  
Damit hat die LZ77–Ausgangsfolge eine Länge von&nbsp; $7 · 7 = 49$&nbsp; Bit, während die Eingangsfolge nur&nbsp; $15 · 2 = 30$&nbsp; Bit benötigt hat.}}
+
Thus the LZ77 output sequence has a length of&nbsp; $7 - 7 = 49$&nbsp; bit, while the input sequence only needed&nbsp; $15 - 2 = 30$&nbsp; bit.}}
  
  
 
{{BlaueBox|TEXT=
 
{{BlaueBox|TEXT=
$\text{Fazit:}$&nbsp; '''Eine Lempel–Ziv–Komprimierung macht nur bei großen Dateien Sinn !'''}}
+
$\text{Conclusion:}$&nbsp; '''A Lempel-Ziv compression only makes sense with large files !'''}}
  
  
==Die Lempel–Ziv–Variante LZ78 ==  
+
==The Lempel-Ziv-Variant LZ78 ==  
 
<br>
 
<br>
Der LZ77–Algorithmus erzeugt dann eine sehr ineffiziente Ausgabe, wenn sich häufigere Zeichenfolgen erst mit größerem Abstand wiederholen.&nbsp; Solche Wiederholungen können aufgrund der begrenzten Puffergröße&nbsp; $G$&nbsp; des&nbsp; ''Sliding Window''&nbsp; oft nicht erkannt werden.
+
The LZ77-algorithm produces very inefficient output if more frequent strings are repeated only with a larger distance.&nbsp; Such repetitions can often not be recognized due to the limited buffer size&nbsp; $G$&nbsp; des&nbsp; ''Sliding Window''&nbsp;.
  
Lempel und Ziv haben dieses Manko bereits ein Jahr nach der Veröffentlichung der ersten Version LZ77 korrigiert:  
+
Lempel and Ziv corrected this shortcoming already one year after the release of the first version LZ77:  
*Der Algorithmus LZ78 verwendet zur Komprimierung anstelle des lokalen Wörterbuchs (Suchpuffer) ein globales Wörterbuch.  
+
*The algorithm LZ78 uses a global dictionary for compression instead of the local dictionary (search buffer).  
*Bei entsprechender Wörterbuchgröße lassen sich somit auch solche Phrasen, die schon längere Zeit vorher aufgetreten sind, effizient komprimieren.
+
*The size of the dictionary allows efficient compression of phrases that have been used for a long time before.
  
  
 
{{GraueBox|TEXT=
 
{{GraueBox|TEXT=
$\text{Beispiel 4:}$&nbsp;  
+
$\text{Example 4:}$&nbsp;  
Zur Erklärung des LZ78–Algorithmus betrachten wir die gleiche Folge&nbsp; '''ABABCBCBAABCABe'''&nbsp; wie für das LZ77–$\text{Beispiel 3}$.
+
To explain the LZ78 algorithm we consider the same sequence&nbsp; '''ABABCBCBAABCABe'''&nbsp; as for the LZ77-$\text{Example 3}$.
  
[[File:Inf_T_2_2_S3_neu.png|frame|Generierung des Wörterbuchs und Ausgabe bei LZ78]]
+
[[File:Inf_T_2_2_S3_neu.png|frame|Generation of the dictionary and output at LZ78]]
  
*Die Grafik zeigt&nbsp; (mit roter Hinterlegung)&nbsp; das Wörterbuch mit Index&nbsp; $I&nbsp;$&nbsp; (in Dezimal– und Binärdarstellung, Spalte 1 und 2)&nbsp; und dem entsprechenden Inhalt (Spalte 3), der zum Codierschritt&nbsp; $i&nbsp;$&nbsp; eingetragen wird (Spalte 4).
+
*The graphic shows&nbsp; (with red background)&nbsp; the dictionary with index&nbsp; $I&nbsp;$&nbsp; (in decimal and binary representation, column 1 and 2)&nbsp; and the corresponding content (column 3), which is entered for coding step&nbsp; $i&nbsp;$&nbsp; (column 4).
 
   
 
   
  
*Bei LZ78 gilt sowohl für die Codierung als auch für die Decodierung stets&nbsp; $i = I$.
+
*For LZ78 both encoding and decoding are always&nbsp; $i = I$.
  
  
*In Spalte 5 findet man die formalisierte Coderausgabe&nbsp; $($Index&nbsp; $I$,&nbsp; neues Zeichen&nbsp; $Z)$.
+
*In column 5 you find the formalized code output&nbsp; $($Index&nbsp; $I$,&nbsp; new character&nbsp; $Z)$.
  
 
   
 
   
*In Spalte 6 ist die dazugehörige Binärcodierung angegeben mit vier Bit für den Index und der gleichen Zeichenzuordnung&nbsp; '''A''' &#8594; '''00''',&nbsp; '''B''' &#8594; '''01''',&nbsp; '''C''' &#8594; '''10''',&nbsp; '''e''' („end–of–file”) &#8594; '''11'''&nbsp; wie im&nbsp; $\text{Beispiel 3}$.
+
*In column 6 the corresponding binary coding is given with four bits for the index and the same character assignment&nbsp; '''A''' &#8594; '''00''',&nbsp; '''B''' &#8594; '''01''',&nbsp; '''C''' &#8594; '''10''',&nbsp; '''e''' ("end-of-file") &#8594; '''11'''&nbsp; as in&nbsp; $\text{Example 3}$.
 
<br clear=all>
 
<br clear=all>
*Zu Beginn&nbsp; (Schritt $\underline{i = 0}$)&nbsp; ist das Wörterbuch&nbsp; (WB)&nbsp; leer bis auf den Eintrag&nbsp; '''ε'''&nbsp; $($leeres Zeichen, nicht zu verwechseln mit dem Leerzeichen, das aber hier nicht verwendet wird$)$&nbsp; mit Index&nbsp; $I = 0$.
+
*At the beginning&nbsp; (step $\underline{i = 0}$)&nbsp; the dictionary is&nbsp; (WB)&nbsp; empty except for the entry&nbsp; '''ε'''&nbsp; $($empty character, not to be confused with the space character, which is not used here$)$&nbsp; with index&nbsp; $I = 0$.
*Im Schritt&nbsp; $\underline{i = 1}$&nbsp; findet man im Wörterbuch noch keinen verwertbaren Eintrag, und es wird&nbsp; ('''0,&nbsp; A''')&nbsp; ausgegeben&nbsp; ('''A'''&nbsp; folgt auf&nbsp; '''ε''').&nbsp; Im Wörterbuch erfolgt der Eintrag&nbsp; '''A'''&nbsp; in Zeile&nbsp; $I = 1$&nbsp; (abgekürzt&nbsp; '''1: A''').
+
*In the step&nbsp; $\underline{i = 1}$&nbsp; there is no usable entry in the dictionary yet, and it becomes&nbsp; ('''0,&nbsp; A''')&nbsp; output&nbsp; ('''A'''&nbsp; follows&nbsp; '''ε'''). &nbsp; In the dictionary, the entry&nbsp; '''A'''&nbsp; follows in line&nbsp; $I = 1$&nbsp; (abbreviated&nbsp; '''1: A''').
*Damit vergleichbar ist die Vorgehensweise im zweiten Schritt&nbsp; ($\underline{i = 2}$).&nbsp; Ausgegeben wird hier&nbsp; ('''0,&nbsp; B''')&nbsp; und ins Wörterbuch wird&nbsp; '''2: B'''&nbsp; eingetragen.
+
*The procedure in the second step&nbsp; ($\underline{i = 2}$).&nbsp; The output is&nbsp; ('''0,&nbsp; B''')&nbsp; and the dictionary entry is&nbsp; '''2: B'''&nbsp;.
*Da bei Schritt&nbsp; $\underline{i = 3}$&nbsp; bereits der Eintrag&nbsp; '''1: A'''&nbsp; gefunden wird, können hier die Zeichen&nbsp; '''AB'''&nbsp; gemeinsam durch&nbsp; ('''1, B''')&nbsp; codiert werden und es wird der neue Wörterbucheintrag&nbsp; '''3: AB'''&nbsp; vorgenommen.
+
*As the entry&nbsp; $\underline{i = 3}$&nbsp; is already found in step&nbsp; '''1: A'''&nbsp;, the characters&nbsp; '''AB'''&nbsp; can be coded together by&nbsp; ('''1, B''')&nbsp; and the new dictionary entry&nbsp; '''3: AB'''&nbsp; is made.
*Nach Codierung und Eintrag des neuen Zeichens&nbsp; '''C'''&nbsp; in Schritt&nbsp; $\underline{i = 4}$&nbsp; wird im Schritt&nbsp; $\underline{i = 5}$&nbsp; das Zeichenpaar&nbsp; '''BC'''&nbsp; gemeinsam codiert &nbsp; ⇒ &nbsp; ('''2, C''')&nbsp; und in das Wörterbuch&nbsp; '''5: BC'''&nbsp; eingetragen.
+
*After coding and insertion of the new character&nbsp; '''C'''&nbsp; in step&nbsp; $\underline{i = 4}$&nbsp; the pair of characters&nbsp; '''BC'''&nbsp; is coded together &nbsp; ⇒ &nbsp; ('''2, C''') and entered into the dictionary&nbsp; '''5: BC'''&nbsp; in step&nbsp; $\underline{i = 5}$&nbsp;.
*In Schritt&nbsp; $\underline{i = 6}$&nbsp; werden mit&nbsp; '''6: BA'''&nbsp; ebenfalls zwei Zeichen gemeinsam behandelt und in den beiden letzten Schritten jeweils drei, nämlich&nbsp; '''7: ABC'''&nbsp; und&nbsp; '''8: ABe'''.  
+
*In step&nbsp; $\underline{i = 6}$&nbsp; two characters are treated together with&nbsp; ''''6: BA'''&nbsp; and in the last two steps three each, namely&nbsp; '''7: ABC'''&nbsp; and&nbsp; '''8: ABe'''.  
*Die Ausgabe&nbsp; (3, '''C''')&nbsp; in Schritt&nbsp; $\underline{i = 7}$&nbsp; steht für&nbsp; „WB(3) + '''C”''' = '''ABC'''&nbsp; und die Ausgabe&nbsp; (3, '''e''')&nbsp; in Schritt&nbsp; $\underline{i = 8}$&nbsp; für&nbsp; '''ABe'''.
+
*The output&nbsp; (3, '''C''')&nbsp; in step&nbsp; $\underline{i = 7}$&nbsp; stands for&nbsp; "WB(3) + '''C''' = '''ABC''' &nbsp; and the output&nbsp; (3, '''e''')&nbsp; in step&nbsp; $\underline{i = 8}$&nbsp; for&nbsp; '''ABe'''.
  
  
In diesem&nbsp; $\text{Beispiel 4}$&nbsp; besteht somit die LZ78–Codesymbolfolge aus&nbsp; $8 · 6 = 48$&nbsp; Bit.&nbsp; Das Ergebnis ist vergleichbar mit dem LZ77–$\text{Beispiel 3}$&nbsp; $(49$ Bit$)$.}}  
+
In this&nbsp; $\text{Example 4}$&nbsp; the LZ78 code symbol sequence thus consists of&nbsp; $8 - 6 = 48$&nbsp; Bit.&nbsp; The result is comparable to the LZ77-$\text{Example 3}$&nbsp; $(49$ Bit$)$.}}
  
  
 
{{BlaueBox|TEXT=
 
{{BlaueBox|TEXT=
$\text{Fazit:}$&nbsp; Auf Details und Verbesserungen von LZ78 wird hier verzichtet.&nbsp; Hier verweisen wir auf den&nbsp; [[Information_Theory/Komprimierung_nach_Lempel,_Ziv_und_Welch#Der_Lempel.E2.80.93Ziv.E2.80.93Welch.E2.80.93Algorithmus|LZW–Algorithmus]], der auf den nächsten Seiten beschrieben wird.&nbsp; Soviel nur vorneweg:
+
$\text{Conclusion:}$&nbsp; Details and improvements of LZ78 will be omitted here.&nbsp; Here we refer to the&nbsp; [[Information_Theory/Compression According to Lempel, Ziv and Welch#The_Lempel. E2.80.93Ziv.E2.80.93Welch.E2.80.93Algorithm|LZW-Algorithm]], which will be described on the following pages.&nbsp; Only this much will be said now:
*Der Index&nbsp; $I$&nbsp; wird hier einheitlich mit vier Bit dargestellt, wodurch das Wörterbuch auf&nbsp; $16$&nbsp; Einträge beschränkt ist.&nbsp; Durch eine ''variable Bitanzahl''&nbsp; für den Index kann man diese Einschränkung umgehen.&nbsp; Gleichzeitig erhält man so einen besseren Komprimierungsfaktor.
+
*The index&nbsp; $I$&nbsp; is uniformly represented here with four bits, whereby the dictionary is limited to&nbsp; $16$&nbsp; entries.&nbsp; By a ''variable number of bits''&nbsp; for the index one can bypass this limitation.&nbsp; At the same time one gets a better compression factor.
*Das Wörterbuch muss bei allen LZ–Varianten nicht übertragen werden, sondern wird beim Decoder in genau gleicher Weise erzeugt wie auf der Coderseite.&nbsp; Die Decodierung erfolgt bei LZ78 – nicht aber bei LZW – ebenfalls in analoger Weise wie die Codierung.
+
*The dictionary does not have to be transmitted with all LZ variants, but is generated with the decoder in exactly the same way as on the coder side.&nbsp; The decoding is also done with LZ78, but not with LZW, in the same way as the coding.
*Alle LZ–Verfahren sind asymptotisch optimal, das heißt, dass bei unendlich langen Folgen die mittlere Codewortlänge&nbsp; $L_{\rm M}$&nbsp; pro Quellensymbol gleich der Quellenentropie&nbsp; $H$&nbsp; ist.  
+
*All LZ procedures are asymptotically optimal, i.e., for infinitely long sequences the mean code word length&nbsp; $L_{\rm M}$&nbsp; per source symbol is equal to the source entropy&nbsp; $H$&nbsp;.  
*Bei kurzen Folgen ist die Abweichung allerdings beträchtlich.&nbsp; Mehr dazu am&nbsp; [[Information_Theory/Komprimierung_nach_Lempel,_Ziv_und_Welch#Quantitative_Aussagen_zur_asymptotischen_Optimalit.C3.A4t|Kapitelende]].}}
+
*For short sequences, however, the deviation is considerable.&nbsp; More about this at&nbsp; [[Information_Theory/Compression_by_Lempel,_Ziv_and_Welch#Quantitative_Statements_on_asymptotic_Optimality|end of chapter]].}}
  
  
==Der Lempel–Ziv–Welch–Algorithmus  ==  
+
==The Lempel-Ziv-Welch algorithm ==  
 
<br>
 
<br>
Die heute gebräuchlichste Variante der Lempel–Ziv–Komprimierung wurde von&nbsp; [https://de.wikipedia.org/wiki/Terry_Welch Terry Welch]&nbsp; entworfen und 1983 veröffentlicht.&nbsp; Wir bezeichnen diese im Folgenden als den&nbsp; ''Lempel–Ziv–Welch–Algorithmus'', abgekürzt mit &bdquo;LZW&rdquo;.&nbsp; Ebenso wie LZ78 leichte Vorteile gegenüber LZ77 aufweist&nbsp; (wie zu erwarten – warum sonst hätte der Algorithmus modifiziert werden sollen?),&nbsp; hat LZW gegenüber LZ78 auch mehr Vorteile als Nachteile.
+
The most common variant of Lempel-Ziv compression used today was designed by&nbsp; [https://en.wikipedia.org/wiki/Terry_Welch Terry Welch]&nbsp; and published in 1983.&nbsp; In the following we refer to it as the&nbsp; ''Lempel-Ziv-Welch-Algorithm'', abbreviated as "LZW". &nbsp; Just as LZ78 has slight advantages over LZ77&nbsp; (as expected, why else would the algorithm have been modified?),&nbsp; LZW also has more advantages than disadvantages compared to LZ78.
  
[[File:P_ID2430__Inf_T_2_2_S4_neu.png|center|frame|LZW–Codierung der Folge&nbsp; '''ABABCBCBAABCABe''']]
+
[[File:P_ID2430__Inf_T_2_2_S4_neu.png|center|frame|LZW encoding of the sequence&nbsp; '''ABABCBCBAABCABe'']]
  
Die Grafik zeigt die Coderausgabe für die beispielhafte Eingangsfolge&nbsp; '''ABABCBCBAABCABe'''.&nbsp; Rechts dargestellt ist das Wörterbuch (rot hinterlegt), das bei der LZW–Codierung sukzessive entsteht.&nbsp; Die Unterschiede gegenüber LZ78 erkennt man im Vergleich zur Grafik auf der letzten Seite, nämlich:
+
The graphic shows the coder output for the exemplary input sequence&nbsp; '''ABABCBCBAABCABe'''.&nbsp; On the right is the dictionary (highlighted in red), which is successively generated during LZW encoding.&nbsp; The differences to LZ78 can be seen in comparison to the graphic on the last page, namely
*Bei LZW sind im Wörterbuch schon zu Beginn&nbsp; $(i = 0)$&nbsp; alle im Text vorkommenden Zeichen eingetragen und einer Binärfolge zugeordnet, im Beispiel mit den Indizes&nbsp; $I = 0$, ... ,&nbsp; $I = 3$.&nbsp; Das bedeutet aber auch, dass bei LZW doch gewisse Kenntnisse über die Nachrichtenquelle vorhanden sein müssen, während LZ78 eine „echte universelle Codierung” darstellt.
+
*For LZW, all characters occurring in the text are already entered at the beginning of&nbsp; $(i = 0)$&nbsp; and assigned to a binary sequence, in the example with the indices&nbsp; $I = 0$, ... ,&nbsp; $I = 3$.&nbsp; This also means that LZW requires some knowledge of the message source, whereas LZ78 is a "true universal encoding".
*Bei LZW wird zu jedem Codierschritt&nbsp; $i$&nbsp; nur der Wörterbuchindex&nbsp; $I$&nbsp; übertragen, während bei LZ78 die Kombination&nbsp; $(I$,&nbsp; $Z)$&nbsp; ausgegeben wird; $Z$&nbsp; bezeichnet dabei das aktuell neue Zeichen.&nbsp; Aufgrund des Fehlens von&nbsp; $Z$&nbsp; in der Coderausgabe ist die LZW–Decodierung komplizierter als bei LZ78, wie auf der Seite&nbsp; [[Information_Theory/Komprimierung_nach_Lempel,_Ziv_und_Welch#Decodierung_des_LZW.E2.80.93Algorithmus|Decodierung des LZW&ndash;Algorithmus]]&nbsp; beschrieben.  
+
*For LZW, only the dictionary index&nbsp; $I$&nbsp; is transmitted for each encoding step&nbsp; $i$&nbsp; while for LZ78 the output is the combination&nbsp; $(I$,&nbsp; $Z)$,&nbsp;where $Z$&nbsp; denotes the current new character. &nbsp; Due to the absence of&nbsp; $Z$&nbsp; in the code output, LZW decoding is more complicated than with LZ78, as described on page&nbsp; [[Information_Theory/Compression_According_to_Lempel,_Ziv_and_Welch#Decoding_of_LZW.E2.80.93Algorithm|Decoding of LZW&ndash;Algorithm]]&nbsp;.  
 
 
 
 
  
 
{{GraueBox|TEXT=
 
{{GraueBox|TEXT=
$\text{Beispiel 5:}$&nbsp; Für diese beispielhafte LZW–Codierung wird wie bei &bdquo;LZ77&rdquo; und &bdquo;LZ78&rdquo; wieder die Eingangsfolge&nbsp; '''ABABCBCBAABCABe'''&nbsp; vorausgesetzt.&nbsp; Die folgende Beschreibung bezieht sich also auf die obige Grafik.
+
$\text{Example 5:}$&nbsp; For this exemplary LZW encoding, as with "LZ77" and "LZ78" again the input sequence&nbsp; '''ABABCBCBAABCABe'''&nbsp; is assumed.&nbsp; So the following description refers to the above graphic.
  
<u>Schritt i = 0</u> (Vorbelegung): &nbsp; Die erlaubten Zeichen&nbsp; '''A''',&nbsp; '''B''',&nbsp; '''C'''&nbsp; und&nbsp; '''e'''&nbsp; („end–of–file”) werden in das Wörterbuch eingetragen und den Indizes&nbsp; $I = 0$, ... , $I = 3$&nbsp; zugeordnet.
+
<u>Step i = 0</u> (default): &nbsp; The allowed characters&nbsp; '''A''',&nbsp; '''B''',&nbsp; '''C'''&nbsp; and&nbsp; '''e'''&nbsp; ("end-of-file") are entered into the dictionary and assigned to the indices&nbsp; $I = 0$, ... , $I = 3$&nbsp;.
  
<u>Schritt i = 1</u>: &nbsp; '''A'''&nbsp; wird durch den Dezimalindex&nbsp; $I = 0$&nbsp; codiert und dessen Binärdarstellung&nbsp; '''0000'''&nbsp; übertragen.&nbsp; Anschließend wird ins Wörterbuch die Kombination aus dem aktuellen Zeichen&nbsp; '''A'''&nbsp; und dem nachfolgenden Zeichen&nbsp; '''B'''&nbsp; der Eingangsfolge unter dem Index&nbsp; $I = 4$&nbsp; abgelegt.
+
<u>Step i = 1</u>: &nbsp; '''A'''&nbsp; is coded by the decimal index&nbsp; $I = 0$&nbsp; and its binary representation&nbsp; '''0000'''&nbsp; is transmitted. &nbsp; Then the combination of the current character&nbsp; '''A'''&nbsp; and the following character&nbsp; '''B'''&nbsp; of the input sequence is stored in the dictionary under the index&nbsp; $I = 4$&nbsp;.
  
<u>Schritt i = 2</u>: &nbsp; Darstellung von&nbsp; '''B'''&nbsp; durch Index&nbsp; $I = 1$&nbsp; bzw.&nbsp; '''0001'''&nbsp; (binär) sowie Wörterbucheintrag von&nbsp; '''BA'''&nbsp; unter dem Index&nbsp; $I = 5$.
+
<u>step i = 2</u>: &nbsp; representation of&nbsp; '''B'''&nbsp; by index&nbsp; $I = 1$&nbsp; or.&nbsp; '''0001'''&nbsp; (binary) as well as dictionary entry of&nbsp; '''BA'''&nbsp; placed under index&nbsp; $I = 5$.
  
<u>Schritt i = 3</u>: &nbsp; Aufgrund des Eintrags&nbsp; '''AB'''&nbsp; zum Zeitpunkt&nbsp; $i = 1$&nbsp; ist der zu übertragende Index&nbsp; $I = 4$&nbsp; (binär: '''0100''').&nbsp; Neuer Eintrag ins Wörterbuch:&nbsp; '''ABC'''&nbsp; unter&nbsp; $I = 6$.
+
<u>Step i = 3</u>: &nbsp; Because of the entry&nbsp; '''AB'''&nbsp; at time&nbsp; $i = 1$&nbsp; the index to be transmitted is&nbsp; $I = 4$&nbsp; (binary: '''0100''').&nbsp; New dictionary entry of&nbsp; '''ABC'''&nbsp; under&nbsp; $I = 6$.
  
<u>Schritt i = 8</u>: &nbsp; Hier werden die Zeichen&nbsp; '''ABC'''&nbsp; gemeinsam durch den Index&nbsp; $I = 6$&nbsp; (binär: '''0110''')&nbsp; dargestellt und der Eintrag für&nbsp; '''ABCA'''&nbsp; vorgenommen.
+
<u>Step i = 8</u>: &nbsp; Here the characters&nbsp; '''ABC'''&nbsp; are represented together by the index&nbsp; $I = 6$&nbsp; (binary: '''0110''')&nbsp; and the entry for&nbsp; '''ABCA'''&nbsp; is made.
  
Mit der Codierung von&nbsp; '''e'''&nbsp; (EOF–Marke) ist der Codiervorgang nach zehn Schritten beendet.&nbsp; Bei LZ78 wurden nur acht Schritte benötigt.&nbsp; Es ist aber zu berücksichtigen:
+
With the encoding of&nbsp; '''e'''&nbsp; (EOF mark) the encoding process is finished after ten steps.&nbsp; With LZ78 only eight steps were needed.&nbsp; But it has to be considered:
*Der LZW–Algorithmus benötigt für die Darstellung dieser fünfzehn Eingangssymbole nur&nbsp; $10 · 4 = 40$&nbsp; Bit gegenüber den&nbsp; $8 · 6 = 48$&nbsp; Bit bei LZ78.&nbsp; Vorausgesetzt sind für diese einfache Rechnung jeweils vier Bit zur Indexdarstellung.
+
*The LZW algorithm needs only&nbsp; $10 \cdot 4 = 40$&nbsp; Bit versus the&nbsp; $8 \cdot 6 = 48$&nbsp; Bit for LZ78.&nbsp; Provided that for this simple calculation, four bits each are needed for index representation.
*Sowohl bei LZW als auch bei LZ78 kommt man mit weniger Bit aus&nbsp; $($nämlich mit&nbsp; $34$&nbsp; bzw.&nbsp; $42)$, wenn man berücksichtigt, dass zum Schritt&nbsp; $i = 1$&nbsp; der Index nur mit zwei Bit codiert werden muss&nbsp; $(I ≤ 3)$&nbsp; und für&nbsp; $i = 2$&nbsp; bis&nbsp; $i = 5$&nbsp; drei Bit ausreichen&nbsp; $(I ≤ 7)$.}}
+
*LZW as well as LZ78 require less bits&nbsp; $($namely &nbsp; $34$&nbsp; or &nbsp; $42)$, if one considers that for the step&nbsp; $i = 1$&nbsp; the index has to be coded with two bits only&nbsp; $(I ≤ 3)$&nbsp; and for&nbsp; $2 i 5$&nbsp; three bits are sufficient&nbsp; $(I ≤ 7)$.}}
  
  
Auf den nächsten Seiten wird auf die variable Bitanzahl zur Indexdarstellung sowie auf die Decodierung von LZ78– und LZW–codierten Binärfolgen im Detail eingegangen.
+
The following pages describe in detail the variable bit count for index representation and the decoding of LZ78- and LZW-encoded binary sequences.
  
  
==Lempel–Ziv–Codierung mit variabler Indexbitlänge ==  
+
==Lempel-Ziv-Coding with variable index bit length ==  
 
<br>
 
<br>
Aus Gründen einer möglichst kompakten Darstellung betrachten wir nun nur noch Binärquellen mit dem Wertevorrat&nbsp; $\{$'''A''', '''B'''$\}$.&nbsp; Das Abschlusszeichen&nbsp; '''end–of–file'''&nbsp; bleibt ebenfalls unberücksichtigt.  
+
For reasons of a most compact representation, we now consider only binary sources with the value set&nbsp; $\{$'''A''', '''B'''$\}$.&nbsp; The terminating character&nbsp; '''end-of-file'''&nbsp; is also not considered.  
  
[[File:P_ID2432__Inf_T_2_2_S5_neu.png|center|frame|LZW–Codierung einer binären Eingangsfolge]]
+
[[File:P_ID2432__Inf_T_2_2_S5_neu.png|center|frame|LZW-Coding of a binary input sequence]]
  
Wir demonstrieren die LZW–Codierung anhand eines Bildschirmabzugs unseres interaktiven Flash–Moduls&nbsp; [[Applets:Lempel-Ziv-Welch|Lempel–Ziv–Welch&ndash;Algorithmen]].  
+
We demonstrate the LZW coding by means of a screenshot of our interactive Flash module&nbsp; [[Applets:Lempel-Ziv-Welch|Lempel-Ziv-Welch&ndash;Algorithms]].  
  
*Beim ersten Codierschritt&nbsp; $(i = 1)$&nbsp; wird&nbsp; '''A'''&nbsp; &nbsp;⇒&nbsp; '''0'''&nbsp;  codiert.&nbsp; Danach erfolgt im Wörterbuch der Eintrag mit Index&nbsp; $I = 2$&nbsp; und&nbsp; Inhalt&nbsp; '''AB'''.
+
*In the first coding step&nbsp; $(i = 1)$&nbsp; '''A'''&nbsp; &nbsp;⇒&nbsp; '''0'''.&nbsp; Afterwards the entry with index&nbsp; $I = 2$&nbsp; and&nbsp; content&nbsp; '''AB'''.
*Da es bei Schritt&nbsp; $i = 1$&nbsp; im Wörterbuch mit&nbsp; '''A'''&nbsp; und&nbsp; '''B'''&nbsp; nur zwei Einträge gibt, genügt ein Bit.&nbsp; Dagegen werden bei Schritt&nbsp; $i = 2$&nbsp; und&nbsp; $i = 3$&nbsp; für&nbsp; '''B''' &nbsp;⇒&nbsp; '''01'''&nbsp; bzw.&nbsp; '''A''' &nbsp;⇒&nbsp; '''00'''&nbsp; jeweils zwei Bit benötigt.
+
*As there are only two entries in step&nbsp; $i = 1$&nbsp; in the dictionary (&nbsp; '''A'''&nbsp; and&nbsp; '''B'''&nbsp;) one bit is sufficient. &nbsp; On the other hand, for step&nbsp; $i = 2$&nbsp; and&nbsp; $i = 3$&nbsp; for&nbsp; '''B''' &nbsp;⇒&nbsp; '''01'''&nbsp; and &nbsp; '''A''' &nbsp;⇒&nbsp; '''00'''&nbsp; two bits are needed in each case.
*Ab &nbsp;$i = 4$&nbsp; erfolgt die Indexdarstellung mit drei Bit, ab&nbsp; $i = 8$&nbsp; mit vier Bit und ab&nbsp; $i = 16$&nbsp; mit fünf Bit.&nbsp; Hieraus lässt sich ein einfacher Algorithmus für die jeweilige Index–Bitanzahl&nbsp; $L(i)$&nbsp; ableiten.
+
*Starting on &nbsp;$i = 4$&nbsp;, the index representation is done with three bits, then from &nbsp; $i = 8$&nbsp; with four bits and from&nbsp; $i = 16$&nbsp; with five bits.&nbsp; A simple algorithm for the respective index bit number&nbsp; $L(i)$&nbsp; can be derived.
*Betrachten wir abschließend den Codierschritt&nbsp; $i = 18$.&nbsp; Hier wird die rot markierte Sequenz&nbsp; '''ABABB''', die zum Zeitpunkt&nbsp; $i = 11$&nbsp; in das Wörterbuch eingetragen wurde&nbsp; $($Index&nbsp; $I = 13$ ⇒ '''1101'''$)$&nbsp; bearbeitet.&nbsp; Die Coder&ndash;Ausgabe lautet wegen&nbsp; $i ≥ 16$&nbsp; aber nun&nbsp; '''01101'''&nbsp; (grüne Markierung bei der Coder&ndash;Ausgabe).
+
*Let's finally consider the coding step&nbsp; $i = 18$.&nbsp; Here, the sequence&nbsp; '''ABABB''' marked in red, which was entered into the dictionary at time&nbsp; $i = 11$&nbsp; at time&nbsp; $($Index&nbsp; $I = 13$ ⇒ '''1101'''$)$&nbsp; is edited. &nbsp; However, the coder output is now&nbsp; '''01101'''&nbsp;because of&nbsp; $i ≥ 16$&nbsp; (green mark at the coder output).
  
  
Die Aussagen gelten auch für&nbsp; [[Information_Theory/Komprimierung_nach_Lempel,_Ziv_und_Welch#Die_Lempel.E2.80.93Ziv.E2.80.93Variante_LZ78|LZ78]].&nbsp; Das heißt: &nbsp; Beim LZ78 ergibt sich durch eine variable Indexbitlänge die gleiche Verbesserung  wie beim LZW.
+
The statements also apply to&nbsp; [[Information_Theory/Compression According to Lempel, Ziv and Welch#The_Lempel.E2.80.93Ziv.E2.80.93Variant_LZ78|LZ78]].&nbsp; That is: &nbsp; With the LZ78 a variable index bit length results in the same improvement as with the LZW.
  
 
 
 
 
==Decodierung des LZW–Algorithmus ==
+
==Decoding of the LZW algorithm ==
 
<br>
 
<br>
Am Decoder liegt nun die auf der&nbsp; [[Information_Theory/Komprimierung_nach_Lempel,_Ziv_und_Welch#Lempel.E2.80.93Ziv.E2.80.93Codierung_mit_variabler_Indexbitl.C3.A4nge|letzten Seite]]&nbsp; ermittelte Coder–Ausgabe als Eingangsfolge an.&nbsp; Die Grafik zeigt, dass es auch bei variabler Indexbitlänge möglich ist, diese Folge eindeutig zu decodieren. Bitte beachten Sie:
+
The decoder now displays the decoded output on the&nbsp; [[Information_Theory/Compression_by_Lempel,_Ziv_and_Welch#Lempel-Ziv-Coding with variable index bit length|last page]]&nbsp; as input sequence.&nbsp; The graphic shows that it is possible to uniquely decode this sequence even with variable index bit lengths. Please note:
  
*Dem Decoder ist bekannt, dass im ersten Codierschritt&nbsp; $(i = 1)$&nbsp; der Index&nbsp; $I&nbsp;$ mit nur einem Bit codiert wurde, in den Schritten&nbsp; $i = 2$&nbsp; und&nbsp; $i = 3$&nbsp; mit zwei Bit, ab&nbsp; $i = 4$&nbsp; mit drei Bit, ab&nbsp; $i = 8$&nbsp; mit vier Bit, usw.
+
*The decoder knows that in the first coding step&nbsp; $(i = 1)$&nbsp; the index&nbsp; $I&nbsp;$ was coded with only one bit, in the steps&nbsp; $i = 2$&nbsp; and&nbsp; $i = 3$&nbsp; with two bit, from &nbsp; $i = 4$&nbsp; with three bit, from&nbsp; $i = 8$&nbsp; with four bit, and so on.
*Beim Decoder wird das gleiche Wörterbuch generiert wie beim Coder, doch erfolgen hier die Wörterbucheinträge einen Zeitschritt später.  
+
*The decoder generates the same dictionary as the coder, but the dictionary entries are made one time step later.  
  
  
[[File:P_ID2433__Inf_T_2_2_S6_neu.png|center|frame|LZW–Decodierung einer binären Eingangsfolge]]
+
[[File:P_ID2433__Inf_T_2_2_S6_neu.png|center|frame|LZW-Decoding of a binary input sequence]]
  
*Zum Schritt&nbsp; $\underline{i = 1}$&nbsp; wird also das anliegende Symbol&nbsp; '''0'''&nbsp; als&nbsp; '''A'''&nbsp; decodiert.&nbsp; Ebenso ergibt sich zum Schritt&nbsp; $\underline{i = 2}$&nbsp; aus der Vorbelegung des Wörterbuches und der hierfür vereinbarten Zwei–Bit–Darstellung: &nbsp; '''01''' &nbsp; ⇒ &nbsp; '''B'''.
+
*At step&nbsp; $\underline{i = 1}$&nbsp; the adjacent symbol&nbsp; '''0'''&nbsp; is decoded as&nbsp; '''A'''&nbsp;. &nbsp; Likewise, the following results for step&nbsp; $\underline{i = 2}$&nbsp; from the preassignment of the dictionary and the two-bit representation agreed upon for this: &nbsp; '''01''' &nbsp; ⇒ &nbsp; '''B'''.
*Der Eintrag der Zeile&nbsp; $\underline{I = 2}$&nbsp; $($Inhalt: &nbsp; '''AB'''$)$&nbsp; des Wörterbuchs erfolgt also erst zum Schritt&nbsp; $\underline{i = 2}$, während beim&nbsp; [[Information_Theory/Komprimierung_nach_Lempel,_Ziv_und_Welch#Lempel.E2.80.93Ziv.E2.80.93Codierung_mit_variabler_Indexbitl.C3.A4nge|Codiervorgang]]&nbsp; dies bereits am Ende von Schritt&nbsp; $i = 1$&nbsp; geschehen konnte.
+
*The entry of the line&nbsp; $\underline{I = 2}$&nbsp; $($content: &nbsp; '''AB'''$)$&nbsp; of the dictionary is therefore only made at the step&nbsp; $\underline{i = 2}$, while at the&nbsp; [[Information_Theory/Compression According to Lempel, Ziv and Welch#Lempel-Ziv-Coding with variable index bit length|Coding process]]&nbsp; this could already be done at the end of step&nbsp; $i = 1$&nbsp;.
*Betrachten wir nun die Decodierung für&nbsp; $\underline{i = 4}$.&nbsp; Der Index&nbsp; $\underline{I = 2}$&nbsp; liefert das Decodierergebnis&nbsp; '''010''' &nbsp; ⇒ &nbsp; '''AB'''&nbsp; und im nächsten Schritt&nbsp; $(\underline{i = 5})$&nbsp; wird die Wörterbuchzeile&nbsp; $\underline{I = 5}$&nbsp; mit&nbsp; '''ABA'''&nbsp; belegt.
+
*Let us now consider the decoding for&nbsp; $\underline{i = 4}$. &nbsp; The index&nbsp; $\underline{I = 2}$&nbsp; returns the decoding result&nbsp; '''010''' &nbsp; ⇒ &nbsp; '''AB'''&nbsp; and in the next step&nbsp; $(\underline{i = 5})$&nbsp; the dictionary line&nbsp; $\underline{I = 5}$&nbsp; will be filled with&nbsp; '''ABA'''&nbsp;.
*Diese Zeitverschiebung hinsichtlich der Wörterbuch–Einträge kann zu Decodierproblemen führen.&nbsp; Zum Beispiel gibt es zum Schritt&nbsp; $\underline{i = 7}$&nbsp; noch keinen Wörterbuch–Eintrag mit Index&nbsp; $\underline{I= 7}$.
+
*This time difference with respect to the dictionary entries can lead to decoding problems.&nbsp; For example, for step&nbsp; $\underline{i = 7}$&nbsp; there is no dictionary entry with index&nbsp; $\underline{I= 7}$.
*Was ist in einem solchen Fall&nbsp; $(\underline{I = i})$&nbsp; zu tun?&nbsp; Man nimmt in diesem Fall das Ergebnis des vorherigen Decodierschrittes&nbsp; $($hier: &nbsp; '''BA'''&nbsp; für&nbsp; $\underline{i = 6})$&nbsp; und fügt das erste Zeichen dieser Sequenz am Ende noch einmal an.&nbsp; Man erhält so das Decodierergebnis für&nbsp; $\underline{i = 7}$&nbsp; zu&nbsp; '''111''' &nbsp; ⇒ &nbsp; '''BAB'''.
+
*What is to do in such a case as&nbsp; $(\underline{I = i})$?&nbsp; In this case you take the result of the previous decoding step&nbsp; $($here: &nbsp; '''BA'''&nbsp; for&nbsp; $\underline{i = 6})$&nbsp; and append the first character of this sequence at the end again. &nbsp; This gives the decoding result for&nbsp; $\underline{i = 7}$&nbsp; to&nbsp; '''111''' &nbsp; ⇒ &nbsp; '''BAB'''.
*Natürlich ist es unbefriedigend, nur ein Rezept anzugeben.&nbsp; In der&nbsp; [[Aufgaben:Aufgabe_2.4Z:_Nochmals_LZW-Codierung_und_-Decodierung|Aufgabe 2.4Z]]&nbsp; sollen Sie das hier demonstrierte Vorgehen begründen.&nbsp; Wir verweisen auf die Musterlösung zu dieser Aufgabe.
+
*Naturally, it is unsatisfactory to specify only one recipe.&nbsp; In the&nbsp; [[Aufgaben:Aufgabe_2.4Z:_Nochmals_LZW-Codierung_und_-Decodierung|Exercise 2.4Z]]&nbsp; you should justify the procedure demonstrated here.&nbsp; We refer to the sample solution for this exercise.
  
  
Bei der LZ78–Decodierung tritt das hier geschilderte Problem nicht auf, da nicht nur der Index&nbsp; $I&nbsp;$, sondern auch das aktuelle Zeichen&nbsp; $Z$&nbsp; im Codierergebnis enthalten ist und übertragen wird.
+
With LZ78 decoding, the problem described here does not occur because not only the index&nbsp; $I&nbsp;$ but also the current character&nbsp; $Z$&nbsp; is included in the encoding result and is transmitted.
 
 
 
 
 
   
 
   
==Restredundanz als Maß für die Effizienz von Codierverfahren==
+
==Remaining redundancy as a measure for the efficiency of encoding methods==
 
<br>
 
<br>
Für den Rest dieses Kapitels gehen wir von folgenden Voraussetzungen aus:
+
For the rest of this chapter we assume the following prerequisites:
*Der&nbsp; ''Symbolumfang''&nbsp; der Quelle&nbsp; $($oder im übertragungstechnischen Sinne: &nbsp; die Stufenzahl)&nbsp; sei&nbsp; $M$, wobei&nbsp; $M$&nbsp; eine Zweierpotenz darstellt  &nbsp; ⇒ &nbsp; $M = 2, \ 4, \ 8, \ 16$, ....
+
*The&nbsp; ''symbol range''&nbsp; the source&nbsp; $($or in the transmission sense: &nbsp; the number of stages)&nbsp; sei&nbsp; $M$, where&nbsp; $M$&nbsp; represents a power of two &nbsp; ⇒ &nbsp; $M = 2, \ 4, \ 8, \ 16$, ....
*Die Quellenentropie sei&nbsp; $H$.&nbsp; Gibt es keine statistischen Bindungen zwischen den Symbolen und sind diese zudem gleichwahrscheinlich, so gilt&nbsp; $H = H_0$, wobei&nbsp; $H_0 = \log_2 \ M$&nbsp; den Entscheidungsgehalt angibt.&nbsp; Andernfalls gilt $H < H_0$.
+
*The source entropy is&nbsp; $H$.&nbsp; If there are no statistical bonds between the symbols and if they are equally probable, then&nbsp; $H = H_0$, where&nbsp; $H_0 = \log_2 \ M$&nbsp; indicates the decision content.&nbsp; Otherwise, $H < H_0$ applies.
*Eine Symbolfolge der Länge&nbsp; $N$&nbsp; wird quellencodiert und liefert eine binäre Codefolge der Länge&nbsp; $L$.&nbsp; Über die Art der Quellencodierung treffen wir vorerst keine Aussage.
+
*A symbol sequence of length&nbsp; $N$&nbsp; is source-coded and returns a binary code sequence of length&nbsp; $L$.&nbsp; For the time being we do not make any statement about the type of source coding.
  
  
Line 323: Line 323:
  
  
==Effizienz der Lempel–Ziv–Codierung  ==
+
According to the&nbsp; [[Information_Theory/General_Description#Source Encoding Theorem|Source Encoding Theorem]]&nbsp; the mean code word length&nbsp; $L_{\rm M}$&nbsp; must be greater than or equal to the source entropy&nbsp; $H$&nbsp; (in bit/source symbol).&nbsp; This means
 +
*for the total length of the source-encoded binary sequence:
 +
:$$L \ge N \cdot H \hspace{0.05cm},$$
 +
*for the relative redundancy of the code sequence, in the following called&nbsp; '''Rest Redundancy''':
 +
:$$r = \frac{L - N \cdot H}{L} \hspace{0.05cm}.$$
 +
 
 +
{{GraueBox|TEXT=
 +
$\text{Example 6:}$&nbsp; If there were a&nbsp; ''perfect source encoding'' for a redundancy-free binary source symbol sequence&nbsp; $(M = 2,\ p_{\rm A} = p_{\rm B} = 0.5$,&nbsp; without statistical bonds$)$&nbsp; of length&nbsp; $N = 10000$, the code sequence would have length&nbsp; $L = 10000$.
 +
 
 +
<u>Consequence:</u> &nbsp; If in a code the result&nbsp; $L = N$&nbsp; is never possible, then this code is called&nbsp; ''not&ndash;perfect''.
 +
*Lempel-Ziv is not suitable for this redundancy-free message source.&nbsp; It will always be&nbsp; $L > N$&nbsp; &nbsp; You can also put it quite succinctly like this: &nbsp; The perfect source encoding here is "no encoding at all".
 +
*A redundant binary source with &nbsp;$p_{\rm A} = 0.89$,&nbsp; $p_{\rm B} = 0.11$ &nbsp; ⇒ &nbsp; $H = 0.5$&nbsp; could be represented with a perfect source encoding with&nbsp;$L = 5000$&nbsp; bit, without being able to say what this perfect source encoding looks like.
 +
*For a quaternary source,&nbsp; $H > 1 \ \rm (bit/source symbol)$&nbsp; is possible, so that even with perfect source encoding there will always be&nbsp; $L > N$&nbsp;.&nbsp; If the source is redundancy-free&nbsp; (no bonds, all&nbsp; $M$&nbsp; symbols equally probable), it has entropy&nbsp; $H= 2 \ \rm (bit/source symbol)$.
 +
 
 +
 
 +
For all these examples of perfect source encoding, the relative redundancy of the code sequence (residual redundancy) is&nbsp; $r = 0$. That is: &nbsp; The zeros and ones are equally probable and there are no statistical bonds between the individual binary symbols.
 +
<br>
 +
 
 +
'''The problem is: &nbsp; At finite sequence length&nbsp; $N$&nbsp; there is no perfect source code'''&nbsp;!}}
 +
 
 +
 
 +
==Efficiency of Lempel-Ziv encoding ==
 
<br>
 
<br>
Von den Lempel–Ziv–Algorithmen weiß man (und kann diese Aussage sogar beweisen), dass sie&nbsp; '''asymptotisch optimal'''&nbsp; sind.&nbsp; Das bedeutet, dass die relative Redundanz der Codesymbolfolge&nbsp; (hier als Funktion der Quellensymbolfolgenlänge&nbsp; $N$&nbsp; geschrieben)  
+
From the Lempel-Ziv algorithms we know (and can even prove this statement) that they are&nbsp; '''asymptotically optimal''' &nbsp; This means that the relative redundancy of the code symbol sequence&nbsp; (here written as a function of the source symbol sequence length&nbsp; $N$&nbsp;)  
 
   
 
   
:$$r(N) = \frac{L(N) - N \cdot H}{L(N)}= 1 - \frac{ N \cdot H}{L(N)}\hspace{0.05cm}$$
+
:$$r(N) = \frac{L(N) - N \cdot H}{L(N)}= 1 - \frac{ N \cdot H}{L(N)}\hspace{0.05cm}$$
  
für große&nbsp; $N$&nbsp; den Grenzwert &bdquo;Null&rdquo; liefert:
+
for large&nbsp; $N$&nbsp; returns the limit value "zero":
 
   
 
   
 
:$$\lim_{N \rightarrow \infty}r(N) = 0 \hspace{0.05cm}.$$
 
:$$\lim_{N \rightarrow \infty}r(N) = 0 \hspace{0.05cm}.$$
  
Was aber sagt die Eigenschaft&nbsp; „asymptotisch optimal”&nbsp; für praxisrelevante Folgenlängen aus?&nbsp; Nicht allzu viel, wie der nachfolgende Bildschirmabzug unseres Simulationstools&nbsp; [[Applets:Lempel-Ziv-Welch|Lempel–Ziv–Algorithmen]]&nbsp; zeigt. Alle Kurven gelten exakt nur für den [[Information_Theory/Komprimierung_nach_Lempel,_Ziv_und_Welch#Der_Lempel.E2.80.93Ziv.E2.80.93Welch.E2.80.93Algorithmus|LZW–Algorithmus]].&nbsp; Die Ergebnisse für&nbsp; [[Information_Theory/Komprimierung_nach_Lempel,_Ziv_und_Welch#LZ77_.E2.80.93_die_Grundform_der_Lempel.E2.80.93Ziv.E2.80.93Algorithmen|LZ77]]&nbsp; und&nbsp; [[Information_Theory/Komprimierung_nach_Lempel,_Ziv_und_Welch#Die_Lempel.E2.80.93Ziv.E2.80.93Variante_LZ78|LZ78]]&nbsp; sind aber nur geringfügig schlechter.
+
But what does the property&nbsp; "asymptotically optimal"&nbsp; say for practical sequence lengths?&nbsp; Not too much, as the following screenshot of our simulation tool&nbsp; [[Applets:Lempel-Ziv-Welch|Lempel-Ziv-Algorithms]]&nbsp; shows. All curves apply exactly only to the [[Information_Theory/Compression_by_Lempel,_Ziv_and_Welch#The_Lempel.E2.80.93Ziv.E2.80.93Welch.E2.80.93Algorithm|LZW-Algorithm]]].&nbsp; However, the results for&nbsp; [[Information_Theory/Compression According to Lempel, Ziv and Welch#LZ77 - the basic form of the Lempel-Ziv-algorithms|LZ77]]&nbsp; and&nbsp; [[Information_Theory/Compression_by_Lempel,_Ziv_and_Welch#The_Lempel.E2.80.93Ziv.E2.80.93Variant_LZ78|LZ78]]&nbsp; are only slightly worse.
 +
 
  
Die drei Grafiken zeigen für verschiedene Nachrichtenquellen die Abhängigkeit folgender Größen von der Quellensymbolfolgenlänge&nbsp; $N$:
+
The three graphs show for different message sources the dependence of the following sizes on the source symbol sequence length&nbsp; $N$:
*die erforderliche Bitanzahl&nbsp; $N · \log_2 M$&nbsp; ohne Quellencodierung&nbsp; (schwarze Kurven),
+
*the required number of bits&nbsp; $N \cdot \log_2 M$&nbsp; without source coding&nbsp; (black curves),
*die erforderliche Bitanzahl&nbsp; $H$ · $N$&nbsp; bei perfekter Quellencodierung&nbsp; (grau–gestrichelt),
+
*the required number of bits&nbsp; $H$ \cdot $N$&nbsp; with perfect source encoding&nbsp; (gray dashed),
*die erforderliche Bitanzahl&nbsp; $L(N)$&nbsp; bei LZW–Codierung&nbsp; (rote Kurven nach Mittelung),
+
*the required number of bits&nbsp; $L(N)$&nbsp; for LZW coding&nbsp; (red curves after averaging),
*die relative Redundanz &nbsp; &rArr; &nbsp; Restredundanz &nbsp;$r(N)$&nbsp; bei LZW–Codierung (grüne Kurven).
+
*the relative redundancy &nbsp; &rArr; &nbsp; residual redundancy &nbsp;$r(N)$&nbsp; in case of LZW coding (green curves).
  
  
[[File:P_ID2450__Inf_T_2_2_S7b_neu.png|frame|Beispielhafte Verläufe von&nbsp; $L(N)$&nbsp; und&nbsp; $r(N)$]]
+
[[File:P_ID2450__Inf_T_2_2_S7b_neu.png|frame|Example curves of&nbsp; $L(N)$&nbsp; and&nbsp; $r(N)$]].
  
$\underline{\text{Redundante Binärquelle (obere Grafik)} }$  
+
$\underline{\text{Redundant binary source (upper graphic)} }$  
 
:$$M = 2, \hspace{0.1cm}p_{\rm A} = 0.89,\hspace{0.1cm} p_{\rm B} = 0.11$$
 
:$$M = 2, \hspace{0.1cm}p_{\rm A} = 0.89,\hspace{0.1cm} p_{\rm B} = 0.11$$
:$$\Rightarrow \hspace{0.15cm} H = 0.5 \ \rm bit/Quellensymbol\text{:}$$  
+
:$$\Rightarrow \hspace{0.15cm} H = 0.5 \ \rm bit/source symbol\text{:}$$  
*Die schwarze und die graue Kurve sind echte Gerade (nicht nur bei diesem Parametersatz).
+
*The black and grey curves are true straight lines (not only for this parameter set).
*Die rote Kurve&nbsp; $L(N)$&nbsp; ist leicht gekrümmt&nbsp; (mit bloßem Auge schwer zu erkennen).
+
*The red curve&nbsp; $L(N)$&nbsp; is slightly curved&nbsp; (difficult to see with the naked eye).
*Wegen dieser Krümmung von&nbsp; $L(N)$&nbsp; fällt die Restredundanz (grüne Kurve) leicht ab.
+
*Because of this curvature of&nbsp; $L(N)$&nbsp; the residual redundancy (green curve) drops slightly.
:$$r(N) = 1 - 0.5 · N/L(N).$$  
+
:$$r(N) = 1 - 0.5 \cdot N/L(N).$$  
*Abzulesen sind die Zahlenwerte
+
*The numerical values can be read
 
:$$L(N = 10000) = 6800,\hspace{0.5cm}
 
:$$L(N = 10000) = 6800,\hspace{0.5cm}
 
r(N = 10000) = 26.5\%.$$
 
r(N = 10000) = 26.5\%.$$
  
  
$\underline{\text{Redundanzfreie Binärquelle (mittlere Grafik)} }$  
+
$\underline{\text{Redundancy-free binary source (middle graphic)} }$  
 
:$$M = 2,\hspace{0.1cm} p_{\rm A} = p_{\rm B} = 0.5$$  
 
:$$M = 2,\hspace{0.1cm} p_{\rm A} = p_{\rm B} = 0.5$$  
:$$\Rightarrow \hspace{0.15cm} H = 1 \ \rm bit/Quellensymbol\text{:}$$
+
:$$\Rightarrow \hspace{0.15cm} H = 1 \ \rm bit/source symbol\text{:}$$
* Hier fallen die graue und die schwarze Gerade zusammen und die leicht gekrümmte rote Kurve liegt erwartungsgemäß darüber.  
+
* Here the grey and the black straight line coincide and the slightly curved red curve lies above it, as expected.  
*Obwohl hier die LZW–Codierung eine Verschlechterung bringt – erkennbar aus der Angabe&nbsp; $L(N = 10000) = 12330$, ist die relative Redundanz  kleiner als bei der oberen Grafik:  
+
*Although the LZW coding brings a deterioration here, recognizable from the indication&nbsp; $L(N = 10000) = 12330$, the relative redundancy is smaller than in the upper graph:  
 
:$$r(N = 10000) = 18.9\%.$$
 
:$$r(N = 10000) = 18.9\%.$$
  
  
  
$\underline{\text{Redundante Quaternärquelle (untere Grafik)} }$
+
$\underline{\text{Redundant quaternary source (lower graphic)} }$
 
:$$M = 4,\hspace{0.1cm}p_{\rm A} = 0.7,\hspace{0.1cm} p_{\rm B} = p_{\rm C} = p_{\rm D} = 0.1$$
 
:$$M = 4,\hspace{0.1cm}p_{\rm A} = 0.7,\hspace{0.1cm} p_{\rm B} = p_{\rm C} = p_{\rm D} = 0.1$$
:$$ \Rightarrow \hspace{0.15cm} H \approx 1.357 \ \rm bit/Quellensymbol\text{:}$$
+
:$$ \Rightarrow \hspace{0.15cm} H \approx 1.357 \ \rm bit/source symbol\text{:}$$
* Ohne Quellencodierung wären für&nbsp; $N = 10000$&nbsp; Quaternärsymbole&nbsp; $20000$&nbsp; Binärsymbole (Bit) erforderlich  (schwarze Kurve).
+
* Without source coding, for&nbsp; $N = 10000$&nbsp; Quaternary symbols&nbsp; $20000$&nbsp; binary symbols (bit) would be required (black curve).
* Bei perfekter Quellencodierung ergäben sich&nbsp; $N \cdot H= 13570$&nbsp; Bit&nbsp; (graue Kurve).
+
* If source encoding was perfect, this would result in&nbsp; $N \cdot H= 13570$&nbsp; Bit&nbsp; (grey curve).
* Mit der (nicht perfekten) LZW–Codierung benötigt man&nbsp; $L(N = 10000) ≈ 16485$&nbsp; Bit&nbsp;   (rote Kurve).  
+
* With (imperfect) LZW encoding you need&nbsp; $L(N = 10000) ≈ 16485$&nbsp; Bit&nbsp; (red curve).  
*Die relative Redundanz beträgt hier&nbsp; $r(N = 10000) ≈17.7\%$&nbsp;   (grüne Kurve).
+
*The relative redundancy here is&nbsp; $r(N = 10000) ≈17.7\%$&nbsp; (green curve).
  
  
==Quantitative Aussagen zur asymptotischen Optimalität== 
+
==Quantitative statements on asymptotic optimality== 
 
<br>
 
<br>
Die Ergebnisse der letzten Seite haben gezeigt, dass die relative Restredundanz&nbsp; $r(N = 10000)$&nbsp; deutlich größer ist als der theoretisch versprochene Wert&nbsp; $r(N \to \infty) = 0$.  
+
The results on the last page have shown that the relative residual redundancy&nbsp; $r(N = 10000)$&nbsp; is significantly greater than the theoretically promised value&nbsp; $r(N \to \infty) = 0$.  
  
Dieses praxisrelevante Ergebnis soll nun am Beispiel der redundanten Binärquelle mit&nbsp; $H = 0.5 \ \rm bit/Quellensymbol$&nbsp; entsprechend der mittleren Grafik auf der letzten Seite präzisiert werden, wobei wir aber nun für die Quellensymbolfolgenlänge Werte zwischen&nbsp; $N=10^3$&nbsp; und&nbsp; $N=10^{12}$&nbsp; betrachten.
+
This practically relevant result shall now be clarified using the example of the redundant binary source with&nbsp; $H = 0.5 \ \rm bit/source symbol$&nbsp; according to the middle graphic on the last page. However, we now consider values between&nbsp; $N=10^3$&nbsp; and&nbsp; $N=10^{12}$&nbsp; for the source symbol sequence length.
  
[[File:P_ID2443__Inf_T_2_2_S8_neu.png|frame|LZW–Restredundanz&nbsp; $r(N)$&nbsp; bei redundanter Binärquelle&nbsp; $(H = 0.5)$ ]]
+
[[File:P_ID2443__Inf_T_2_2_S8_neu.png|frame|LZW-Rest redundancy&nbsp; $r(N)$&nbsp; with redundant binary source&nbsp; $(H = 0.5)$ ]].
 
{{GraueBox|TEXT=
 
{{GraueBox|TEXT=
$\text{Beispiel 7:}$&nbsp; Die Grafik zeigt Simulationen mit&nbsp; $N = 1000$&nbsp; Binärsymbolen.  
+
$\text{Example 7:}$&nbsp; The graphic shows simulations with&nbsp; $N = 1000$&nbsp; binary symbols.  
*Nach Mittelung über zehn Versuchsreihen ergibt sich&nbsp; $r(N = 1000) ≈35.2\%$.  
+
*After averaging over ten series of experiments the result is&nbsp; $r(N = 1000) ≈35.2\%$.  
*Unterhalb des gelben Punktes&nbsp; $($im Beispiel bei&nbsp; $N ≈ 150)$&nbsp; bringt der LZW–Algorithmus sogar eine Verschlechterung.  
+
*below the yellow dot&nbsp; $($in the example with&nbsp; $N ≈ 150)$&nbsp; the LZW algorithm even brings a deterioration.  
*In diesem Bereich gilt nämlich&nbsp; $L > N$, das heißt: &nbsp; <br>Die rote Kurve liegt oberhalb der schwarzen.
+
*In this range, namely&nbsp; $L > N$, that is: &nbsp; <br>The red curve is above the black one.
  
  
In der unteren Tabelle sind die Ergebnisse für diese redundante Binärquelle&nbsp; $(H = 0.5)$&nbsp; zusammengefasst:
+
In the table below, the results for this redundant binary source&nbsp; $(H = 0.5)$&nbsp; are summarized
  
[[File:Inf_T_2_2_S8b_neu.png|right|frame|Einige Zahlenwerte zur Effizienz der LZW–Codierung]]
+
[[File:Inf_T_2_2_S8b_neu.png|right|frame|Some numerical values for the efficiency of LZW coding]]
  
*Der Komprimierungsfaktor&nbsp; $K(n)= L(n)/N$&nbsp; nimmt mit steigendem&nbsp; $N$&nbsp; nur sehr langsam ab&nbsp; (Zeile 3).
+
*The compression factor&nbsp; $K(n)= L(n)/N$&nbsp; decreases with increasing&nbsp; $N$&nbsp; only very slowly&nbsp; (line 3).
*In Zeile 4 ist die Restredundanz&nbsp; $r(N)$&nbsp; für verschiedene Längen  zwischen&nbsp; $N =1000$&nbsp; und&nbsp; $N =50000$&nbsp; angegeben.&nbsp;  
+
*In line 4 the rest redundancy&nbsp; $r(N)$&nbsp; is given for different lengths between&nbsp; $N =1000$&nbsp; and&nbsp; $N =50000$&nbsp;;  
*Entsprechend einschlägiger Literaturangaben nimmt diese Restredundanz proportional zu&nbsp; $\big[\hspace{0.05cm}\lg(N)\hspace{0.05cm}\big]^{-1}$&nbsp; ab.  
+
*According to relevant literature this residual redundancy decreases proportionally to&nbsp; $\big[\hspace{0.05cm}\lg(N)\hspace{0.05cm}\big]^{-1}$&nbsp;.  
*In Zeile 5 sind die Ergebnisse einer empirischen Formel eingetragen $($Anpassung für $N = 10000)$:
+
*In line 5 the results of an empirical formula are entered $($adaptation for $N = 10000)$:
 
   
 
   
:$$r\hspace{0.05cm}'(N) = \frac{A}{ {\rm lg}\hspace{0.1cm}(N)}\hspace{0.5cm}{\rm mit}$$
+
:$$r\hspace{0.05cm}'(N) = \frac{A}{ {\rm lg}\hspace{0.1cm}(N)}\hspace{0.5cm}{\rm with}$$
 
:$$ A = {r(N = 10000)} \cdot { {\rm lg}\hspace{0.1cm}10000} = 0.265 \cdot 4 = 1.06
 
:$$ A = {r(N = 10000)} \cdot { {\rm lg}\hspace{0.1cm}10000} = 0.265 \cdot 4 = 1.06
 
\hspace{0.05cm}.$$
 
\hspace{0.05cm}.$$
*Man erkennt die gute Übereinstimmung zwischen unseren Simulationsergebnissen&nbsp; $r(N)$&nbsp; und der Faustformel&nbsp; $r\hspace{0.05cm}′(N)$.  
+
*You can see the good agreement between our simulation results&nbsp; $r(N)$&nbsp; and the rule of thumb&nbsp; $r\hspace{0.05cm}′(N)$.  
*Man erkennt aber auch, dass die Restredundanz des LZW–Algorithmus für&nbsp; $N = 10^{12}$&nbsp; noch immer&nbsp; $8.8\%$&nbsp; beträgt.
+
*You can also see that the residual redundancy of the LZW algorithm for&nbsp; $N = 10^{12}$&nbsp; is still&nbsp; $8.8\%$&nbsp;.
*Bei anderen Quellen erhält man mit anderen&nbsp; $A$&ndash;Werten ähnliche Ergebnisse.&nbsp; Der prinzipielle Verlauf bleibt gleich.&nbsp; Siehe auch&nbsp; [[Aufgaben:Aufgabe_2.5:_Restredundanz_bei_LZW-Codierung|Aufgabe 2.5]]&nbsp; und&nbsp; [[Aufgaben:Aufgabe_2.5Z:_Komprimierungsfaktor_vs._Restredundanz|Aufgabe 2.5Z]].}}
+
*For other sources, with other&nbsp; $A$&ndash;values you will get similar results.&nbsp; The principle process remains the same.&nbsp; See also&nbsp; [[Aufgaben:Aufgabe_2.5:_Restredundanz_bei_LZW-Codierung|Exercise 2.5]]&nbsp; and&nbsp; [[Aufgaben:Aufgabe_2.5Z:_Komprimierungsfaktor_vs._Restredundanz|Task 2.5Z]].}}
  
 
 
 
 
==Aufgaben zum Kapitel  ==
+
==Exercises to chapter ==  
 
<br>
 
<br>
 
[[Aufgaben:2.3 Zur LZ78-Komprimierung|Aufgabe 2.3: Zur LZ78-Komprimierung]]
 
[[Aufgaben:2.3 Zur LZ78-Komprimierung|Aufgabe 2.3: Zur LZ78-Komprimierung]]

Revision as of 14:13, 2 November 2020


Static and dynamic dictionary techniques


Many data compression methods use dictionaries.  the idea is the following:

  • Construct a list of character patterns that occur in the text,
  • and encode these patterns as indices of the list.


This procedure is particularly efficient if certain patterns are repeated frequently in the text and this is also taken into account in the coding.  A distinction is made here

  • Procedure with static dictionary,
  • Procedure with dynamic dictionary.




$\text{(1) Procedure with static dictionary}$

A static dictionary is only useful for very special applications, for example for a file of the following form:

File to edit in this section

For example, the assignments result in

$$"\boldsymbol{\rm 0}" \hspace{0.05cm} \mapsto \hspace{0.05cm} \boldsymbol{\rm 000000} \hspace{0.05cm},\hspace{0.15cm} ... \hspace{0.15cm},\hspace{0.05cm} "\boldsymbol{\rm 9}" \hspace{0.05cm} \mapsto \hspace{0.05cm} \boldsymbol{\rm 001001} \hspace{0.05cm}, "\hspace{-0.03cm}\_\hspace{-0.03cm}\_\hspace{0.03cm}" \hspace{0.1cm}{\rm (Blank)}\hspace{0.05cm} \mapsto \hspace{0.05cm} \boldsymbol{\rm 001010} \hspace{0.05cm},$$
$$"\hspace{-0.01cm}.\hspace{-0.01cm}" \hspace{0.1cm}{\rm (Punkt)}\hspace{0.05cm} \mapsto \hspace{0.05cm} \boldsymbol{\rm 001011} \hspace{0.05cm}, "\hspace{-0.01cm},\hspace{-0.01cm}" \hspace{0.1cm}{\rm (Komma)}\hspace{0.05cm} \mapsto \hspace{0.05cm} \boldsymbol{\rm 001011} \hspace{0.05cm}, " {\rm end\hspace{-0.1cm}-\hspace{-0.1cm}of\hspace{-0.1cm}-\hspace{-0.1cm}line}\hspace{0.05cm} \mapsto \hspace{0.05cm} \boldsymbol{\rm 001101} \hspace{0.05cm},$$
$$"\boldsymbol{\rm A}" \hspace{0.05cm} \mapsto \hspace{0.05cm} \boldsymbol{\rm 100000} \hspace{0.05cm},\hspace{0.15cm} ... \hspace{0.15cm},\hspace{0.05cm} "\boldsymbol{\rm E}" \hspace{0.05cm} \mapsto \hspace{0.05cm} \boldsymbol{\rm 100100} \hspace{0.05cm}, \hspace{0.15cm} ... \hspace{0.15cm},\hspace{0.05cm} "\boldsymbol{\rm L}" \hspace{0.05cm} \mapsto \hspace{0.05cm} \boldsymbol{\rm 101011} \hspace{0.05cm},\hspace{0.15cm}"\boldsymbol{\rm M}" \hspace{0.05cm} \mapsto \hspace{0.05cm} \boldsymbol{\rm 101100} \hspace{0.05cm},$$
$$"\boldsymbol{\rm O}" \hspace{0.05cm} \mapsto \hspace{0.05cm} \boldsymbol{\rm 101110} \hspace{0.05cm},\hspace{0.15cm} ... \hspace{0.15cm},\hspace{0.05cm} "\boldsymbol{\rm U}" \hspace{0.05cm} \mapsto \hspace{0.05cm} \boldsymbol{\rm 110100} \hspace{0.05cm}, "\boldsymbol{\rm Name\hspace{-0.1cm}:\hspace{-0.05cm}\_\hspace{-0.03cm}\_}" \hspace{0.05cm} \mapsto \hspace{0.05cm} \boldsymbol{\rm 010000} \hspace{0.05cm},\hspace{0.05cm}$$
$$"\boldsymbol{\rm ,\_\hspace{-0.03cm}\_Vorname\hspace{-0.1cm}:\hspace{-0.05cm}\_\hspace{-0.03cm}\_}" \hspace{0.05cm} \mapsto \hspace{0.05cm} \boldsymbol{\rm 010001} \hspace{0.05cm},\hspace{0.05cm} "\boldsymbol{\rm ,\_\hspace{-0.03cm}\_Wohnort\hspace{-0.1cm}:\hspace{-0.05cm}\_\hspace{-0.03cm}\_}" \hspace{0.05cm} \mapsto \hspace{0.05cm} \boldsymbol{\rm 010010} \hspace{0.05cm},\hspace{0.15cm} ... \hspace{0.15cm}$$

for the first line of the above text, binary source coded with six bits per character:

$$\boldsymbol{010000} \hspace{0.15cm}\boldsymbol{100000} \hspace{0.15cm}\boldsymbol{100001} \hspace{0.15cm}\boldsymbol{100100} \hspace{0.15cm}\boldsymbol{101011} \hspace{0.3cm} \Rightarrow \hspace{0.3cm} \boldsymbol{(\rm Name\hspace{-0.1cm}:\hspace{-0.05cm}\_\hspace{-0.03cm}\_) \hspace{0.05cm}(A)\hspace{0.05cm}(B)\hspace{0.05cm}(E)\hspace{0.05cm}(L)}$$
$$\boldsymbol{010001} \hspace{0.15cm}\boldsymbol{101011}\hspace{0.15cm} \boldsymbol{100100} \hspace{0.15cm}\boldsymbol{101110} \hspace{0.3cm} \Rightarrow \hspace{0.3cm} \boldsymbol{(,\hspace{-0.05cm}\_\hspace{-0.03cm}\_\rm Vorname\hspace{-0.1cm}:\hspace{-0.05cm}\_\hspace{-0.03cm}\_) \hspace{0.05cm}(L)\hspace{0.05cm}(E)\hspace{0.05cm}(O)}$$
$$\boldsymbol{010010} \hspace{0.15cm}\boldsymbol{110100} \hspace{0.15cm}\boldsymbol{101011} \hspace{0.15cm}\boldsymbol{101100} \hspace{0.3cm}\Rightarrow \hspace{0.3cm} \boldsymbol{(,\hspace{-0.05cm}\_\hspace{-0.03cm}\_\rm Wohnort\hspace{-0.1cm}:\hspace{-0.05cm}\_\hspace{-0.03cm}\_) \hspace{0.05cm}(U)\hspace{0.05cm}(L)\hspace{0.05cm}(M)} \hspace{0.05cm} $$
$$\boldsymbol{001101} \hspace{0.3cm}\Rightarrow \hspace{0.3cm} ({\rm end\hspace{-0.1cm}-\hspace{-0.1cm}of\hspace{-0.1cm}-\hspace{-0.1cm}line}) \hspace{0.05cm}$$

$\text{Conclusion:}$  In this specific application the first line can be displayed with  $14 \cdot 6 = 84$  Bit.

  • In contrast, conventional binary coding would require  $39 \cdot 7 = 273$  bits since:
  • Because of the lowercase letters in the text, six bits per character are not sufficient here.
  • For the entire text, this results in  $103 \cdot 6 = 618$  Bit versus  $196 \cdot 7 = 1372$  Bit.
  • However, the code table must also be known to the recipient.




$\text{(2) Procedure with dynamic dictionary}$

Nevertheless, all relevant compression methods do not work with static dictionaries, but with dynamic dictionaries, which are created successively only during the coding:

  • Such procedures are flexible and do not have to be adapted to the application   One speaks of universal source coding procedures.
  • A single pass is sufficient, whereas with a static dictionary the file must first be analyzed before the encoding process.
  • At the sink, the dynamic dictionary is generated in the same way as for the source .  this eliminates the need to transfer the dictionary.


Extract from the hexdump of a natural image in BMP format

.

$\text{Example 1:}$  The graphic shows a small section of  $80$  Byte of a  BMP-File  in hexadecimal representation.  It is the uncompressed representation of a natural picture.

  • You can see that in this small section of a landscape image the bytes  $\rm FF$,  $\rm 55$  and  $\rm 47$  occur very frequently.
  • Data compression is therefore promising.
  • But since other parts of the  $\text{4 MByte}$ file or other byte combinations dominate in other image contents, the use of a static dictionary would not be appropriate here.


Possible encoding of a simple graphic

$\text{Example 2:}$  For an artificially created graphic, for example a form, you could work with a static dictionary.

We are looking at a b/w image with  $27 × 27$  pixels, where the mapping "black"   ⇒   0  and "white"   ⇒   1  has been agreed upon.

  • At the top (black marker) each line is described by  $27$  zeros.
  • In the middle (blue marking), three zeros and three ones always alternate.
  • At the bottom (red mark), each line is delimited by  $25$  ones by two zeros.


LZ77 - the basic form of the Lempel-Ziv-algorithms


The most important procedures for data compression with a dynamic dictionary go back to  Abraham Lempel  and  Jacob Ziv  zurück.  The entire Lempel-Ziv family  (in the following we will use for this briefly:   LZ procedure)  can be characterized as follows

  • Lempel-Ziv methods use the fact that often whole words, or at least parts of them, occur several times in a text.  One collects all word fragments, which are also called  phrases  in a sufficiently large dictionary.
  • Contrary to the entropy coding developed before (by Shannon and Huffman), the frequency of single characters or character strings is not the basis of the compression here, so that the LZ procedures can be applied even without knowledge of the source statistics.
  • LZ compression accordingly manages with a single pass and also the source symbol range  $M$  and the symbol set  $\{q_μ\}$  with  $μ = 1$, ... , $M$  does not have to be known.  This is called Universal Source Coding.


We first look at the Lempel-Ziv algorithm in its original form from 1977, known as  LZ77:

  • This works with a window that is successively moved over the text  one also speaks of a  sliding window.
  • The window size  $G$  is an important parameter that decisively influences the compression result.


Sliding window with LZ77 compression

The graphic shows an example of the  sliding windows.  This is divided into

  • the preview buffer  $($blue background),  and
  • the search buffer  $($red background, with the positions  $P = 0$, ... , $7$   ⇒   window size  $G = 8)$.


The edited text consists of the four words  MissMission'Mississippi'  and  Mistral', each separated by a hyphen.  At the time in question the preview buffer contains  Mississi.

  • Search now in the search buffer for the best match   ⇒   the string with the maximum match length  $L$.  This is the result for the position  $P = 7$  and the length  $L = 5$  to  Missi.
  • This step is then expressed by the triple  $(7,  5,  $ s$)$  expressed   ⇒   general  $(P, \ L, \ Z)$, where  $Z =$ s  specifies the character that no longer matches the string found in the search buffer.
  • At the end the window is moved by  $L + 1 = 6$  character is moved to the right.  In the preview buffer there is now  sippi-Mi,  in the search buffer  n-Missis'  and the encoding gives the triple  $(2, 2,$  p$)$.


In the following example the LZ77-coding algorithms are described in more detail.  The decoding runs in a similar way.

$\text{Example 3:}$  We consider the LZ77 encoding of the string  ABABCBCBAABCABe  according to the following graphic.  The input sequence has the length $N = 15$. 

Further is assumed:

  • For the characters apply  $Z ∈ \{$ ABCe $\}$,  where  e  corresponds to the  end-of-file  (end of the input string)
  • The size of the preview and search buffer are  $G = 4$   ⇒   Position  $P ∈ {0, 1, 2, 3}$.
To illustrate the LZ77 encoding


Display of the encoding process:

Step 1 and 2:   The characters  A  and  B  are encoded by the triple  $(0, 0,  $ A$)$  and  $(0, 0,  $ B$)$, because they are not yet stored in the search buffer.   Then move the Sliding Window by 1.

step 3:   AB  is masked by the search buffer and at the same time the still unknown character  C  is appended.  After that the Sliding Window is moved three positions to the right.

Step 4:   This shows that the search string  BCB  may also end in the preview buffer.  Now the window can be moved four positions to the right.

Step 5:   Only  A  is found in the search buffer and  B  is dropped.  If the search buffer is larger, however,  ABC  could be masked together.  For this purpose  $G ≥ must be 7$ .

Step 6:   Likewise, the character  C  must be coded separately due to the buffer being too small.  But since  CA  hasn't occurred before,  would not improve the compression here  $G = 7$ 

Step 7:   With the consideration of the end-of-file  (e)  together with  AB  from the search buffer, the encoding process is finished.


Before transmission, the specified triples must of course be binary coded.  In this example you need

  • the position  $P ∈ \{0, 1, 2, 3\}$  two Bit  (yellow background in the table above),
  • the copy length  $L$  three bits  (green background), so that one could also  $L = 7$  still be displayed,
  • all characters are two bits  (white background),  for example  A00B01C10e ("end-of-file") → 11.


Thus the LZ77 output sequence has a length of  $7 - 7 = 49$  bit, while the input sequence only needed  $15 - 2 = 30$  bit.


$\text{Conclusion:}$  A Lempel-Ziv compression only makes sense with large files !


The Lempel-Ziv-Variant LZ78


The LZ77-algorithm produces very inefficient output if more frequent strings are repeated only with a larger distance.  Such repetitions can often not be recognized due to the limited buffer size  $G$  des  Sliding Window .

Lempel and Ziv corrected this shortcoming already one year after the release of the first version LZ77:

  • The algorithm LZ78 uses a global dictionary for compression instead of the local dictionary (search buffer).
  • The size of the dictionary allows efficient compression of phrases that have been used for a long time before.


$\text{Example 4:}$  To explain the LZ78 algorithm we consider the same sequence  ABABCBCBAABCABe  as for the LZ77-$\text{Example 3}$.

Generation of the dictionary and output at LZ78
  • The graphic shows  (with red background)  the dictionary with index  $I $  (in decimal and binary representation, column 1 and 2)  and the corresponding content (column 3), which is entered for coding step  $i $  (column 4).


  • For LZ78 both encoding and decoding are always  $i = I$.


  • In column 5 you find the formalized code output  $($Index  $I$,  new character  $Z)$.


  • In column 6 the corresponding binary coding is given with four bits for the index and the same character assignment  A00B01C10e ("end-of-file") → 11  as in  $\text{Example 3}$.


  • At the beginning  (step $\underline{i = 0}$)  the dictionary is  (WB)  empty except for the entry  ε  $($empty character, not to be confused with the space character, which is not used here$)$  with index  $I = 0$.
  • In the step  $\underline{i = 1}$  there is no usable entry in the dictionary yet, and it becomes  (0,  A)  output  (A  follows  ε).   In the dictionary, the entry  A  follows in line  $I = 1$  (abbreviated  1: A).
  • The procedure in the second step  ($\underline{i = 2}$).  The output is  (0,  B)  and the dictionary entry is  2: B .
  • As the entry  $\underline{i = 3}$  is already found in step  1: A , the characters  AB  can be coded together by  (1, B)  and the new dictionary entry  3: AB  is made.
  • After coding and insertion of the new character  C  in step  $\underline{i = 4}$  the pair of characters  BC  is coded together   ⇒   (2, C) and entered into the dictionary  5: BC  in step  $\underline{i = 5}$ .
  • In step  $\underline{i = 6}$  two characters are treated together with  '6: BA  and in the last two steps three each, namely  7: ABC  and  8: ABe.
  • The output  (3, C)  in step  $\underline{i = 7}$  stands for  "WB(3) + C = ABC   and the output  (3, e)  in step  $\underline{i = 8}$  for  ABe.


In this  $\text{Example 4}$  the LZ78 code symbol sequence thus consists of  $8 - 6 = 48$  Bit.  The result is comparable to the LZ77-$\text{Example 3}$  $(49$ Bit$)$.


$\text{Conclusion:}$  Details and improvements of LZ78 will be omitted here.  Here we refer to the  LZW-Algorithm, which will be described on the following pages.  Only this much will be said now:

  • The index  $I$  is uniformly represented here with four bits, whereby the dictionary is limited to  $16$  entries.  By a variable number of bits  for the index one can bypass this limitation.  At the same time one gets a better compression factor.
  • The dictionary does not have to be transmitted with all LZ variants, but is generated with the decoder in exactly the same way as on the coder side.  The decoding is also done with LZ78, but not with LZW, in the same way as the coding.
  • All LZ procedures are asymptotically optimal, i.e., for infinitely long sequences the mean code word length  $L_{\rm M}$  per source symbol is equal to the source entropy  $H$ .
  • For short sequences, however, the deviation is considerable.  More about this at  end of chapter.


The Lempel-Ziv-Welch algorithm


The most common variant of Lempel-Ziv compression used today was designed by  Terry Welch  and published in 1983.  In the following we refer to it as the  Lempel-Ziv-Welch-Algorithm, abbreviated as "LZW".   Just as LZ78 has slight advantages over LZ77  (as expected, why else would the algorithm have been modified?),  LZW also has more advantages than disadvantages compared to LZ78.

LZW encoding of the sequence  'ABABCBCBAABCABe

The graphic shows the coder output for the exemplary input sequence  ABABCBCBAABCABe.  On the right is the dictionary (highlighted in red), which is successively generated during LZW encoding.  The differences to LZ78 can be seen in comparison to the graphic on the last page, namely

  • For LZW, all characters occurring in the text are already entered at the beginning of  $(i = 0)$  and assigned to a binary sequence, in the example with the indices  $I = 0$, ... ,  $I = 3$.  This also means that LZW requires some knowledge of the message source, whereas LZ78 is a "true universal encoding".
  • For LZW, only the dictionary index  $I$  is transmitted for each encoding step  $i$  while for LZ78 the output is the combination  $(I$,  $Z)$, where $Z$  denotes the current new character.   Due to the absence of  $Z$  in the code output, LZW decoding is more complicated than with LZ78, as described on page  Decoding of LZW–Algorithm .


$\text{Example 5:}$  For this exemplary LZW encoding, as with "LZ77" and "LZ78" again the input sequence  ABABCBCBAABCABe  is assumed.  So the following description refers to the above graphic.

Step i = 0 (default):   The allowed characters  ABC  and  e  ("end-of-file") are entered into the dictionary and assigned to the indices  $I = 0$, ... , $I = 3$ .

Step i = 1:   A  is coded by the decimal index  $I = 0$  and its binary representation  0000  is transmitted.   Then the combination of the current character  A  and the following character  B  of the input sequence is stored in the dictionary under the index  $I = 4$ .

step i = 2:   representation of  B  by index  $I = 1$  or.  0001  (binary) as well as dictionary entry of  BA  placed under index  $I = 5$.

Step i = 3:   Because of the entry  AB  at time  $i = 1$  the index to be transmitted is  $I = 4$  (binary: 0100).  New dictionary entry of  ABC  under  $I = 6$.

Step i = 8:   Here the characters  ABC  are represented together by the index  $I = 6$  (binary: 0110)  and the entry for  ABCA  is made.

With the encoding of  e  (EOF mark) the encoding process is finished after ten steps.  With LZ78 only eight steps were needed.  But it has to be considered:

  • The LZW algorithm needs only  $10 \cdot 4 = 40$  Bit versus the  $8 \cdot 6 = 48$  Bit for LZ78.  Provided that for this simple calculation, four bits each are needed for index representation.
  • LZW as well as LZ78 require less bits  $($namely   $34$  or   $42)$, if one considers that for the step  $i = 1$  the index has to be coded with two bits only  $(I ≤ 3)$  and for  $2 ≤ i ≤ 5$  three bits are sufficient  $(I ≤ 7)$.


The following pages describe in detail the variable bit count for index representation and the decoding of LZ78- and LZW-encoded binary sequences.


Lempel-Ziv-Coding with variable index bit length


For reasons of a most compact representation, we now consider only binary sources with the value set  $\{$A, B$\}$.  The terminating character  end-of-file  is also not considered.

LZW-Coding of a binary input sequence

We demonstrate the LZW coding by means of a screenshot of our interactive Flash module  Lempel-Ziv-Welch–Algorithms.

  • In the first coding step  $(i = 1)$  A   ⇒  0.  Afterwards the entry with index  $I = 2$  and  content  AB.
  • As there are only two entries in step  $i = 1$  in the dictionary (  A  and  B ) one bit is sufficient.   On the other hand, for step  $i = 2$  and  $i = 3$  for  B  ⇒  01  and   A  ⇒  00  two bits are needed in each case.
  • Starting on  $i = 4$ , the index representation is done with three bits, then from   $i = 8$  with four bits and from  $i = 16$  with five bits.  A simple algorithm for the respective index bit number  $L(i)$  can be derived.
  • Let's finally consider the coding step  $i = 18$.  Here, the sequence  ABABB marked in red, which was entered into the dictionary at time  $i = 11$  at time  $($Index  $I = 13$ ⇒ 1101$)$  is edited.   However, the coder output is now  01101 because of  $i ≥ 16$  (green mark at the coder output).


The statements also apply to  LZ78.  That is:   With the LZ78 a variable index bit length results in the same improvement as with the LZW.


Decoding of the LZW algorithm


The decoder now displays the decoded output on the  last page  as input sequence.  The graphic shows that it is possible to uniquely decode this sequence even with variable index bit lengths. Please note:

  • The decoder knows that in the first coding step  $(i = 1)$  the index  $I $ was coded with only one bit, in the steps  $i = 2$  and  $i = 3$  with two bit, from   $i = 4$  with three bit, from  $i = 8$  with four bit, and so on.
  • The decoder generates the same dictionary as the coder, but the dictionary entries are made one time step later.


LZW-Decoding of a binary input sequence
  • At step  $\underline{i = 1}$  the adjacent symbol  0  is decoded as  A .   Likewise, the following results for step  $\underline{i = 2}$  from the preassignment of the dictionary and the two-bit representation agreed upon for this:   01   ⇒   B.
  • The entry of the line  $\underline{I = 2}$  $($content:   AB$)$  of the dictionary is therefore only made at the step  $\underline{i = 2}$, while at the  Coding process  this could already be done at the end of step  $i = 1$ .
  • Let us now consider the decoding for  $\underline{i = 4}$.   The index  $\underline{I = 2}$  returns the decoding result  010   ⇒   AB  and in the next step  $(\underline{i = 5})$  the dictionary line  $\underline{I = 5}$  will be filled with  ABA .
  • This time difference with respect to the dictionary entries can lead to decoding problems.  For example, for step  $\underline{i = 7}$  there is no dictionary entry with index  $\underline{I= 7}$.
  • What is to do in such a case as  $(\underline{I = i})$?  In this case you take the result of the previous decoding step  $($here:   BA  for  $\underline{i = 6})$  and append the first character of this sequence at the end again.   This gives the decoding result for  $\underline{i = 7}$  to  111   ⇒   BAB.
  • Naturally, it is unsatisfactory to specify only one recipe.  In the  Exercise 2.4Z  you should justify the procedure demonstrated here.  We refer to the sample solution for this exercise.


With LZ78 decoding, the problem described here does not occur because not only the index  $I $ but also the current character  $Z$  is included in the encoding result and is transmitted.


Remaining redundancy as a measure for the efficiency of encoding methods


For the rest of this chapter we assume the following prerequisites:

  • The  symbol range  the source  $($or in the transmission sense:   the number of stages)  sei  $M$, where  $M$  represents a power of two   ⇒   $M = 2, \ 4, \ 8, \ 16$, ....
  • The source entropy is  $H$.  If there are no statistical bonds between the symbols and if they are equally probable, then  $H = H_0$, where  $H_0 = \log_2 \ M$  indicates the decision content.  Otherwise, $H < H_0$ applies.
  • A symbol sequence of length  $N$  is source-coded and returns a binary code sequence of length  $L$.  For the time being we do not make any statement about the type of source coding.


Nach dem  Quellencodierungstheorem  muss dann die mittlere Codewortlänge  $L_{\rm M}$  größer oder gleich der Quellenentropie  $H$  (in bit/Quellensymbol) sein.  Das bedeutet

  • für die Gesamtlänge der quellencodierten Binärfolge:
$$L \ge N \cdot H \hspace{0.05cm},$$
  • für die relative Redundanz der Codefolge, im Folgenden kurz  Restredundanz  genannt:
$$r = \frac{L - N \cdot H}{L} \hspace{0.05cm}.$$

$\text{Beispiel 6:}$  Gäbe es für eine redundanzfreie binäre Quellensymbolfolge  $(M = 2,\ p_{\rm A} = p_{\rm B} = 0.5$,  ohne statistische Bindungen$)$  der Länge  $N = 10000$  eine  perfekte Quellencodierung, so hätte auch die Codefolge die Länge  $L = 10000$.

Konsequenz:   Ist bei einem Code das Ergebnis  $L = N$  nie möglich, so bezeichnet man diesen Code als  nicht–perfekt.

  • Für diese redundanzfreie Nachrichtenquelle ist Lempel–Ziv nicht geeignet.  Es wird stets  $L > N$  gelten.  Man kann es auch ganz lapidar so ausdrücken:   Die perfekte Quellencodierung ist hier „gar keine Codierung”.
  • Eine redundante Binärquelle mit  $p_{\rm A} = 0.89$,  $p_{\rm B} = 0.11$   ⇒   $H = 0.5$  könnte man mit einer perfekten Quellencodierung durch  $L = 5000$  Bit darstellen, ohne dass wir hier sagen können, wie diese perfekte Quellencodierung aussieht.
  • Bei einer Quaternärquelle ist  $H > 1 \ \rm (bit/Quellensymbol)$  möglich, so dass auch bei perfekter Codierung stets  $L > N$  sein wird.  Ist die Quelle redundanzfrei  (keine Bindungen, alle  $M$  Symbole gleichwahrscheinlich), so hat sie die Entropie  $H= 2 \ \rm (bit/Quellensymbol)$.


Bei allen diesen Beispielen für perfekte Quellencodierung wäre die relative Redundanz der Codefolge (also die Restredundanz)  $r = 0$. Das heißt:   Die Nullen und Einsen sind gleichwahrscheinlich und es bestehen keine statistischen Bindungen zwischen den einzelnen Binärsymbolen.

Das Problem ist:   Bei endlicher Folgenlänge  $N$  gibt es keine perfekte Quellencodierung !


According to the  Source Encoding Theorem  the mean code word length  $L_{\rm M}$  must be greater than or equal to the source entropy  $H$  (in bit/source symbol).  This means

  • for the total length of the source-encoded binary sequence:
$$L \ge N \cdot H \hspace{0.05cm},$$
  • for the relative redundancy of the code sequence, in the following called  Rest Redundancy:
$$r = \frac{L - N \cdot H}{L} \hspace{0.05cm}.$$

$\text{Example 6:}$  If there were a  perfect source encoding for a redundancy-free binary source symbol sequence  $(M = 2,\ p_{\rm A} = p_{\rm B} = 0.5$,  without statistical bonds$)$  of length  $N = 10000$, the code sequence would have length  $L = 10000$.

Consequence:   If in a code the result  $L = N$  is never possible, then this code is called  not–perfect.

  • Lempel-Ziv is not suitable for this redundancy-free message source.  It will always be  $L > N$    You can also put it quite succinctly like this:   The perfect source encoding here is "no encoding at all".
  • A redundant binary source with  $p_{\rm A} = 0.89$,  $p_{\rm B} = 0.11$   ⇒   $H = 0.5$  could be represented with a perfect source encoding with $L = 5000$  bit, without being able to say what this perfect source encoding looks like.
  • For a quaternary source,  $H > 1 \ \rm (bit/source symbol)$  is possible, so that even with perfect source encoding there will always be  $L > N$ .  If the source is redundancy-free  (no bonds, all  $M$  symbols equally probable), it has entropy  $H= 2 \ \rm (bit/source symbol)$.


For all these examples of perfect source encoding, the relative redundancy of the code sequence (residual redundancy) is  $r = 0$. That is:   The zeros and ones are equally probable and there are no statistical bonds between the individual binary symbols.

The problem is:   At finite sequence length  $N$  there is no perfect source code !


Efficiency of Lempel-Ziv encoding


From the Lempel-Ziv algorithms we know (and can even prove this statement) that they are  asymptotically optimal   This means that the relative redundancy of the code symbol sequence  (here written as a function of the source symbol sequence length  $N$ )

$$r(N) = \frac{L(N) - N \cdot H}{L(N)}= 1 - \frac{ N \cdot H}{L(N)}\hspace{0.05cm}$$

for large  $N$  returns the limit value "zero":

$$\lim_{N \rightarrow \infty}r(N) = 0 \hspace{0.05cm}.$$

But what does the property  "asymptotically optimal"  say for practical sequence lengths?  Not too much, as the following screenshot of our simulation tool  Lempel-Ziv-Algorithms  shows. All curves apply exactly only to the LZW-Algorithm].  However, the results for  LZ77  and  LZ78  are only slightly worse.


The three graphs show for different message sources the dependence of the following sizes on the source symbol sequence length  $N$:

  • the required number of bits  $N \cdot \log_2 M$  without source coding  (black curves),
  • the required number of bits  $H$ \cdot $N$  with perfect source encoding  (gray dashed),
  • the required number of bits  $L(N)$  for LZW coding  (red curves after averaging),
  • the relative redundancy   ⇒   residual redundancy  $r(N)$  in case of LZW coding (green curves).


Example curves of  $L(N)$  and  $r(N)$

.

$\underline{\text{Redundant binary source (upper graphic)} }$

$$M = 2, \hspace{0.1cm}p_{\rm A} = 0.89,\hspace{0.1cm} p_{\rm B} = 0.11$$
$$\Rightarrow \hspace{0.15cm} H = 0.5 \ \rm bit/source symbol\text{:}$$
  • The black and grey curves are true straight lines (not only for this parameter set).
  • The red curve  $L(N)$  is slightly curved  (difficult to see with the naked eye).
  • Because of this curvature of  $L(N)$  the residual redundancy (green curve) drops slightly.
$$r(N) = 1 - 0.5 \cdot N/L(N).$$
  • The numerical values can be read
$$L(N = 10000) = 6800,\hspace{0.5cm} r(N = 10000) = 26.5\%.$$


$\underline{\text{Redundancy-free binary source (middle graphic)} }$

$$M = 2,\hspace{0.1cm} p_{\rm A} = p_{\rm B} = 0.5$$
$$\Rightarrow \hspace{0.15cm} H = 1 \ \rm bit/source symbol\text{:}$$
  • Here the grey and the black straight line coincide and the slightly curved red curve lies above it, as expected.
  • Although the LZW coding brings a deterioration here, recognizable from the indication  $L(N = 10000) = 12330$, the relative redundancy is smaller than in the upper graph:
$$r(N = 10000) = 18.9\%.$$


$\underline{\text{Redundant quaternary source (lower graphic)} }$

$$M = 4,\hspace{0.1cm}p_{\rm A} = 0.7,\hspace{0.1cm} p_{\rm B} = p_{\rm C} = p_{\rm D} = 0.1$$
$$ \Rightarrow \hspace{0.15cm} H \approx 1.357 \ \rm bit/source symbol\text{:}$$
  • Without source coding, for  $N = 10000$  Quaternary symbols  $20000$  binary symbols (bit) would be required (black curve).
  • If source encoding was perfect, this would result in  $N \cdot H= 13570$  Bit  (grey curve).
  • With (imperfect) LZW encoding you need  $L(N = 10000) ≈ 16485$  Bit  (red curve).
  • The relative redundancy here is  $r(N = 10000) ≈17.7\%$  (green curve).


Quantitative statements on asymptotic optimality


The results on the last page have shown that the relative residual redundancy  $r(N = 10000)$  is significantly greater than the theoretically promised value  $r(N \to \infty) = 0$.

This practically relevant result shall now be clarified using the example of the redundant binary source with  $H = 0.5 \ \rm bit/source symbol$  according to the middle graphic on the last page. However, we now consider values between  $N=10^3$  and  $N=10^{12}$  for the source symbol sequence length.

LZW-Rest redundancy  $r(N)$  with redundant binary source  $(H = 0.5)$

.

$\text{Example 7:}$  The graphic shows simulations with  $N = 1000$  binary symbols.

  • After averaging over ten series of experiments the result is  $r(N = 1000) ≈35.2\%$.
  • below the yellow dot  $($in the example with  $N ≈ 150)$  the LZW algorithm even brings a deterioration.
  • In this range, namely  $L > N$, that is:  
    The red curve is above the black one.


In the table below, the results for this redundant binary source  $(H = 0.5)$  are summarized

Some numerical values for the efficiency of LZW coding
  • The compression factor  $K(n)= L(n)/N$  decreases with increasing  $N$  only very slowly  (line 3).
  • In line 4 the rest redundancy  $r(N)$  is given for different lengths between  $N =1000$  and  $N =50000$ ;
  • According to relevant literature this residual redundancy decreases proportionally to  $\big[\hspace{0.05cm}\lg(N)\hspace{0.05cm}\big]^{-1}$ .
  • In line 5 the results of an empirical formula are entered $($adaptation for $N = 10000)$:
$$r\hspace{0.05cm}'(N) = \frac{A}{ {\rm lg}\hspace{0.1cm}(N)}\hspace{0.5cm}{\rm with}$$
$$ A = {r(N = 10000)} \cdot { {\rm lg}\hspace{0.1cm}10000} = 0.265 \cdot 4 = 1.06 \hspace{0.05cm}.$$
  • You can see the good agreement between our simulation results  $r(N)$  and the rule of thumb  $r\hspace{0.05cm}′(N)$.
  • You can also see that the residual redundancy of the LZW algorithm for  $N = 10^{12}$  is still  $8.8\%$ .
  • For other sources, with other  $A$–values you will get similar results.  The principle process remains the same.  See also  Exercise 2.5  and  Task 2.5Z.


Exercises to chapter


Aufgabe 2.3: Zur LZ78-Komprimierung

Aufgabe 2.3Z: Zur LZ77-Codierung

Aufgabe 2.4: Zum LZW-Algorithmus

Aufgabe 2.4Z: Nochmals LZW-Codierung und -Decodierung

Aufgabe 2.5: Relative Restredundanz bei LZW-Codierung

Aufgabe 2.5Z: Komprimierungsfaktor vs. Restredundanz