Datenkompression: Verlustfreie Verfahren: Wörterbuchbasierte Verfahren: LZ78

zurück

5 Verlustfreie_Verfahren

5.2 Wörterbuchbasierte Verfahren

5.2.1 LZ77 - Lempel, Ziv (1977)

5.2.2 LZ78 - Lempel, Ziv (1978)

5.2.3 LZSS - Storer, Szymanski (1982)

5.2.4 LZW - Welch (1984)

5.2.5 LZPP - Pylak (2003)

5.2.6 LZFG - Fiala, Green

5.2.7 LZRW - Williams (1989-1991)

5.2.8 LZV - Vogt (1994)

5.2.9 LZMW - Miller, Wegman (1985)

5.2.10 LZC - ?

5.2.11 LZT - Tischer (1987)

5.2.12 LZJ - Jakobsson

5.2.13 LZR - Rodeh, Pratt, Even

5.2.14 LZB - Bell

5.2.15 LZH - Herd

5.2.16 LZO - Oberhumer

5.2.17 LZP/LZCB - Bloom (1996)

5.2.18 LZAP - Storer (1988)

5.2.19 LZY - Yabba

5.2.20

LZ78 - Lempel, Ziv 1978

Die zweite grundlegende Technik der verlustfreien Datenkompression in Verbindung mit einem Wörterbuchverfahren stammt erneut von Abraham Lempel und Jacob Ziv und wurde im Jahr 1978 vorgestellt. Der Titel der Arbeit, in dem dieses Verfahren vorgestellt wurde, war "Compression of Individual Sequences via Variable-Rate Coding". Dieses Verfahren arbeitet auf eine modifizierte Weise verglichen mit dem Verfahren von 1977 (LZ77). Dieser zweite Algorithmus ist heute unter dem Namen LZ78 bekannt.

Oft wird der LZ78 Algorithmus als etwas grundlegend Neues dargestellt, dabei handelt es sich um eine sehr wichtige Optimierung des LZ77 Algorithmus. Der LZ78 Algorithmus ist der Übergang von einem Verfahren, das auf einem konstant großen Zeichenpuffer arbeitet, auf ein tabellengestütztes Verfahren. Das größte Problem des LZ77-Verfahrens stellt die Redundanz im Suchpuffer dar. Das bedeutet, dass verschiedene Kombinationen von Offset und Längenangaben auf identische Zeichenfolgen zeigen.

Beispiel für Redundanz im Suchpuffer von LZ77

13	12	11	10	9	8	7	6	5	4	3	2	1	0	1	2	3	4	5	6
a	b	c	a	b	c	a	b	c	a	b	c	d	c	a	b	c	a	b	c
Suchpuffer													Vorschaupuffer

Links können sie ein Beispiel sehen, welches die Redundanz im Suchpuffer genauer erläutern soll. Betrachtet man die Zeichenkette "abc", so stellt man fest, dass man sie mit verschiedenen Tupeln (Offset,Länge) darstellen kann. Im Beispiel sind es die Tupel (13,3) (10,3) (7,3) und (4,3). Für die Zeichenkette "ca" trifft ähnliches zu Sie ist an den Positionen (11,2), (8,2) und (5,2) zu finden. Weitere mehrfach auftretende Zeichenketten sind "abcabc", "ab", "bc", "bca", "bcab" und so geht es weiter. Wenn die folgenden (noch zu codierenden) Zeichen aus dem Vorschaupuffer in den Suchpuffer wandern, gibt es noch mehr Tupel für jede einzelne Zeichenkette, ohne dass diese zu Kompression beitragen können. Die Frage lautet nun, ob diese Redundanz wirklich notwendig und sie wirklich unvermeidbar ist. Kann man nicht eine Form der Darstellung finden, in der man diese Offset und Längenabgaben durch etwas effizienteres ersetzt?

Der Schlüssel zur Lösung des dargestellten Problems besteht darin, eine Tabelle zu pflegen, in der bereits alle bekannten Zeichenketten aufbewahrt werden, aber doppelte Einträge nicht ein zweites Mal in diese Tabelle aufgenommen werden und statt der Ausgabe eines Paares von Offset und Länge, wird lediglich der Tabellenindex und ein Folgezeichen in den Ausgabestrom übertragen. Natürlich müssen weiterhin Literale und Tabellenindexe voneinander unterschieden werden. Diese Tabelle wird im Folgenden als Wörterbuch (engl. dictionary) bezeichnet. Im Prinzip verhält sich die Tabelle genau wie ein Wörterbuch, es wird ein bestimmter Tabellenindex auf eine endliche Zeichenkette abgebildet und man achtet streng darauf, ausschließlich neue Wörter/Phrasen in das Wörterbuch aufzunehmen. Gestartet wird stets mit einem leeren oder in manchen Fällen vorinitialisiertem Wörterbuch.

Somit unterscheidet sich der LZ78-Algorithmus vom LZ77 Algorithmus in der Gestalt, dass

• es keinen redundanten Suchpuffer i.e.S, wie beim LZ77 Verfahren mehr gibt, sondern ein Wörterbuch,
• stets nur einzigartige Eintrage in das Wörterbuch aufgenommen werden und
• sich das Wörterbuch an die zu codierenden Daten anpasst.

Codierung

Die Codierung ist relativ einfach. Das codierte Wort besteht aus zwei Informationen. Die erste Information ist der sog. Tabellenindex, die zweite Information ist ein Zeichen. Wie man erkennen kann, verzichtet man bei diesem verfahren auf die Angabe einer Längeninformation, weil sie implizit aus der Tabelle berechenbar ist.

Algorithmus

Code-Fragment

Beispiel

Erneut soll das Beispiel "In Ulm, um Ulm, und um Ulm herum." für die Demonstration der Codierung mit dem LZ78 Algorithmus herangezogen werden.

Beispiel für die Codierung mit dem LZ78 Algorithmus.

Links finden Sie das Beispiel

Codierung des Ausgabestroms

Die Codierung des Ausgabestroms ist relativ simpel. Es werden der Reihe nach die Tupel mit den Tabellenindexen und den Folgesymbolen ausgegeben. Jeder Tabellenindex umfasst 12 Bit. Jedes Folgesymbol 8 Bit. Die Bit-Breite des Tabellenindex ist beliebig parametrierbar. Es gibt Varianten dieser Codierung mit 12 bis 16 Bit Größe, das hängt zumeist von der Größe der zu codierenden Datei ab.

Beispiel für einen Ausgabe-Tupel.

11	10	9	8	7	6	5	4	3	2	1	0	7	6	5	4	3	2	1	0
Tabellenindex												Folgezeichen

Effizienz des Ausgabestroms

Beispiel

Beispiel

Aufgaben

Aufgabe(n) - LZ78-Codierung

1. [M15] Bewerten Sie die konstante Breite eines Ausgabewertes im Hinblick auf die Effizienz. Wie kann dieses Problem behoben werden? (Siehe LZW - Codierer und Decodierer kennen die Bit-Breite des letzten benutzten Tabellenindex, daher dynamische Anpassung an die Bitbreite.)
2. [A20] Untersuchen Sie, ob dieses Verfahren mit einer zusätzlichen Entropiecodierung zu verbessern ist. Wenn ja, an welchen Stellen, müsste der Entropiecodierer ansetzen?
3. [A20] Was müsste man an diesem Verfahren verändern, um Beispielsweise RLE Sequenzen der Länge 8..263 zu implementieren. (1. Entweder Escape Code über Tabellenindex (effizienter), oder 2. gar nichts, weil sich der Algorithmus an die Eingabe anpasst)
4. [A15] Wie können Codierer und Decodierer miteinander synchronisiert werden. Als Beispiel dient eine außerplanmäßige Löschung des Wörterbuchs, weil sich die Statistik der Eingabe vollständig verändert hat und sich das erzeugte Wörterbuch als untauglich herausstellt? (Escapecodes anhand von Tabellenindexen) (nur sehr geringer Codierverlust, Nutzen ist jedoch sehr hoch)
5. [A20] Durch welche Überlegung kann das Folgesymbol eliminiert werden? (LZW-Variante)

