Häufiges kurz, Seltenes lang
Bei einem Code fester Länge kostet ein seltenes Zeichen so viel wie ein häufiges. Der Huffman-Code gibt häufigen Zeichen kurze und seltenen Zeichen lange Codewörter.
- Häufigkeit:wie oft ein Zeichen vorkommt; ANANASBANANE: A 5, N 4, S 1, B 1, E 1.
- Variable Länge:Codewörter dürfen unterschiedlich lang sein.
- Präfixfrei:kein Codewort ist Anfang eines anderen — so lässt sich ohne Trennzeichen decodieren.
- Codebaum:Zeichen sitzen in den Blättern, der Weg von der Wurzel liefert das Codewort.
Huffman-Code: Häufige Zeichen bekommen kurze, seltene Zeichen lange Codewörter.
Variable Länge: Die Codewörter sind unterschiedlich lang; der Code ist präfixfrei: Kein Codewort ist Anfang eines anderen, so geht das Decodieren ohne Trennzeichen.
Codebaum: Die Zeichen sitzen in den Blättern, der Weg von der Wurzel liefert das Codewort.
Der Algorithmus Schritt für Schritt
Der Baum wächst von unten nach oben: aus einzelnen Blättern wird durch Zusammenfassen ein einziger Baum.
- 1. Blätter:für jedes Zeichen ein Knoten mit seiner Häufigkeit.
- 2. Zusammenfassen:die zwei Knoten mit den kleinsten Häufigkeiten unter einen neuen Knoten hängen; er trägt die Summe.
- 3. Wiederholen:bis nur ein Baum übrig ist — der neue Knoten nimmt wieder am Vergleich teil.
- 4. Beschriften:Kante nach links 0, nach rechts 1; hier hängt der kleinere Knoten links.
- Gleichstand:bei gleichen Häufigkeiten frei wählen: die Codewörter ändern sich, die Gesamtlänge nicht.
Baue den Huffman-Baum für das Wort im Balken: Klicke nacheinander die zwei Knoten mit den kleinsten Häufigkeiten an — oder wähle sie mit Tab und Enter. Stimmt die Wahl, werden sie zu einem neuen Knoten verbunden.
Halte fest: Immer die zwei kleinsten Häufigkeiten verbinden — auch neu entstandene Knoten zählen mit. Die Wurzel trägt am Ende die Anzahl aller Zeichen.
Huffman-Regel: Immer die zwei Knoten mit den kleinsten Häufigkeiten zu einem Knoten mit der Summe zusammenfassen, bis ein Baum entsteht.
Ablauf: Für jedes Zeichen ein Blatt mit seiner Häufigkeit; neue Knoten nehmen am Vergleich wieder teil; Kante nach links 0, nach rechts 1.
Wurzel: Sie trägt die Anzahl aller Zeichen; bei Gleichstand ändern sich die Codewörter, nicht die Gesamtlänge.
Allgemeine Hinweise
Neue Knoten zählen mit
Wer nur die ursprünglichen Blätter der Reihe nach verbindet, erhält eine Kette statt eines Huffman-Baums. Nach jedem Schritt neu die zwei kleinsten suchen.
Wurzel als Probe
Die Wurzel muss die Anzahl aller Zeichen tragen — bei ANANASBANANE also 12. Sonst fehlt ein Blatt.
Konvention notieren
Schreibe dazu, ob der kleinere Knoten links hängt und ob links 0 bedeutet. In Aufgaben gilt die vorgegebene Konvention.