Der Lempel-Ziv-Welch-Algorithmus (kurz LZW-Algorithmus oder LZW genannt) ist ein häufig bei Grafikformaten zur Datenkompression, also zur Reduzierung der Datenmenge, eingesetzter Algorithmus. Ein Großteil der Funktionsweise dieses Algorithmus wurde 1978 von Abraham Lempel und Jacob Ziv entwickelt und veröffentlicht (LZ78). Einige Detailverbesserungen wurden 1983 von Terry A. Welch gemacht.[1]
LZW ist ein verlustfreies Komprimierungsverfahren. Es wird zum Beispiel im 1987 von CompuServe-Mitarbeitern entwickelten Bildformat GIF und optional in TIFF eingesetzt. Es eignet sich aber für jede Form von Daten, da das eingesetzte Wörterbuch erst zur Laufzeit generiert wird und so unabhängig vom Format ist. LZW ist wohl der bekannteste Vertreter der LZ-Familie.
Funktionsweise
BearbeitenLZW komprimiert mittels dynamischem Wörterbuch, in dem sich die am häufigsten vorkommenden Zeichenketten, wie z. B. „ist“, „die“ und „ein“ ansammeln und dann nur noch unter einer Abkürzung angesprochen werden müssen. Der Vorteil bei diesem Algorithmus liegt darin, dass kein zusätzliches Wörterbuch abgelegt werden muss und dass das Wörterbuch sich dynamisch an den jeweiligen Inhalt anpasst. Der Decoder 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 mit 00hex, Eintrag 2 mit 02hex, … , Eintrag 255 mit FFhex (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 ein Zeichen lang ist, wird meistens nur dieses Zeichen gespeichert, da ein Verweis auf das entsprechende Element 12 Bit, das Zeichen selbst aber nur 8 Bit belegt. Die Unterscheidung, ob jetzt ein Verweis oder ein Symbol im Bitstrom kommt, kann per Flag gesetzt werden.
Kompression
BearbeitenAlgorithmus zur Kompression
BearbeitenDer Algorithmus wird zunächst einen 9-Bit-Code zurückgeben, später kann dieser Code bis zu 12 Bit breit werden, sofern das Alphabet nicht vorher durch Senden eines Clear-Codes gelöscht wird.
Die untersten 256 Werte des Codieralphabets seien vordefiniert und entsprechen bei der Rückgabe sich selber. Der Algorithmus sucht nun das längste vorhandene Muster aus den Codes im Codieralphabet an der Eingabe und gibt den entsprechenden Wert zurück. Das wäre zu Beginn nur ein Byte, das durch einen 9-Bit-Code mit 0 als neuntes Bit ausgegeben wird. Darauf kettet er das nächste Zeichen der Eingabe an dieses Muster an und fügt das Resultat als nächsthöheren Eintrag ins Alphabet ein. Und so geht das die ganze Zeit weiter, bis das Alphabet vollläuft. Das Alphabet wird im Kompressor intern mitgeführt, aber nicht explizit gespeichert. Der Dekompressor baut es seinerseits auch aus der Eingabe auf. Er kann es rekonstruieren. Es gibt auch noch den K[Omega]K-Fall, bei dem das Muster aus dem Alphabet dem Dekompressor noch nicht bekannt ist. Aber er kann den Wert rekonstruieren.
Zum Abspeichern einer Tabelle mit 4096 Mustern, deren Länge jeweils bis zu 4096 Zeichen beträgt, würde man im Allgemeinen 16 MiB benötigen. Jedoch beginnt jedes Muster der Länge n in der Tabelle mit einem Teilmuster der Länge n-1, welches sich ebenfalls in der Tabelle befindet. Damit kann man die gesamte Tabelle in zwei Feldern Prefix und Suffix ablegen. Dabei enthält das letzte Zeichen des Musters k und den Index des Startmusters (also einen Verweis auf einen weiteren Eintrag in der Tabelle). Falls das Muster die Länge eins hat, wird auf eine Konstante <leeres Muster> gesetzt. Ein Eintrag in der Tabelle sei im Algorithmus dargestellt als Paar Muster = (Prefix, Suffix). Der Algorithmus arbeitet dann wie folgt.
initialisiere Mustertabelle mit (<leeres Muster> zeichen) für alle Zeichen
muster := <leeres Muster>
solange noch Zeichen verfügbar
zeichen := lies nächstes Zeichen
wenn (muster zeichen) in Mustertabelle dann
muster := (muster zeichen)
sonst
füge (muster zeichen) zur Mustertabelle hinzu
Ausgabe muster
muster := zeichen
wenn muster nicht <leeres Muster> dann
Ausgabe muster
Dabei enthält die Variable muster den Index des entsprechenden Musters in der Tabelle und Ausgabe muster bedeutet, dass der Index des aktuellen Musters in die Ausgabedatei geschrieben wird. Bei der Anweisung muster := zeichen wird muster auf den Index des Eintrags (<leeres Muster> zeichen) gesetzt. Da die Mustertabelle aber mit diesen Mustern initialisiert wurde, entspricht dieser Index genau dem Zeichen.
Beispiel zur Kompression
BearbeitenEin Beispiel mit der Zeichenkette „LZWLZ78LZ77LZCLZMWLZAP“
| Zeichenkette | gefundener Eintrag | Ausgabe | neuer Eintrag |
|---|---|---|---|
| LZWLZ78LZ77LZCLZMWLZAP | L | L | LZ (wird zu <256>) |
| ZWLZ78LZ77LZCLZMWLZAP | Z | Z | ZW (wird zu <257>) |
| WLZ78LZ77LZCLZMWLZAP | W | W | WL (wird zu <258>) |
| LZ78LZ77LZCLZMWLZAP | LZ (= <256>) | <256> | LZ7 (wird zu <259>) |
| 78LZ77LZCLZMWLZAP | 7 | 7 | 78 (wird zu <260>) |
| 8LZ77LZCLZMWLZAP | 8 | 8 | 8L (wird zu <261>) |
| LZ77LZCLZMWLZAP | LZ7 (= <259>) | <259> | LZ77 (wird zu <262>) |
| 7LZCLZMWLZAP | 7 | 7 | 7L (wird zu <263>) |
| LZCLZMWLZAP | LZ (= <256>) | <256> | LZC (wird zu <264>) |
| CLZMWLZAP | C | C | CL (wird zu <265>) |
| LZMWLZAP | LZ (= <256>) | <256> | LZM (wird zu <266>) |
| MWLZAP | M | M | MW (wird zu <267>) |
| WLZAP | WL (= <258>) | <258> | WLZ (wird zu <268>) |
| ZAP | Z | Z | ZA (wird zu <269>) |
| AP | A | A | AP (wird zu <270>) |
| P | P | P | - |
Es entsteht also die Zeichenkette „L Z W <256> 7 8 <259> 7 <256> C <256> M <258> Z A P“ („Ausgabe“ von oben nach unten gelesen), die mit 16 12-Bit-Zeichen (entspricht 24 8-Bit-Zeichen) anstatt ursprünglich 22 8-Bit-Zeichen dieselbe Information enthalten.
Dekompression
BearbeitenAlgorithmus der Dekompression
BearbeitenZur Dekompression kann aus den Codewörtern der Reihe nach genau die gleiche Mustertabelle erzeugt werden, da bei der Kompression immer nur das alte Muster und nicht das neue Muster mit dem nächsten Zeichen ausgegeben wurde. Bei der Komprimierung beginnt jedes Muster mit dem letzten Zeichen des vorherigen zur Tabelle hinzugefügten Musters. Umgekehrt ist bei der Dekomprimierung das letzte Zeichen des Musters, welches zur Tabelle hinzugefügt werden muss, gleich dem ersten Zeichen des aktuellen Musters, welches ausgegeben werden soll.
Problematisch wird es, wenn das auszugebende Muster noch nicht in der Tabelle eingetragen ist. Dann kann man auch nicht in der Tabelle nach dem ersten Zeichen dieses Musters suchen. Das passiert aber nur, falls ein Muster mehrmals direkt hintereinander auftritt. Dann gilt: Das neue Muster ist das vorherige Muster erstes Zeichen des vorherigen Musters.
INITIALISIERE Mustertabelle MIT (<leeres Muster>,Zeichen) FÜR ALLE Zeichen
last := lies_ersten_Code()
Ausgabe(Muster VON last)
SOLANGE NOCH Codes_verfügbar() WIEDERHOLE:
next := lies_nächsten_Code()
WENN next IN Mustertabelle DANN:
FÜGE ( (Muster VON last), erstes_Zeichen_von(Muster VON next)) ZUR Mustertabelle HINZU
SONST:
FÜGE ( (Muster VON last), erstes_Zeichen_von(Muster VON last)) ZUR Mustertabelle HINZU
Ausgabe(Muster VON next)
last := next
Beispiel zur Dekompression
BearbeitenDie 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“.
Pseudocode
BearbeitenDas folgende Beispiel in Pseudocode zeigt Funktionen, die den Lempel-Ziv-Welch-Algorithmus für die Kompression und Dekompression verwenden.
/**
* symbolDictionary // Diese Map ordnet jedem Symbol den entsprechenden Zahlenwert von 0 bis 255 zu
* lzwCode // Vektor für den codierten Text
*/
// Diese Funktion erzeugt den codierten Text mit dem Lempel-Ziv-Welch-Algorithmus
function encodeWithLZW(inputText)
{
for i := 0 to 255 do
{
symbolDictionary[symbolText] := i
}
code := 256
for i := 0 to inputText.length() - 1 do
{
c := "" // Variable für die aktuelle Zeichenkette
if (i ist nicht das Ende des eingegebenen Texts)
{
c := concat(c, inputText[i 1])
}
if (das Wort concat(p, c) ist im Dictionary enthalten)
{
p := concat(p, c)
}
else
{
lzwCode := concat(lzwCode, symbolDictionary[p]) // Codewort dem codierten Text hinzufügen
symbolDictionary[concat(p, c)] := code // Wort concat(p, c) dem Dictionary hinzufügen
code := code 1
p := c
}
}
lzwCode := concat(lzwCode, symbolDictionary[p]) // Codewort dem codierten Text hinzufügen
return lzwCode
}
/**
* lzwCode // Vektor für den codierten Text
* symbolDictionary // Diese Map ordnet jedem Symbol den entsprechenden Zahlenwert von 0 bis 255 zu
*/
// Diese Funktion decodiert den codierten Text mit dem Lempel-Ziv-Welch-Algorithmus
function decodeWithLZW(lzwCode)
{
for i := 0 to 255 do
{
symbolDictionary[i] := symbolText
}
previousCodeWord := lzwCode[0]
symbolText := symbolDictionary[previousCodeWord] // Variable für die aktuellen decodierte Zeichenkette
decodedText := symbolText
count := 256 // Zähler für die hinzugefügten Schlüssel des Dictionary
for i := 0 to lzwCode.length() - 1 do
{
codeWord := lzwCode[i 1]; // Variable für das aktuelle Codewort
if (das aktuelle Codewort ist nicht im Dictionary enthalten)
{
symbolText := symbolDictionary[previousCodeWord]
symbolText := concat(symbolText, symbolText[0]) // Symbol der Zeichenkette hinzufügen
}
else
{
symbolText := symbolDictionary[codeWord]
}
decodedText := concat(decodedText, symbolText) // Aktuelle decodierte Zeichenkette dem decodierten Text hinzufügen
symbolDictionary[count] := concat(symbolDictionary[previousCodeWord], symbolText[0]) // Zahlenwert count dem Dictionary hinzufügen
count := count 1
previousCodeWord := codeWord // Variable für das vorige Codewort setzen
}
return decodedText
}
Varianten
BearbeitenDer 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 (von Victor S. Miller, Mark N. Wegman 1985) unterscheidet sich dadurch, dass 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 Anschluss gefunden werden kann, angehängt werden kann. Dieses ist bei speziellen Daten recht praktisch (z. B. eine Datei, welche aus 10.000 „a“s besteht), LZW kommt allerdings mit allgemeinen Daten besser zurecht.
Patente
BearbeitenFü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.[2]
Zwei US-Patente wurden für den LZW-Algorithmus ausgestellt: Nr. 4.814.746 von Victor S. Miller und 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.[3][1]
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 Lizenz-Gebü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 JFIF 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 dieses 1999 auch auf freie Software aus. Diese Verwertung als Softwarepatent rief in Entwickler- und Anwenderkreisen weltweit Empörung hervor und motivierte die rasche Entwicklung des ausschließlich auf frei verfügbarem Code basierenden und leistungsfähigeren Grafikdateiformats PNG.
Viele Rechtsexperten kamen zum Schluss, dass das Patent solche Geräte nicht abdecke, 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.
Weblinks
Bearbeiten- Lempel-Ziv-Welch-Kompression ( vom 31. März 2003 im Internet Archive)
- The GIF Controversy: A Software Developer's Perspective (englisch)
Einzelnachweise
Bearbeiten- ↑ a b Patent US4558302: High speed data compression and decompression apparatus and method. Angemeldet am 20. Juni 1983, veröffentlicht am 10. Dezember 1985, Anmelder: Sperry Corporation, Erfinder: Terry Welch.
- ↑ Patent US4464650: Apparatus and method for compressing data signals and restoring the compressed data signals. Angemeldet am 10. August 1981, veröffentlicht am 7. August 1984, Anmelder: Sperry Corporation, Erfinder: Lempel, Ziv, Cohn und Eastman.
- ↑ Patent US4814746: Data compression method. Angemeldet am 11. August 1986, veröffentlicht am 21. März 1989, Anmelder: IBM, Erfinder: Victor S. Miller, Mark N. Wegman.