Huffman-Kodierung

Die Huffman-Kodierung ist eine Form der Entropiekodierung, die 1952 von David A. Huffman entwickelt und in der Abhandlung A Method for the Construction of Minimum-Redundancy Codes publiziert wurde.^[1] Sie ordnet einer festen Anzahl an Quellsymbolen jeweils Codewörter mit variabler Länge zu. In der Informationstechnik ist sie ein Präfixcode, der üblicherweise für verlustfreie Kompression benutzt wird. Wie bei anderen Entropiekodierungen werden häufiger vorkommende Zeichen mit weniger Bits repräsentiert als seltener vorkommende Zeichen.

Grundlagen

Der Huffman-Baum für den Beispielsatz "this is an example of a huffman tree"

Um Daten möglichst redundanzfrei darzustellen, müssen die Quellsymbole mit Codewörtern unterschiedlicher Wortlängen kodiert werden. Die Länge der Codewörter entspricht dabei idealerweise ihrem Informationsgehalt. Um einen Code auch wieder eindeutig dekodieren zu können, muss er die Kraftsche Ungleichung erfüllen und zusätzlich noch präfixfrei sein, d. h., kein Codewort darf der Beginn eines anderen sein.

Die Grundidee ist, einen k-nären Wurzelbaum (ein Baum mit jeweils k Kindern je Knoten) für die Darstellung des Codes zu verwenden. In diesem sog. Huffman-Baum stehen die Blätter für die zu kodierenden Zeichen, während der Pfad von der Wurzel zum Blatt das Codesymbol bestimmt. Im Gegensatz zur Shannon-Fano-Kodierung wird der Baum dabei von den Blättern zur Wurzel (englisch bottom-up) erstellt.

Dieser Baum kann mit einem Heap und einer Vorrangwarteschlange implementiert werden.^[2]^[3]

Im Unterschied zum Morsecode benötigt man bei einer Huffman-Codierung keine Trennzeichen. Eine Trennung der Codewörter ist nicht notwendig, da die Codierung präfixfrei ist. Dadurch ist kein Codewort Anfang eines anderen Codewortes.

Der bei der Huffman-Kodierung gewonnene Baum liefert garantiert eine optimale und präfixfreie Kodierung. D. h., es existiert kein symbolbezogenes Kodierverfahren, das einen kürzeren Code generieren könnte, wenn die Auftrittswahrscheinlichkeiten der Symbole bekannt sind.

Geschichte

Im Jahre 1951 hatten David A. Huffman und seine Klassenkameraden am MIT im Kurs Informationstheorie die Wahl zwischen einer Seminararbeit und einer Abschlussprüfung. Die Seminararbeit, betreut von Professor Robert M. Fano, sollte die Findung des effizientesten binären Codes thematisieren. Huffman, der nicht in der Lage war, die Effizienz eines Codes zu beweisen, war nur knapp vor dem Entschluss, aufzugeben und sich für die Abschlussprüfung vorzubereiten, als er auf die Idee stieß, einen frequenzsortierten Binärbaum zu verwenden, und somit in kürzester Zeit jene Methode als effizienteste beweisen konnte.

Auf diese Weise übertraf Huffman seinen Professor Fano, der gemeinsam mit dem Begründer der Informationstheorie Claude Shannon einen ähnlichen Code entwickelte. Indem Huffman den Baum von unten nach oben anstatt von oben nach unten erstellte, vermied er die größte Schwachstelle der suboptimalen Shannon-Fano-Kodierung.^[4]

Algorithmus

Veranschaulichung einer Huffman-Kodierung. Das Quellalphabet ist

X:=\{\_,A,B,C,D,E\}

und das Codealphabet ist

C:=\{0,1\}

. Schritt 1 zeigt den Originaltext. Die Schritte 2 bis 6 erzeugen den Baum. Der fertige Baum in Schritt 6 wird durchlaufen, um das Codebuch zu erzeugen. Schritt 7 zeigt das Codebuch und Schritt 8 den codierten Text.

Definitionen

$X$ ist das Quellalphabet – der Zeichenvorrat, aus dem die Quellsymbole bestehen
$p_{x}$ ist die A-priori-Wahrscheinlichkeit und relative Häufigkeit des Symbols $x$ (die relative Häufigkeit)
$C$ ist das Codealphabet – der Zeichenvorrat, aus dem die Codewörter bestehen
$m$ ist die Mächtigkeit $\vert C\vert$ des Codealphabetes $C$ – die Anzahl der verschiedenen Zeichen

Erzeugen des Baumes

Ermittle für jedes Quellsymbol die relative Häufigkeit, d. h., zähle, wie oft jedes Zeichen vorkommt, und teile durch die Anzahl aller Zeichen.
Erstelle für jedes Quellsymbol einen einzelnen Knoten (die einfachste Form eines Baumes) und notiere im Knoten die Häufigkeit.
Wiederhole die folgenden Schritte so lange, bis nur noch ein einziger Baum übrig ist:
- Wähle $m$ (Teil-)Bäume mit den $m$ geringsten Häufigkeiten in deren Wurzel (diese Wahl ist im Allgemeinen nicht eindeutig).
- Fasse diese $m$ Bäume zu einem neuen (Teil-)Baum zusammen.
- Notiere die Summe der Häufigkeiten in der Wurzel.

Konstruktion des Codebuchs

Ordne jedem Kind eines Knotens eindeutig ein Zeichen aus dem Codealphabet zu.
Lies für jedes Quellsymbol (Blatt im Baum) das Codewort aus:
- Beginne an der Wurzel des Baums.
- Die Codezeichen auf den Kanten des Pfades von oben nach unten ergeben das zugehörige Codewort.

Kodierung

Lies ein Quellsymbol ein.
Ermittle das zugehörige Codewort aus dem Codebuch.
Gib das Codewort aus.

Mittlere Wortlänge

Die mittlere Länge eines Codeworts kann auf drei Arten berechnet werden.

Über die gewichtete Summe der Codewortlängen:

{\overline {l}}=\sum _{x\in X}p_{x}l_{x}

Die Summe aus der Anzahl der Schritte im Baum multipliziert mit der Häufigkeit eines Symbols.

Indem man die Auftrittswahrscheinlichkeiten an allen Zwischenknoten des Huffman-Baums summiert.
Bei ausschließlich gleicher Häufigkeit der zu codierenden Elemente ist die mittlere Länge

l=\log _{2}\ m

mit

m\in N

als Anzahl der zu codierenden Elemente.

Beispiele

Ein Huffman-Baum. Die Wurzel des Baumes befindet sich rechts, die Blätter links.

Das Quellalphabet sei $X:=\{a,b,c,d\}$ . Als Codealphabet wählen wir den Binärcode $C:=\{0,1\}$ und $m=\vert C\vert =2$ . Der Text $aababcabcd$ soll komprimiert werden.

Zuerst werden die relativen Häufigkeiten bestimmt:

{\begin{aligned}p_{a}&=0{,}4\\p_{b}&=0{,}3\\p_{c}&=0{,}2\\p_{d}&=0{,}1\end{aligned}}

Es wird ein Huffman-Baum konstruiert und anschließend die Codewörter an den Kanten eingetragen (siehe Bild rechts).

Daraus ergibt sich folgendes Codebuch:

{\begin{aligned}a&\rightarrow 1\\b&\rightarrow 01\\c&\rightarrow 001\\d&\rightarrow 000\end{aligned}}

Mit diesem Codebuch wird der ursprüngliche Text kodiert:

Originaltext	a	a	b	a	b	c	a	b	c	d
Kodierter Text	1	1	01	1	01	001	1	01	001	000

Diese Huffman-Kodierung kodiert jedes Symbol mit durchschnittlich ${\overline {l}}=0{,}4\cdot 1+0{,}3\cdot 2+0{,}2\cdot 3+0{,}1\cdot 3=0{,}4+0{,}6+0{,}6+0{,}3=1{,}9$ Bit. Das ist die mittlere Codewortlänge. Bei einer naiven Kodierung würde jedes der 4 Symbole mit $\log _{2}(4)=2$ Bit kodiert.

Die Entropie liegt bei

{\begin{aligned}H(X)&=-(0{,}4\cdot \log _{2}(0{,}4)+0{,}3\cdot \log _{2}(0{,}3)+0{,}2\cdot \log _{2}(0{,}2)+0{,}1\cdot \log _{2}(0{,}1))\\&\approx 1{,}846\end{aligned}}

Bit je Symbol. Dadurch, dass der Informationsgehalt je Quellsymbol keine ganze Zahl ist, verbleibt bei der Kodierung eine Rest-Redundanz.

Für den Beispielsatz "this is an example of a huffman tree" ist das Quellalphabet $X:=\{\_,a,e,f,h,i,l,m,n,o,p,r,s,t,u,x\}$ gegeben, wobei _ in diesem Fall für das Leerzeichen steht. Aus den absoluten Häufigkeiten der Quellsymbole, die in den Blättern des rechts dargestellten Huffman-Baums stehen, ergibt sich folgendes Codebuch:

absolute Häufigkeit	Zuordnung
${\begin{aligned}\_:7\\a:4\\e:4\\f:3\\h:2\\i:2\\l:1\\m:2\\n:2\\o:1\\p:1\\r:1\\s:2\\t:2\\u:1\\x:1\\\end{aligned}}$	${\begin{aligned}\_&\rightarrow 111\\a&\rightarrow 010\\e&\rightarrow 000\\f&\rightarrow 1101\\h&\rightarrow 1010\\i&\rightarrow 1000\\l&\rightarrow 11001\\m&\rightarrow 0111\\n&\rightarrow 0010\\o&\rightarrow 00110\\p&\rightarrow 10011\\r&\rightarrow 11000\\s&\rightarrow 1011\\t&\rightarrow 0110\\u&\rightarrow 00111\\x&\rightarrow 10010\\\end{aligned}}$

Mit diesem Codebuch wird der Beispielsatz kodiert:

Originaltext	t	h	i	s	_	i	s	_	a	n	_	e	x	a	m	p	l	e	_	o	f	_	a	_	h	u	f	f	m	a	n	_	t	r	e	e
Kodierter Text	0110	1010	1000	1011	111	1000	1011	111	010	0010	111	000	10010	010	0111	10011	11001	000	111	00110	1101	111	010	111	1010	00111	1101	1101	0111	010	0010	111	0110	11000	000	000

Diese Huffman-Kodierung kodiert jedes Symbol des Beispielsatzes (insgesamt 36 Zeichen) mit durchschnittlich

${\overline {l}}={\tfrac {1}{36}}\cdot (7\cdot 3+4\cdot 3+4\cdot 3+3\cdot 4+2\cdot 4+2\cdot 4+1\cdot 5+2\cdot 4+2\cdot 4+1\cdot 5+1\cdot 5+1\cdot 5+2\cdot 4+2\cdot 4+1\cdot 5+1\cdot 5)={\tfrac {1}{36}}\cdot 135=3{,}75$

Bit. Das ist die mittlere Codewortlänge. Bei einer naiven Kodierung würde jedes der 16 Symbole mit $\log _{2}(16)=4$ Bit kodiert.

Dekodierung

Zur Dekodierung eines Huffman-kodierten Datenstroms ist beim klassischen Verfahren das im Kodierer erstellte Codebuch notwendig. Grundsätzlich wird dabei umgekehrt als im Kodierungsschritt vorgegangen. Der Huffman-Baum wird im Dekodierer wieder aufgebaut und mit jedem eingehenden Bit – ausgehend von der Wurzel – der entsprechende Pfad im Baum abgelaufen, bis man an einem Blatt ankommt. Dieses Blatt ist dann das gesuchte Quellsymbol und man beginnt mit der Dekodierung des nächsten Symbols wieder an der Wurzel.

Beispiel

Der Dekodierer hat das Codebuch

{\begin{aligned}a&\rightarrow 1\\b&\rightarrow 01\\c&\rightarrow 001\\d&\rightarrow 000\end{aligned}}

und die empfangene Nachricht 1101101001101001000.

Jetzt wird für jedes empfangene Bit ausgehend von der Wurzel der Pfad im Baum abgelaufen, bis ein Blatt erreicht wurde (siehe Abbildung). Sobald ein Blatt erreicht wurde, speichert der Dekodierer das Symbol des Blattes und beginnt wieder bei der Wurzel, bis das nächste Blatt erreicht wird. Daraus ergibt sich der dekodierte Text:

Kodierter Text	1	1	01	1	01	001	1	01	001	000
Dekodierter Text	a	a	b	a	b	c	a	b	c	d

Pseudocode

Die folgenden Beispiele in Pseudocode zeigen Funktionen für die Generierung der Huffman-Kodierung.

Erzeugen des Baumes

Diese Funktion erzeugt einen Huffman Tree als Min-Heap und gibt einen Zeiger auf den Wurzelknoten zurück. Die Knoten des Min-Heap werden in einer Vorrangwarteschlange gespeichert.

/**
 * left // linker Kindknoten
 * right // rechter Kindknoten
 * top // Elternknoten
 * minHeap // Vorrangwarteschlange für den Min-Heap
 */
 function createHuffmanTree(symbolList, frequencyList, symbolsCount)
 {
   // Fügt die Knoten mit Symbol und Häufigkeit in die Vorrangwarteschlange ein
   foreach (symbol in symbolList)
   {
       Knoten mit Symbol und Häufigkeit in minHeap einfügen
   }
   // Der HuffmanTree wird schrittweise erzeugt, bis sich alle Knoten einem Baum befinden und nur noch der Wurzelknoten in der Vorrangwarteschlange ist
   while (die Anzahl der Knoten in minHeap ist nicht 1) // Solange die Anzahl der Knoten in der Vorrangwarteschlange nicht 1 ist
   {
       // Entfernt die zwei Knoten mit der kleinsten Häufigkeit aus der Vorrangwarteschlange
       left := minHeap.top()
       minHeap.pop()
       right := minHeap.top()
       minHeap.pop()
       Erzeuge einen neuen inneren Knoten top mit der Summe der Häufigkeiten der zwei Knoten left->frequency und right->frequency
       // Fügt die zwei Knoten mit der kleinsten Häufigkeit als linken und rechten Kindknoten des neuen inneren Knoten in den Baum ein
       top->left := left
       top->right := right
       minHeap.push(top) // Fügt den neuen Knoten in die Vorrangwarteschlange ein
   }
   return minHeap.top() // Gibt einen Zeiger auf den Wurzelknoten zurück
 }

Erzeugen des Codebuchs

Diese rekursive Funktion erzeugt das Codebuch für die Huffman-Kodierung, indem sie jedem Symbol des Quellalphabet ein binäres Codewort als Zeichenkette zuordnet.

/**
 * dictionary // Zuordnungstabelle für das Codebuch
 */
 // Diese rekursive Funktion erzeugt das Codebuch für die Huffman-Kodierung und speichert es in der Variable dictionary
 function createDictionary(node, codeword, dictionary)
 {
   if (der Knoten ist node ist leer)
   {
       return; // Abbruchbedingung, wenn kein linker oder rechter Teilbaum vorhanden ist
   }
   if (node->symbol is kein innerer Knoten, also ein Blatt) // Wenn der Knoten kein innerer Knoten, also ein Blatt ist
   {
       dictionary.insert(node->symbol, codeword); // Fügt die Kombination aus Symbol und Codewort dem Codebuch hinzu
       return; // Verlässt die Funktion
   }
   createDictionary(node->left, concat(codeword, "0"), dictionary) // Rekusiver Aufruf für den linken Teilbaum, das Codesymbol 0 für die linke Kante wird angefügt
   createDictionary(node->right, concat(codeword, "1"), dictionary) // Rekusiver Aufruf für den rechten Teilbaum, das Codesymbol 1 für die rechte Kante wird angefügt
 }

Optimalität

Für mittlere Codewortlänge ${\overline {l}}$ eines Huffman-Codes gilt^[5]

\mathrm {H} (X)\leq {\overline {l}}\leq \mathrm {H} (X)+1

Das bedeutet, im Mittel benötigt jedes Codesymbol mindestens so viele Stellen wie sein Informationsgehalt, höchstens jedoch eine mehr.

${\overline {l}}=\mathrm {H} (X)$ gilt genau dann, wenn alle Wahrscheinlichkeiten Zweierpotenzen sind ( $2^{-m_{x}},\;m_{x}\in \mathbb {N} ^{+}$ ). In dem Fall sagt man, die Huffman-Kodierung sei optimal bezüglich der Entropie.

Fasst man $n$ Quellsymbole zu einem großen Symbol $y$ zusammen, so gilt für die mittleren Codesymbollängen ${\overline {l}}_{y}$

\mathrm {H} _{n}(X)\leq {\overline {l}}_{y}\leq \mathrm {H} _{n}(X)+{\frac {1}{n}}

,

das heißt, mit zunehmender Anzahl $n$ gemeinsam kodierter Quellsymbole geht die mittlere Codewortlänge asymptotisch gegen die Entropie – die Huffman-Kodierung ist asymptotisch optimal.

