Huffmann Verfahren

Huffman Applet

Konzept:


sampletree.gif (1920 bytes)

Bild: Huffman-Baum

Man sieht z.B., daß a mit 00 einen kürzeren Code hat als d mit 110.

Algorithmus:

  1. LIST := leere Liste. Diese nimmt später alle Buchstaben mit der Häufigkeit Ihres Auftretens auf.

  2. 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.

  3. 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".

Lasse Deine Zeichenkette nach Huffman kodieren und komprimieren:

Zeichenkette zum Kodieren eingeben: