mikrocontroller.net

Forum: Offtopic LZW Algorithmus?


Autor: jo (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo ich habe eine Frage zum LZW Algorithmus.

http://de.wikipedia.org/wiki/Lempel-Ziv-Welch-Algorithmus.

Die Original Zeichenkette ist

LZWLZ78LZ77LZCLZMWLZAP.

Es wird ein Wörterbuch erstellt, in dem vorkommt:

LZ <256>
ZW <257>
WL <258>
LZ7 <259>
....


Das Wörterbuch ist, im Verlgleich zur Original Zeichenkette sehr lang. 
Was bringt das denn, wenn das Wörterbuch, das Teil der Komprimierung 
ist, länger ist als die original Kette?

Autor: Max Mustermann (max93)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>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?

Autor: Sven P. (haku) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
jo wrote:
> Das Wörterbuch ist, im Verlgleich zur Original Zeichenkette sehr lang.
> Was bringt das denn, wenn das Wörterbuch, das Teil der Komprimierung
> ist, länger ist als die original Kette?

Vorsicht mit den Zeichenketten. Ansonsten hast du schon Recht, 
Knackpunkt solcher Verfahren ist es, einen gescheiten Kompromiss zu 
finden aus
- Umfang des Wörterbuches und
- Größe des Blockes, für den das Wörterbuch gilt.

Autor: A. K. (prx)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: jo (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Danke für Eure Antworten.
Was meint ihr damit, dass ich Zeichenketten nicht verstanden habe? 
Könntet ihr mir dann das erklären? Danke schön ;)
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.

Danke für Eure Antworten !

Autor: SlashN /n (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wie man ohne Woerterbuch auf die Zeichenkette kommt ? Durch den 
Algorithmus. Das Woerterbuch ist quasi ein temporaeres Nebenprodukt. 
Alternativ koennte man ja zuerst die Datei analysieren, das Woerterbuch 
entwickeln und dann die komprimierte Datei mit dem Woerterbuch als 
Vorspann senden. Die Frage ist dann um wieviel wuerde sich die moegliche 
Kompression erhoehen ?

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>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

Autor: jo (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
okay danke für eure antworten, vielen dank ;)

Autor: Rufus Τ. Firefly (rufus) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Lookahead (Schau zurück)

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

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail, Yahoo oder Facebook? Keine Anmeldung erforderlich!
Mit Google-Account einloggen | Mit Facebook-Account einloggen
Noch kein Account? Hier anmelden.