LZW Kompression

[Alfred]

kann mir einer erklären wie der lzw allo
funtzt ? ich raff das einfach nich..
was wird in die tabelle geschrieben und wie ????

ich hab mir schon hunderte pseudocodes angeschaut
google gequelt etc.

ich kapierst trotzdem nich..
erbarmt sich jemand und erklärt mir den für doofe ?
thx schon ma im voraus..

mfg alfred

[MrEasy]

verschoben nach algorithmen

[Jan Krüger]

Der LZW-Algorithmus ist patentiert (das Patent läuft demnächst ab), es empfiehlt sich also, das Ganze vorsichtig anzugehen. Im Zweifelsfalle gibt es den LZ77-Algorithmus, der einige Ähnlichkeiten zu LZW aufweist und patentfrei ist. Aber den erkläre ich hier jetzt mal nicht.
Ich werde versuchen, dir die Grundsätze zu erklären. Ich kann nicht versprechen, dass es wirklich ganz genau so funktioniert, aber so hab ich's in Erinnerung. ;)
Es gibt außerdem eine recht gute Erklärung im Buch "Algorithmen" im Addison-Wesley-Verlag. Zumindest denke ich, dass es das Buch war.

Und auf in die Theorie:
Komprimierung übersetzt ein Alphabet (das Eingabealphabet, I) (das ist eine Menge von unterschiedlichen Werten, z.B. 0-255) in ein anderes (das Ausgabealphabet, O), mit dem Ziel, dass der resultierende Text kürzer ist. Im Falle der LZW-Komprimierung werden teilweise auch mehrere Zeichen in einem Zeichen des Ausgabealphabets zusammengefasst.

Es gibt mehrere Abwandlungen des LZW-Algorithmus; ich gehe hier nur auf den Algorithmus mit einem Ausgabealphabet statischer Größe vor. Natürlich benutzen die meisten Implementationen die cleverere Variante mit dynamischem Ausgabealphabet, aber das kannst du dann immer noch woanders nachlesen.

Vorbereitung
Damit der LZW-Algorithmus etwas bewirken kann, muss das Ausgabealphabet größer sein als das Eingabealphabet. Beispielsweise könnte das Eingabealphabet von 0-255 (8-bit-Werte) und das Ausgabealphabet von 0-511 (9-bit-Werte) reichen. Ich bleibe im weiteren Verlauf bei diesem Beispiel.
Offensichtlich ergibt sich hier ein Problem mit der Datenbreite der Werte... zur Lösung benutzt man ein ähnliches Verfahren wie UUEncode (d.h. die 9-bit-Werte werden in 8-bit-Blöcke aufgeteilt und diese dann als handelsübliche Bytes behandelt).
Zunächst wird jeder Wert aus dem Eingabealphabet dem entsprechenden Wert des Ausgabealphabets zugeordnet (d.h. O(0) = I(0), O(1) = I(1) usw.). Die übrigen freien Plätze des Ausgabealphabets werden während der Komprimierung belegt.

Komprimierung
Zunächst wird ein Zwischenbuffer angelegt. Alle Zeichen, die während der Komprimierung aus dem Originaltext eingelesen werden, werden an diesen Buffer angehängt. Danach passiert Folgendes:
1) nächstes Zeichen des Eingabetextes an den Buffer anhängen. Sollte kein Zeichen mehr übrig gewesen sein, weiter zu Schritt 6.
2) Wenn der momentane Inhalt des Buffers schon ein Zeichen des Ausgabealphabets ist (nicht vergessen, ein Zeichen des Ausgabealphabets kann mehreren Zeichen des Eingabealphabets entsprechen), das entsprechende Zeichen des Ausgabealphabets irgendwo zwischenspeichern und zurück zu 1.
3) das in Schritt 2 eben zwischengespeicherte Ausgabezeichen an den (komprimierten) Ausgabetext anhängen.
4) den momentanen Bufferinhalt dem ersten unbelegten Zeichen des Ausgabealphabets zuordnen. Buffer bis auf das letzte Zeichen leerräumen.
5) zurück zu Schritt 1.
6) das Ausgabezeichen finden, das dem momentanen Bufferinhalt entspricht, und an den Ausgabetext anhängen.

Beispiel
Eingabealphabet (Größe: 4):
1 = A
2 = B
3 = C
4 = D

Ausgabealphabet (Größe: 8):
1 = A
2 = B
3 = C
4 = D

Eingabetext = 123123 (ABCABC)
Buffer = (leer)

1. Durchlauf
Buffer = A (entspricht Ausgabezeichen 1, weiter)
Buffer = AB (nicht im Ausgabealphabet, neues Zeichen: 5 = AB)
Ausgabetext = 1
Buffer = B

2. Durchlauf
Buffer = BC (nicht im Ausgabealphabet, neues Zeichen: 6 = BC)
Ausgabetext = 12
Buffer = C

3. Durchlauf
Buffer = CA (nicht im Ausgabealphabet, neues Zeichen: 7 = CA)
Ausgabetext = 123
Buffer = A

4. Durchlauf
Buffer = AB (entspricht Ausgabezeichen 5, weiter)
Buffer = ABC (nicht im Ausgabealphabet, neues Zeichen: 8 = ABC)
Ausgabetext = 1235
Buffer = C

5. Durchlauf
keine weiteren Eingabezeichen.
Buffer = C, entspricht Ausgabezeichen 3
Ausgabetext = 12353

Fertig
Anzahl Bits im Eingabetext: 6*3 = 18
Anzahl Bits im Ausgabetext: 5*4 = 20
In diesem Fall hat die Komprimierung leider in Wirklichkeit vergrößert statt verkleinert, aber so geht's im Leben - nichts ist perfekt.

Wie die Dekomprimierung funktioniert, darfst du selber rausfinden. ;)

[Scavi]

Das ist ja n blöder Algorithmus, wer hat sich denn sowas ausgedacht ? Da würde ich eher den Huffman Alg. verwenden, der iss logischer, einfacher zu verstehen und komprimiert immer.
...iss aber halt nüch LZW, wird eher beim WAV -> MP3 komprimieren genutzt.

[Alfred]

hertzlichen dank :)
ich glaube das muss ich mir nur noch 2-3 mal durchlesen dann hab ichs geschnaggelt :)

zum thema patentschutz :
ich brauche den lzw um pdf streams zu dekodieren.
das ganze ist für ein betriebsinternes produkt und desshalb
patentrechlich unbedenklich.

und da es leider keine apis gibt die "einfach so " für lau
aus pdf ein xml machen muss ich das eben selbermachen :)

mfg und thx Alfred

[Scavi]

Guck dir mal das Perlmodul "pdf2xml.pm" an !

[Alfred]

thx muss leider in java sein..

[Jan Krüger]

Original geschrieben von Scavi
Das ist ja n blöder Algorithmus, wer hat sich denn sowas ausgedacht ? Da würde ich eher den Huffman Alg. verwenden, der iss logischer, einfacher zu verstehen und komprimiert immer.
...iss aber halt nüch LZW, wird eher beim WAV -> MP3 komprimieren genutzt.
LZW ist eindeutig kein blöder Algorithmus, du magst ihn höchstens nicht. Ich habe hier auch nicht den vollständigen Algorithmus beschrieben, dazu hatte ich schlicht und ergreifend keine Zeit... eine realistische Implementation würde ein dynamisch wachsendes Ausgabealphabet benutzen und außerdem versuchen, eine optimale Start- und Endgröße des Alphabets festzulegen. Im Worst Case würde der Algorithmus dann 0% komprimieren. Entwickelt wurde er von Lempel, Ziv und Welch. Einsatzgebiet des Algorithmus in Reinform ist das Dateiformat GIF, das von CompuServe entwickelt wurde. Weil der LZW-Algorithmus in vielen Ländern noch immer von Unisys patentiert ist, gibt es mit diesem Dateiformat auch immer wieder Lizenzprobleme... Details hier (http://burnallgifs.org/).

Der von dir angesprochene Algorithmus wurde von Lempel, Ziv und Huffman entwickelt, ein damit vergleichbarer Algorithmus wäre noch die Abwandlung unter Verwendung von Shannon-Fano-Bäumen. Dass der LZH- bzw. Shannon-Fano-Algorithmus immer komprimiert, stimmt nicht, das ist codierungstheoretisch auch gar nicht möglich - es gibt eine maximale Informationsdichte. Um nochmal kurz auf die Funktionsweise zurückzukommen: häufig auftretende Eingabezeichen werden durch Ausgabezeichen einer geringen Bitlänge ausgedrückt. Dadurch müssen aber längere Bitfolgen automatisch durch längere Bitfolgen ausgedrückt werden, die seltensten Zeichen hätten dann in der Ausgabe längere Bitfolgen als die Eingangszeichen. Hier gilt, genauso wie beim LZW- bzw. LZ77-Algorithmus, dass im Worst Case gar nicht komprimiert wird.

In beiden Fällen bin ich davon ausgegangen, dass am Ende überprüft wird, ob die komprimierte Ausgabe größer ist als die Eingabe und eventuell der Komprimierungsschritt im Nachhinein als unsinnig erkannt werden kann.

Abschlussbemerkung: beide Algorithmen haben Einsatzgebiete, in denen sie besser abschneiden als der jeweils andere. Der LZW-Algorithmus komprimiert Wiederholungen, der LZH-Algoritmus komprimiert Daten mit stark vorherrschenden Werten. Zufallsdaten können von keinem der beiden Algorithmen komprimiert werden.
Es ist auch möglich (und ich denke, dass die meisten Programme das in der Praxis auch so machen), die beiden Algorithmen zu kombinieren. Ich habe selber mal ein Crossover zwischen Shannon-Fano und LZ77 in i386-Assembler implementiert, habe aber, nachdem das Programm prinzipiell komplett war, abgebrochen, weil mir das Debuggen der ganzen Fehler, die ich eingebaut habe, zu nervig wurde. ;)

[Scavi]

??? Das bei einigen Buchstaben des zu komprimierenden Alphabetes logischerweise die Anzahl der Bits nach der Kodierung höher ist als vorher mag sein, aber das trifft nur in sehr wenigen Fällen zu, da ja die Verteilungen der Buchstaben des Alphabetes vorher überprüft wird und jeden Buchstaben eine Wahrscheinlichkeit "zugeordnet" wird. Die oft vorkommenden Buchstaben des zu kodierenden Alphabetes "bekommen" logischerweise die höchste Wahrscheinlichkeit und werden somit nur als 1, 2 bit kodiert. Das Alphabet müsste schon sehr gross sein, damit Buchstaben so kodiert werden, damit die Anzahl der Bits nach dem kodieren für kleine und grosse Wahrscheinlichkeiten zusammen die Anzahl der Bits vor dem Kodieren oder sogar mehr ergeben. Meines Wissens komprimiert Huffman immer. Ich habe allerdings auch noch keine Komplexitätsrechnung aufgestellt !

[Jan Krüger]

Geh den Huffman-Algorithmus mal für eine JPEG- oder MP3-Datei oder eine Datei mit absolut zufälligem Inhalt durch, dann siehst du, was ich meine.
Der folgende String komprimiert übrigens mit LZH auch nicht, wenn er in der Eingabe mit 2 Bit pro Zeichen codiert ist:
"AACBDBACADBDCBDC"

[DarkTom]

Noch ein paar Worte zu Huffman:

Der kodierte Text kann in der Tat nicht länger sein als der ursprüngliche Text. Bei gleicher Häufigkeit der Buchstaben wird er aber auch nicht kürzer sein.