Diese Optimalität der Huffman-Kodierung lässt sich mit vollständiger Induktion beweisen.^[6]^[7]

Laufzeit

Sei $n$ die Anzahl der Zeichen des Originaltexts und $d$ die Anzahl der verschiedenen Zeichen (meist deutlich weniger als Zeichen im Text). Die erste Anweisung, die die Häufigkeiten der Zeichen zählt, hat die asymptotische Laufzeit $O(n)$ , da sie jedes Zeichen im Text beachten muss. Die for-Schleife iteriert über die verschiedenen Zeichen im Quellalphabet. Diese Schleife iteriert lediglich $O(d)$ Mal und nicht $O(n)$ Mal. Die while-Schleife beginnt mit einer Vorrangwarteschlange, die $d$ Elemente enthält, und reduziert diese in jeder Iteration um ein Element. Sie iteriert also $O(d)$ Mal. In jeder Iteration ruft sie zweimal die Funktion pop und einmal die Funktion push auf, jeweils mit einer asymptotischen Laufzeit von $O(\log(d))$ bei Verwendung eines Heaps. Alle anderen Operationen innerhalb der while-Schleife sind in konstanter Laufzeit implementierbar. Die Laufzeit der while-Schleife ist also $O(d\cdot \log(d))$ . Damit ist die Gesamtlaufzeit für die Huffman-Kodierung $O(n+d\cdot \log(d))$ .^[8]

Adaptive Huffman-Kodierung

Die adaptive Huffman-Kodierung aktualisiert laufend den Baum. Der anfängliche Baum wird erzeugt, indem eine vorgegebene Wahrscheinlichkeitsverteilung für alle Quellsymbole angenommen wird (bei völliger Unkenntnis der Quelle eine Gleichverteilung). Mit jedem neuen Quellsymbol wird dieser aktualisiert, wodurch sich ggf. auch die Codesymbole ändern. Dieser Aktualisierungsschritt kann im Dekodierer nachvollzogen werden, so dass eine Übertragung des Codebuchs nicht nötig ist.

Mit dieser Methode kann ein Datenstrom on-the-fly kodiert werden. Er ist jedoch erheblich anfälliger für Übertragungsfehler, da ein einziger Fehler zu einer – ab der Fehlerstelle – komplett falschen Dekodierung führt.

Siehe auch

Literatur

Thomas M. Cover, Joy A. Thomas: Elements of Information Theory

Weblinks

Freie Universität Berlin, Institut für Informatik: Präfixcodes und der Huffman–Algorithmus
Freie Universität Berlin, Institut für Informatik: Huffman-Kodierung
SwissEduc: Huffman-Code
LNTwww: Huffman- und Shannon-Fano-Codierung
Huffman Coding Java (Codebeispiel in Java)
Paul E. Black, National Institute of Standards and Technology: Huffman Coding, Dictionary of Algorithms and Data Structures.
Huffman Tree Generator (Web Application)

Einzelnachweise

↑ D. A. Huffman: A method for the construction of minimum-redundancy codes. In: Proceedings of the I.R.E. September 1952, S. 1098–1101 (compression.ru [PDF]).
↑ David Wagner, University of California, Berkeley: Data Compression via Huffman Coding
↑ Northeastern University: Priority Queue; Heapsort; Huffman Code
↑ Profil: David A. Huffman
↑ Strutz: Bilddatenkompression, SpringerVieweg, 2009
↑ University of California, Berkeley: Proof of Optimality of Huffman Coding
↑ University of Toronto: Proof of Optimality of Huffman Codes
↑ Justus Piater, Universität Innsbruck: Huffman Coding: Algorithmus und Analyse

[orig_paper-1] D. A. Huffman: A method for the construction of minimum-redundancy codes. In: Proceedings of the I.R.E. September 1952, S. 1098–1101 (compression.ru [PDF]).

[2] David Wagner, University of California, Berkeley: Data Compression via Huffman Coding

[3] Northeastern University: Priority Queue; Heapsort; Huffman Code

[4] Profil: David A. Huffman

[Strutz-5] Strutz: Bilddatenkompression, SpringerVieweg, 2009

[6] University of California, Berkeley: Proof of Optimality of Huffman Coding

[7] University of Toronto: Proof of Optimality of Huffman Codes

[8] Justus Piater, Universität Innsbruck: Huffman Coding: Algorithmus und Analyse

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]