Huffman-Codierung

Definition - Was bedeutet Huffman-Codierung?

Die Huffman-Codierung ist ein verlustfreier Datencodierungsalgorithmus. Der Prozess hinter seinem Schema umfasst das Sortieren numerischer Werte aus einer Menge in der Reihenfolge ihrer Häufigkeit. Die am wenigsten häufigen Zahlen werden nach und nach über den Huffman-Baum eliminiert, der die beiden niedrigsten Frequenzen aus der sortierten Liste in jedem neuen „Zweig“ hinzufügt. Die Summe wird dann über den beiden eliminierten niedrigeren Frequenzwerten positioniert und ersetzt sie in der neuen sortierten Liste. Jedes Mal, wenn ein neuer Zweig erstellt wird, wird die allgemeine Richtung des Baums entweder nach rechts (für höhere Werte) oder nach links (für niedrigere Werte) verschoben. Wenn die sortierte Liste erschöpft ist und der Baum vollständig ist, ist der Endwert Null, wenn der Baum mit einer linken Zahl endet, oder eins, wenn er mit der rechten endet. Dies ist eine Methode zum Reduzieren von komplexem Code in einfachere Sequenzen und ist bei der Videokodierung üblich.

Technische.me erklärt Huffman Coding

Die Datenkomprimierung hat eine Vorgeschichte, die vor dem physischen Rechnen liegt. Morsecode komprimiert beispielsweise Informationen, indem Zeichen, die in der englischen Sprache statistisch üblich sind (wie die Buchstaben „e“ und „t“), kürzere Codes zugewiesen werden. Die Huffman-Codierung entstand als Ergebnis eines Klassenprojekts am MIT durch seinen damaligen Schüler David Huffman.

1951 nahm Huffman an einem Kurs bei Robert Fano teil, der (mit Hilfe eines Ingenieurs und Mathematikers namens Claude Shannon) ein Effizienzschema erfand, das als Shannon-Fano-Codierung bekannt ist. Als Fano seiner Klasse die Möglichkeit gab, entweder eine Hausarbeit zu schreiben oder eine Abschlussprüfung abzulegen, entschied sich Huffman für die Hausarbeit, um eine effiziente binäre Codierungsmethode zu finden. Dies führte zu einer Huffman-Codierung, die in den 1970er Jahren zu einem bedeutenden digitalen Codierungsalgorithmus geworden war.