LZW Dekomprimierung
URL: https://www.overclockers.at/coding-stuff/lzw_dekomprimierung_205197/page_1 - zur Vollversion wechseln!
thr|janus schrieb am 25.02.2009 um 14:09
Hi,
brauche hilfe bei meinem C# commandline projekt, das huffman und lzw de- & komprimieren können soll. speziell die LZW dekomprimierung macht mir sorgen, der rest funktioniert mittlerweile schon ganz gut.
das programm muss generell nicht mit anderen file-types oder programmen kompatibel sein.
also folgendes problem:
ich habe vom bsp auf wikipedia.de folgende message komprimiert:
LZWLZ78LZ77LZCLZMWLZAP
die komprimierung funktioniert an sich einwandfrei, vorausgesetzt meine theorie zur speicherung ist richtig: ich hab ein dictionary mit der kompletten ascii tabelle also 256 + 15 einträge. jeder eintrag hat einen dezimalen schlüssel, der zum speichern der komprimierten msg dann in binär umgewandelt wird ("code"), so hat z.b. der buchstabe/eintrag 'L' den wert 76 bzw 1001100.
so wird bspw. der anfang der message "LZW" wird also gespeichert als 100110010110101010111.
die dazugehörige tabelle würde so aussehen:
1001100 76 L
1011010 90 Z
1010111 87 W
bis jetzt noch mitgekommen? 
gut, denn das problem ist jetzt folgendes.
beim dekomprimieren wird die gespeicherte, komprimierte message gelesen, beschränken wir uns mal auf "LZW" dann wäre die gespeicherte msg wieder 100110010110101010111.
aber wie soll ich das parsen genau machen? wenn ich einfach von vorne anfange den bitstrom zu lesen bis ich ein zeichen finde komme ich ja auch schon mit dem ersten bit '1' auf einen eintrag im dictionary. wenn ich lese bis ich keinen eintrag mit dem code mehr finde und dann zurück gehe hab ich nur einen falschen eintrag: 153, der mit 10011001 halt einfach eine stelle länger ist..
hat jemand vielleicht einen tip oder eine idee die mir weiterhelfen könnte!?
danke schon mal im voraus für irgendwelche hinweise!
mfg
janus
Lukas schrieb am 25.02.2009 um 18:04
kA ob ich das jetzt richtig verstanden habe aber wenn ich den bitstrom 100110010110101010111 habe und diese tabelle:
1001100 = 76 = L
1011010 = 90 = Z
1010111 = 87 = W
dann würde ich immer 8bit parsen und daraus den ascii char lesen oder versteh ich da was falsch? also aus dem bitstrom immer 8 bit in eine variable schreiben und die hat dan automatisch den wert des gewünschten ascii chars.
thr|janus schrieb am 25.02.2009 um 22:09
naja, dann gibts nach wie vor ein problem: es gibt auch einträge mit codes länger als 8bit (ergibt sich aus den 256+ einträgen..).
und selbst wenn ich 8bit lese.. die "tabelle" die ich gepostet hab hat codes mit 7bit länge 
die ganze tabelle/dictionary hat wie bereits gesagt insgesamt 256 (ascii) + 13 (kombinierte "wörter", z.b. "LZ" "ZW" etc) einträge.
quilty schrieb am 25.02.2009 um 22:33
Bei LZW kennst du ja das "Standard"-Dictionary, d.h. du weißt ja wieviele Bits du zu beginn auslesen musst. Von dort weg baust du dir dann dass restliche Dictionary zusammen und weißt somit ab wann du längere Codes auslesen musst.
---- hach falsch erinnert - ignore ----
Also wenn mich mein Gedächnis zu LZW nicht im Stich lässt erkenne ich schon mal einen Fehler: ALLE Codes in deiner Tabelle müssen die gleiche Länge haben.
----
thr|janus schrieb am 25.02.2009 um 23:00
hmm das würde sinn machen 
dann wärs auch klar wieviel bits ich lesen muss, jo! und die codes die nicht X bits lang sind halt mit 0 auffüllen. klingt nicht schlecht, mein gedanke dabei war nur dass dann bei kleinen files z.b. statt einem char (8 bit) auf einmal 9 oder 10 bits pro char gespeichert werden müssen.. auf der anderen seite erspart man sich ja trotzdem durch die lzw kompression bzw die zusammengesetzten einträge etwas.
werd ich mir nochmal durchdenken, aber ich glaub das müsste hinhaun - vielen dank!
ich werd dann posten obs funktioniert oder noch weitere fehler/fragen auftauchen.
mfg
janus
quilty schrieb am 25.02.2009 um 23:32
Neben durchdenken würde ich mir auch nochmals die Funktionsweise des Algorithmus durchlesen.
Z.B. Auffüllen ist nie notwendig, da zu jedem beliebigen Zeitpunkt während der Laufzeit des Ver- bzw. Entschlüsselungsalgorithmus alle im Dictionary vorhandenen Codes zu diesem Zeitpunkt die gleiche Länge haben.
watchout schrieb am 25.02.2009 um 23:43
Ich hoffe ja das liegt an der Erklärung, aber...
Was bringt dir ein Dictionary Algorithmus wenn du erst wieder die gesamte Menge möglicher Werte ins Dictionary aufnimmst? (gesamte ASCII Table)
Sollte nicht außerdem die Wortlänge größer als 7/8bit sein?
quilty schrieb am 26.02.2009 um 00:27
Das Startwörterbuch MUSS alle möglichen elementare Symbole enthalten welche in der zu komprimierenden Nachricht enthalten sein könnten.
Im Laufe des Algorithmus (sowohl beim En- als auch Decoden) wird das sogar noch größer, weil du ja Wörter aufnimmst die aus Konkatenationen der elementaren Symbole bestehen.
Bsp: Byte-Stream zu komprimieren -> Wörterbuch hat 256 Einträge zu Beginn, wird jedoch gleich zu beginn größer werden und somit werden 9-bit Codes geschrieben -> mit diesen 9-bits können aber ziemlich lange Byte-Folgen abgebildet werden -> selbst wenn die Folge nur 2 Byte lang ist spart man sich 7bit.
watchout schrieb am 26.02.2009 um 00:53
Das Startwörterbuch MUSS alle möglichen elementare Symbole enthalten welche in der zu komprimierenden Nachricht enthalten sein könnten.
Im Laufe des Algorithmus (sowohl beim En- als auch Decoden) wird das sogar noch größer, weil du ja Wörter aufnimmst die aus Konkatenationen der elementaren Symbole bestehen.
Bsp: Byte-Stream zu komprimieren -> Wörterbuch hat 256 Einträge zu Beginn, wird jedoch gleich zu beginn größer werden und somit werden 9-bit Codes geschrieben -> mit diesen 9-bits können aber ziemlich lange Byte-Folgen abgebildet werden -> selbst wenn die Folge nur 2 Byte lang ist spart man sich 7bit.
Ja hast recht, hab den LZW nochmal nachgelesen, hab auch glaub ich etwas falsch verstanden was du da machst
thr|janus schrieb am 26.02.2009 um 07:54
Neben durchdenken würde ich mir auch nochmals die Funktionsweise des Algorithmus durchlesen.
Z.B. Auffüllen ist nie notwendig, da zu jedem beliebigen Zeitpunkt während der Laufzeit des Ver- bzw. Entschlüsselungsalgorithmus alle im Dictionary vorhandenen Codes zu diesem Zeitpunkt die gleiche Länge haben.
naja, die codes der vorhandenen einträge sind definitiv nicht gleich. der erste eintrag hat z.b. code "1" während der 255. eintrag "11111111" hat.
hab den algorithmus schon ein paar mal per hand am papier durchgemacht und sowohl in der englischen als auch deutschen wiki gelesen, aber das mit der gleichen codelänge ist mir wohl entgangen..
sorry meine erklärung war glaub ich wirklich etwas unverständlich und dürftig.. umso mehr danke ich nochmal für die hilfe, ich kanns erst am samstag probieren aber ich bin mir sicher dass es so jetzt klappen sollte.
mfg
janus
Luzandro schrieb am 26.02.2009 um 08:18
naja, die codes der vorhandenen einträge sind definitiv nicht gleich. der erste eintrag hat z.b. code "1" während der 255. eintrag "11111111" hat.
Das schon, aber was er wohl meinte ist, dass du mit der minimalen Blocklänge anfangen kannst, damit sich eben dein Startmapping noch ausgeht und wenn du mehr Werte benötigst, vergrößert sich eben die Länge ab diesem Eintrag. Nachdem das Mapping beim Komprimieren und Dekomprimieren analog "on the fly" generiert wird, weißt du ja immer wie lang dein Block gerade sein muss und brauchst nicht von vornherein eine maximale Größe festlegen und schon die Startwerte unnötigerweise "auffüllen".
thr|janus schrieb am 28.02.2009 um 14:35
Das schon, aber was er wohl meinte ist, dass du mit der minimalen Blocklänge anfangen kannst, damit sich eben dein Startmapping noch ausgeht und wenn du mehr Werte benötigst, vergrößert sich eben die Länge ab diesem Eintrag. Nachdem das Mapping beim Komprimieren und Dekomprimieren analog "on the fly" generiert wird, weißt du ja immer wie lang dein Block gerade sein muss und brauchst nicht von vornherein eine maximale Größe festlegen und schon die Startwerte unnötigerweise "auffüllen".
mit startmapping sind wohl die ascii-tabelle bzw die ersten 256 einträge gemeint. du meinst also ich soll einfach als codelänge (blocklänge?) des startmappings 8bit verwenden (anfangs sind ja nicht mehr bit nötig). und ab dem punkt, wo zusätzliche einträge dazukommen, einen längeren code - das wäre eine lösung, ja!
dann fällt mir aber noch eine frage dazu ein: ich müsste die einträge des startmappings dann ja trotzdem auf 8bit "auffüllen" oder?
die aussage deines letzten satzes versteh ich so leider nicht. ich weiß aber wie die generierung des mappings bei de- & komprimierung on the fly erstellt wird. könntest du bitte den rest nochmal mit anderen worten erklären?
vielen dank an alle die mir bis jetzt geholfen haben!
mfg janus
P.S.:
hab mir LZW auf wikipedia nochmal durchgelesen und bin dabei auf folgendes gestoßen:
Einträge im Wörterbuch werden üblicherweise über einen 12 Bit langen Index angesprochen. [...] Wenn die gefundene Zeichenkette nur 1 Zeichen lang ist, wird meistens nur dieses Zeichen gespeichert, da ein Verweis auf das entsprechende Element 12 Bit, das Zeichen selber aber nur 8 Bit belegt. Die Unterscheidung, ob jetzt ein Verweis oder ein Symbol im Bitstrom kommt, kann per Flag gesetzt werden.
macht sinn! so werd ichs wohl machen. muss also bei der anstehenden anpassung auch noch meine implementation des LZW kompressors ändern
quilty schrieb am 28.02.2009 um 23:49
ist eigentlich nichts neues - für rekordbrecher ein thema, für gamer nicht.
Hast du Byte als Eingangsdaten dann wirst du 256 Einträge im Startwörterbuch haben, bei Int16 sind es 65536, bei Int32 halt 4294967296, bei einem eigenen Datentyp der nur die 26 Großbuchstaben des Alphabets als Wert annehmen kann hast du 26 Einträge im Startwörterbuch ...
Und die Codelänge beim Startwörterbuch ist halt entsprechend lang. Fix 8bit wäre der größte Schwachsinn.
und ab dem punkt, wo zusätzliche einträge dazukommen, einen längeren code - das wäre eine lösung, ja!
Das wäre DIE Lösung wie es im Algorithmus vorgesehen ist.
dann fällt mir aber noch eine frage dazu ein: ich müsste die einträge des startmappings dann ja trotzdem auf 8bit "auffüllen" oder?
die aussage deines letzten satzes versteh ich so leider nicht. ich weiß aber wie die generierung des mappings bei de- & komprimierung on the fly erstellt wird. könntest du bitte den rest nochmal mit anderen worten erklären?
Das Wörterbuch wird wohl eine IList<T[]> sein, dann schreib dir doch ein Methode die dir mit aus IList.IndexOf(T[] entry) einen Code mit der Länge log2(IList.Count) erzeugt.
vielen dank an alle die mir bis jetzt geholfen haben!
mfg janus
P.S.:
hab mir LZW auf wikipedia nochmal durchgelesen und bin dabei auf folgendes gestoßen:
macht sinn! so werd ichs wohl machen. muss also bei der anstehenden anpassung auch noch meine implementation des LZW kompressors ändern
Persönlich würde ich zuerst die Standardvariante lauffähig machen und dann mit möglichen Optimierungen beginnen.
thr|janus schrieb am 01.03.2009 um 10:37
gut, danke nochmal. meine eingangsdaten sind an sich bytes, aber da die codes ja 12bit lang sind, muss man halt dementsprechend anfangs 2 byte lesen und danach immer zusammenstückeln.
bin jetzt dabei, die version mit einer einheitlichen 12bit codelänge zum laufen zu bringen.
greetz
overclockers.at v4.thecommunity
© all rights reserved by overclockers.at 2000-2025