Huffman-Code Schritt für Schritt
Über diese App
Aus den Häufigkeiten eines Textes wächst der Huffman-Baum: Die zwei leichtesten Knoten verlassen das Heap-Feld, fliegen unter einen neuen Knoten mit der Summe, und der neue Knoten wandert per heappush zurück. Gerechnet wird exakt wie der Code der Folien (heapq mit __lt__), auch für eigenen Text. Danach Codes ablesen, 61 statt 133 Bit für KLEINERBEISPIELTEXT, und den Bitstrom ohne Trennzeichen Bit für Bit durch den Baum zurücklesen. Mit Vorhersagefrage und Schalter für andere Wahl bei Gleichstand.
Wie Huffman-Codes entstehen
Die Huffman-Codierung vergibt häufigen Zeichen kurze und seltenen Zeichen lange Bitfolgen. Man beginnt mit einem Knoten je Zeichen, gewichtet mit seiner Häufigkeit. Dann nimmt man immer die zwei leichtesten Knoten, hängt sie unter einen neuen Knoten mit der Summe ihrer Gewichte und legt diesen zurück. Am Ende bleibt ein Baum; der Weg von der Wurzel zu einem Blatt, links 0 und rechts 1, ist der Code des Zeichens. Kein Code ist Anfang eines anderen, deshalb lässt sich der Bitstrom ohne Trennzeichen eindeutig decodieren.
Was die App zeigt
Oben wächst der Wald aus Teilbäumen, die oberste Reihe ist immer genau der Inhalt der Liste heap. Beim Verschmelzen leuchten die zwei kleinsten Knoten, verlassen das Heap-Feld per heappop, fliegen unter einen neuen Knoten und kehren per heappush zurück. Gerechnet wird exakt wie Python-Code mit heapq und __lt__, auch für eigenen Text. Danach zeigt eine Tabelle die Codes und die Bitzahl; für KLEINERBEISPIELTEXT sind es 61 statt 133 Bit in 7-Bit-ASCII.
Selbst ausprobieren
Wähle ein Beispiel oder gib eigenen Text mit bis zu 40 Zeichen ein und gehe Schritt für Schritt durch Zählen, heapify, Verschmelzen, Codes ablesen und Codieren. Vor jedem Verschmelzen fragt die App, welche zwei Knoten drankommen. Ein Schalter zeigt, wie eine andere Wahl bei Gleichstand andere, aber gleich gute Codes ergibt. Im Decodieren-Panel liest du einen Bitstrom Bit für Bit durch den Baum zurück.
Häufige Fragen
- Wie funktioniert die Huffman-Codierung?
- Man zählt, wie oft jedes Zeichen vorkommt, und verschmilzt wiederholt die zwei seltensten Knoten zu einem neuen Knoten mit der Summe ihrer Häufigkeiten. Der entstehende Baum liefert die Codes: Jede Kante nach links ist eine 0, nach rechts eine 1. Häufige Zeichen liegen nah an der Wurzel und bekommen kurze Codes.
- Warum braucht ein Huffman-Code keine Trennzeichen?
- Huffman-Codes sind präfixfrei: Kein Code ist der Anfang eines anderen, weil alle Zeichen in Blättern stehen. Beim Decodieren läuft man von der Wurzel Bit für Bit den Baum hinab; erreicht man ein Blatt, ist ein Zeichen fertig, und man beginnt wieder oben.
- Ist der Huffman-Code eindeutig?
- Nicht unbedingt. Bei gleich großen Häufigkeiten gibt es mehrere Wahlmöglichkeiten, die zu verschiedenen Bäumen und Codes führen. Die Gesamtlänge der codierten Nachricht ist aber bei allen gleich und unter den präfixfreien Codes minimal.
- Was kann ich in der Huffman-App tun?
- Den Baum für Beispieltexte oder eigenen Text Schritt für Schritt bauen, vorher tippen, welche Knoten verschmelzen, Codes ablesen, die Bitzahl mit fester Länge und ASCII vergleichen und einen Bitstrom durch den Baum decodieren. Der zugehörige Python-Code steht im Code-Panel.
Fach: Informatik
Mehr aus Informatik
- Ackermann-Funktion
- Aufzug-Simulator
- Binär-Werkstatt
- Binäre vs. lineare Suche
- Collatz-Problem (3n+1)
- CPU-Innenleben
- Das Innere austauschen
- Ein Frame in 16 Millisekunden — wie eine Game-Engine ein Bild rechnet (3D)
Eine VisuApp von heyprof: interaktiv, kostenlos im Browser, ohne Anmeldung. Was ist eine VisuApp? · Alle Apps