Zum Inhalt springen

Lempel-Ziv-Welch-Algorithmus

aus Wikipedia, der freien Enzyklopädie
Dies ist eine alte Version dieser Seite, zuletzt bearbeitet am 29. August 2005 um 17:58 Uhr durch 213.54.79.243 (Diskussion). Sie kann sich erheblich von der aktuellen Version unterscheiden.

Der LZW- oder auch Lempel-Ziv-Welch-Algorithmus ist ein häufig bei Grafikformaten zur Datenkompression, also zur Reduzierung der Datenmenge, eingesetzter Algorithmus. Ein Großteil der Funktionweise dieses Algorithmus wurde 1978 von Abraham Lempel und Jacob Ziv entwickelt und veröffentlicht (LZ78). Einige Detailverbesserungen wurden 1984 von Terry A. Welch gemacht.

LZW ist ein verlustfreies Komprimierungsverfahren. Es wird zum Beispiel im 1987 von CompuServe-Mitarbeitern entwickelten Bildformat GIF benutzt und kann optional auch in TIFF und JPEG eingesetzt werden. Es eignet sich aber für jede Form von Daten, da das eingesetzte Wörterbuch erst zur Laufzeit generiert wird und so unanbhangig vom Format ist. LZW ist wohl der bekannteste Vertreter der LZ-Familie.

Funktionsweise

LZW komprimiert mittels Wörterbüchern, in denen die am häufigsten vorkommenden Zeichenketten, wie z.B. 'ist', 'die' und 'ein', gespeichert werden und nun nur noch unter einer Abkürzung angesprochen werden müssen. Der Knackpunkt bei diesem Algorithmus liegt darin, dass das Wörterbuch nicht zusätzlich abgelegt werden muss. Dieses wird implizit mit in die Datei geschrieben. Der Decoder, sofern richtig programmiert, ist in der Lage, es aus dem Datenstrom zu rekonstruieren. Einträge im Wörterbuch werden üblicherweise über einen 12 Bit langen Index angesprochen. Es sind also maximal 212 = 4096 Einträge möglich. Die Einträge mit dem Index 0 bis 255 werden mit den entsprechenden Bytes gefüllt, also Eintrag 0 $00, Eintrag 2 mit $02, ... , Eintrag 255 mit $FF (Hexadezimalsystem). Nachfolgende Einträge, die zur Laufzeit eingefügt werden, müssen also zwangsweise mit dem Index 256 beginnen. Neue Einträge werden generiert, indem der gefundene Eintrag plus dem nächsten Zeichen gespeichert wird. Wenn die gefundene Zeichenkette nur 1 Zeichen lang ist, wird meist nur dieses Zeichen gespeichert, da ein Verweis auf das entsprechende Element 12 Bit, das Zeichen selber nur 8 Bit belegt. Die unterscheidung, ob jetzt ein Verweis oder ein Symbol im Bitstrom kommt, kann per Flag gesetzt werden.

Beispiel zur Kompression

Ein Beispiel mit der Zeichenkette "LZWLZ78LZ77LZCLZMWLZAP"

Zeichenkette gefundener Eintrag Ausgabe neuer Eintrag
LZWLZ78LZ77LZCLZMWLZAP L L LZ <256>
ZWLZ78LZ77LZCLZMWLZAP Z Z ZW <257>
WLZ78LZ77LZCLZMWLZAP W W WL <258>
LZ78LZ77LZCLZMWLZAP LZ <256> <256> LZ7 <259>
78LZ77LZCLZMWLZAP 7 7 78 <260>
8LZ77LZCLZMWLZAP 8 8 8L <261>
LZ77LZCLZMWLZAP LZ7 <259> <259> LZ77 <262>
7LZCLZMWLZAP 7 7 7L <263>
LZCLZMWLZAP LZ <256> <256> LZC <264>
CLZMWLZAP C C CL <264>
LZMWLZAP LZ <256> <256> LZM <265>
MWLZAP M M MW <266>
WLZAP WL <258> <258> WLZ <267>
ZAP Z Z ZA <268>
AP A A AP <269>
P P P -

Es entsteht also die Zeichenkette "L Z W <256> 78 <259> 7 <256> C <256> M <258> Z A P" ("Ausgabe" von oben nach unten gelesen).

