LZW-Algorithmus

Der LZW-Algorithmus ist eine weitverbreitete verlustfreie Kompression für Fotos und Grafiken, 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.

Was die Wiederholung von Datensequenzen betrifft, so kann es sich beispielsweise in einer Grafik um sich wiederholende Farbmuster handeln oder in einem Text um wiederkehrende Zeichenfolgen. Eine Wiederholung einer Datensequenz liegt vor, wenn beispielsweise eine größere Anzahl aufeinander folgende Pixel vollkommen identische Farben hat. Bei einer solchen Kompression werden nicht jedem Pixel das gleiche Byte zugewiesen, sondern es wird lediglich das erste Pixel mit einem Erkennungscode und dem Byte für den Farbwert gespeichert. Da die folgenden Pixel den gleichen Farbwert haben, wird als nächster Farbwert derjenige gespeichert, der von den vorherigen Farbwerten abweicht. Dadurch werden alle dazwischen liegende Pixel nicht gespeichert, was zu einer erheblichen Datenreduktion führt.

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 eine wesentlich höhere Datenreduktion erreicht als mit dem Run Length Encoding ( RLE). Der LZW-Algorithmus wird im Graphics Interchange Format ( GIF) benutzt, in einer Variante auch im PNG-Dateiformat und optional im Tagged Image File Format ( TIFF).

Informationen zum Artikel
Deutsch: LZW-Algorithmus
Englisch: Lempel, Ziv, Welsh - LZW
Veröffentlicht: 07.05.2020
Wörter: 241
Tags: Grafikkompression
Links: Algorithmus, Kompression, Foto, Grafik, Annahme
Übersetzung: EN
Sharing: