Huffman-Codierung: Wie ein MIT-Student ein Kompressionsverfahren fand, das seit 75 Jahren verwendet wird

Im Jahr 1951 erhielt David Huffman, ein Doktorand am Massachusetts Institute of Technology (MIT), eine Aufgabe, an der zuvor selbst Claude Shannon und sein Lehrer Robert Fano erfolglos gearbeitet hatten. Er sollte den effizientesten Weg finden, Symbole mit binären Codes variabler Länge zu kodieren und dabei die Häufigkeit jedes einzelnen Symbols zu berücksichtigen.

Mehrere Monate lang probierte Huffman einen Ansatz nach dem anderen aus, doch die Lösung wollte sich nicht einstellen. Schließlich war er bereits dabei, seine Notizen wegzuwerfen und sich auf seine Abschlussprüfung vorzubereiten, als ihm plötzlich ein Gedanke kam.

Anstatt den Codierungsbaum von oben nach unten aufzubauen, entschied er sich für den umgekehrten Weg: vom untersten Niveau aus zu starten und wiederholt die beiden Symbole mit der geringsten Häufigkeit zusammenzuführen.

So entstand der Huffman-Algorithmus, der unter allen binären Präfixcodes bei gegebenen Symbolhäufigkeiten die minimale durchschnittliche Wortlänge liefert.

75 Jahre später wird dieser Algorithmus nach wie vor in Formaten wie ZIP, GZIP, JPEG und MP3 eingesetzt.