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:
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:
Nach der 6. Sortierung:
Nach der letzten Sortierung:
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:
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:
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: