Frage zur Komprimierung
-
Hallo!
Wie kann ich LZW Daten möglichst platzsparend in Dateien schreiben (also für jedes Codewort nur die Anzahl an Bits, die wirklich benötigt werden)? Also z.B. für 511 9 Bit und nicht 16.
-
Nochmal mit Huffman rübergehen. Dann hast du aber die Baumdaten noch mitzuspeichern. Lohnt nur bei grösseren Datenmengen!
-
Ich würde sagen, du sammelst erstmal fleißig Bits zusammen, bis ein Byte voll ist, und schreibst das dann aus. Aufpassen mußt du am Ende, dass das letzte, evtl. halbe, Byte nicht verloren geht.
-
@bashar: Und wie willst du das wieder rekonstruieren. Ich sehe da keine Möglichkeit!
-
Ich weiß nicht, wer von uns die Frage falsch verstanden hat. Vielleicht sollte sich Steven nochmal melden.
-
Beispiel:
Er speichert seine 511 als erste Information:1 1 1 1 1 1 1 1 1 d d d d d d dEr will es jetzt platzsparend machen und nutzt die restlichen Bits
für das nächst Bit oder zumindestenst Teilen davon.
Woher soll der Entpacker jetzt wissen das er nur die ersten 9 Bit nehmen soll?Na gut man kann nach der Kodierung schauen wie hoch der Wert des höchsten Codes ist. Und nur die Anzahl Bits speichern, die dieser benötigt. Das heisst aber das ich selbst kleinere Codes mit dieser Anzahl speichern muss. Am Ende
kommt was grösseres raus als man reingebracht hat!
-
der Entpacker weiß, daß das Alphabet am Anfang 9 Bit breit ist, daher nimmt er auch nur 9 Bit. Sobald das Alphabet voll ist merkt er das und erweitert auf 10Bit. Das funktioniert. Und zwar genauso wie's Bashar beschrieben hat. gif wird zum Beispiel so gespeichtert. Der Vorteil davon ist, daß man das Alphabet on the fly rekonstruieren kann, es also nicht mitspeichern muß.
-
*an den kopf klatsch*
Ja is ja logisch. Aber das ist doch Teil des LZW-Algos. Was hat bashar vor?
-
Bashar erklärt nur, wie man das praktisch umsetzt, man kann ja keine Bits rauschreiben, deswegen muß man halt Puffern bis man ein ganzes Byte zusammen hat. Das wird dann rausgeschrieben. Und da das letzte Byte halt unter umständen nicht ganz voll wird muß man darauf achten, es trotzdem mit rauszuschreiben.
MfG Jester
-
Original erstellt von Bashar:
Ich würde sagen, du sammelst erstmal fleißig Bits zusammen, bis ein Byte voll ist, und schreibst das dann aus. Aufpassen mußt du am Ende, dass das letzte, evtl. halbe, Byte nicht verloren geht.Ja, so hab ich mir das auch gedacht, aber wie kann man das Bits-Sammeln realisieren. Hat jemand da einen (schnellen!) Algo für mich? Das mit dem letzten Byte ist kein Problem, da ich schon eine EOF-Markierung vorgesehen habe. Nach dieser kann ich einfach noch irgendwelche Müll-Bits reinschreiben, bis das Byte voll ist.
-
Am einfachste ist es denke ich so:
Du nimmst eine
deque<int> buffer; mit push_back hängste hinten 1er / 0er an. Wenn size() Dir nen Wert >=8 liefert, dann machste ein unsigned char byte = 0; for(int i=0; i<8; ++i) { byte <<= 1; byte |= (buffer.pop_front() == 0) ? 0 : 1; }einfach null in das byte, dann holste immer das nächste bit und machst es mit oder rein. Beim nächsten Bit wird alles vorher eins nach links geschoben. Fertig!
MfG Jester
[ Dieser Beitrag wurde am 25.05.2003 um 10:40 Uhr von Jester editiert. ]
-
warum nicht einfach ein bitset nehmen und sobald ein gewisser wert überschritten ist in die datei schreiben und das was noch übrig bleigt an den anfang des bitsets kopieren ...
-
gegenfrage: warum nicht die deque nehmen, die von Haus aus das anfügen hinten und abnehmen vorne unterstützt?
-
hmm vielleicht weil man bei einer huffmenkompremierung bitweise schreibt und es etwas natürlicher ist einfach in ein bitset zu schreiben ...
ich kopierl lieber mal den teil eines bitsets anstatt jedesmal mit bitshiftopertionen und so händisch auf das ende einer deque zu schreiben...