Huffmann-Kodierung

Eine Zeichenfolge soll kodiert werden. Hierfür kann die Huffmann-Kodierung verwendet werden. Die Huffmann-Kodierung hat den Vorteil, dass sie die Fano-Bedingung erfüllt. Die Huffmann-Kodierung schaut sich die übergebene Zeichenfolge an, und erstellt eine Tabelle über die relativen Häufigkeiten der einzelnen Zeichen. Es werden dann jeweils paarweise die “Knoten” verbunden, welche die geringste relative Häufigkeit besitzen. Dadurch entsteht immer ein neuer Knoten. Setzt man dies Fort, erhält man einen Baum, bei dem von jedem Knoten, der kein Blatt ist, jeweils nach links oder rechts gewandert werden kann, bis man ein Blatt erreicht. Im Blatt steht dann ein Zeichen. Die Bewegung “Links” bzw. “Rechts” muss kodiert werden. Man erhält somit eine Kodierung, bei der die Zeichen mit der größten relativen Häufigkeit am kürzesten von der Wurzel entfernt sind, also den kürzesten Code besitzen.

Die Huffmann-Kodierung besitzt immer die minimale Länge!

Die Huffmann-Kodierung erfüllt immer die Fano-Bedingung!