Huffman-Codierung einfach erklärt

Bei der Huffman-Codierung bekommen die Zeichen Codewörter mit unterschiedlicher Länge. Ein Codewort ist eine kurze Folge aus Bits, zum Beispiel 01. Im fertigen Bitstrom stehen die Codewörter ohne Lücken hintereinander. Du musst also selbst erkennen, wo ein Codewort endet.

Um einen Code eindeutig decodieren zu können, muss er präfixfrei sein: Kein Codewort darf der Beginn eines anderen Codeworts sein. Der Huffman-Code ist ein solcher Präfixcode. Beim Morsecode braucht man dagegen Trennzeichen. Bei der Huffman-Codierung ist keine Trennung nötig, weil die Codierung präfixfrei ist.

Die Codewörter lesen wir an einem Baum ab. Die Wurzel ist der oberste Knoten, ein Blatt ist ein Knoten ganz unten ohne Kinder. Im Huffman-Baum stehen die Zeichen nur in den Blättern. Der Pfad von der Wurzel zum Blatt bestimmt das Codewort. So kann kein Codewort der Anfang eines anderen sein.

Beim Decodieren gehst du mit jedem Bit einen Schritt im Baum, bis du ein Blatt erreichst. Dieses Blatt ist das Zeichen. Dann beginnst du wieder an der Wurzel. Ein präfixfreies Beispiel ist das Codebuch a→1, b→01, c→001, d→000.

Zuerst zählst du, wie oft jedes Zeichen vorkommt. Teilst du durch die Anzahl aller Zeichen, erhältst du die relative Häufigkeit. Jedes Zeichen bekommt dann einen eigenen Knoten, in den du seine Häufigkeit schreibst.

Dann wiederholst du: Wähle die zwei Bäume, die in ihrer Wurzel die geringsten Häufigkeiten haben, und fasse sie zu einem neuen Baum zusammen. In dessen Wurzel schreibst du die Summe der beiden Häufigkeiten. Das machst du, bis nur noch ein Baum übrig ist. Mit jedem Schritt wird aus m Symbolen ein Problem mit m−1 Symbolen. Bei 5 Symbolen brauchst du deshalb 4 Schritte, bei 7 Symbolen 6 Schritte. Ein zweites Beispiel mit 7 Symbolen hat A mit 0,4 und sechs Symbole mit je 0,1. Gibt es mehrere mögliche Wahlen, ist die Wahl im Allgemeinen nicht eindeutig.

Der Baum entsteht von den Blättern zur Wurzel (englisch bottom-up). Für die Codewörter schreibst du auf die beiden Kanten unter einem Knoten 0 und 1. Eine Kante ist die Verbindungslinie zwischen zwei Knoten. Das Codewort eines Zeichens liest du ab, indem du an der Wurzel beginnst und die Zeichen auf den Kanten bis zum Blatt hintereinander schreibst.

Ein Codebuch ist eine Liste, die jedem Zeichen sein Codewort zuordnet. Beim Codieren machst du für jedes Zeichen drei Dinge: Du liest das Zeichen ein, suchst sein Codewort im Codebuch und gibst das Codewort aus. Die Codewörter hängst du ohne Lücken aneinander.

Beim Decodieren gehst du umgekehrt vor. Beim klassischen Verfahren brauchst du dazu das Codebuch, das der Codierer erstellt hat. Der Huffman-Baum wird wieder aufgebaut. Mit jedem Bit gehst du von der Wurzel aus einen Schritt, bis du ein Blatt erreichst. Das Blatt ist das Zeichen. Danach beginnst du für das nächste Zeichen wieder an der Wurzel.

Bei der adaptiven Huffman-Codierung wird der Baum laufend aktualisiert. Der Decodierer kann das nachvollziehen. Deshalb muss dort kein Codebuch übertragen werden.

Die Bitlänge einer codierten Nachricht erhältst du, indem du für jedes Zeichen Häufigkeit mal Codewortlänge rechnest und alles addierst. Teilst du durch die Anzahl der Zeichen, bekommst du die mittlere Codewortlänge in Bit pro Zeichen. Beim Satz „this is an example of a huffman tree“ sind das 135 Bit für 36 Zeichen, also 135 : 36 = 3,75 Bit pro Zeichen.

Zum Vergleich: Für 16 verschiedene Zeichen brauchen gleich lange Codewörter 4 Bit pro Zeichen, denn 2 hoch 4 ist 16. Das sind 36 · 4 = 144 Bit. Mit Huffman sind es 135 Bit.

Grenzen: Die Entropie ist ein Maß für den mittleren Informationsgehalt pro Zeichen. Je seltener ein Zeichen vorkommt, desto höher ist seine Information. Die mittlere Länge eines Huffman-Codes liegt zwischen der Entropie H und H + 1. Sie ist genau dann gleich H, wenn alle Wahrscheinlichkeiten Zweierpotenzen sind, also 1/2, 1/4, 1/8 und so weiter. Sonst bleibt eine Rest-Redundanz, weil der Informationsgehalt eines Zeichens keine ganze Zahl ist. Im Beispiel aababcabcd sind es 1,9 Bit statt der Entropie von etwa 1,846 Bit. Fasst man n Zeichen zu einem großen Symbol zusammen, geht die mittlere Länge mit wachsendem n gegen die Entropie.

Der Huffman-Baum liefert garantiert eine optimale präfixfreie Codierung: Kein Verfahren, das jedes Symbol einzeln codiert, erzeugt einen kürzeren Code, wenn die Wahrscheinlichkeiten der Symbole bekannt sind. Huffman wird üblicherweise für verlustfreie Kompression benutzt, bei der keine Information verloren geht. Die adaptive Variante ist erheblich anfälliger für Übertragungsfehler, weil ein einziger Fehler ab der Fehlerstelle zu komplett falscher Decodierung führt.