Huffman-Komprimierung im Detail

1st Official Post

    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? :smiling_face:

    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

    Geht nicht, gibt's nicht!

    Edited 16 times, last by manakoDE (March 8, 2020 at 5:27 PM).

    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 :smiling_face:

    Geht nicht, gibt's nicht!

    • Official Post

    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 (March 19, 2020 at 5:53 PM).

    Hallo!

    Das TuT ist ja leider nicht mehr komplett. Hat nun jemand davon eine PDF Datei erstellt, die man noch irgendwo laden könnte oder gibt es eine Möglichkeit, dieses TuT noch mal zu aktualisieren? Außerdem würde mich mal interessieren, um was für ein Tool es hier geht?

    bye

    0.) Allgemeine Info (kurz)


    Huffman-Coding ist eine verlustfreie, präfixfreie Kompression: häufige Zeichen bekommen kürzere Bitfolgen – perfekt zum effizienten Speichern und Dekomprimieren. 


    1.) Beispiel-Eingabe:

    "ABRACADABRA"

    • Länge: 11 Zeichen → ursprünglich 11 × 8 Bit = 88 Bit.
    • Zählen der Häufigkeiten:
      • A: 5, B: 2, R: 2, C: 1, D: 1

    2.) Sortieren & Baum bauen

    1. Lege jede Zeichen-Frequenz als Blatt an und sortiere (Priority Queue):
      [C:1, D:1, B:2, R:2, A:5]
    2. Nimm die beiden geringsten → C(1)+D(1)=2 → neuer Knoten [CD:2].
    3. Queue neu sortiert: [B:2, R:2, CD:2, A:5]
    4. Weiter so: B(2)+R(2)=4 → [BR:4]
    5. Nochmals: CD(2)+BR(4)=6 → [CD/BR:6]
    6. Schließlich: A(5)+6=11 → Root [gesamt:11]
      So entsteht der Huffman-Baum.

    3.) Bitcodes zuweisen

    • Linker Zweig = 0, rechter = 1.
    • Lauf durch den Baum zum Blatt = Code:

    Zeichen

    Code

    A

    0

    R

    10

    B

    111

    C

    1100

    D

    1101

    4.) Kodieren des Strings


    Original: A B R A C A D A B R A

    Bitfolgen ersetzen:

    Ergebnis:


    🎯 Was ist Canonical Huffman- Codierung?


    Beim Standard-Huffman müssen Baumstruktur und Codewörter übertragen werden – das kostet Platz. Bei der kanonischen Version reicht es, nur Code‑Längen zu speichern. Der Empfänger kann dann die Codes selbst rekonstruiert erzeugen .


    🔄 1. Ausgangslage: Normale Huffman-Codes

    Aus dem Standard-Huffman-Prozess für “ABRACADABRA” haben wir z. B. folgende Code-Längen:

    Code
    Symbol : Häufigkeit : Länge
A      : 5           : 1
B      : 2           : 3
R      : 2           : 3
C      : 1           : 4
D      : 1           : 4

    (Details wie im bisherigen Beispiel mit dem Baum.)


    📊 2. Kanonischer Prozess: Sortieren

    Sortiere nach Code-Länge, dann alphabetisch:

    Code
    1 bit: A
3 bit: B, R
4 bit: C, D

    🧮 3. Kanonische Codes berechnen

    • Erstes Symbol jeder Länge bekommt den kleinstmöglichen Code (alles Nullen).
    • Danach: vorheriger Code + 1, dann bei Längensprung nach links shift bis zur neuen Länge.

    Schritt-für-Schritt:

    1. A (1 Bit)
      • Start bei 0 → Code: 0
      • nextCode = 0 + 1 = 1
    2. B (3 Bit)
      • Längensprung von 1 auf 3 → shift left um (3−1)=2 → 1<<2 = 4 (100)
      • Code für B = 100
      • nextCode = 4 + 1 = 5
    3. R (3 Bit)
      • gleiche Länge → kein shift → nextCode = 5 (101) → Code 101
      • nextCode = 5 + 1 = 6
    4. C (4 Bit)
      • Längensprung von 3 auf 4 → 6<<1 = 12 (1100) → Code 1100
      • nextCode = 12 + 1 = 13
    5. D (4 Bit)
      • gleiche Länge → nextCode = 13 (1101) → Code 1101
      • nextCode = 13 + 1 = 14

    Kanonische Codes:

    Code
    A = 0
B = 100
R = 101
C = 1100
D = 1101

    📦 4. Kodieren mit kanonischen Codes

    String: A B R A C A D A B R A

    Ersetzungen:

    Code
    A → 0
B → 100
R → 101
C → 1100
D → 1101

    Resultierende Bitfolge:

    Code
    0 100 101 0 1100 0 1101 0 100 101 0
= 0|100|101|0|1100|0|1101|0|100|101|0

    Gesamtlänge: 1 + 3 + 3 + 1 + 4 + 1 + 4 + 1 + 3 + 3 + 1 = 25 Bit

    Minimal über Standard-Huffman (23 Bit), aber nur Code-Längen sind kodiert – also sparen wir Baum-Overhead.

    🎯 Vorteile

    • Du speicherst nur [1,3,3,4,4] statt ganzer Baumstruktur.
    • Empfänger baut Codes neu auf, spart Bytes.
    • Schnelle Decodierung durch einfache Inkremente und Shifts.

    ✅ Zusammenfassung

    1. Normale Huffman-Codes errechnen & Längen speichern
    2. Sortieren nach Länge/Alphabet
    3. Kanonische Codes mit Sequenz, Shifts & Inkrementen erzeugen
    4. Nur Längen mitsenden, Empfänger rekonstruiert Codes

    Cheers 🥂


    sephirothneu7nlq8.png

    Wer sich entschieden hat, etwas zu tun, und an nichts anderes denkt, überwindet alle Hindernisse.

    Quote from Headmember

    Und von welchem Tool war nun die Rede?

    Das war einfach nur eine kleine Spielerei, die das oben erklärte programmiertechnisch etwas veranschaulicht hat.

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


    Edgar Allan Poe