Huffman-Kodierung

Der von David Huffman beschriebene Algorithmus ordnet allen Zeichen, die in den betrachteten Daten auftreten können, einen Endknoten in einem binären Baum zu. Als Attribut erhalten diese Knoten die Auftrittshäufigkeiten der ensprechenden Zeichen.

Die Baumstruktur entsteht durch das schrittweise Zusammenfassen dieser Knoten. Dazu werden die beiden Knoten mit der geringsten Auftrittshäufigkeit einem neuen Knoten untergeordnet, der die Summe der beiden Auftrittshäufigkeiten zugewiesen bekommt. Bereits zusammengefaßte Knoten werden im weiteren Verlauf nicht mehr beachtet, da sie bereits in den Baum eingebettet sind. Das Prozedere wird solange durchlaufen, bis alle Knoten in einer Wurzel zusammengeführt sind.

Kodebaum nach Huffman

Zur En- bzw. Dekodierung werden den Kanten des Huffman-Baums die binären Werte 0 bzw. 1 zugeordnet. Der "Weg" von der Wurzel des Huffman-Baums zu dem entsprechenden Endknoten ergibt den Huffman-Kode des Zeichens, dem der Endknoten zugeordnet ist.

 <   ^   >