Huffman Tree

Psycho

verstehe nicht so ganz wie du anhand der codewortlänge auf das
entsprechende wort zurückschließen willst???

(oder doch mit gedacht?)

rapso

oha.. falls du dich gut auskennst und nicht davon noch nichts gehört hast.. vielleicht hab ich dann ja was erfunden *träum*

HuffmanRapso ... *G* das wäre ja ma wat

rapso->greets();

Hallo!

Ich habe auch ein Huffman Programm geschrieben bin aber nicht so ganz glücklich mit der Kompressionsrate..

Kann mir jemand sagen welche Kopressionsverfahren in Kombination mit Huffman besonders günstig sind??

mfg

otze

burrow-wheeler-transformation ist als präprozessor genial.

Hast du vielleicht ne gute seite wo das erklärt wird???

die allwissende müllhalde gibt da nicht so viel her..

Prof84

rapso schrieb:

ich kann schon den baum rekonstruieren indem ich nur die codelänge angebe
*sichdasselbstausdachte*

addaptives hab ich mir auch angesehen, aber irgendwie hab ich da ein mulmiges gefühl bezüglich compressionsrate.

mich wundert auch, dass der addaptive huffman tree darin ein vorteil haben soll, denn gegen ende ist es immer schwieriger ihn auf die richtige codelänge zu trimmen, weil er soviele "altlasten" hat

hab noch ne frage, huffman kann maximal auf 1bit/zeichen packen, gibt es da ne lösung für? sonst würde die kompressionsrate nur 1:8 maximal sein (bei byte)
ich hab versucht 16bit und 24bit zu benutzen, das ergibt manchmal ein besseres ergäbniss (besonders bei wav dateien mit vorher einem prediction transform durchlauf).

Nö!

http://www.iti.fh-flensburg.de/lang/algorithmen/code/huffman/huffman.htm

otze

@TheHuffmanFreak

da:

http://www-user.tu-chemnitz.de/~mfie/compproj/

ist zwar schon älter, aber meiner meinung nach durchgehend gut erklärt. werden einige kompressionsmethoden besprochen,bilder filme texte usw

b7f7

rapso schrieb:

hab noch ne frage, huffman kann maximal auf 1bit/zeichen packen, gibt es da ne lösung für? sonst würde die kompressionsrate nur 1:8 maximal sein (bei byte)
ich hab versucht 16bit und 24bit zu benutzen, das ergibt manchmal ein besseres ergäbniss (besonders bei wav dateien mit vorher einem prediction transform durchlauf).
würde mich über weitere posts freuen
rapso->greets();

wenn du bilder packst dan zip danach oder nutz RLE

otze

RLE bei huffman? bist du noch bei sinnen? huffman ist bekannt dafür,dass das was übrigbleibt kaum bis keinerlei redundanzen enthält, deshalb wird huffman als postprozessor eingesetzt

rapso

das jemand die langeweile hat so nen fast 2jahre alten thread auszugrabben

