Komprimierung nach Lempel, Ziv und Welch

1. Informationstheorie
2. Quellencodierung – Datenkomprimierung
3. Komprimierung nach Lempel, Ziv und Welch

• Vorherige Seite
• Nächste Seite

• Vorherige Seite
• Nächste Seite

Statische und dynamische Wörterbuchtechniken

Viele Datenkomprimierungsverfahren verwenden Wörterbücher. Die Idee ist dabei die Folgende: Man konstruiere eine Liste der Zeichenmuster, die im Text vorkommen, und codiere diese Muster als Indizes der Liste. Besonders effizient ist diese Vorgehensweise, wenn sich bestimmte Muster im Text häufig wiederholen und dies bei der Codierung auch berücksichtigt wird. Hierbei unterscheidet man:

• Verfahren mit statischem Wörterbuch,
• Verfahren mit dynamischem Wörterbuch (Beschreibung auf der nächsten Seite).

Verfahren mit statischem Wörterbuch Ein statisches Wörterbuch ist nur für ganz spezielle Anwendungen sinnvoll, zum Beispiel für eine Datei der folgenden Form:

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

für die mit 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} \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}$$

Bei dieser spezifischen Anwendung lässt sich die erste Zeile mit 14 · 6 = 84 Bit darstellen. Dagegen würde man bei herkömmlicher Binärcodierung 39 · 7 = 273 Bit benötigen (aufgrund der Kleinbuchstaben im Text reichen hier 6 Bit pro Zeichen nicht aus). Für den gesamten Text ergeben sich 103 · 6 = 618 Bit gegenüber 196 · 7 = 1372 Bit. Allerdings muss die Codetabelle auch dem Empfänger bekannt sein.

Verfahren mit dynamischem Wörterbuch Alle relevanten Komprimierungsverfahren arbeiten allerdings nicht mit statischem Wörterbuch, sondern mit dynamischen Wörterbüchern, die erst während der Codierung sukzessive entstehen:

• Solche Verfahren sind flexibel einsetzbar und müssen nicht an die Anwendung adaptiert werden. Man spricht von universellen Quellencodierverfahren.
• Es genügt dann ein einziger Durchlauf, während bei Verfahren mit statischem Wörterbuch die Datei vor dem Codiervorgang erst analysiert werden muss.
• An der Sinke wird das dynamische Wörterbuch in gleicher Weise generiert wie bei der Quelle. Damit entfällt die Übertragung des Wörterbuchs.

{{{TEXT}}}

{{{TEXT}}}

LZ77 – die Grundform der Lempel–Ziv–Algorithmen

