LZW Algorithmus?

>Was bringt das denn, wenn das Wörterbuch, das Teil der Komprimierung
>ist, länger ist als die original Kette?

Gegenfrage. Was bringt das denn, wenn du nach Kompressionsalgorithmen 
fragst, wenn du nicht einmal die Implementierung von Zeichenketten 
verstehst?

Wie im Wiki Artikel ganz oben unter "Funktionsweise" erwähnt wird, ist 
das Wörterbuch nicht en bloc Bestandteil der übertragenen/gespeicherten 
Daten, sondern findet sich nur im Speicher von Decoder und Encoder. Der 
Decoder rekonstruiert das Wörterbuch inkrementell anhand der gleichen 
Regeln, die den Encoder es aufbauen lassen.

Die Grösse des Wörterbuchs geht also direkt nur logarithmisch über die 
Breite vom Index in die komprimierten Daten ein. Da dieser aber 
üblicherweise seinerseits in einer zweiten Stufe komprimiert codiert 
wird, beispielsweise über Huffman, spielt das keine wesentliche Rolle.

>Wenn das Wörterbuch nicht bestandteil der Datei ist, verstehe ich noch
>nicht, wie man dann ohne das Wörterbuch auf die ursprüngliche
>Zeichenkette kommt. Denn ohne das Buch kennt man die Übersetzung ja
>nicht.

Die unkomprimierten Daten selber sind das Wörterbuch. LZW ist ein 
sogenannter Lookahead (Schau zurück) Algorithmus. Die Daten landen 
Zeichenweise in einen Datenbuffer, zb. 256 Zeichen passen in den 
Lookahead Buffer. Dieser Buffer ist dein Wörterbuch. Steht darin eine 
Zeichenfolge wie "LZW" und nun kommt eine Zeichenfolge rein wie "LZK" 
dann speichert LZW im Ausgabebuffer nur einen binären Index als Verweis 
in diesen Lookahead Buffer zum Offest "LZ" statt dem "LZK", und noch die 
Längeangabe 2 als Ausgabe.

Beim Dekomprimieren wird das Ganze dann invers betrieben. Die 256 
zuletzt dekomprimierten Zeichen landen ebenfalls in einen Buffer, der 
dann als Wörterbuch dient um die im komprimierten Stream gespeicherten 
Indizes + Längenangaben wieder in Zeichenfolgen umwandeln zu können.

Betrachtet man es nun genauer so ist die maximale Länge dieses Buffers 
beim Komprimieren und Dekomprimieren defakto exakt die Länge der Daten 
die du so komprimieren möchtest. Die praktisch maximal beste Länge 
dieses Buffers wäre dann Datenlänge / 2. Allerdings entsteht dann das 
Problem das je länger dieser Buffer wird mehr Bits für die Speicherung 
des Indizes im komprimierten Stream benötigt werden. Das bedeutet also 
Datenexpansion und reduziert die max. machbare Komprimierung. Deswegen 
benutzen moderne LZW Verfahren quasi eine Liveanalyse der Daten und 
können dynamisch die zu benutzende Lookahead-Buffer-Größe verändern.

Diesen Buffer stellst du dir also als ein sliding Window, gleitendes 
Fenster, über die Daten vor.

Praktischerweise beträgt die Größe dieses Buffer immer eine Potenz von 
2, da so das Ratio von Komprimierungsrate zu nötiger Bitgröße der 
Indizes und Längenangaben am besten ist.

Oft benutzt man nun noch eine Huffman-Kodierung dieser LZW-Steuerdaten 
(Index + Textlänge + Steuercodes). Beim Huffman kann man zwei 
unterschiedliche Verfahren annehmen. Eines davon arbeitet mit einem 
Wörterbuch und dieses wird meistens am Ende des komprimierten Stream 
auch gespeichert. Beim Dekomprimieren liest man zuerst diese 
Huffman-Code-Tabelle in den Speicher, da man nur mit dieser exakt 
dekomprimieren kann. Die zweite Gruppe der Huffmann-Verfahren baut immer 
dynamisch diese Tabelle auf und somit muß diese nicht gespeichert 
werden.
Je nach Datengröße und Entropie der Daten ist das Eine oder Andere 
besser im Sinne des Komprimierratios.

Gruß Hagen

> Lookahead (Schau zurück)

Interessante Übersetzung. Eigentlich heißt das "schau voraus".

Tatsache habe "schau zurück" geschrieben ;) Rufus hat natürlich Recht, 
Vorausschau-Buffer ist richtig. Ist ja auch logisch wenn man die 
Funktionsweise im LZW betrachtet.

Gruß Hagen