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?
>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?
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.
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.
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 !
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 ?
>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
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.