Die wichtigsten Verfahren zur Datenkomprimierung mit dynamischem Wörterbuch gehen auf Abraham Lempel und Jacob Ziv zurück. Die gesamte Lempel–Ziv–Familie (im Folgenden verwenden wir hierfür kurz: 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 Phrasen bezeichnet, in einem ausreichend großen Wörterbuch.
• Im Gegensatz zur vorher entwickelten Entropiecodierung (z.B. von Shannon und Huffman) 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.
• LZ–Komprimierungsverfahren kommen dementsprechend mit einem einzigen Durchgang aus und auch der Quellensymbolumfang $M$ und die Symbolmenge $\{q_μ\}$ mit $μ = 1$, ... , $M$ muss nicht bekannt sein. Man spricht von universeller Quellencodierung (englisch: Universal Source Coding).

Wir betrachten zunächst den Lempel–Ziv–Algorithmus in seiner ursprünglichen Form aus dem Jahre 1977, bekannt unter der Bezeichnung LZ77. Dieser arbeitet mit einem Fenster, das sukzessive über den Text verschoben wird; man spricht auch von einem Sliding Window. Die Fenstergröße $G$ ist dabei ein wichtiger Parameter, der das Komprimierungsergebnis entscheidend beeinflusst.

Die Grafik zeigt eine beispielhafte Belegung des Sliding Windows. Dieses ist unterteilt in

• den Vorschaupuffer (blaue Hinterlegung) und
• den Suchpuffer (rote Hinterlegung, mit Positionen $P = 0$, ... , $7$ ⇒ $G = 8$).

Der bearbeitete Text umfasst die vier Worte Miss, Mission, Mississippi und Mistral, jeweils getrennt durch einen Bindestrich. Zum betrachteten Zeitpunkt steht im Vorschaupuffer Mississi.

• Gesucht wird nun im Suchpuffer die beste Übereinstimmung ⇒ die Zeichenfolge mit der maximalen Übereinstimmungslänge $L$. Diese ergibt sich für die Position $P = 7$ und die Länge $L = 5$ zu Missi.
• Dieser Schritt wird durch das Triple (7, 5, s) ausgedrückt ⇒ allgemein ( $P$, $L$, $Z$ ), wobei $Z$ = s das Zeichen angibt, das nicht mehr mit der gefundenen Zeichenfolge im Suchpuffer übereinstimmt.
• Anschließend wird das Fenster um $L + 1 = 6$ Zeichen nach rechts verschoben. Im Vorschaupuffer steht nun sippi–Mi, im Suchpuffer n–Missis und die Codierung ergibt das Triple (2, 2, p).

Im folgenden Beispiel werden die LZ77–Codier– und Decodier–Algorithmen genauer beschrieben.

{{{TEXT}}}

Die Lempel–Ziv–Variante LZ78

Der LZ77–Algorithmus erzeugt dann eine sehr ineffiziente Ausgabe, wenn sich häufigere Zeichenfolgen erst mit größerem Abstand wiederholen. Aufgrund der begrenzten Puffergröße $G$ des Sliding Window können solche Wiederholungen 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 im Text aufgetaucht sind, effizient komprimieren.

{{{TEXT}}}

Der Lempel–Ziv–Welch–Algorithmus

Die heute gebräuchlichste Variante der Lempel–Ziv–Komprimierung wurde von Terry Welch entworfen und 1983 veröffentlicht. Wir nennen diese 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 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:

• 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$.
• 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 $i$ nur ein Wörterbuchindex $I$ übertragen, während bei LZ78 die Kombination ($I$, $Z$) ausgegeben wird; $Z$ gibt dabei das aktuell neue Zeichen an.
• Aufgrund des Fehlens von $Z$ in der Coderausgabe ist die LZW–Decodierung komplizierter als bei LZ78, wie auf der Seite Decodierung des LZW–Algorithmus beschrieben.

{{{TEXT}}}

Auf den beiden folgenden Seiten wird auf die variable Bitanzahl zur Indexdarstellung sowie auf die Decodierung von LZ78– und LZW–codierten Binärfolgen noch im Detail eingegangen.

Lempel–Ziv–Codierung mit variabler Indexbitlänge

Aus Gründen einer möglichst kompakten Darstellung betrachten wir nun nur noch Binärquellen mit dem Wertevorrat { A, B }. Auch das Abschlusszeichen end–of–file bleibt unberücksichtigt.

Wir betrachten die LZW–Codierung anhand eines Bildschirmabzugs unseres interaktiven Flash–Moduls Lempel–Ziv–Algorithmen. Die Aussagen gelten aber in gleicher Weise für LZ78.

• Beim ersten Codierschritt ( $i$ = 1 ) wird A mit 0 codiert. Danach erfolgt im Wörterbuch der Eintrag mit dem Index $I$ = 2 und dem Inhalt 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 2 und 3 für B ⇒ 01 bzw. A ⇒ 00 jeweils zwei Bit benötigt.
• Ab $i$ = 4 erfolgt die Indexdarstellung mit 3 Bit, ab $i$ = 8 mit 4 Bit und ab $i$ = 16 mit 5 Bit. Hieraus lässt sich ein einfacher Algorithmus für die jeweilige Index–Bitanzahl $L(i)$ 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 Ausgabe lautet wegen $i$ ≥ 16 aber nun 01101 (grüne Markierung).

Die Verbesserung durch variable Indexbitlänge ist auch bei LZ78 in gleicher Weise möglich.

Decodierung des LZW–Algorithmus

Am Decoder liegt nun die auf der letzten Seite ermittelte Coder–Ausgabe als Eingangsfolge an. Die Grafik zeigt, dass es auch bei variabler Indexbitlänge möglich ist, diese Folge eindeutig zu decodieren.

Beim Decoder wird das gleiche Wörterbuch generiert wie beim Coder, doch erfolgen hier die Wörterbucheinträge einen Zeitschritt später. Weiter gilt:

• Dem Decoder ist bekannt, dass im ersten Codierschritt der Index $I $ mit nur einem Bit codiert wurde, in den Schritten 2 und 3 mit zwei Bit, ab $i = 4$ mit drei Bit, ab $i = 8$ mit vier Bit, usw.
• Zum Schritt $i = 1$ wird also 0 als A decodiert. Ebenso ergibt sich zum Schritt $i = 2$ aus der Vorbelegung des Wörterbuches und der vereinbarten Zwei–Bit–Darstellung: 1 ⇒ 01 ⇒ B.
• Der Eintrag der Zeile $I = 2$ (Inhalt: AB) des Wörterbuchs erfolgt also erst zum Schritt $i = 2$, während beim Codiervorgang dies bereits am Ende von Schritt $i = 1$ geschehen konnte.
• Betrachten wir weiter die Decodierung für $i = 4$. Der Index $I =2$ liefert das Decodierergebnis AB und im nächsten Schritt ($i = 5$) wird die Wörterbuchzeile $I =5$ mit ABA belegt.
• Diese Zeitverschiebung hinsichtlich der WB–Einträge kann zu Decodierproblemen führen. Zum Beispiel gibt es zum Schritt $i = 7$ noch keinen Wörterbuch–Eintrag mit Index $I = 7$.
• Was ist in einem solchen Fall ( $I = i$ ) zu tun? Man nimmt in diesem Fall das Ergebnis des vorherigen Decodierschrittes (hier: BA für $i = 6$) und fügt das erste Zeichen dieser Sequenz am Ende noch einmal an. Man erhält so das Decodierergebnis für $i = 7$ zu BAB.
• Natürlich ist es unbefriedigend, nur ein Rezept anzugeben. In der Aufgabe 2.4Z sollen Sie das Vorgehen selbst begründen. Wir verweisen hier auf die Musterlösung zur Aufgabe.

Bei der LZ78–Decodierung tritt das hier geschilderte Problem nicht auf, da nicht nur der Index $I $, sondern auch das aktuelle Zeichen $Z$ im Codierergebnis enthalten ist und übertragen wird.

Effizienz der Lempel–Ziv–Codierung

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, ....
• Die Quellenentropie sei $H$. Gibt es keine statistischen Bindungen zwischen den Symbolen, so gilt $H$ = $H_0$, wobei $H_0$ = ld $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.

Nach dem Quellencodierungstheorem muss die mittlere Codewortlänge $L_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}.$$

Gäbe es für eine redundanzfreie binäre Quellensymbolfolge ( $M$ = 2, $p_A$ = $p_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.

• Für diese Nachrichtenquelle ist Lempel–Ziv nicht geeignet. Es wird $L$ > $N$ gelten. Man kann es auch ganz lapidar ausdrücken: Die perfekte Quellencodierung ist hier gar keine Codierung.
• Eine redundante Binärquelle mit $p_A$ = 0.89, $p_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 (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 bit/Quellensymbol.

Bei allen diesen Beispielen für perfekte Quellencodierung wäre die relative Redundanz der Codefolge (Restredundanz) $r$ = 0. Das heißt: Die Nullen und Einsen sind gleichwahrscheinlich und es bestehen keine statistischen Bindungen zwischen einzelnen Symbolen. Das Problem ist: Bei endlicher Folgenlänge $N$ gibt es keine perfekte Quellencodierung.

Von den Lempel–Ziv–Algorithmen weiß man (und kann diese Aussage sogar beweisen), dass sie asymptotisch optimal sind. Das bedeutet, dass die relative Redundanz der Codesymbolfolge

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

(hier als Funktion der Quellensymbolfolgenlänge $N$ geschrieben) für große $N$ den Grenzwert 0 liefert:

$$\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 des Flash–Moduls Lempel–Ziv–Algorithmen zeigt. Die Kurven gelten für den LZW–Algorithmus. Die Ergebnisse für LZ77 und LZ78 sind aber nur geringfügig schlechter.

[[Datei: P_ID2441__Inf_T_2_2_S7a_neu.png|Beispielhafte Verläufe von L(N) und r(N)]]

Diese Grafik (und auch die Grafiken auf den nächsten Seiten) zeigen die Abhängigkeit der folgenden Größen von der Quellensymbolfolgenlänge $N$:

• die erforderliche Bitanzahl ( $N$ · ld $M$) ohne Quellencodierung (schwarze Kurven),
• die erforderliche Bitanzahl ( $H$ · $N$ ) bei perfekter Quellencodierung (grau–gestrichelt),
• die erforderliche Bitanzahl $L(N)$ bei LZW–Codierung (rote Kurven nach Mittelung),
• die relative Redundanz $r(N)$ bei LZW–Codierung (grüne Kurven).

Die Grafik auf dieser Seite gilt für eine redundante Binärquelle ( $M$ = 2 ) mit der Quellenentropie $H$ = 0.5. Man erkennt:

• Die schwarze und die graue Kurve sind echte Gerade (nicht nur bei diesem Parametersatz).
• Die rote Kurve $L(N)$ zeigt eine leichte Krümmung (mit bloßem Auge schwer zu erkennen).
• Wegen dieser Krümmung von $L(N)$ fällt die grüne Kurve $r(N)$ = 1 – 0.5 · $N/L(N)$ leicht ab.
• Abzulesen sind die Zahlenwerte $L$( $N$ = 10000 ) = 6800 und $r$( $N$ = 10000 ) = 26.5%.

In der oberen Grafik ist nochmals die redundante Binärquelle mit $H$ = 0.5 dargestellt. Die mittlere Grafik gilt dagegen für gleichwahrscheinliche Binärsymbole ⇒ $H$ = 1. Hier fallen die graue und die schwarze Gerade zusammen und die leicht gekrümmte rote Kurve liegt erwartungsgemäß darüber. Obwohl hier die LZW–Codierung eine Verschlechterung bringt – erkennbar aus der Angabe $L$( $N$ = 10000 ) = 12330, ist die relative Redundanz mit $r$( $N$ = 10000 ) = 18.9% kleiner als bei der oberen Grafik.

Bei einer redundanten Quaternärquelle mit $H$ = 1.357 wären entsprechend der unteren Grafik ohne Codierung 20000 Bit (für $N$ = 10000) erforderlich und mit LZW–Codierung nur $L$ ≈ 16485. Die relative Redundanz beträgt hier $r$( $N$ = 10000 ) = 17.7%.

Quantitative Aussagen zur asymptotischen Optimalität

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$ → ∞ ) = 0. Dieses praxisrelevante Ergebnis soll nun am Beispiel der redundanten Binärquelle mit $H$ = 0.5 bit/Quellensymbol präzisiert werden.

Die Grafik zeigt jeweils Simulationen mit $N$ = 1000 Binärsymbolen, wobei sich nach Mittelung über 10 Versuchsreihen $r$( $N$ = 1000 ) = 35.2% ergibt. Unterhalb des gelben Punktes (im Beispiel bei $N$ ≈ 150) bringt der LZW–Algorithmus sogar eine Verschlechterung. In diesem Bereich gilt nämlich $L$ > $N$. Die Tabelle fasst die Simulationsergebnisse für die redundante Binärquelle ( $$ = 0.5 ) zusammen: In der Zeile 4 ist die Restredundanz $r(N)$ für verschiedene Folgenlängen $N$ zwischen 1000 und 50000 angegeben. Man erkennt den nur langsamen Abfall mit steigendem $N$. Entsprechend Literaturangaben nimmt die Restredundanz mit 1/lg( $N$ ) ab. In Zeile 5 sind die Ergebnisse einer empirischen Formel eingetragen (Anpassung für $N$ = 10000): $$r'(N) = {A}/{{\rm lg}\hspace{0.1cm}(N)} \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 \hspace{0.05cm}.$$

Man erkennt die gute Übereinstimmung zwischen unseren Simulationsergebnissen $r(N)$, basierend auf unserem Interaktionsmodul Lempel–Ziv–Algorithmen, und der Faustformel $r′(N)$. Man erkennt aber auch, dass für $N$ = 1012 die Restredundanz des LZW–Algorithmus noch immer 8.8% beträgt. Bei anderen Quellen erhält man mit anderen Zahlenwerten des Parameters $A$ ähnliche Ergebnisse. Der prinzipielle Kurvenverlauf bleibt aber gleich. Siehe auch Aufgabe A2.5 und Aufgabe Z2.5.