LZW - Lempel-Ziv-Welch

 
erstellt von: Martina Schwed
erstellt am: 05.07.2005 geändert am: 10.04.2006 Modul-ID: 12715
Zu den Favoriten Modul bearbeiten Download des Moduls
Keywords
nächstes Kapitel

Einleitung

LZW steht für Lempel-Ziv-Welch und ist einer der häufigsten Kompressionsalgorithmen für die Datenkompression bei Grafikformaten. LZW ist ein verlustfreier und symmetrischer (= Kodierung und Dekodierung sind gleich schnell) Algorithmus, der in folgenden Formaten genutzt wird:

  • GIF
  • TIFF (optional)
  • PostScript Level II
  • JPEG (optional)

Weiters liegt LZW dem Packprogramm "compress" und "zip" zugrunde.

LZW kann auf jede Form von digitalen Daten angewendet werden, sowohl auf Text- als auch auf Bilddaten. LZW speichert die komprimierten Daten in Byte-Form ab, wodurch eine Plattformunabhängigkeit erreicht wird.

Der LZW-Algorithmus basiert auf der Idee, dass sich in einer Wertefolge bestimmte Teilfolgen wiederholen. Er konstruiert ein Datenlexikon (= data dictonary) aller unkomprimierten Informationen. Der Datenstrom wird auf Muster (= substrings) untersucht und entwickelt daraus die Einträge für das Lexikon. Die Muster werden gemeinsam mit einer Kodierung (= code) im Lexikon gespeichert. Taucht in einem Datenstrom ein bereits im Lexikon gespeichertes Muster auf, so wird die vorhandene Kodierung in den komprimierten Datenstrom geschrieben. Da die Kodierung physikalisch kleiner ist als das Muster, das es repräsentiert, wird eine Datenkompression erreicht.

Eine Besonderheit des LZW-Algorithmus ist, dass das Lexikon nicht mitgespeichert wird, wodurch noch mal Speicherplatz gespart werden kann.

Das Kernstück dieses Algorithmus ist das Lexikon. Da das Lexikon ständig und vor allem schnell durchsucht werden muss, wird das Lexikon nicht sequenziell, also der Reihe nach, sondern mittels eines Hash-Algorithmus durchsucht. Ein Hash-Alogorithmus bildet die Werte auf eine wesentlich kleinere Zielmenge ab und verringert somit die Suchzeit. Weiters muss darauf geachtet werden, dass kein Überlauf im Lexikon auftritt.

nächstes Kapitel

Ergänzende und vertiefende Module

erstellt von: Mirjam Koeck erstellt am: 07.06.2005 geändert am: 10.04.2006

erstellt von: David Schwingenschloegl erstellt am: 02.02.2005 geändert am: 10.04.2006

erstellt von: Mirjam Koeck erstellt am: 02.02.2005 geändert am: 10.04.2006

erstellt von: David Wojak erstellt am: 03.02.2005 geändert am: 10.04.2006

erstellt von: Mirjam Koeck erstellt am: 03.02.2005 geändert am: 10.04.2006