Beispiel zur Dekompression

Die Zeichen werden der Reihe nach eingelesen. Ein Zeichen ergibt mit dem vorhergehenden Zeichen, bzw. Wörterbucheintrag einen neuen Eintrag in das Wörterbuch.

aktuelles Zeichen erster Buchstabe Neuer Eintrag Ausgabe
L - - L
Z Z LZ (=256) Z
W W ZW (=257) W
<256> L WL (=258) LZ
7 7 LZ7 (=259) 7
8 8 78 (=260) 8
<259> L 8L (=261) LZ7
7 7 LZ77 (=262) 7
<256> L 7L (=263) LZ
C C LZC (=264) C
<256> L CL (=265) LZ
M M LZM (=266) M
<258> W MW (=267) WL
Z Z WLZ (=268) Z
A A ZA (=269) A
P P AP (=270) P

"Ausgabe" von oben nach unten gelesen ergibt wieder die vorher codierte Zeichenkette "LZWLZ78LZ77LZCLZMWLZAP"

Varianten

Der LZ78-Algorithmus arbeitet ähnlich, startet jedoch mit einem leeren Wörterbuch.

LZC ist nur eine leichte Abwandlung von LZW. Die Indexgröße und damit die Wörterbuchgröße ist variabel, startet bei 9 Bit und kann bis zu einer vom Nutzer festgelegten Größe wachsen. Es kann eine bis zu 7% bessere Kompression erwartet werden.

LZMW unterscheidet sich dadurch, das anstatt nur jeweils ein Zeichen an eine Zeichenkette im Wörterbuch anzuhängen, jede Zeichenkette mit dem längsten bekannten String, der in der nachfolgenden Eingabe unmittelbar im Anschluß gefunden werden kann. Dies ist bei speziellen Daten recht praktisch (z.B. eine Datei, welche aus 10'000 'a's besteht), LZW kommt allerdings mit allgemeinen Daten besser zurrecht.

Patente

Für LZW und ähnliche Algorithmen wurden verschiedene Patente in den USA und anderen Ländern ausgestellt. LZ78 wurde durch das am 10. August 1981 eingereichte und am 7. August 1984 gewährte US-Patent 4.464.650 der Sperry Corporation (später zu Unisys fusioniert) abgedeckt, in dem Lempel, Ziv, Cohn und Eastman als Erfinder eingetragen sind.

Zwei US-Patente wurden für den LZW-Algorithmus ausgestellt: Nr. 4.814.746 von Victor S. Miller and Mark N. Wegman für IBM, eingereicht am 1. Juni 1983, sowie Nr. 4.558.302 von Welch für die Sperry Corporation, später Unisys Corporation, eingereicht am 20. Juni 1983.

Das US-Patent 4.558.302 verursachte die größte Kontroverse. Eine der am weitesten verbreiteten Anwendungen für LZW war das in den 1990er Jahren für Webseiten immer populärer werdende GIF-Format für Bilder. Unisys hatte zwar bereits seit 1987 Lizenzgebühren für die LZW-Verwendung in Hardware und hardwarenaher Software verlangt, die tantiemenfreie Nutzung des LZW-Algorithmus jedoch gestattet, während GIF sich neben JPEG zu einem Standard-Format entwickelte. Im Dezember 1994 begann Unisys jedoch mit CompuServe Lizenzgebühren von Entwicklern kommerzieller Software, die das GIF-Format lesen und schreiben konnte, zu verlangen und dehnte dies im August 1999 auch auf freie Software aus. Dieses Verhalten rief in Entwickler- und Anwenderkreisen weltweit Empörung hervor.

Viele Rechtsexperten kamen zum Schluss, dass das Patent solche Geräte nicht abdeckt, die LZW-Daten zwar dekomprimieren, aber nicht komprimieren können. Aus diesem Grund kann das weit verbreitete Programm gzip Dateiarchive im Z-Format zwar lesen, aber nicht schreiben.

Das US-Patent 4.558.302 lief am 20. Juni 2003 nach 20 Jahren aus. Die entsprechenden europäischen, kanadischen und japanischen Patente folgten im Juni 2004.

Siehe auch

Abgerufen von „https://de.wikipedia.org/w/index.php?title=Lempel-Ziv-Welch-Algorithmus&oldid=8898166“