Der Lempel-Ziv-Welch (LZW) Algorithmus

Bilder im GIF Dateiformat werden mithilfe der LZW Kompression kodiert. Dieser rekursive Algorithmus wurde zuerst im Jahre 1977 von Abraham Lempel und Jacob Ziv entwickelt und später von Terry Welch verbessert. Der Algorithmus erlangte eine recht zweifelhafte Berühmtheit durch Patenforderungen der Firma Unisys, welche sich nicht nur an kommerzielle Firmen, sondern auch an die Open Source Gemeinschaft und freie Softwareentwickler richteten. Nicht zuletzt aufgrund dieser Patentstreitigkeiten verlor das bis dato überaus populäre GIF Grafikformat an Bedeutung, welches dem Aufstieg des PNG- Grafikformates begünstigte. Glücklicherweise wird dieses Patent dieses Jahr (2004) auslaufen, womit dieser Algorithmus wieder frei verfügbar wird.

Grundlegend funktioniert diese Datenkompression dadurch, dass Farbwerte in Zeichenketten umgewandelt werden, welche dann referenziert und abgepeichert werden. Das Ziel hierbei ist es, möglichst lange Zeichenketten dadurch zu konstruieren, dass nach Sequenzen identischer benachbarter Farbabfolgen in der gesamten Datei gesucht wird. In vereinfachter Form lässt sich dies an folgendem Beispiel verdeutlichen:

1. RRGBGBGGBRGBBGBRRGBGBGBGBBBRRBGBG
2. Wenn die Zeichenkette aufgespaltet wird, lassen sich folgende Sequenzen konstruieren: RRG BGB GG BR GB BGB RRG BGB G BGB B BR R BGB G $_1$_2GG$_3GB$_2$_1$_2G$_2B$_3R$_2G [$_1=RRG][$_2=BGB][$_3=BR]
3. oder eine andere Möglichkeit: RR GBGB G GBR GB B GBR R GBGB GBGB BB RR B GB G $_1$_2G$_3$_4B$_3R$_2$_2BB$_1B$_4G [$_1=RR][$_2=GBGB][$_3=GBR][$_4=GB]
4. ...und noch eine weitere Möglichkeit: RRGBGBG GB R GB B GB RRGBGBG B GB BBRRB GB G $_1$_2R$_2B$_2$_1B$_2BBRRB$_2G [$_1=RRGBGBG][$_2=GB]

Am Günstigsten ist das Ergebnis, welches den geringsten Speicherplatz benötigt. Aus obigen Beispielen wird deutlich, dass viele kurze Sequenzen wie in Beispiel #3 vergleichsweise viel Speicher verbrauchen, wohingegen Konstruktionen mit möglichst langen identischen Sequenzen wie in Beispiel #4 zu einem geringeren Platzbedarf führen.

Wie nun der LZW-Algorithmus zur Kompression und zum Wiederaufbau von GIF-Grafiken funktioniert, ist aus den folgenden Ablaufdiagrammen ersichtlich.

Algorithmus zur Kodierung von GIF-Grafiken

Algorithmus zur Dekodierung von GIF-Grafiken

Obige Diagramme basieren auf den Originalbildern GIFENCOD.GIF und GIFDECOD.GIF von Bob Montgomery