Information Theory/Compression According to Lempel, Ziv and Welch

1. Information Theory
2. Quellencodierung – Datenkomprimierung
3. Compression According to Lempel, Ziv and Welch

• Previous page
• Next page

• Previous page
• Next page

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

für die mit 6 Bit pro Zeichen binär–quellencodierte erste Zeile des obigen Textes:

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.

Die Grafik zeigt einen kleinen Ausschnitt von 80 Byte einer BMP–Datei in Hexadezimaldarstellung. Es handelt sich um die unkomprimierte Darstellung eines natürlichen Bildes.

Man erkennt, dass in diesem kleinen Ausschnitt einer Landschaftsaufnahme die Bytes FF, 55 und 47 sehr häufig auftreten. Eine Datenkomprimierung ist deshalb erfolgversprechend. Da aber an anderen Stellen der 4 MByte–Datei oder bei anderem Bildinhalt andere Bytekombinationen dominieren, wäre hier die Verwendung eines statischen Wörterbuchs nicht zielführend.

Bei einer künstlich erzeugten Grafik – zum Beispiel bei einem Formular – könnte man dagegen durchaus mit einem statischen Wörterbuch arbeiten. Wir betrachten hier ein S/W–Bild mit 27 × 27 Pixeln, wobei die Zuordnung „Schwarz” ⇒ 0 und „Weiß” ⇒ 1 vereinbart wurde.

• Im oberen Bereich (schwarze Markierung) wird jede Zeile durch 27 Nullen beschrieben.
• In der Mitte (blaue Markierung) wechseln sich jeweils drei Nullen und drei Einsen ab.
• Unten (rote Markierung) werden pro Zeile 25 Einsen durch zwei Nullen begrenzt.

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_μ$, $μ$ = 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).

Auf der nächsten Seite werden die LZ77–Codier & Decodier–Algorithmen genauer beschrieben.

Als weiteres Beispiel betrachten wir die LZ77–Codierung des Strings ABABCBCBAABCABe entsprechend der folgenden Grafik. Die Eingangsfolge hat die Länge $N$ = 15. Weiter wird vorausgesetzt:

• Zeichen $Z$ ∈ { A, B, C, e }, e entspricht end–of–file (Ende des Eingabe–Strings),
• Größe von Vorschau– und Suchpuffer jeweils $G$ = 4 ⇒ Position $P$ ∈ {0, 1, 2, 3}.

Hierzu einige Anmerkungen (Hinweis: Der Decodiervorgang läuft in vergleichbarer Weise ab):

• Schritt 1 und 2: Es werden die Zeichen A und B durch die Triple (0, 0, A) und (0, 0, B) codiert, da diese im Suchpuffer noch nicht abgelegt sind. Dann Verschiebung des Sliding Window um 1.
• Schritt 3: AB wird über den Suchpuffer maskiert und gleichzeitig das noch unbekannte Zeichen C angehängt. Danach wird das Sliding Window um 3 Positionen nach rechts verschoben.
• Schritt 4: Hier wird gezeigt, dass der Suchstring BCB auch im Vorschaupuffer enden darf. Jetzt kann das Fenster um 4 Positionen verschoben werden.
• Schritt 5: Es wird im Suchpuffer lediglich A gefunden und B abgehängt. Bei größerem Suchpuffer könnten dagegen ABC gemeinsam maskiert werden. Dazu müsste G ≥ 7 sein.
• Schritt 6: Ebenso muss das Zeichen C aufgrund des zu kleinen Puffers separat codiert werden. Da aber CA vorher noch nicht aufgetreten ist, würde G = 7 die Komprimierung nicht verbessern.
• Schritt 7: Mit der Berücksichtigung des end–of–file (e) gemeinsam mit AB aus dem Suchpuffer ist der Codiervorgang abgeschlossen.

Vor der Übertragung müssen natürlich die angegebenen Triple noch binär codiert werden. Dabei benötigt man im vorliegenden Beispiel für

• die Position $P$ ∈ {0, 1, 2, 3} zwei Bit (gelbe Hinterlegung),
• die Kopierlänge $L$ drei Bit (grün hinterlegt), so dass man auch $L$ = 7 noch darstellen könnte,
• alle Zeichen mit jeweils zwei Bit (weiß hinterlegt), z.B. A → 00, B → 01, C = 10, e = 11.

Damit hat die LZ77–Ausgangsfolge eine Länge von 7 · 7 = 49 Bit, während die Eingangsfolge nur 15 · 2 = 30 Bit benötigt ⇒ Eine LZ–Komprimierung macht nur bei großen Dateien Sinn.

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.

Zur Erklärung des LZ78–Algorithmus betrachten wir die gleiche Folge ABABCBCBAABCABe wie für das LZ77–Beispiel auf der letzten Seite.

• Die Grafik zeigt (mit roter Hinterlegung) das Wörterbuch mit Index $I$ (in Dezimal– und Binärdarstellung, Spalte 1 und 2) und dem entsprechenden Inhalt (Spalte 3), der zum Codierschritt $i$ eingetragen wird (Spalte 4). Bei LZ78 gilt sowohl für die Codierung als auch für die Decodierung stets $i$ = $I$.
• In Spalte 5 findet man die formalisierte Coderausgabe (Index I, neues Zeichen Z). In der Spalte 6 ist die dazugehörige Binärcodierung angegeben mit vier Bit für den Index und der gleichen Zeichenzuordnung A → 00, B → 01, C → 10, e („end–of–file”) → 11 wie im letzten Beispiel.

Der LZ78–Algorithmus wird nun anhand dieses Beispiels wie folgt erklärt:

• Zu Beginn (Schritt $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.
• Im Schritt $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).
• Damit vergleichbar ist die Vorgehensweise im zweiten Schritt ( $i$ = 2 ). Ausgegeben wird hier (0, B) und ins Wörterbuch wird 2:B eingetragen.
• Da bei Schritt 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.
• Nach Codierung und Eintrag des neuen Zeichens C in Schritt 4 wird im Schritt 5 das Zeichenpaar BC gemeinsam codiert ⇒ (2, C) und in das Wörterbuch 5:BC eingetragen.
• In Schritt 6 werden mit BA ebenfalls zwei Zeichen gemeinsam behandelt und in den beiden letzten Schritten jeweils drei, nämlich 7:ABC und 8:ABe. Die Ausgabe (3, C) steht für „WB(3) + C” = ABC und die Ausgabe (3, e) für ABe.

Im Beispiel besteht somit die LZ78–Codesymbolfolge aus 8 · 6 = 48 Bit. Das Ergebnis ist vergleichbar mit LZ77 (49 Bit). Auf Details und Verbesserungen von LZ78 wird hier verzichtet. Hier verweisen wir auf den LZW–Algorithmus, der auf den nächsten Seiten beschrieben wird. Soviel nur vorneweg:

• Der Index $I$ wird hier einheitlich mit 4 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.
• 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.
• Alle LZ–Verfahren sind asymptotisch optimal, das heißt, dass bei unendlich langen Folgen die mittlere Codewortlänge pro Quellensymbol gleich der Quellenentropie ist: $L_M$ = $H$. Bei kurzen Folgen ist die Abweichung allerdings beträchtlich. Mehr dazu am Kapitelende.

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. Nähere Angaben zur LZW–Decodierung finden Sie später im Kapitels.

Für die nachfolgende beispielhafte LZW–Codierung wird wie bei der Beschreibung von LZ77 und LZ78 wieder die Eingangsfolge ABABCBCBAABCABe vorausgesetzt.

• Schritt i = 0 (Vorbelegung): 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.
• Schritt i = 1: 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.
• Schritt i = 2: Darstellung von $B$ durch Index $I$ = 1 bzw. 0001 (binär) sowie Wörterbucheintrag von BA mit Index $I$ = 5.
• Schritt i = 3: Aufgrund des Wörterbucheintrags AB zum Zeitpunkt $i$ = 1 ergibt sich der zu übertragende Index $I$ = 4 (binär: 0100). Danach wird ins Wörterbuch ABC neu eingetragen.
• Schritt i = 8: 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 e (EOF–Marke) ist der Codiervorgang nach 10 Schritten beendet. Bei LZ78 wurden nur 8 Schritte benötigt. Es ist aber zu berücksichtigen:

• Der LZW–Algorithmus benötigt für die Darstellung dieser 15 Eingangssymbole nur 10 · 4 = 40 Bit gegenüber den 8 · 6 = 48 Bit bei LZ78. Vorausgesetzt ist für diese einfache Rechnung jeweils 4 Bit zur Indexdarstellung.
• Sowohl bei LZW als auch bei LZ78 kommt man mit weniger Bit aus (nämlich mit 34 bzw. 42), wenn man berücksichtigt, dass zum Schritt $i$ = 1 der Index nur mit 2 Bit codiert werden muss ( $I$ ≤ 3 ) und für $i$ = 2 bis $i$ = 5 auch 3 Bit ausreichen ( $I$ ≤ 7 ).

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.