Informationstheorie/Komprimierung nach Lempel, Ziv und Welch - Versionsgeschichte

Maintenance script: Add English interlanguage link

2026-03-16T12:27:27Z

Add English interlanguage link

← Nächstältere Version		Version vom 16. März 2026, 14:27 Uhr
Zeile 398:		Zeile 398:

	{{Display}}		{{Display}}
			[[en:Information_Theory/Compression_According_to_Lempel,_Ziv_and_Welch]]

Maintenance script: Join multi-line formulas for MW 1.43 parser compat

2026-02-24T13:37:47Z

Join multi-line formulas for MW 1.43 parser compat

← Nächstältere Version		Version vom 24. Februar 2026, 15:37 Uhr
Zeile 28:		Zeile 28:
	Beispielsweise ergibt sich mit den Zuordnungen		Beispielsweise ergibt sich mit den Zuordnungen

	:$$"\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}"\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},$$
	"\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 (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},$$
	"\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 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 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 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 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}\_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}$$
	"\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:		für die mit jeweils sechs Bit pro Zeichen binär–quellencodierte erste Zeile des obigen Textes:

	:$$\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}\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)}$$
	\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}		:$$\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)}$$
	\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}		:$$\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} $$
	\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}		:$$\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}$$
	\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}$$

	{{BlaueBox\|TEXT=		{{BlaueBox\|TEXT=
Zeile 355:		Zeile 331:
	:$$r(N) = 1 - 0.5 · N/L(N).$$		:$$r(N) = 1 - 0.5 · N/L(N).$$
	*Abzulesen sind die Zahlenwerte		*Abzulesen sind die Zahlenwerte
	:$$L(N = 10000) = 6800,\hspace{0.5cm}		:$$L(N = 10000) = 6800,\hspace{0.5cm}r(N = 10000) = 26.5\%.$$
	r(N = 10000) = 26.5\%.$$


Zeile 401:		Zeile 376:

	:$$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 mit}$$
	:$$ 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  $r(N)$  und der Faustformel  $r\hspace{0.05cm}′(N)$.		*Man erkennt die gute Übereinstimmung zwischen unseren Simulationsergebnissen  $r(N)$  und der Faustformel  $r\hspace{0.05cm}′(N)$.
	*Man erkennt aber auch, dass die Restredundanz des LZW–Algorithmus für  $N = 10^{12}$  noch immer  $8.8\%$  beträgt.		*Man erkennt aber auch, dass die Restredundanz des LZW–Algorithmus für  $N = 10^{12}$  noch immer  $8.8\%$  beträgt.

Guenter am 8. Juli 2021 um 13:23 Uhr

2021-07-08T13:23:35Z

← Nächstältere Version		Version vom 8. Juli 2021, 15:23 Uhr
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:		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		Beispielsweise ergibt sich mit den Zuordnungen
Zeile 265:		Zeile 265:
	Wir demonstrieren die LZW–Codierung anhand eines Bildschirmabzugs unseres interaktiven SWF–Moduls  [[Applets:Lempel-Ziv-Welch\|Lempel–Ziv–Welch–Algorithmen]].		Wir demonstrieren die LZW–Codierung anhand eines Bildschirmabzugs unseres interaktiven SWF–Moduls  [[Applets:Lempel-Ziv-Welch\|Lempel–Ziv–Welch–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  $(i = 1)$  wird  '''A'''   ⇒  '''0'''  codiert.  Danach erfolgt im Wörterbuch der Eintrag mit dem Index  $I = 2$  und dem  Inhalt  '''AB'''.		*Beim ersten Codierschritt  $(i = 1)$  wird  '''A'''   ⇒  '''0'''  codiert.  Danach erfolgt im Wörterbuch der Eintrag mit dem Index  $I = 2$  und dem  Inhalt  '''AB'''.

Guenter am 29. Juni 2021 um 11:49 Uhr

2021-06-29T11:49:05Z

← Nächstältere Version		Version vom 29. Juni 2021, 13:49 Uhr
Zeile 418:		Zeile 418:
	[[Aufgaben:2.4Z Nochmals LZW-Codierung und -Decodierung\|Aufgabe 2.4Z: Nochmals LZW-Codierung und -Decodierung]]		[[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]]		[[Aufgaben:Aufgabe_2.5Z:_Komprimierungsfaktor_vs._Restredundanz\|Aufgabe 2.5Z: Komprimierungsfaktor vs. Restredundanz]]

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

← Nächstältere Version		Version vom 28. Juni 2021, 19:30 Uhr
Zeile 113:		Zeile 113:
	==LZ77 – die Grundform der Lempel–Ziv–Algorithmen ==		==LZ77 – die Grundform der Lempel–Ziv–Algorithmen ==
	<br>		<br>
	Die wichtigsten Verfahren zur Datenkomprimierung mit dynamischem Wörterbuch gehen auf  [https://de.wikipedia.org/wiki/Abraham_Lempel Abraham Lempel]  und  [https://de.wikipedia.org/wiki/Jacob_Ziv Jacob Ziv]  zurück.  Die gesamte Lempel–Ziv–Familie  (im Folgenden verwenden wir hierfür kurz:   ~~LZ–Verfahren~~)  kann wie folgt charakterisiert werden:		Die wichtigsten Verfahren zur Datenkomprimierung mit dynamischem Wörterbuch gehen auf  [https://de.wikipedia.org/wiki/Abraham_Lempel Abraham Lempel]  und  [https://de.wikipedia.org/wiki/Jacob_Ziv Jacob Ziv]  zurück.  Die gesamte Lempel–Ziv–Familie  (im Folgenden verwenden wir hierfür kurz:   $\rm LZ$–Verfahren)  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.  Man sammelt alle Wortfragmente, die man auch als  &bdquo;Phrasen”  bezeichnet, in einem ausreichend großen Wörterbuch.		*Lempel–Ziv–Verfahren nutzen die Tatsache, dass in einem Text oft ganze Wörter – oder zumindest Teile davon – mehrfach vorkommen.  Man sammelt alle Wortfragmente, die man auch als  &bdquo;Phrasen”  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.		*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.

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

← Nächstältere Version		Version vom 23. Januar 2020, 15:37 Uhr
Zeile 376:		Zeile 376:
	==Quantitative Aussagen zur asymptotischen Optimalität==		==Quantitative Aussagen zur asymptotischen Optimalität==
	<br>		<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  $r(N = 10000)$  deutlich größer ist als der theoretisch versprochene Wert  $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  $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.

	[[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  $r(N)$  bei redundanter Binärquelle  $(H = 0.5)$ ]]
	{{GraueBox\|TEXT=		{{GraueBox\|TEXT=
	$\text{Beispiel 7:}$  Die Grafik zeigt Simulationen mit $N = 1000$ Binärsymbolen.		$\text{Beispiel 7:}$  Die Grafik zeigt Simulationen mit  $N = 1000$  Binärsymbolen.
	*Nach Mittelung über zehn Versuchsreihen ergibt sich $r(N = 1000) ≈35.2\%$.		*Nach Mittelung über zehn Versuchsreihen ergibt sich  $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  $($im Beispiel bei  $N ≈ 150)$  bringt der LZW–Algorithmus sogar eine Verschlechterung.
	*In diesem Bereich gilt nämlich $L > N$, das heißt:   <br>Die rote Kurve liegt oberhalb der schwarzen.		*In diesem Bereich gilt nämlich  $L > N$, das heißt:   <br>Die rote Kurve liegt oberhalb der schwarzen.
	~~<br clear=all>~~
	~~In der folgenden Tabelle sind die Ergebnisse für diese redundante Binärquelle $(H = 0.5)$ zusammengefasst:~~

	~~[[Datei:Inf_T_2_2_S8b_neu.png\|center\|frame\|Einige Zahlenwerte zur Effizienz der LZW–Codierung]]~~

	*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  $(H = 0.5)$  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)$:
			[[Datei:Inf_T_2_2_S8b_neu.png\|right\|frame\|Einige Zahlenwerte zur Effizienz der LZW–Codierung]]

			*Der Komprimierungsfaktor  $K(n)= L(n)/N$  nimmt mit steigendem  $N$  nur sehr langsam ab  (Zeile 3).
			*In Zeile 4 ist die Restredundanz  $r(N)$  für verschiedene Längen zwischen  $N =1000$  und  $N =50000$  angegeben.
			*Entsprechend einschlägiger Literaturangaben nimmt diese Restredundanz proportional zu  $\big[\hspace{0.05cm}\lg(N)\hspace{0.05cm}\big]^{-1}$  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}.$$		\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  $r(N)$  und der Faustformel  $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  $N = 10^{12}$  noch immer  $8.8\%$  beträgt.
			*Bei anderen Quellen erhält man mit anderen  $A$–Werten ähnliche Ergebnisse.  Der prinzipielle Verlauf bleibt gleich.  Siehe auch  [[Aufgaben:Aufgabe_2.5:_Restredundanz_bei_LZW-Codierung\|Aufgabe 2.5]]  und  [[Aufgaben:Aufgabe_2.5Z:_Komprimierungsfaktor_vs._Restredundanz\|Aufgabe 2.5Z]].}}

	Bei anderen Quellen erhält man mit anderen ~~Zahlenwerten des Parameters~~ $A$ ähnliche Ergebnisse. Der prinzipielle ~~Kurvenverlauf~~ bleibt gleich. Siehe auch [[Aufgaben:Aufgabe_2.5:_Restredundanz_bei_LZW-Codierung\|Aufgabe 2.5]] und [[Aufgaben:Aufgabe_2.5Z:_Komprimierungsfaktor_vs._Restredundanz\|Aufgabe 2.5Z]].}}

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

Änderungen zeigen

← Nächstältere Version		Version vom 29. Juni 2021, 13:49 Uhr
Zeile 418:		Zeile 418:
	[[Aufgaben:2.4Z Nochmals LZW-Codierung und -Decodierung\|Aufgabe 2.4Z: Nochmals LZW-Codierung und -Decodierung]]		[[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]]		[[Aufgaben:Aufgabe_2.5Z:_Komprimierungsfaktor_vs._Restredundanz\|Aufgabe 2.5Z: Komprimierungsfaktor vs. Restredundanz]]

← Nächstältere Version		Version vom 29. Juni 2021, 13:38 Uhr
Zeile 300:		Zeile 300:
	<br>		<br>
	Für den Rest dieses Kapitels gehen wir von folgenden Voraussetzungen aus:		Für den Rest dieses Kapitels gehen wir von folgenden Voraussetzungen aus:
	*Der~~  ''~~Symbolumfang~~'' ~~ der Quelle  $($oder im übertragungstechnischen Sinne:   die Stufenzahl)  sei  $M$, wobei  $M$  eine Zweierpotenz darstellt   ⇒   $M = 2, \ 4, \ 8, \ 16$, ....		*Der Symbolumfang der Quelle  $($oder im übertragungstechnischen Sinne:   die Stufenzahl)  sei  $M$, wobei  $M$  eine Zweierpotenz darstellt   ⇒   $M = 2, \ 4, \ 8, \ 16$, ....
	*Die Quellenentropie sei  $H$.  Gibt es keine statistischen Bindungen zwischen den Symbolen und sind diese zudem gleichwahrscheinlich, so gilt  $H = H_0$, wobei  $H_0 = \log_2 \ M$  den Entscheidungsgehalt angibt.  Andernfalls gilt $H < H_0$.		*Die Quellenentropie sei  $H$.  Gibt es keine statistischen Bindungen zwischen den Symbolen und sind diese zudem gleichwahrscheinlich, so gilt  $H = H_0$, wobei  $H_0 = \log_2 \ M$  den Entscheidungsgehalt angibt.  Andernfalls gilt $H < H_0$.
	*Eine Symbolfolge der Länge  $N$  wird quellencodiert und liefert eine binäre Codefolge der Länge  $L$.  Über die Art der Quellencodierung treffen wir vorerst keine Aussage.		*Eine Symbolfolge der Länge  $N$  wird quellencodiert und liefert eine binäre Codefolge der Länge  $L$.  Über die Art der Quellencodierung treffen wir vorerst keine Aussage.
Zeile 312:		Zeile 312:

	{{GraueBox\|TEXT=		{{GraueBox\|TEXT=
	$\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$.		$\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  &bdquo;perfekte Quellencodierung”, so hätte auch die Codefolge die Länge  $L = 10000$.

	<u>Konsequenz:</u>   Ist bei einem Code das Ergebnis  $L = N$  nie möglich, so bezeichnet man diesen Code als  ''nicht–perfekt''.		<u>Konsequenz:</u>   Ist bei einem Code das Ergebnis  $L = N$  nie möglich, so bezeichnet man diesen Code als  &bdquo;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 &bdquo;gar keine Codierung”.		*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 &bdquo;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.		*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.
Zeile 320:		Zeile 320:


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

Zeile 336:		Zeile 336:
	:$$\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  „asymptotisch optimal”  für praxisrelevante Folgenlängen aus?  Nicht allzu viel, wie der nachfolgende Bildschirmabzug unseres Simulationstools  [[Applets:Lempel-Ziv-Welch\|Lempel–Ziv–Algorithmen]]  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]].  Die Ergebnisse für  [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch#LZ77_.E2.80.93_die_Grundform_der_Lempel.E2.80.93Ziv.E2.80.93Algorithmen\|LZ77]]  und  [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch#Die_Lempel.E2.80.93Ziv.E2.80.93Variante_LZ78\|LZ78]]  sind aber nur geringfügig schlechter.		Was aber sagt die Eigenschaft  „asymptotisch optimal”  für praxisrelevante Folgenlängen aus?  Nicht allzu viel, wie der nachfolgende Bildschirmabzug unseres Simulationstools  [[Applets:Lempel-Ziv-Welch\|Lempel–Ziv–Algorithmen]]  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]].  Die Ergebnisse für  [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch#LZ77_.E2.80.93_die_Grundform_der_Lempel.E2.80.93Ziv.E2.80.93Algorithmen\|LZ77]]  und  [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch#Die_Lempel.E2.80.93Ziv.E2.80.93Variante_LZ78\|LZ78]]  sind aber nur geringfügig schlechter.

	Die drei Grafiken zeigen für verschiedene Nachrichtenquellen die Abhängigkeit folgender Größen von der Quellensymbolfolgenlänge  $N$:		Die drei Grafiken zeigen für verschiedene Nachrichtenquellen die Abhängigkeit folgender Größen von der Quellensymbolfolgenlänge  $N$:
Zeile 388:		Zeile 388:
	*Nach Mittelung über zehn Versuchsreihen ergibt sich  $r(N = 1000) ≈35.2\%$.		*Nach Mittelung über zehn Versuchsreihen ergibt sich  $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  $($im Beispiel bei  $N ≈ 150)$  bringt der LZW–Algorithmus sogar eine Verschlechterung.
	*In diesem Bereich gilt nämlich  $L > N$, das heißt:   <br>Die rote Kurve liegt oberhalb der schwarzen.		*In diesem Bereich gilt nämlich  $L > N$, das heißt:   <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]]		[[Datei:Inf_T_2_2_S8b_neu.png\|right\|frame\|Einige Zahlenwerte zur Effizienz der LZW–Codierung]]

	*Der Komprimierungsfaktor  $K(n)= L(n)/N$  nimmt mit steigendem  $N$  nur sehr langsam ab  (Zeile 3).		*Der Komprimierungsfaktor  $K(N)= L(N)/N$  nimmt mit steigendem  $N$  nur sehr langsam ab  (Zeile 3).
	*In Zeile 4 ist die Restredundanz  $r(N)$  für verschiedene Längen zwischen  $N =1000$  und  $N =50000$  angegeben.		*In Zeile 4 ist die Restredundanz  $r(N)$  für verschiedene Längen zwischen  $N =1000$  und  $N =50000$  angegeben.
	*Entsprechend einschlägiger Literaturangaben nimmt diese Restredundanz proportional zu  $\big[\hspace{0.05cm}\lg(N)\hspace{0.05cm}\big]^{-1}$  ab.		*Entsprechend einschlägiger Literaturangaben nimmt diese Restredundanz proportional zu  $\big[\hspace{0.05cm}\lg(N)\hspace{0.05cm}\big]^{-1}$  ab.