Lempel-Ziv-Welch-Algorithmus

Grundprinzip und Einsatz

Der Lempel-Ziv-Welch-Algorithmus (LZW) ist ein verlustfreies Komprimierungsverfahren: Nach der Dekompression sind die ursprünglichen Daten vollständig wiederhergestellt. Er wird häufig bei Grafikformaten eingesetzt, etwa im 1987 von CompuServe-Mitarbeitern entwickelten GIF-Format und optional in TIFF. Da sein Wörterbuch erst während der Verarbeitung erzeugt wird, eignet sich LZW grundsätzlich für jede Datenform.

LZW verwendet ein dynamisches Wörterbuch. Häufig vorkommende Zeichenketten wie „ist“, „die“ oder „ein“ werden darin gesammelt und anschließend durch kurze Verweise angesprochen. Das Wörterbuch muss nicht zusätzlich gespeichert werden: Der Decoder baut es aus dem Datenstrom wieder auf. Lempel und Ziv veröffentlichten die wesentlichen Grundlagen 1978 als LZ78; Terry A. Welch nahm 1983 Detailverbesserungen vor. LZW ist ein bekannter Vertreter der LZ-Familie.

Wörterbuch und Codierung

Üblicherweise werden Wörterbucheinträge über einen 12 Bit langen Index angesprochen. Damit sind höchstens 2^{12} = 4096 Einträge möglich. Die Indizes 0 bis 255 sind von Anfang an mit den entsprechenden Bytes belegt: 0 steht für 00_{hex}, 2 für 02_{hex} und 255 für FF_{hex}. Zur Laufzeit ergänzte Einträge beginnen daher bei Index 256.

Ein neuer Eintrag entsteht aus dem gefundenen Muster und dem folgenden Zeichen. Ist eine gefundene Zeichenkette nur ein Zeichen lang, wird meistens das Zeichen selbst gespeichert: Es benötigt 8 Bit, ein Verweis dagegen 12 Bit. Ob im Bitstrom ein Verweis oder ein Symbol folgt, kann durch ein Flag gekennzeichnet werden.

Bei der Kompression sind die 256 Zeichen des Codieralphabets vordefiniert. Der Algorithmus sucht in der Eingabe jeweils das längste bereits vorhandene Muster, gibt dessen Code aus und fügt dieses Muster zusammen mit dem nächsten Zeichen als neuen Wörterbucheintrag hinzu. Anfangs wird ein 9-Bit-Code ausgegeben; später kann er bis zu 12 Bit breit werden, sofern das Alphabet nicht vorher durch einen Clear-Code gelöscht wird. Das Wörterbuch wird im Kompressor mitgeführt, aber nicht ausdrücklich gespeichert, weil der Dekompressor es ebenfalls aus den Codes aufbauen kann.

Eine Tabelle mit 4096 Mustern von jeweils bis zu 4096 Zeichen würde allgemein 16 MiB benötigen. Speicher lässt sich sparen, weil jedes Muster der Länge n mit einem Muster der Länge n-1 beginnt. Deshalb kann ein Eintrag als Paar (Prefix, Suffix) abgelegt werden: Suffix_k ist das letzte Zeichen von Muster k, Prefix_k verweist auf dessen Startmuster. Bei Mustern der Länge eins verweist Prefix_k auf die Konstante <leeres Muster>.

Kompressionsbeispiel

Für die Zeichenkette „LZWLZ78LZ77LZCLZMWLZAP“ werden zunächst einzelne Zeichen ausgegeben und neue Kombinationen eingetragen: LZ wird zu <256>, ZW zu <257> und WL zu <258>. Später können bereits bekannte Folgen als ein Code ausgegeben werden, zum Beispiel LZ als <256>, LZ7 als <259> und WL als <258>.

Die resultierende Ausgabe lautet „L Z W <256> 7 8 <259> 7 <256> C <256> M <258> Z A P“. Sie besteht aus 16 12-Bit-Zeichen, also 24 8-Bit-Zeichen, und enthält dieselbe Information wie die ursprünglichen 22 8-Bit-Zeichen. Das Beispiel zeigt zugleich, dass die Codierung nicht bei jeder kurzen Eingabe kleiner sein muss.

Dekompression und Sonderfall

Bei der Dekompression wird aus den Codewörtern in derselben Reihenfolge dieselbe Mustertabelle aufgebaut. Das funktioniert, weil die Kompression immer das alte Muster ausgibt, nicht das gerade neu erzeugte Muster. Für einen neuen Eintrag wird das vorherige Muster mit dem ersten Zeichen des aktuell auszugebenden Musters verbunden. Der erste Code wird direkt als Muster ausgegeben; danach werden nacheinander weitere Codes gelesen, ausgegeben und passende neue Einträge ergänzt.

Ein Sonderfall tritt auf, wenn das aktuelle auszugebende Muster noch nicht im Wörterbuch vorhanden ist; dies wird auch als K[Omega]K-Fall bezeichnet. Er kommt nur vor, wenn ein Muster unmittelbar mehrfach hintereinander erscheint. Dann lässt sich das fehlende Muster dennoch bestimmen: Es ist das vorherige Muster plus das erste Zeichen des vorherigen Musters.

Beim angegebenen Beispiel entstehen beim Einlesen unter anderem die Einträge LZ (=256), ZW (=257), WL (=258), LZ7 (=259) und 78 (=260). Die Ausgabe der Codes ergibt wieder exakt „LZWLZ78LZ77LZCLZMWLZAP“.

Varianten und Patente

LZ78 arbeitet ähnlich wie LZW, beginnt aber mit einem leeren Wörterbuch. LZC ist eine leichte Abwandlung: Die Index- und damit Wörterbuchgröße ist variabel, beginnt bei 9 Bit und kann bis zu einer vom Nutzer festgelegten Größe wachsen. Dadurch kann eine bis zu 7 % bessere Kompression erwartet werden. LZMW von Victor S. Miller und Mark N. Wegman aus dem Jahr 1985 hängt nicht nur ein Zeichen an eine Wörterbuchzeichenkette an, sondern die längste bekannte Zeichenkette, die unmittelbar danach in der Eingabe vorkommt. Bei speziellen Daten, etwa einer Datei aus 10.000 „a“s, kann dies praktisch sein; bei allgemeinen Daten kommt LZW besser zurecht.

Für LZW und ähnliche Verfahren bestanden Patente. LZ78 war durch das am 10. August 1981 eingereichte und am 7. August 1984 gewährte US-Patent 4.464.650 der Sperry Corporation abgedeckt. Für LZW wurden unter anderem US-Patent 4.814.746 von Miller und Wegman für IBM, eingereicht am 1. Juni 1983, sowie US-Patent 4.558.302 von Welch für Sperry, später Unisys, eingereicht am 20. Juni 1983, ausgestellt.

Besonders umstritten war Patent 4.558.302 wegen des verbreiteten GIF-Formats. Unisys verlangte ab Dezember 1994 zusammen mit CompuServe Lizenzgebühren von Entwicklern kommerzieller GIF-Software und bezog 1999 auch freie Software ein. Dies trug zur schnellen Entwicklung des frei verfügbaren und leistungsfähigeren Grafikformats PNG bei. Viele Rechtsexperten vertraten die Auffassung, Geräte zum reinen Dekomprimieren seien nicht vom Patent erfasst; gzip kann deshalb Z-Dateiarchive lesen, aber nicht schreiben. Das US-Patent lief am 20. Juni 2003 nach 20 Jahren aus, die entsprechenden europäischen, kanadischen und japanischen Patente im Juni 2004.