frage zum huffman-kompressions-algorithmus



  • ich habe obiges verfahren zur kompression verstanden (aus diversen tutorials erlesen) jedoch kein tutorial gefunden, welches mir erklaerte, wo denn nun der binärbaum, der zum entpacken des komprimierten files gebraucht wird, abgelegt wird !?!? wird dieser etwa auch im komprimierten file selber abgelegt? wie wird das denn in den gaengigne kompressionstools gemacht!? 😕

    ideen und anregungen hierzu waeren nett.

    danke.



  • Ja, bei der Huffmankodierung muß der Baum mit in der Datei abgelegt werden, weil er sich nicht aus den Daten rekonstruieren läßt. Es gibt aber auch Kodierungen bei denen das geht. Bei LZW-Kompression zum Beispiel läßt sich die Kodierung aus der komprimierten Datei rekonstruieren.



  • danke fuer die klare antwort ... 🙂

    ich nehme an eine standard-vorgehensweise zum ablegen des codierungsbaumes in eine datei gibt es nicht (kann man sozusagen nach eigenen methoden tun)!?

    dankeschoen vorab.



  • Mir ist keine Standardvorgehensweise bekannt. Ich würde mich da an Deiner Stelle auch nicht zu sehr drauf konzentrieren. Der Baum ist ja normalerweise recht klein. Bei großen Dateien fällt er kaum ins Gewicht, bei kleinen Dateien, wo der vielleicht ins Gewicht fallen würde komprimiert man ohnehin nicht.

    Also einfach ne kleine Liste rein: Zeichen Codewort Zeilenumbruch usw.
    Vielleicht noch ein bißchen tricksen, nicht daß es Probleme gibt, wenn ein Codewort wie der Zeilenumbruch aussieht.

    MfG Jester



  • wenn man viele kleine dateien komprimiert, fällt das sehr ins gewicht wie der baum abgelegt wird (z.b.backup von sourcen erstellen 😉 ).

    am einfachsten ist es den counter der zeichen abzulegen und beim entpacken den tree rekonstruieren.

    eine standardisierte methode gibt es nicht, weil die vielen möglichen algorithmen zum tree-ablegen für bestimmte trees gut bzw schlecht sind, gibt kein uber-algorithm dafür. wenn man es also gut machen möchte, muss man mehrere implementieren und von fall zu fall den besten nehmen.


Log in to reply