LZW-Komprimierung

Dezember 2017
Die LZW-Komprimierung basiert auf dem Lempel-Ziv-Welch-Algorithmus und wird vor allem für Grafikformate benutzt, vor allem bei GIFs. Hier erfahren Sie, wie die Datenkomprimierung nach dieser Methode funktioniert.


LZW-Komprimierung

Abraham Lempel und Jakob Ziv sind die Entwicker des LZ77-Komprimierers, der 1977 erfunden wurde (daher auch sein Name). Dieser Komprimierer wurde damals für die Archivierung benutzt (wird von ZIP-, ARJ- und LHA-Formaten benutzt).

1978 entwickelten sie den LZ78-Komprimierer, der auf die Komprimierung von Bilder oder jeden anderen binären Dateityp spezialisiert war.

1984 veränderte ihn Terry Welch (von der Firma Unisys), damit man ihn bei den Kontrollern von Festplatten benutzen konnte. Sein Initial wird zur Abkürzung LZ hinzugefügt und ergibt LZW.
LZW ist ein sehr schneller Algorithmus sowohl bei der Komprimierung als auch bei der Dekomprimierung und basiert auf die Vielzahl von Vorkommen von Zeichensequenzen in der zu kodierenden Kette. Das Prinzip besteht darin, Motive durch einen Zuweisungscode (Kennzeichen) zu ersetzen, indem nach und nach ein Wörterbuch aufgebaut wird.

Desweiteren arbeitet er auf Bits und nicht auf Bytes. Er hängt also nicht von der Art und Weise ab, wie der Prozessor Informationen kodiert. Er ist einer der beliebtesten Algorithmen , und wird insbesondere in Formaten wie TIFF und GIF angewandt. Die LZW-Komprimierungsmethode, die von der Firma Unisys patentiert wurde, ist der der Algorithmus LZ77, der in PNG-Bildern benutzt wird.

Aufbau des Wörterbuchs

Das Wörterbuch wird mit 256 Werten der ASCII-Tabelle initialisiert. Die zu komprimierende Datei wird in Byte-Ketten aufgeteilt (so auch für monochrome Bilder - auf 1 Bit kodiert - ist diese Komprimierung wenig wirksam), jede dieser Ketten wird mit dem Wörterbuch verglichen und hinzugefügt, falls sie nicht vorhanden ist.

Komprimierung

Der Algorithmus durchläuft den Informationsfluss, indem er ihn kodiert; falls eine Kette kleiner ist als das längste Wort im Wörterbuch, so wird sie übertragen.

Dekomprimierung

Bei der Dekomprimierung rekonstruiert der Algorithmus das Wörterbuch andersherum, letzteres muss also nicht gespeichert werden.

Foto: © donets - 123RF.com

Lesen Sie auch


LZW Compression
LZW Compression
Compresión LZW
Compresión LZW
Compression MZW
Compression MZW
Compressione MZW
Compressione MZW
Compressão LZW
Compressão LZW
Letztes Update am 16. November 2017 04:50 von SilkeCCM.
Das Dokument mit dem Titel "LZW-Komprimierung" wird auf CCM (de.ccm.net) unter den Bedingungen der Creative Commons-Lizenz zur Verfügung gestellt. Unter Berücksichtigung der Lizenzvereinbarungen dürfen Sie das Dokument verwenden, verändern und kopieren, wenn Sie dabei CCM deutlich als Urheber kennzeichnen.