LZ77-Datenkompression

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten (Unterschied zur vorletzten Version).

LZ77 wurde 1977 von Jacob Ziv und Abraham Lempel als Verfahren zur Datenkompression veröffentlicht. Erstmals machten sich die Autoren zu Nutze, dass ganze Wörter, oder zumindest Teile davon, in einem Text mehrfach vorkommen. Im Gegensatz dazu wurde bei der zuvor fast ausschließlich genutzten Huffman- bzw. Shannon-Fano-Kodierung lediglich die unterschiedliche Häufigkeit einzelner Zeichen in einem Text ausgenutzt (siehe auch Entropiekodierung).

Bei dem LZ77-Algorithmus spricht man von einem gleitenden Fenster (engl.: sliding window). Hierbei wird ein Fenster beliebiger konstanter Größe in einen Vorschau-Puffer und ein Text-Feld eingeteilt. Das Fenster wandert nun über den zu komprimierenden Text, wobei der Inhalt des Vorschau-Puffers zu komprimieren ist und im Text-Feld bereits komprimierte Zeichenketten liegen, die nun als Lexikon benutzt werden.

Komprimierte Daten werden als 3-Tupel ausgegeben. Hierbei wird zunächst die Position des Lexikon-Eintrages im Fenster angegeben (ob von links oder rechts zu zählen begonnen wird ist egal, Hauptsache es wird konsequent gemacht), dann folgt die Länge der zu kopierenden Daten und schließlich das danach folgende Zeichen. Letzteres ist nötig, um Zeichen komprimieren zu können, die sich nicht im Lexikon befinden. Hier wird nämlich als Position und Länge 0 angegeben, womit nur der dritte Teil des Tupels eingefügt wird, nämlich das nächste Zeichen.

Beispiel der Komprimierung des Wortes ANANAS mit einem 8 Zeichen großen Lexikon-Fenster plus 4 Zeichen Vorschau (die Position wird hier von links angegeben):

 01234567
|________|____|
|        |ANAN| => (0,0,A)
|       A|NANA| => (0,0,N)
|      AN|ANAS| => (6,2,A)
|   ANANA|S   | => (0,0,S)
|  ANANAS|    | fertig, da Vorschau leer

Rekonstruktion aus Codewörtern [ (0,0,A),(0,0,N),(6,2,A),(0,0,S) ] mit 8 Zeichen Lexikon-Fenster:

          |01234567|
(0,0,A) =>|_______A| keine Komprimierung => "A" anhängen
(0,0,N) =>|______AN| keine Komprimierung => "N" anhängen
(6,2,A) =>|___ANANA| nächste 2 Zeichen ab Stelle 6 kopieren und "A" anhängen
(0,0,S) =>|__ANANAS| keine Komprimierung => "S" anhängen

Die Kompressionsgüte ist direkt vom Lexikon abhängig. Um gute Kompressionsraten zu erhalten, muss das Fenster daher eine gewisse Größe erreichen. Da aber der zu komprimierende Text mit jedem Eintrag im Lexikon verglichen werden muss, steigt die zum Komprimieren benötigte Zeit mit der Größe des Fensters stark an. Der LZ77-Algorithmus in Reinform fand daher zunächst wenig Beliebtheit. James Storer und Thomas Szymanski verbesserten 1982 einige Probleme in dem nun Lempel-Ziv-Storer-Szymanski (LZSS) genannten Algorithmus.

Heute wird die LZ77-Kompression u.a. noch auf dem Game Boy Advance und weiteren eingebetteten Systemen verwendet. Mit Huffman kombiniert wird LZ77 in dem vielbenutzten Deflate-Algorithmus verwendet, welcher wiederum von sehr bekannten Komprimierungsprogrammen sowie dem Grafikformat PNG genutzt wird. Dass LZ77 mit keinerlei Patenten belegt ist, dürfte wohl der Grund sein, dass er heute immer noch dem ein Jahr später veröffentlichten Nachfolger LZ78 vorgezogen wird.

Siehe auch: Lempel-Ziv-Welch-Algorithmus, LZX (Algorithmus)

[Bearbeiten] Literatur

A Universal Algorithm for Sequential Data Compression, Jacob Ziv und Abraham Lempel, 1977. Erschienen in IEEE Transactions on Information Theory, Nr. 3, Volume 23, Seiten 337-343 [1]
The Data Compression Book, Mark Nelson und Jean-Loup Gailly, 1996 (2. Auflage), New York: M&T Books, ISBN 1558514341