Informationstheorie/Komprimierung nach Lempel, Ziv und Welch - Versionsgeschichte

Guenter am 8. Juli 2021 um 13:23 Uhr

2021-07-08T13:23:35Z

Guenter am 29. Juni 2021 um 11:49 Uhr

2021-06-29T11:49:05Z

Guenter am 29. Juni 2021 um 11:38 Uhr

2021-06-29T11:38:20Z

Guenter am 28. Juni 2021 um 17:30 Uhr

2021-06-28T17:30:04Z

Guenter am 28. Juni 2021 um 14:45 Uhr

2021-06-28T14:45:27Z

Änderungen zeigen

Guenter am 23. Januar 2020 um 13:37 Uhr

2020-01-23T13:37:29Z

Guenter am 23. Januar 2020 um 12:17 Uhr

2020-01-23T12:17:00Z

Änderungen zeigen

Guenter am 23. Januar 2020 um 11:25 Uhr

2020-01-23T11:25:34Z

Guenter am 22. Januar 2020 um 10:19 Uhr

2020-01-22T10:19:17Z

Guenter am 22. Januar 2020 um 09:35 Uhr

2020-01-22T09:35:43Z

Änderungen zeigen

@@ Zeile 24: / Zeile 24: @@
 Ein statisches Wörterbuch ist nur für ganz spezielle Anwendungen sinnvoll, zum Beispiel für eine Datei der folgenden Form:
-[[Datei:P_ID2424__Inf_T_2_2_S1a.png|center|frame|Zu bearbeitende Datei in diesem Abschnitt]]
+[[Datei:EN_Inf_T_2_2_S1a.png|center|frame|Zu bearbeitende Datei in diesem Abschnitt]]
 Beispielsweise ergibt sich mit den Zuordnungen
@@ Zeile 265: / Zeile 265: @@
 Wir demonstrieren die LZW–Codierung anhand eines Bildschirmabzugs unseres interaktiven SWF–Moduls&nbsp; [[Applets:Lempel-Ziv-Welch|Lempel–Ziv–Welch&ndash;Algorithmen]].
-[[Datei:P_ID2432__Inf_T_2_2_S5_neu.png|right|frame|LZW–Codierung einer binären Eingangsfolge]]
+[[Datei:Inf_T_2_2_S5_v2.png|right|frame|LZW–Codierung einer binären Eingangsfolge]]
 *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 dem Index&nbsp; $I = 2$&nbsp; und dem&nbsp; Inhalt&nbsp; '''AB'''.

@@ Zeile 418: / Zeile 418: @@
 [[Aufgaben:2.4Z Nochmals LZW-Codierung und -Decodierung|Aufgabe 2.4Z: Nochmals LZW-Codierung und -Decodierung]]
-[[Aufgaben:Aufgabe_2.5:_Restredundanz_bei_LZW-Codierung|Aufgabe 2.5: Relative Restredundanz bei LZW-Codierung]]
+[[Aufgaben:Aufgabe_2.5:_Restredundanz_bei_LZW-Codierung|Aufgabe 2.5: Restredundanz bei LZW-Codierung]]
 [[Aufgaben:Aufgabe_2.5Z:_Komprimierungsfaktor_vs._Restredundanz|Aufgabe 2.5Z: Komprimierungsfaktor vs. Restredundanz]]

@@ Zeile 300: / Zeile 300: @@
 <br>
 Für den Rest dieses Kapitels gehen wir von folgenden Voraussetzungen aus:
-*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$, ....
+*Der Symbolumfang  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$, ....
 *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$.
 *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.
