Menu

LZW-Komprimierung

Letztes Update am Donnerstag 21 Dezember 2017 à 20:26 von Silke Grasreiner.

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

Warum heißt die Komprimierung LZW?

Abraham Lempel und Jakob Ziv sind die Entwicker des LZ77-Komprimierers, der 1977 erfunden wurde (daher 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 Bildern und von jedem anderen binären Dateityp spezialisiert war.

1984 veränderte ihn Terry Welch (von der Firma Unisys), damit man ihn bei den Controllern von Festplatten benutzen konnte. Sein Initial wurde zur Abkürzung LZ hinzugefügt und ergab LZW.

Besonderheiten von LZW

LZW ist ein sehr schneller Algorithmus, sowohl bei der Komprimierung als auch bei der Dekomprimierung, und basiert auf einer Vielzahl von Zeichensequenzen in der zu codierenden Kette. Das Prinzip besteht darin, Motive durch einen Zuweisungscode (Kennzeichen) zu ersetzen, indem nach und nach ein Wörterbuch aufgebaut wird.

Des Weiteren arbeitet LZW auf Basis von Bits und nicht von Bytes. Der Algorithmus hängt also nicht von der Art und Weise ab, wie der Prozessor Informationen codiert. Er ist einer der beliebtesten Algorithmen und wird insbesondere bei Formaten wie TIFF und GIF angewendet.

Aufbau des Wörterbuchs

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

Komprimierung und Dekomprimierung

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

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

Foto: © donets - 123RF.com

Unsere Inhalte werden in Zusammenarbeit mit IT-Experten erstellt, unter der Leitung von Jean-François Pillou, Gründer von CCM.net. CCM ist eine führende internationale Technologie-Webseite und in elf Sprachen verfügbar.
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.
PNG
Treten Sie der Community bei