LZ77

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Dieser Artikel behandelt den Datenkompressionsalgorithmus, weitere Bedeutungen unter LZ77 (Begriffsklärung)

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

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 Tripel 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) →|________| keine Komprimierung → „A” anhängen
(0,0,N) →|_______A| keine Komprimierung → „N” anhängen
(6,2,A) →|______AN| nächste 2 Zeichen ab Stelle 6 kopieren und „A” anhängen
(0,0,S) →|___ANANA| keine Komprimierung → „S” anhängen
(-,-,-) →|__ANANAS| fertig, da Eingabetupel leer

Geschichte[Bearbeiten]

Die Kompressionsgüte ist direkt vom Lexikon abhängig. Um gute Kompressionsraten zu erhalten, muss das Fenster daher eine gewisse Mindestgröß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 Beachtung. 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[Bearbeiten]

Heute wird die LZ77-Kompression u. a. noch auf dem Game Boy Advance und weiteren eingebetteten Systemen verwendet. Mit der Huffman-Kodierung 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[Bearbeiten]

Literatur[Bearbeiten]

  • 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 1-55851-434-1

Weblinks[Bearbeiten]