LZW (Lempel, Ziv, Welsh)

Der LZW-Algorithmus ist eine weitverbreitete verlustfreie Kompression, die von Jacob Ziv, Abraham Lempel und Welsh 1984 entwickelt wurde. Es handelt sich um einen eindimensionalen Kompressionsalgorithmus der auf der Annahme basiert, dass sich in einer Datenfolge bestimmte Datensequenzen wiederholen. So beispielsweise in einer Grafik bestimmte Farbmuster oder in einem Text wiederkehrende Zeichenfolgen.

<< Anzeige >>

Beim LZW-Verfahren werden die Daten in Abschnitte zerlegt, die in eine Codetabelle eingetragen werden. Dazu wird ein Datenblock fester Länge abgetastet, daraus werden Pointer gewonnen und ein Wörterbuch abgeleitet. Den zu übertragenden Zeichen werden über eine Zuordnungstabelle LZW-Codes zugewiesen, die auch übertragen werden.

Mit dem LZW-Verfahren wird bei detailreichen Grafiken im Gegensatz zur Lauflängencodierung (RLE) eine wesentlich höhere Datenreduktion erreicht.

LZW wird im GIF-Dateiformat benutzt, in einer Variante auch im PNG-Dateiformat und optional in TIFF.