Den Huffman-Baum aufbauen

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.

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.