Huffman-Kodierung

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

• Über die gewichtete Summe der Codewortlängen:

${\displaystyle {\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

${\displaystyle l=\log _{2}\ m}$ mit ${\displaystyle m\in N}$ als Anzahl der zu codierenden Elemente.

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

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

Zuerst werden die relativen Häufigkeiten bestimmt:

${\displaystyle {\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:

${\displaystyle {\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:

Diese Huffman-Kodierung kodiert jedes Symbol mit durchschnittlich ${\displaystyle {\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 ${\displaystyle \log _{2}4=2}$ Bit kodiert.

Die Entropie liegt bei

${\displaystyle {\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)\\&=1{,}85\end{aligned}}}$

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

Der Dekodierer hat das Codebuch

${\displaystyle {\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:

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
 }

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
   }
   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
 }