LZW Dekomprimierung

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

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.

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

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?

Zitat von quilty

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

Zitat von thr|janus

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".

Zitat von thr|janus

Zitat von Nico

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.

Zitat

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.

Zitat

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.

Zitat

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.