btw. ich hab mit ein paar tricks es geschaft besser als 1:8 zu packen, das problem hab ich also nicht mehr. was mich jetzt stört ist die langsammkeit von 35MB/s beim packen und entpacken, (wobei mich nur das entpacken kümmert). RAW von der platte zu lesen wäre da doch fixer.:(
aber das bekomm ich sicherlich auch noch besser hin.

rapso->greets();

b7f7

otze schrieb:

RLE bei huffman? bist du noch bei sinnen? huffman ist bekannt dafür,dass das was übrigbleibt kaum bis keinerlei redundanzen enthält, deshalb wird huffman als postprozessor eingesetzt

wenn Huffman zb 2 Farben hat braucht er 1 bit [0,1]
nun kommen die aber hintereinander (Huffman beachtet Häufigkeit nicht Reihenfolge) in 8 bit hat man 8 Pixel also 1:8 byte.
hat man grosse Bereiche zu überbrücken... dan geht RLE recht fein.

Da hab ich ja ma wieder ne schöne diskussion angezettelt

Habt ihr denn noch ein paar tipps für mich wie ich meinen huffman noch effektiver machen kann??

otze

RlE ist zwar bei skizzen gut,aber bei komplexeren 2 farbenbildern(ergo komplexeren skizzen, die sehr fein gerastert sind), neigt RLE dazu, das bild ungemein zu vergrößern,da eine wiederholungsangabe mindestens 3Byte verschlingt. Huffmann bleibt hingegen aber bei konstant 1/8 der originalgröße.

aber worum es hier ging, war das packergebnis des huffmannschen algorithmus zu verbessern, und dafür ist ein RLE absolut ungeeignet, da huffmann keine redundazen übriglässt.
ich wag sogar zu behaupten, dass man aus einem gepackten bild mit keiner verlustfreien packmethode noch eine anschauliche menge Bytes gewinnen kann. Die heutigen algorithmen sind teilweise sogut, dass sie aus den Daten fast perfekte RADs komprimieren, und die sind nicht mehr weiter zu packen(gibt dafür sogar mathematische beweise).

//edit tipps um huffmann effektiver zu machen: arithemtische kodierung/LZ77 davorschalten

rapso

otze schrieb:

RlE ist zwar bei skizzen gut,aber bei komplexeren 2 farbenbildern(ergo komplexeren skizzen, die sehr fein gerastert sind), neigt RLE dazu, das bild ungemein zu vergrößern,da eine wiederholungsangabe mindestens 3Byte verschlingt. Huffmann bleibt hingegen aber bei konstant 1/8 der originalgröße.

es gibt viele möglichkeiten RLE zu implementieren, 3byte sind sehr aus der luft gegriffen, trifft bestimmt nichtmal für 10% der verschiedenen implementierungen zu... wenn ich mal 10% aus der luft greifen darf.

otze schrieb:

aber worum es hier ging, war das packergebnis des huffmannschen algorithmus zu verbessern, und dafür ist ein RLE absolut ungeeignet, da huffmann keine redundazen übriglässt.

in dem beispiel von ihm lässt huffman soviel redundanz übrig dass man es am besten mit RLE packen dürfte. zwar ein seltener fall, aber er trifft voll zu.

otze schrieb:

ich wag sogar zu behaupten, dass man aus einem gepackten bild mit keiner verlustfreien packmethode noch eine anschauliche menge Bytes gewinnen kann. Die heutigen algorithmen sind teilweise sogut, dass sie aus den Daten fast perfekte RADs komprimieren, und die sind nicht mehr weiter zu packen(gibt dafür sogar mathematische beweise).

und immerwieder kommt ein neuer algorithmus und packt es doch kleiner. das problem ist, dass man nicht DIE formel kennt um die größt mögliche kompression zuerrechnen.

otze schrieb:

//edit tipps um huffmann effektiver zu machen: arithemtische kodierung/LZ77 davorschalten

emm... in kombination mit huffman? ich glaube da ist gerade AC ein konkurierendes system zu huffman was sich nur schlecht kombinieren lässt mit huffman.

rapso->greets();

Ich habe gerade einen dicken Fehler in meinem Programm gefunden..
Wenn ein Codewort länger als 8 Bytes ist stürzt das Programm ab..

Ist das überhaupt möglich das ein Codewort aus mehr als 8 Bytes besteht oder bau ich meinen Baum falsch? Hab grad ne Denkblockade.. bitte helft mir!

Wie sollte ich den Baum am besten speichern?
Wieviel Bytes sollte ich für die Codewörter der Buchstaben einplanen?

Bis jetzt habe ich den Fehler gemacht nur 1 Byte für die Codierung eines Buchstaben zu verwenden plus ein Byte was angibt wieviel Bits von diesem Byte verwendet werden sollen..ich bin blöderweise davin ausgegangen das die codewörter nur 8 stellen lang sind

Wie lang werden die so bei droßen dateien??