Huffman-Komprimierung im Detail

  • Name: Huffman-Coding

    Typ: Präfixfreie Komprimierung

    Verlustfrei: Ja

    Beispiel: Beliebig

    Link: Wikipedia

    Andere Tutorials: LZSS



    0.) Generelle Infos

    1.) Zählen aller Zeichen im Eingabestrom

    2.) Sortieren aller Einträge

    3.) Positionen im Huffman-Baum festlegen

    4.) Huffman-Bits ermitteln

    5.) Stärken und Schwächen von Huffman-Komprimierung



    0.) Generelle Infos

    Diese kleine Einführung soll euch dabei helfen zu verstehen wie die Huffman-Kodierung funktioniert,

    ich werde versuchen alles, wie immer, ohne Fachchinesisch und komplexe Berechnungen zu erklären.


    Falls jetzt jemand denkt: "Oh Gott, Huffman, das mit diesem komischen Baum!", oder sowas, bitte lest einfach weiter,

    das Wort "Baum", oder "Tree" wird sicher fallen, aber er ist sehr simpel zu erstellen, auch ohne dass man ihn versteht.


    Falls ihr das Gelesene an einem praktischem Beispiel ausprobieren und selbst einen Kompressor basteln wollt,

    ist natürlich etwas Kenntnis in Sachen Programmierung erforderlich, ansonsten könnt ihr mit meinem kleinen Test-Tool

    verschiedene Sachen ausprobieren.


    Download: Huffman-Kodierung



    1.) Zählen aller Zeichen im Eingabestrom

    Als Erstes zählen wir die Häufigkeit aller Zeichen in unserem Eingabestrom, in unserem Beispiel wollen wir den

    String "snes-projects" in Huffman-Bits umwandeln.

    Unser Eingabestrom hat 13 Zeichen, 13 x 8 Bit = 104 Bit.


    Hier eine Liste der Zählung:

    CharCount2.png


    Wie wir unschwer erkennen kommt das "s" und das "e" häufiger vor als die anderen zeichen, diese Häufigkeit macht sich die

    Huffman-Kompression zunutze.



    2.) Sortieren aller Einträge

    Im nächsten Schritt müssen wir alle Einträge sortieren und aus diesen "Zweige" und "Blätter" erstellen.


    Ein "Zweig" teilt sich immer in 2 weitere Ableger, dieses können weitere "Zweige", oder "Blätter" sein,

    "Blätter" sind immer das Ende eines Huffman-Codes, unser dekomprimiertes Zeichen.


    Sortiert wird immer auf- oder absteigend, nach der Häufigkeit der Buchstaben, in meinem Programm ist es absteigend.

    Wir nehmen uns jetzt die beiden kleinsten Einträge, in dem Fall "-" und "c", packen diese beiden zu einem

    "Zweig" zusammen und packen ihn hinten an die Liste.

    Unsere beiden "Blätter" "-" und "c" packen wir in eine neue Liste.


    Wichtig hierbei ist, dass die Liste nach JEDEM Durchlauf neu nach Größen sortiert wird!!!


    1.) Sortieren

    2.) Die beiden kleinsten Werte nehmen und zusammenzählen

    3.) Den erstellten "Zweig" an die Liste hängen

    4.) Die beiden "Blätter" in eine zweite Liste packen

    5.) Löschen der beiden "Blätter" aus der ersten Liste

    6.) Wieder bei Schritt 1 anfangen, bis nur noch ein Eintrag in der ersten Liste übrig bleibt.


    Hier wie es aussieht nach der ersten Sortierung:

    Sorted1.png



    Nach der 6. Sortierung:

    Sorted6.png



    Nach der letzten Sortierung:

    SortedFinal.png


    Jetzt haben wir einen Huffman-Baum in Form einer Liste, sieht nicht aus wie ein Baum, oder? :)


    3.) Positionen im Huffman-Baum festlegen


    Jetzt kommen wir zum spaßigen Teil.

    Unser Decoder braucht später einige Infos um zu wissen wie was zu lesen ist, daher müssen wir alle "Blätter" und

    "Zweige" markieren, das stellt aber kein Problem dar, weil unser "Baum" in der ersten Spalte als Liste durch die Sortierung vorhanden ist.


    Als erstes legen wir alle Positionen fest, so wie die Daten später in der Datei liegen aus der der Huffman-Baum gelesen wird.

    Wir starten bei der Position 0x4, die ersten 4 Bytes sind für unsere beiden Haupteinträge reserviert, mehr dazu später.

    Jedes Eintrag mit einem einzelnen Zeichen (Blatt) ist 2 Bytes lang und jeder andere Eintrag, mit mehr als einem Zeichen, ist 5 Bytes lang.


    Zur Erklärung, aber hier erstmal unwichtig:

    Jeder Eintrag braucht eine eindeutige Identifizierung, deswegen ist jedem einzelnen Zeichen ein Byte mit dem Wert "0x00" und jedem andren Eintrag ein Byte mit

    dem Wert "0xFF" vorgesetzt.


    0x00 = Unkomprimiertes Zeichen (Blatt)

    0xFF = Ein Eintrag der tiefer in den Baum führt (Zweig)


    So sieht die Zuordnung aus wenn sie fertig ist:

    Positions.png




    4.) Huffman-Bits ermitteln


    Jetzt ermitteln wir die Huffman-Bits, dies ist auch recht einfach, weil sie durch die Sortierung in der Liste sehr leicht zu ermitteln sind.

    Die beiden letzten letzten Einträge sind immer unsere Teilbäume, "rts" ist der Teilbaum der nach Links führt und "e-cjnop" ist der Teilbaum

    der nach Rechts führt.


    Was könnte man anstatt "Links" und "Rechts" nehmen um einem Prozessor die Entscheidung zu erleichtern was was ist?

    Richtig "0" und "1" ...!


    "rts" ist also "0" und "e-cjnop" ist "1"


    ...


    Zur Info:

    Die Anzahl der Einträge in einem Huffman-Baum, egal ob als Liste oder sonstwie gespeichert, ist immer durch 2 teilbar,

    daher können wir immer sagen dass ein Eintrag, dessen Position in der Liste eine gerade Zahl ist, eine Linke (0) Abzweigung,

    und ein ungerader Index eine Rechte (1) Abzweigug darstellt.

    Nicht vergessen: Es wird immer bei Index 0 angefangen.


    Hier ein Beispiel:

    BitIndexes.png


    Nehmen wir als Beispiel das "s", wir suchen jetzt von unten nach oben wo das "s" auftaucht.

    Als erstes taucht es in dem "Zweig" "rts" auf, also ist das erste Bit eine "0", wenn wir jetzt weiter suchen,

    taucht das "s" das nächste Mal alleine auf (Position 42), dies ist eine Rechte Abzweigung.


    Das "s" hat jetzt also die Bits "01" bekommen, da es alleine steht ist das Festlegen der Bits für diesen Buchstaben auch fertig,

    wir haben hier nämlich einen einzelnen Buchstaben (ein Blatt) erreicht.



    Nehmen wir als Nächstes das "n", dieses finden wir in "e-cjnop", einer Rechten Abzweigung, also "1".

    Als Nächstes finden wir es in "jnop", wieder eine Rechte Abzweigung, also wieder "1".

    Im nächsten Schritt finden wir es in "jn", einer Linken Abzweigung, also "0".

    Und im letzten Schritt steht es alleine in einer Rechten Abzweigung, also "1".


    Das "n" bekommt also die Bitfolge "1101"



    Wenn wir alle Buchstaben durch haben, sieht das Ganze so aus:

    CalculatedBits.png

  • Wow, vor diesem technischen Wissen hatte ich schon immer Respekt. Echt super, dass du es hier teilst!

    Meine Lieblings SNES-RPGs:


    1. Lufia II
    2. Final Fantasy VI
    3. Terranigma, Seiken Densetsu III
    4. Tengai Makyō Zero, Dragon Quest III SNES-Remake
    5. Star Ocean, Shiren the Wanderer
    6. Chrono Trigger
    7. Final Fantasy V, Magical Land of Wozz
    8. Seiken Densetsu II, Zelda: A Link to the Past


    Lieblings-Charaktere: Terra & Shadow (FF 6), Tia & Dekar (Lufia), Carlie (Seiken III), Subaru (TMZ), Schala (CT)

  • Mach ich gerne.

    Wollte das Thema schon länger machen, hab mich dann vor 4 Tagen rangesetzt und einfach angefangen.

    Ich werde das aber noch überarbeiten, mit einem leichteren Beispiel, damit es auch wirklich alle verstehen.

    Ohne Fachbegriffe und höhere Mathematik :-)

  • Also, ich habe mich mal mit dem Tool beschäftigt und etwas rumgespielt. Soweit konnte ich die Schritte mit meinen programmierminimalistischen Wissen nachvollziehen. Jetzt stehe ich vor "linken" und "rechten" Teilbäumen und weiß nicht ganz weiter. Kannst du nochmal erklären warum der eine Teil links und der andere rechts ist?


    EDIT: Die Frage hat sich durch einen Geistesblitz erledigt!

    Deep into that darkness peering,
    long I stood there,
    wondering, fearing, doubting,
    dreaming dreams
    no mortal ever dared to dream before.


    Edgar Allan Poe

    Edited once, last by Poe ().