Allerdings hat Huffman noch ein Problem, das LZW nicht hat: Wird keine festgelegte Buchstabenverteilung angenommen (die ja nicht unbedingt optimal wäre), muss die Übersetzungstabelle (bzw der Huffman-Baum) mit gespeichert werden. Und dadurch kann der Output dann schon größer sein als der Input.

[MichiK]

*nur zum ansehen* - Wer das ganze in einem Programm verwenden möchte, der sollte sich erst mit Unisys wegen einer Lizenz in Verbindung setzen.
siehe http://www.unisys.com/about__unisys/lzw/


void
LZW::inittable()
{
int i;
for (i=0; i<4096; i++) table[i].prev = NULL;
for (i=0; i<256; i++) table[i].symbol = (char)i;
cleartable();
}

void
LZW::cleartable()
{
lastidx = 258;
codelen = 9;
codemask = (1 << codelen) - 1;
}

void
LZW::addentry_encode(entry *prev, char sym)
{
table[lastidx].prev = prev;
table[lastidx].symbol = sym;
lastidx++;
if (lastidx > codemask) codelen++;
codemask = (1 << codelen) - 1;
}

void
LZW::addentry_decode(entry *prev, char sym)
{
table[lastidx].prev = prev;
table[lastidx].symbol = sym;
lastidx++;
if (lastidx >= codemask) codelen++;
codemask = (1 << codelen) - 1;
}

char
LZW::firstsymbol(entry *e)
{
while (e->prev != NULL) e = e->prev;
return e->symbol;
}

void
LZW::writestring(std::ostream &o, entry *e)
{
if (e == NULL) return;
writestring(o, e->prev);
o.write(&e->symbol, 1);
}

void
LZW::readcode(std::istream &i, int &code)
{
while (numbits < codelen)
{
char in;
i.read(&in, 1);
bitbuf = bitbuf | (((int)in & 0xff) << numbits);
numbits += 8;
}
code = bitbuf & codemask;
bitbuf >>= codelen;
numbits -= codelen;
}

void
LZW::writecode(std::ostream &o, int code)
{
bitbuf = bitbuf | (code << numbits);
numbits += codelen;
while (numbits >= 8)
{
char out = (bitbuf & 0xff);
o.write(&out, 1);
bitbuf >>= 8;
numbits -= 8;
}
}

void
LZW::flushcode(std::ostream &o)
{
char out = (bitbuf & 0xff);
o.write(&out, 1);
o.flush();
}

void
LZW::encode(std::istream &i, std::ostream &o)
{
bitbuf = 0;
numbits = 0;
inittable();
writecode(o, 256);

char in = i.get();
while (!i.eof())
{
entry *p = NULL;
int pos = 0;
int code = 0;
while (pos < lastidx)
{
entry *e= &table[pos];
if ((!i.eof()) && (e->prev == p) && (e->symbol == in))
{
in = i.get();
p = e;
code = pos;
}
pos++;
}
writecode(o, code);
addentry_encode(p, in);
if (lastidx >= 4095)
{
writecode(o, 256);
cleartable();
}
}
writecode(o, 257);
flushcode(o);
}

void
LZW::decode(std::istream &i, std::ostream &o)
{
bitbuf = 0;
numbits = 0;
inittable();
int curcode = 0;
int oldcode = 0;

readcode(i, curcode);
while (curcode != 257)
{
if (curcode == 256)
{
cleartable();
readcode(i, curcode);
if (curcode == 257) break;
writestring(o, &table[curcode]);
oldcode = curcode;
}
else
{
if (curcode < lastidx)
{
writestring(o, &table[curcode]);
addentry_decode(&table[oldcode], firstsymbol(&table[curcode]));
oldcode = curcode;
}
else
{
addentry_decode(&table[oldcode], firstsymbol(&table[oldcode]));
writestring(o, &table[lastidx-1]);
oldcode = curcode;
}
}
readcode(i, curcode);
}
}