Die Huffman Kodierung beruht auf dem Verfahren häufig vorkommende Zeichen in einem Eingabealphabet mit einer kürzeren Bitfolge zu kodieren als selten vorkommende Zeichen. Dadurch wird die Gesamtlänge des kodierten Strings kürzer als die des Unkodierten.
Dieses Verfahren wird in vielen gängigen Kompressionsalgorithmen verwendet, wie zum Beispiel bzip oder mp3.
Wir zählen jedes unserer Zeichen in dem Eingabestring ab, und erstellen uns so eine Liste von Tupeln,bei denen jedes Zeichen und dessen absolute Häufigkeit gespeichert wird. Dabei entsteht folgende Tabelle:
| Zeichen | Häufigkeit |
|---|
Wir erstellen aus unserer Liste mit Tupeln eine Initial-Liste mit lauter Blättern (grün). Diese speichern als Wert die Häufigkeit des jeweiligen Buchstaben, sowie den Buchstaben selbst.
Nun suchen wir uns aus dieser Liste die zwei kleinsten Blätter heraus und verknüpfen diese zu einem Teilbaum welcher die zwei Blätter als Kinder hat. Der Wert dieses Teilbaums ist die Summe der beiden Blätter. Dieses Verfahren wird solange fortgesetzt, bis wir aus der Liste einen kompletten Binärbaum zusammengestellt haben. Wichtig ist dabei dass wir immer die zwei vom Wert her kleinsten Bäume/Blätter verbinden!
Dies ist der letzte Schritt vor dem eigentlichen Encodieren. Wir wandern nun den obigen Binärbaum von der Wurzel ausgehend zu allen Blättern ab. Biegen wir dabei links ab (rote Linie), merken wir uns eine 0. Biegen wir rechts ab (blaue Linie) merken wir uns eine 1. Die Bitfolge die wir erhalten wenn wir an einem Blatt angelangen ist die Bitfolge, mit der wir unser Zeichen codieren.
Machen wir das für alle Zeichen, erhalten wir folgende Übersetzungstabelle:
| Zeichen | Häufigkeit | Bitfolge |
|---|
Man sieht sehr deutlich, dass die am häufigsten vorkommenden Zeichen die kürzesten Bitfolgen haben.
Hier sind nun die beiden Strings als Bitfolgen zum einen uncodiert und zum anderen codiert dargestellt. Ich hoffe dass der Algorithmus bei eurer Eingabe was bewirkt hat!
Unkodiert:
Kodiert:
Kompression: