Huffmann Verfahren |
![]() |
Huffman Applet |
Um eine oben skizzierte Codierung zu erreich wird ein binärer Baum (Huffman-Baum) erzeugt, der sich wie folgt liest. Man beginnt an der Wurzel des Baumes und addiert zum bisherigen Code eine 0 (binäre Null) wenn man nach links zu einem Sohnknoten geht und eine 1 (binäre Eins) wenn man nach rechts zu einem Sohnknoten verzweigt.
Bild: Huffman-Baum
Man sieht z.B., daß a mit 00 einen kürzeren Code hat als d mit 110.
LIST := leere Liste. Diese nimmt später alle Buchstaben mit der Häufigkeit Ihres Auftretens auf.
Zähle die Anzahl des Auftretens der Zeichen und bezeichne dies als "Gewicht" für jedes Zeichen. Füge jeden Buchstaben mit seinem Gewicht in LIST ein. Führe dies für alle Zeichen des Textes/der Datei durch.
Finde aus LIST die beiden Knoten, die das kleinste Gewicht besitzen. Erzeuge aus diesen Knoten einen künstlichen Elternknoten, dessen Gewicht genau der Summe der beiden Gewichte der Einzelknoten entspricht. Entfere die beide Knoten aus LIST und füge den Elternknoten in LIST.
Somit sind Knoten mit einem hohen Gewicht näher zur Wurzel als solche mit geringerem Gewicht.
Treten in einem Text die Zeichen {a, b, c, d ,e} mit den Gewichten a=7, b=6, c=5, d=2 und e=1 auf, so ergibt sich ein Knoten, der dem im obigen Bild entspricht. Codiert man den Text "abc" so erhält man auf Grund der eben zugrunde gelegeten Gewichte als Ergebnis den Code "000110".