Huffman-Codierung

David Huffman hat 1952 ein Verfahren entwickelt, mit welchem Zeichen platzsparender codiert werden können. Seine Idee ist, dass Zeichen, welche häufig im Text vorkommen, einen kürzeren Code erhalten, als Zeichen, welche selten im Text vorkommen.

Alltagsbezug

Die Huffman-Codierung und ähnliche Verfahren werden für das Komprimieren von Dateiformaten wie DOCX, JPG oder MP3 eingesetzt. ^[1]

Codebaum

Ein Codebaum ist eine Struktur mit einem Startknoten. Von diesem aus geht es entweder nach links oder rechts unten weiter. Eine 0 im Code bedeutet nach links gehen, eine 1 nach rechts gehen. Wenn ein Knoten mit einem Buchstaben erreicht wird, hat man ein Zeichen decodiert, man beginnt wieder von vorne.

Erstellen eines Huffman-Baumes

Am Beispiel der Codierung des Texts «EINTRITT FREI» soll der Huffman-Algorithmus erläutert werden.

Zuerst zählt man, wie oft jedes Zeichen im Text vorkommt, und erstellt eine Häufigkeitstabelle.

Zeichen	Häufigkeit
E	2
I	3
N	1
T	3
R	2
␣	1
F	1

Nun geht es darum, einen Codierungsbaum zu erstellen. Die Häufigkeiten der Buchstaben bilden je einen Knoten. Die Häufigkeit steht im Knoten, der Buchstaben darunter. Die Knoten werden nach Häufigkeit sortiert:

Nun werden die zwei Knoten mit den kleinsten Häufigkeiten an einen neuen Knoten angehängt. Der neue Knoten enthält die Summe der Häufigkeiten der ursprünglichen Knoten:

Dies wird wiederholt, bis alle Knoten miteinander verbunden sind. Wenn zwei Knoten die gleiche Häufigkeit haben, spielt es keine Rolle, welcher gewählt wird. Im nächsten Schritt wird der kleinste Knoten «N» mit «R» zusammengefasst. Man könnte aber «N» auch mit «E» zusammenfassen.