Decodierung

Algorithmus

LZ78-Decodier Algorithmus

1. Initialisiere die ersten 256 Tabellenindexe 0..255 mit dem korrespondierenden ASCII-Zeichen.
2. markiere alle weiteren Tabellenindexe als leer
3. lese einen Tabellenindex aus der Eingabe
   1. Schreibe die Zeichenkette Tabelle[index], die in der Tabelle referenziert ist in die Ausgabe.
   2. ermittle, das erste Zeichen von Tabelle[index]
   3. konkateniere es mit der Ausgabe aus dem letzten Schleifendurchlauf und Prüfe, ist dieser Eintrag noch nicht in der Tabelle vorhanden, trage ihn dann die erste unbenutzte Tabellenposition ein.
4. fahre mit Schritt 3 fort, bis jedes Eingabesymbol verarbeitet wurde.

Code-Fragment

Aufgaben

Aufgabe(n) - LZ78-Decodierung

1. Noch keine Aufgaben vorhanden

Codierergebnisse mit dem Calgary Corpus

Bewertung

Dieser Algorithmus ist ebenfalls sehr einfach und repräsentiert die Codiertechnik von vor einem Viertel Jahrhundert. Das interessante an diesem Algorithmus ist, dass er quasi das erste Wörterbuchverfahren ist. Viele andere wörterbuchbasierten Techniken (LZ77 und Ableitungen) werden fälschlicherweise so bezeichnet. Korrekt wäre es, den Begriff Phrasencodierung zu verwenden. Doch dieser Begriff ist relativ unbekannt. In seiner Ur-Version ist auch dieser Algorithmus sehr langsam, insbesondere die Suche erweist sich sehr aufwändig. Das Hauptaugenmerk bei Demonstrationen mit diesem Algorithmus sollte besonders auf die Möglichkeiten gelenkt werden, dass eine gerichtete Kommunikation vom Codierer zum Decodierer sehr einfach implementierbar ist und nahezu transparent implementiert werden kann, ohne die Codiereffizienz signifikant zu beeinträchtigen. Ein weiteres Augenmerk sollte darauf gerichtet werden, dass es möglich ist, diesen Algorithmus extrem zu beschleunigen, ohne dass die Codiereffizienz darunter leidet. Das dritte Augenmerk sollte darauf gerichtet werden, dass die Codiereffizienz dadurch beeinflusst werden kann, indem die Einträge, die in das Wörterbuch aufgenommen werden, nach einer bestimmten Strategie erfolgen. Dieser Algorithmus ist sehr vielseitig modifizierbar und es können verschiedene Ziele erreicht werden. (Geschwindigkeit und/oder Codiereffizienz). Viele Forscher benutzten entweder diesen Algorithmus (LZ78 oder LZ77) als Ausgangsbasis für ihre Überlegungen. Viele der LZ78 Varianten sind jedoch durch Patente geschützt (Die entweder die Codiereffizienz verbessern oder die Geschwindigkeit erhöhen), nicht jedoch der originale Algorithmus.

Für LZ78 spricht, dass er sehr leicht erlernbar, sehr leicht modifizierbar und in weiten Teilen durch gängige Verfahren sehr gut zeitlich optimierbar ist. Gegen das Verfahren spricht, dass die meisten denkbaren Varianten noch immer patentiert sind, teilweise sogar mehrfach also die gleiche 'Innovation'. Durch die Phrasencodierung werden schon sehr gute Ergebnisse in Hinblick auf die Kontextmodellierung erreicht.

CiteSeer-Link auf den Artikel

1. http://citeseer.ist.psu.edu/ziv78compression.html