Huffman Tree
-
kann mir jemand nen link zu 'ner information geben wo ich nachlesen kann wie man den tree selbst am effektivsten speichert... oder kann es mir hier jemand sagen?
ich hab zwar schon selbst eine recht zufriedenstellende lösung, aber da gibt es bestimmt jemanden mit einer besseren idee vor mir
( ja, gegoogled hab ich, aber irgendwie find ich nur huffman theorie oder source wie man den tree erstellt, aber nirgens wie man den speichert.)
dank im voraus
rapso->greets();
-
ich würd einfach für jedes Zeichen den Code und die Codelänge abspeichern ... der Baum läßt sich daraus rekonstruieren.
Oder du gehst zur adaptiven Huffmancodierung über, da brauchst du keinen Baum zu speichern, dafür erreicht sie keine optimale Kompressionsrate.
-
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.
hab mir überlegt, ich werde erstmal das ganze array packen und dannte rekursiv immer teilen und packen und wenn die 2 stücke bessere rations aufweisen als das ganze, dann geht's ne rekursion tiefer, damit würde ich genau wie beim addaptiven packen mich auf die häfungen von werten auf bestimmten bereichen des arrays spezialisieren.
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).würde mich über weitere posts freuen
rapso->greets();
-
wie soll das gehen?
falls du huffmann richtig verstanden hast kann es codewörter geben, welche
auf dem selbem niveau (also länge) liegen -> nicht eindeutig
-
wie soll was gehen? bitte präzisier deine fragen ein wenig.
und ja ich hab das verstanden und zig mal implementiert, ich kenne mich damit ein wenig gut aus.
*kopfkratz*
rapso->greets();
-
verstehe nicht so ganz wie du anhand der codewortlänge auf das
entsprechende wort zurückschließen willst???(oder doch mit
gedacht?)
-
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
-
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..
-
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
-
@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
-
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
-
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
-
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();
-
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??
-
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
-
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!