Huffman-Kodierungs-Visualisierer

Die Huffman-Kodierung optimiert die Datenkomprimierung durch die dynamische Erstellung eines Binärbaums basierend auf der statistischen Häufigkeit von Eingabesymbolen. Es weist höchstwahrscheinlichen Zeichen mathematisch kürzere Bitfolgen zu und erreicht damit die theoretische Grenze der Shannon-Entropie. Die strikte Anforderung präfixfreier Codes garantiert eine eindeutige algorithmische Decodierung. Diese deterministische Neuzuweisung der Binärgewichtung minimiert mathematisch die Gesamtdateigröße ohne Datenverlust.

Der Baum wächst von unten nach oben: Zunächst wird jedes Zeichen nach seiner Häufigkeit aufgelistet, dann werden wiederholt die zwei seltensten Elemente zu einem kleinen Teilbaum zusammengefasst und als ein Bündel behandelt. Das wiederholt sich, bis ein einziger Baum übrig bleibt; die Codes liest man dann von oben ab — links ist 0, rechts ist 1. Diese "gierige" Gewohnheit, stets die zwei kleinsten zu vereinen, wirkt kurzsichtig, erzeugt aber beweisbar die kürzestmöglichen Codes.

David Huffman entwickelte das Verfahren 1951 als Doktorand am MIT, als Professor Robert Fano seiner Klasse die Wahl zwischen einer Abschlussprüfung und einer Arbeit über den effizientesten Code ließ. Fano und Claude Shannon hatten es bereits versucht und ihre Bäume von oben nach unten gebaut. Huffman gab fast auf, erkannte dann aber, dass der Aufbau von unten — zuerst die seltensten Symbole verschmelzen — optimal ist, und übertraf damit die Methode seines eigenen Lehrers.