Datenkompression


Kriterien

Übersicht Formate

Grundlagen

Kompressionsverfahren

Shannon-Fano

Huffman

Lempel-Ziv (LZ)

LZ77

LZSS

LZ78

LZW

arithmetische Kodierung

Run Length Encoding

Burrows-Wheeler (BWT)

Implementationen

Datenformate


Glossar

Stichwortverzeichnis


Download


www.BinaryEssence.de

Lempel-Ziv-Welch (LZW)


Das LZW-Kodierungsverfahren stellt eine Abwandlung der von Jacob Ziv und Abraham Lempel vorgestellten Kompressionsmethode LZ78 dar. Publiziert wurde das Verfahren 1984 von Terry A. Welch in dem Artikel "A Technique for High-Performance Data Compression".


Terry A. Welch ist zum Zeitpunkt der Entwicklung führender Mitarbeiter des Sperry Research Centers gewesen. Auf das LZW-Verfahren sind in mehreren Ländern gültige Patente erteilt worden, z.B. in den USA, Europa und Japan. Mittlerweile ist die Firma Unisys Patenthalter, es existieren aber vermutlich auch Patente anderer Firmen, die das LZW-Verfahren berühren. Einige dieser Patente laufen vermutlich 2003 (USA) bzw. 2004 (Europa, Japan) aus.


LZW ist wesentlicher Bestandteil von mehreren Datenformaten, die von großer praktischer Bedeutung sind. So setzen z.B. die Graphikformate gif, tif (optional) und Postscript (optional) LZW zur verlustlosen Datenkompression ein.


Prinzip:


LZW enwickelt während der Kodierung ein Wörterbuch, das die bereits kodierten Zeichen aufnimmt. In den kodierten Daten sind lediglich die Indizes der Einträge in diesem Wörterbuch enthalten. Die ersten 256 Einträge werden mit den einzelnen Zeichen vorbesetzt. Alle nachfolgenden Einträge repräsentieren längere Zeichenketten.


Der von Terry A. Welch vorgestellte Algorithmus definiert den Aufbau des Wörterbuchs und beinhaltet Mechanismen, die sicherstellen, dass die Wörterbücher sowohl bei der Enkodierung als auch bei der Dekodierung identisch sind.


 <   ^   > 

GIF: Datenkompression []

Lempel-Ziv-Kodierung (LZ) Lempel-Ziv-78 (LZ78) arithmetische Kodierung



Anzeigen:

Informations- und Kodierungstheorie