Kleines Nachschlagewerk Informatik
Huffman-Kodierung
Worum geht es?
Der Huffman-Kodierung liegt folgende Idee zu Grunde: Jedes Zeichen braucht den gleichen Speicherplatz. Könnte man nicht sparen, wenn seltene Zeichen mehr Bits, dafür häufige Zeichen weniger Bits bekommen?
Der Kodierungsbaum
Die Kodierung kann man sich baumartig vorstellen. Links heißt 0, rechts heißt 1. Als Beispiel sei ein Baum angegeben:





Damit lässt sich die Bitfolge 110100111111110 eindeutig dekodieren. Nach 110 steht man am L und hat damit den ersten Buchstaben. Es geht wieder von oben los, aber bereits nach 10 ist man wieder bei einem Buchstaben abgelangt, dem I. 01 führt zu N, 1111 zu U und 1110 zu X.
Das Erstellen eines Kodierungsbaumes
Die Dekodierung einer Bitfolge ist recht einfach, wenn man den Baum kennt. Schwieriger ist die Kodierung, weil man diesen erst erstellen muss.

Gegeben sei folgender Text: EIN EINZIGER EIMER WAR LEER. Man kann das Leerzeichen als Zeichen mitzählen, was hier auch getan wird. Zuerst wird die Anzahl aller Buchstaben ermittelt.

BuchstabeAnzahl
E7
I4
N2
Z1
G1
R4
L1
A1
W1
_4


Dann werden alle Buchstaben fortlaufend nach Anzahl sortiert aufgeschrieben. In einem Computerprogramm würde man Nodes erstellen, die sich den Buchstaben und die Anzahl merken können und diese in einer Liste speichern. Bei gleicher Häufigkeit ist die Position in der Liste zufällig.





Dann werden die beiden seltensten Buchstaben über eine neue Node, die sich die Gesamtzahl merkt, verlinkt. Es entsteht ein kleiner Baum. Die Buchstaben werden aus der Liste entfernt und der Baum einsortiert. Wo er bei gleicher Häufigkeit landet, ist nicht wichtig, hier wird immer am Anfang einsortiert.





Es sind vier weitere seltene Buchstaben im Spiel, die ebenfalls zwei kleine Bäume ergeben.





Am Anfang stehen nun zwei Nodes, die schon Bäume enthalten. Natürlich kann man auch die zu einem neuen Baum verbinden und einfügen.





Ein Buchstabe (N) und ein kleiner Baum (MZ (viele Grüße nach Zschopau)) ergeben wieder einen Baum.





Dieses Spiel geht immer weiter, wie die folgenden vier Schritte zeigen. In der oberen Liste werden es immer weniger Nodes, die Bäume werden aber immer größer.











Die letzten beiden Nodes werden noch zusammen gefügt. Die Anzahl in der obersten Node sollte der Gesamtzahl der Zeichen entsprechen, sonst ging etwas schief.





Am Schluss schreibt man an jeden linken Ast eine Null, an jeden rechten Ast eine Eins. Geht man von oben bis zum Buchstaben, ergeben die Astbezeichnungen die Kodierung. Zum R kommt man über rechts-links-rechts, also ist die Kodierung 101. Es ergibt sich folgende Kodierungstabelle:
E01
_00
I100
R101
N1101
M11000
Z11001
A11110
L11111
G11100
W11101
Mit diesem Wissen kann man den Text neu kodieren. Der Anfang (EIN...) lautet somit 011001101...

Möchte man die Einsparung errechnet, summiert man die notwendigen Bits: 7*2+4*2+4*3+4*3+2*4+5+5+5+5+5+5=84. Mit 8-Bit-Kodierung bräuchte man 27*8=216 Bit.
Kritik
So schön wie im Beispiel dargestellt ist die Welt aber nicht immer. Erstens muss man beachten, dass der Baum auch übertragen werden muss. Sonst weiß die Gegenseite nicht, wie sie entpacken soll. Zum zweiten sind nur wenige Buchstaben verwendet worden. Bei 11 verschiedenen Zeichen braucht man nur 4 Bit pro Zeichen, also 108 Bit insgesamt.

Huffman lohnt sich also bei großen Texten, wo die Übertragung des Baumes nicht auffällt bzw. bei Texten mit gleicher Buchstaben-Häufigkeit, wo man auf den Baum verzichten kann. Kodiert man immer deutsche Texte, die ausreichend groß sind, so wird die relative Häufigkeit der Buchstaben nicht sehr schwanken.