@@ Zeile 312: / Zeile 312: @@
 {{GraueBox|TEXT=
-$\text{Beispiel 6:}$&nbsp; Gäbe es für eine redundanzfreie binäre Quellensymbolfolge&nbsp; $(M = 2,\ p_{\rm A} = p_{\rm B} = 0.5$,&nbsp; ohne statistische Bindungen$)$&nbsp; der Länge&nbsp; $N = 10000$&nbsp; eine&nbsp; ''perfekte Quellencodierung'', so hätte auch die Codefolge die Länge&nbsp; $L = 10000$.
+$\text{Beispiel 6:}$&nbsp; Gäbe es für eine redundanzfreie binäre Quellensymbolfolge&nbsp; $(M = 2,\ p_{\rm A} = p_{\rm B} = 0.5$,&nbsp; ohne statistische Bindungen$)$&nbsp; der Länge&nbsp; $N = 10000$&nbsp; eine&nbsp; &bdquo;perfekte Quellencodierung&rdquo;, so hätte auch die Codefolge die Länge&nbsp; $L = 10000$.
-<u>Konsequenz:</u> &nbsp; Ist bei einem Code das Ergebnis&nbsp; $L = N$&nbsp; nie möglich, so bezeichnet man diesen Code als&nbsp; ''nicht&ndash;perfekt''.
+<u>Konsequenz:</u> &nbsp; Ist bei einem Code das Ergebnis&nbsp; $L = N$&nbsp; nie möglich, so bezeichnet man diesen Code als&nbsp; &bdquo;nicht&ndash;perfekt&rdquo;.
 *Für diese redundanzfreie Nachrichtenquelle ist Lempel–Ziv nicht geeignet.&nbsp; Es wird stets&nbsp; $L > N$&nbsp; gelten.&nbsp; Man kann es auch ganz lapidar so ausdrücken: &nbsp; Die perfekte Quellencodierung ist hier &bdquo;gar keine Codierung&rdquo;.
 *Eine redundante Binärquelle mit &nbsp;$p_{\rm A} = 0.89$,&nbsp; $p_{\rm B} = 0.11$ &nbsp; ⇒ &nbsp; $H = 0.5$&nbsp; könnte man mit einer perfekten Quellencodierung durch &nbsp;$L = 5000$&nbsp; Bit darstellen, ohne dass wir hier sagen können, wie diese perfekte Quellencodierung aussieht.
@@ Zeile 320: / Zeile 320: @@
-Bei allen diesen Beispielen für perfekte Quellencodierung wäre die relative Redundanz der Codefolge (also die Restredundanz)&nbsp; $r = 0$. Das heißt: &nbsp; Die Nullen und Einsen sind gleichwahrscheinlich und es bestehen keine statistischen Bindungen zwischen den einzelnen Binärsymbolen.
+Bei allen diesen Beispielen für perfekte Quellencodierung wäre die relative Redundanz der Codefolge (also die Restredundanz)&nbsp; $r = 0$.&nbsp; Das heißt: &nbsp; Die Nullen und Einsen sind gleichwahrscheinlich und es bestehen keine statistischen Bindungen zwischen den einzelnen Binärsymbolen.
 <br>
@@ Zeile 336: / Zeile 336: @@
 :$$\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 [[Informationstheorie/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; [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch#LZ77_.E2.80.93_die_Grundform_der_Lempel.E2.80.93Ziv.E2.80.93Algorithmen|LZ77]]&nbsp; und&nbsp; [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch#Die_Lempel.E2.80.93Ziv.E2.80.93Variante_LZ78|LZ78]]&nbsp; sind aber nur geringfügig schlechter.
+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.&nbsp; Alle Kurven gelten exakt nur für den [[Informationstheorie/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; [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch#LZ77_.E2.80.93_die_Grundform_der_Lempel.E2.80.93Ziv.E2.80.93Algorithmen|LZ77]]&nbsp; und&nbsp; [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch#Die_Lempel.E2.80.93Ziv.E2.80.93Variante_LZ78|LZ78]]&nbsp; sind aber nur geringfügig schlechter.
 Die drei Grafiken zeigen für verschiedene Nachrichtenquellen die Abhängigkeit folgender Größen von der Quellensymbolfolgenlänge&nbsp; $N$:
@@ Zeile 388: / Zeile 388: @@
 *Nach Mittelung über zehn Versuchsreihen ergibt sich&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.
-*In diesem Bereich gilt nämlich&nbsp; $L > N$, das heißt: &nbsp; <br>Die rote Kurve liegt oberhalb der schwarzen.
+*In diesem Bereich gilt nämlich&nbsp; $L > N$, das heißt: &nbsp; <br>Die rote Kurve liegt geringfügig oberhalb der schwarzen.
@@ Zeile 395: / Zeile 395: @@
 [[Datei:Inf_T_2_2_S8b_neu.png|right|frame|Einige Zahlenwerte zur Effizienz der LZW–Codierung]]
-*Der Komprimierungsfaktor&nbsp; $K(n)= L(n)/N$&nbsp; nimmt mit steigendem&nbsp; $N$&nbsp; nur sehr langsam ab&nbsp; (Zeile 3).
+*Der Komprimierungsfaktor&nbsp; $K(N)= L(N)/N$&nbsp; nimmt mit steigendem&nbsp; $N$&nbsp; nur sehr langsam ab&nbsp; (Zeile 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;
 *Entsprechend einschlägiger Literaturangaben nimmt diese Restredundanz proportional zu&nbsp; $\big[\hspace{0.05cm}\lg(N)\hspace{0.05cm}\big]^{-1}$&nbsp; ab.

@@ Zeile 113: / Zeile 113: @@
 ==LZ77 – die Grundform der Lempel–Ziv–Algorithmen  ==
 <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:
+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; $\rm LZ$–Verfahren)&nbsp; kann wie folgt charakterisiert werden:
 *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; &bdquo;Phrasen&rdquo;&nbsp; bezeichnet, in einem ausreichend großen Wörterbuch.
 *Im Gegensatz zur ein paar Jahre 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.

@@ Zeile 376: / Zeile 376: @@
 ==Quantitative Aussagen zur asymptotischen Optimalität==
 <br>
-Die Ergebnisse der letzten Seite haben gezeigt, dass die relative Restredundanz $r(N = 10000)$ deutlich größer ist als der theoretisch versprochene Wert $r(N \to \infty) = 0$.
+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$.
-Dieses praxisrelevante Ergebnis soll nun am Beispiel der redundanten Binärquelle mit $H = 0.5 \ \rm bit/Quellensymbol$ entsprechend der mittleren Grafik auf der letzten Seite präzisiert werden, wobei wir aber nun für die Quellensymbolfolgenlänge Werte zwischen $N=10^3$ und $N=10^{12}$ betrachten.
+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.
-[[Datei:P_ID2443__Inf_T_2_2_S8_neu.png|frame|LZW–Restredundanz $r(N)$ bei redundanter Binärquelle $(H = 0.5)$ ]]
+[[Datei:P_ID2443__Inf_T_2_2_S8_neu.png|frame|LZW–Restredundanz&nbsp; $r(N)$&nbsp; bei redundanter Binärquelle&nbsp; $(H = 0.5)$ ]]
 {{GraueBox|TEXT=
-$\text{Beispiel 7:}$&nbsp; Die Grafik zeigt Simulationen mit $N = 1000$ Binärsymbolen.
+$\text{Beispiel 7:}$&nbsp; Die Grafik zeigt Simulationen mit&nbsp; $N = 1000$&nbsp; Binärsymbolen.
-*Nach Mittelung über zehn Versuchsreihen ergibt sich $r(N = 1000) ≈35.2\%$.
+*Nach Mittelung über zehn Versuchsreihen ergibt sich&nbsp; $r(N = 1000) ≈35.2\%$.
-*Unterhalb des gelben Punktes $($im Beispiel bei $N ≈ 150)$ bringt der LZW–Algorithmus sogar eine Verschlechterung.
+*Unterhalb des gelben Punktes&nbsp; $($im Beispiel bei&nbsp; $N ≈ 150)$&nbsp; bringt der LZW–Algorithmus sogar eine Verschlechterung.
-*In diesem Bereich gilt nämlich $L > N$, das heißt: &nbsp; <br>Die rote Kurve liegt oberhalb der schwarzen.
+*In diesem Bereich gilt nämlich&nbsp; $L > N$, das heißt: &nbsp; <br>Die rote Kurve liegt oberhalb der schwarzen.
-*In der Zeile 4 ist die Restredundanz $r(N)$ für verschiedene Folgenlängen  zwischen $N =1000$ und $N =50000$ angegeben. Man erkennt den nur langsamen Abfall des Komprimierungsfaktors $K(n)= L(n)/N$ mit steigendem $N$.
+In der unteren Tabelle sind die Ergebnisse für diese redundante Binärquelle&nbsp; $(H = 0.5)$&nbsp; zusammengefasst:
-*Entsprechend einschlägiger Literaturangaben nimmt die Restredundanz proportional zu $1/\lg(N)$ ab. In Zeile 5 sind die Ergebnisse einer empirischen Formel eingetragen $($Anpassung für $N = 10000)$:
-:$$r\hspace{0.05cm}'(N) = \frac{A}{ {\rm lg}\hspace{0.1cm}(N)}
+:$$r\hspace{0.05cm}'(N) = \frac{A}{ {\rm lg}\hspace{0.1cm}(N)}\hspace{0.5cm}{\rm mit}$$
-\hspace{0.5cm}{\rm mit}\hspace{0.5cm} 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}.$$
-*Man erkennt die gute Übereinstimmung zwischen unseren Simulationsergebnissen $r(N)$ und der Faustformel $r\hspace{0.05cm}′(N)$.
+*Man erkennt die gute Übereinstimmung zwischen unseren Simulationsergebnissen&nbsp; $r(N)$&nbsp; und der Faustformel&nbsp; $r\hspace{0.05cm}′(N)$.
-*Man erkennt aber auch, dass für $N = 10^{12}$ die Restredundanz des LZW–Algorithmus noch immer $8.8\%$ beträgt.
+*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.
+*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]].}}

@@ Zeile 226: / Zeile 226: @@
 ==Der Lempel–Ziv–Welch–Algorithmus  ==
 <br>
-Die heute gebräuchlichste Variante der Lempel–Ziv–Komprimierung wurde von [https://de.wikipedia.org/wiki/Terry_Welch Terry Welch] entworfen und 1983 veröffentlicht. Wir bezeichnen diese im Folgenden als den ''Lempel–Ziv–Welch–Algorithmus'', abgekürzt mit LZW. Ebenso wie LZ78 leichte Vorteile gegenüber LZ77 aufweist (wie zu erwarten – warum sonst hätte der Algorithmus modifiziert werden sollen?), hat LZW gegenüber LZ78 auch mehr Vorteile als Nachteile.
+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.
-[[Datei:P_ID2430__Inf_T_2_2_S4_neu.png|center|frame|LZW–Codierung der Folge '''ABABCBCBAABCABe''']]
+[[Datei:P_ID2430__Inf_T_2_2_S4_neu.png|center|frame|LZW–Codierung der Folge&nbsp; '''ABABCBCBAABCABe''']]
-Die Grafik zeigt die Coderausgabe für die beispielhafte Eingangsfolge '''ABABCBCBAABCABe'''. Rechts dargestellt ist das Wörterbuch (rot hinterlegt), das bei der LZW–Codierung sukzessive entsteht. Die Unterschiede gegenüber LZ78 erkennt man im Vergleich zur Grafik auf der letzten Seite, nämlich:
+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:
-*Bei LZW sind im Wörterbuch schon zu Beginn ($i = 0$) alle vorkommenden Zeichen eingetragen und einer Binärfolge zugeordnet, im Beispiel mit den Indizes $I = 0$, ... , $I = 3$.
+*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.
-*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.
+*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; [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch#Decodierung_des_LZW.E2.80.93Algorithmus|Decodierung des LZW&ndash;Algorithmus]]&nbsp; beschrieben.
 {{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 '''ABABCBCBAABCABe''' vorausgesetzt.
+$\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.
-Die folgende Beschreibung bezieht sich also auf die obige Grafik.
+<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>Schritt i = 0</u> (Vorbelegung): &nbsp; Die erlaubten Zeichen '''A''', '''B''', '''C''' und '''e''' („end–of–file”) werden in das Wörterbuch eingetragen und den Indizes $I = 0$, ... , $I = 3$ zugeordnet.
+<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>Schritt i = 1</u>: &nbsp; '''A''' wird durch den Dezimalindex $I = 0$ codiert und dessen Binärdarstellung '''0000''' übertragen. Anschließend wird ins Wörterbuch die Kombination aus dem aktuellen Zeichen '''A''' und dem nachfolgenden Zeichen '''B''' der Eingangsfolge unter dem Index $I = 4$ abgelegt.
+<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>Schritt i = 2</u>: &nbsp; Darstellung von '''B''' durch Index $I = 1$ bzw. '''0001''' (binär) sowie Wörterbucheintrag von '''BA''' mit Index $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>Schritt i = 3</u>: &nbsp; Aufgrund des Eintrags '''AB''' zum Zeitpunkt $i = 1$ ist der zu übertragende Index $I = 4$ (binär: '''0100'''). Neuer Eintrag ins Wörterbuch '''ABC''' unter $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>Schritt i = 8</u>: &nbsp; Hier werden die Zeichen '''ABC''' gemeinsam durch den Index $I = 6$ (binär: '''0110''') dargestellt und der Eintrag für '''ABCA''' vorgenommen.
+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:
+*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.
-Mit der Codierung von '''e''' (EOF–Marke) ist der Codiervorgang nach zehn Schritten beendet. Bei LZ78 wurden nur acht Schritte benötigt. Es ist aber zu berücksichtigen:
+*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)$.}}
@@ Zeile 262: / Zeile 258: @@
 ==Lempel–Ziv–Codierung mit variabler Indexbitlänge ==
 <br>
-Aus Gründen einer möglichst kompakten Darstellung betrachten wir nun nur noch Binärquellen mit dem Wertevorrat $\{$'''A''', '''B'''$\}$. Das Abschlusszeichen '''end–of–file''' bleibt ebenfalls unberücksichtigt.
+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.
 [[Datei:P_ID2432__Inf_T_2_2_S5_neu.png|center|frame|LZW–Codierung einer binären Eingangsfolge]]
-Wir demonstrieren die LZW–Codierung anhand eines Bildschirmabzugs unseres interaktiven Flash–Moduls [[Applets:Lempel-Ziv-Welch|Lempel–Ziv–Welch&ndash;Algorithmen]].
+Wir demonstrieren die LZW–Codierung anhand eines Bildschirmabzugs unseres interaktiven Flash–Moduls&nbsp; [[Applets:Lempel-Ziv-Welch|Lempel–Ziv–Welch&ndash;Algorithmen]].
-*Beim ersten Codierschritt $(i = 1)$ wird '''A'''  &nbsp;⇒&nbsp;  '''0'''  codiert. Danach erfolgt im Wörterbuch der Eintrag mit dem Index $I = 2$ und dem Inhalt '''AB'''.
+*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'''.
-*Da es bei Schritt $i = 1$  im Wörterbuch mit '''A''' und '''B''' nur zwei Einträge gibt, genügt ein Bit. Dagegen werden bei Schritt $i = 2$ und $i = 3$ für '''B'''  &nbsp;⇒&nbsp;  '''01''' bzw. '''A'''  &nbsp;⇒&nbsp;  '''00''' jeweils zwei Bit benötigt.
+*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.
-*Ab $i = 4$ erfolgt die Indexdarstellung mit drei Bit, ab $i = 8$ mit vier Bit und ab $i = 16$ mit fünf Bit. Hieraus lässt sich ein einfacher Algorithmus für die jeweilige Index–Bitanzahl $L(i)$ ableiten.
+*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.
-*Betrachten wir abschließend den Codierschritt $i = 18$. Hier wird die rot markierte Sequenz '''ABABB''', die zum Zeitpunkt $i = 11$ in das Wörterbuch eingetragen wurde $($Index $I = 13$ ⇒ '''1101'''$)$ bearbeitet. Die Coder&ndash;Ausgabe lautet wegen $i ≥ 16$ aber nun '''01101''' (grüne Markierung bei der Coder&ndash;Ausgabe).
+*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).
-Die Aussagen gelten auch für [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch#Die_Lempel.E2.80.93Ziv.E2.80.93Variante_LZ78|LZ78]]. Das heißt: &nbsp; Auch beim LZ78 ergibt sich durch eine variable Indexbitlänge die gleiche Verbesserung  wie beim LZW.
+Die Aussagen gelten auch für&nbsp; [[Informationstheorie/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.

@@ Zeile 180: / Zeile 180: @@
 ==Die Lempel–Ziv–Variante LZ78  ==
 <br>
-Der LZ77–Algorithmus erzeugt dann eine sehr ineffiziente Ausgabe, wenn sich häufigere Zeichenfolgen erst mit größerem Abstand wiederholen. Solche Wiederholungen können aufgrund der begrenzten Puffergröße $G$ des ''Sliding Window'' oft nicht erkannt werden.
+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.
 Lempel und Ziv haben dieses Manko bereits ein Jahr nach der Veröffentlichung der ersten Version LZ77 korrigiert:
 *Der Algorithmus LZ78 verwendet zur Komprimierung anstelle des lokalen Wörterbuchs (Suchpuffer) ein globales Wörterbuch.
-*Bei entsprechender Wörterbuchgröße lassen sich somit auch solche Phrasen, die schon längere Zeit vorher aufgetaucht sind, effizient komprimieren.
+*Bei entsprechender Wörterbuchgröße lassen sich somit auch solche Phrasen, die schon längere Zeit vorher aufgetreten sind, effizient komprimieren.
 {{GraueBox|TEXT=
 $\text{Beispiel 4:}$&nbsp;
-Zur Erklärung des LZ78–Algorithmus betrachten wir die gleiche Folge '''ABABCBCBAABCABe''' wie für das LZ77–$\text{Beispiel 3}$.
+Zur Erklärung des LZ78–Algorithmus betrachten wir die gleiche Folge&nbsp; '''ABABCBCBAABCABe'''&nbsp; wie für das LZ77–$\text{Beispiel 3}$.
 [[Datei:Inf_T_2_2_S3_neu.png|frame|Generierung des Wörterbuchs und Ausgabe bei LZ78]]
-*In Spalte 5 findet man die formalisierte Coderausgabe (Index $I$, neues Zeichen $Z$).
-*In Spalte 6 ist die dazugehörige Binärcodierung angegeben mit vier Bit für den Index und der gleichen Zeichenzuordnung '''A''' &#8594; '''00''', '''B''' &#8594; '''01''', '''C''' &#8594; '''10''', '''e''' („end–of–file”) &#8594; '''11''' wie im $\text{Beispiel 3}$.
+*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}$.
 <br clear=all>
-*Zu Beginn (Schritt $\underline{i = 0}$) ist das Wörterbuch (WB) leer bis auf den Eintrag '''ε''' (leeres Zeichen, nicht zu verwechseln mit dem Leerzeichen, das aber hier nicht verwendet wird) mit Index $I = 0$.
+*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$.
-*Im Schritt $\underline{i = 1}$ findet man im Wörterbuch noch keinen verwertbaren Eintrag, und es wird ('''0, A''') ausgegeben ('''A''' folgt auf '''ε'''). Im Wörterbuch erfolgt der Eintrag '''A''' in Zeile $I = 1$ (abgekürzt '''1: A''').
+*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''').
-*Damit vergleichbar ist die Vorgehensweise im zweiten Schritt ($\underline{i = 2}$). Ausgegeben wird hier ('''0, B''') und ins Wörterbuch wird '''2: B''' eingetragen.
+*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.
-*Da bei Schritt $\underline{i = 3}$ bereits der Eintrag '''1: A''' gefunden wird, können hier die Zeichen '''AB''' gemeinsam durch ('''1, B''') codiert werden und es wird der neue Wörterbucheintrag '''3: AB''' vorgenommen.
+*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.
-*Nach Codierung und Eintrag des neuen Zeichens '''C''' in Schritt $\underline{i = 4}$ wird im Schritt $\underline{i = 5}$ das Zeichenpaar '''BC''' gemeinsam codiert  ⇒  ('''2, C''') und in das Wörterbuch '''5: BC''' eingetragen.
+*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.
-*In Schritt $\underline{i = 6}$ werden mit '''6: BA''' ebenfalls zwei Zeichen gemeinsam behandelt und in den beiden letzten Schritten jeweils drei, nämlich '''7: ABC''' und '''8: ABe'''.
+*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'''.
-*Die Ausgabe (3, '''C''') in Schritt $\underline{i = 7}$ steht für „WB(3) + '''C”''' = '''ABC''' und die Ausgabe (3, '''e''') in Schritt $\underline{i = 8}$ für '''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'''.
-In diesem $\text{Beispiel 4}$ besteht somit die LZ78–Codesymbolfolge aus $8 · 6 = 48$ Bit. Das Ergebnis ist vergleichbar mit LZ77–$\text{Beispiel 3}$ $(49$ Bit$)$.}}
+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$)$.}}
 {{BlaueBox|TEXT=
-$\text{Fazit:}$&nbsp;  Auf Details und Verbesserungen von LZ78 wird hier verzichtet. Hier verweisen wir auf den [[Informationstheorie/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.  Soviel nur vorneweg:
+$\text{Fazit:}$&nbsp;  Auf Details und Verbesserungen von LZ78 wird hier verzichtet.&nbsp; Hier verweisen wir auf den&nbsp; [[Informationstheorie/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:
-*Der Index $I$ wird hier einheitlich mit vier Bit dargestellt, wodurch das Wörterbuch auf 16 Einträge beschränkt ist. Durch eine ''variable Bitanzahl'' für den Index kann man diese Einschränkung umgehen. Gleichzeitig erhält man so einen besseren Komprimierungsfaktor.
+*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.
-*Das Wörterbuch muss bei allen LZ–Varianten nicht übertragen werden, sondern wird beim Decoder in genau gleicher Weise erzeugt wie auf der Coderseite. Die Decodierung erfolgt bei LZ78 – nicht aber bei LZW – ebenfalls in analoger Weise wie die Codierung.
+*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.
-*Alle LZ–Verfahren sind asymptotisch optimal, das heißt, dass bei unendlich langen Folgen die mittlere Codewortlänge $L_{\rm M}$ pro Quellensymbol gleich der Quellenentropie $H$ ist.
+*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.
-*Bei kurzen Folgen ist die Abweichung allerdings beträchtlich. Mehr dazu am [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch#Quantitative_Aussagen_zur_asymptotischen_Optimalit.C3.A4t|Kapitelende]].}}
+*Bei kurzen Folgen ist die Abweichung allerdings beträchtlich.&nbsp; Mehr dazu am&nbsp; [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch#Quantitative_Aussagen_zur_asymptotischen_Optimalit.C3.A4t|Kapitelende]].}}