LZ 77

LZ77 ist ein Verfahren zur Datenkompression, das 1977 von Abraham Lempel und Jacob Ziv veröffentlicht wurde. Die Autoren machten sich erstmals 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).

Funktion

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

Geschichte

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, der auch von Phil Katz für den weit verbreiteten Deflate-Algorithmus verwertet wurde. In Reduced Offset Lempel Ziv (ROLZ, auch Lempel Ziv Ross Williams, von Ross Williams, 1991) und dem Lempel-Ziv-Markow-Algorithmus (LZMA, von Igor Pavlov, 1998) fand er bekanntere moderne Nachfolger.

Verwendung

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, der bis ins Jahr 2004 mancherorts in Teilen patentiert war.

Siehe auch

• Lempel-Ziv-Welch-Algorithmus
• LZX (Algorithmus)

Literatur

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

Weblinks

• http://www.lempel-ziv.de/
• Annette Leßmöllmann: „Im Fadenkreuz des Zippers - Komprimierungsprogramme können den Autor eines Textes enttarnen, obwohl sie kein einziges Wort verstehen“. In: DIE ZEIT, Nr. 12/2002, S. 45