Rechnernetze

Huffmann-Kodierung

Die einfache Huffmann-Kodierung stellt eine algorithmische Umsetzung der informationstheoretischen Regel dar, möglichst gleichwahrscheinliche Teilmengen der zu kodierenden Werte zu verwenden, um eine (sub-) optimale Kodierung zu erhalten. Sie erzeugt einen binären Baum, dessen Blätter den Zeichen entsprechen, und der zu jedem Knoten zwei Nachfolger (0, 1) besitzt. Eine Kodierung verwendet jeweils ein entsprechendes Anfangsstück.

Ein Algorithmus zur Huffmankodierung könnte folgendermaßen aussehen:

1. Initialisierung: Alle Zeichen werden Knoten zugeordnet und nach ihrer Häufigkeit in einer Liste sortiert.

2. Solange die Liste der Knoten noch mehr als ein Element enthält:

Entnehme die beiden Elemente mit der geringsten Häufigkeit der Liste und erzeuge einen Elternknoten hierfür.
Weise die Summe der Häufigkeiten der Kinder dem Elternknoten zu und füge diesen Knoten der Liste zu.
Den Zeigern des Elternknoten wird der Code 0, 1 zugeordnet (Reihenfolge im Prinzip beliebig).

ALLER ANFANG IST SCHWER
Zeichen	Häufigkeit h	-log₂(^h/_S)	Code	Anzahl der Bits für Kodierung	-h/S*log^{_{₂(^h/_S)}}	h*Code-Bits
	3	2,93859946	111	3	0,38329558	9
A	3	2,93859946	110	3	0,38329558	9
E	2	3,52356196	101	3	0,30639669	6
L	2	3,52356196	1001	4	0,30639669	8
N	2	3,52356196	1000	4	0,30639669	8
R	2	3,52356196	011	3	0,30639669	6
S	2	3,52356196	0101	4	0,30639669	8
C	1	4,52356196	0100	4	0,19667661	4
F	1	4,52356196	0011	4	0,19667661	4
G	1	4,52356196	00101	5	0,19667661	5
H	1	4,52356196	00100	5	0,19667661	5
I	1	4,52356196	0001	4	0,19667661	4
T	1	4,52356196	00001	5	0,19667661	5
W	1	4,52356196	00000	5	0,19667661	5
S =	23			56	3,67531087	86

Im obigen Beispiel werden 86 Bits zur Kodierung des Textes "ALLER ANFANG IST SCHWER" benutzt, während eine Kodierung der 14 verschiedenen Zeichen mit jeweils 4 Bits 23*4=92 Bits benötigen würde. Die ideelle Entropie ist 3,6753, während die wahre Entropie in diesem Beispiel 86/23 = 3,739 ist, also nahe an der ideellen Entropie liegt.

Grundsätzlich stellt sich die Frage, ob die Huffman-Kodierung jeweils eine bessere Kodierung ergibt als eine Kodierung mit Hilfe gleichlanger Wörter. Die Antwort ist überraschenderweise ja, solange die absolute Häufigkeit der einzelnen Zeichen bekannt ist. Man kann sich das etwa so plausibel machen, dass man von einem ausgeglichenen Baum ausgeht. Dieses entspricht der Kodierung von 2^N Wörtern mit gleichlangen Wörtern. Habe jetzt das Zeichen i eine Häufigkeit h_i, die größer ist als die Summe der Häufigkeiten zweier anderer Zeichen j und k: h_i>h_j+h_k, so lässt sich das erste Zeichen mit N-1 Bits kodieren, es rückt im Baum eine Ebene nach oben, während sich die anderen mit jeweils N+1 Bits kodieren lassen; sie sacken eine Ebene tiefer. Die Kodierung wird sich für das Zeichen i um h_i Bits verringern, während sie sich für die Zeichen j und k um h_j+h_k Bits vergrößern wird; der Gewinn beträgt also h_i-h_j-h_k Bits und ist somit positiv.

Dieses Verfahren lässt sich jetzt verallgemeinert fortsetzen, und man kommt offenbar zu der Huffman-Kodierung, da die Zeichen mit der geringsten Häufigkeit immer tiefer sacken, solange die Summe ihrer Häufigkeiten noch kleiner ist als die eines einzelnen anderen Zeichens.

Daraus folgt also, dass eine Huffman-Kodierung niemals schlechter ist als eine Kodierung mit gleichlangen Wörtern. Ein weiterer Vorteil ist, dass die Anzahl verschiedener Zeichen nicht länger von der Wortlänge abhängt, sondern beliebig gewählt werden kann. Man könnte also zu jeder Anwendung eine Kodierung konstruieren, die genau die von der jeweiligen Anwendung benötigten Zeichen festlegt.

Zum Seitenanfang