Huffman-Kodierung

Entropiekodierung

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.

GrundlagenBearbeiten

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 Morse-Code 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.

GeschichteBearbeiten

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]

AlgorithmusBearbeiten

 
Veranschaulichung einer Huffman-Kodierung. Das Quellalphabet ist   und das Codealphabet ist  . 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

  •   ist das Quellalphabet – der Zeichenvorrat, aus dem die Quellsymbole bestehen
  •   ist die A-priori-Wahrscheinlichkeit und relative Häufigkeit des Symbols   (die relative Häufigkeit)
  •   ist das Codealphabet – der Zeichenvorrat, aus dem die Codewörter bestehen
  •   ist die Mächtigkeit   des Codealphabetes   – 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 die   Teilbäume mit der geringsten Häufigkeit in der Wurzel, bei mehreren Möglichkeiten die Teilbäume mit der geringsten Tiefe.
    • Fasse diese 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ängeBearbeiten

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

  • Über die gewichtete Summe der Codewortlängen:
  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
  mit   als Anzahl der zu codierenden Elemente.

BeispielBearbeiten

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

Das Quellalphabet sei  . Als Codealphabet wählen wir den Binärcode   und  . Der Text   soll komprimiert werden.

Zuerst werden die relativen Häufigkeiten bestimmt:

 

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

Daraus ergibt sich folgendes Codebuch:

 

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   Bit. Das ist die mittlere Codewortlänge. Bei einer naiven Kodierung würde jedes der 4 Symbole mit   Bit kodiert.

Die Entropie liegt bei

 

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

DekodierungBearbeiten

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.

BeispielBearbeiten

Der Dekodierer hat das Codebuch

 

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

ProgrammierungBearbeiten

Die folgende Beispielcode in der Programmiersprache C++ zeigt eine Implementierung der Huffman-Kodierung als Konsolenanwendung. Für den Huffman-Baum wird ein Min-Heap mit einer Vorrangwarteschlange verwendet.[5][6]

Code-Schnipsel  
#include <iostream>
#include <map>
#include <queue>
#include <vector>
using namespace std;

// Datentyp für die Knoten des Huffman Tree
struct MinHeapNode
{
    char symbol;
    int frequency; // Häufigkeit des Symbols
    MinHeapNode* left, * right; // Linker und rechter Kindknoten

    // Konstruktor
    MinHeapNode(char symbol, int frequency)
    {
        left = right = NULL;
        this->symbol = symbol;
        this->frequency = frequency;
    }
};

// Deklariert einen Vergleichsoperator für die Konten des Min-Heap 
struct compare
{
    bool operator()(MinHeapNode* node1, MinHeapNode* node2)
    {
        return node1->frequency > node2->frequency;
    }
};

// Diese rekursive Funktion erzeugt das Codebuch für die Huffman-Kodierung und speichert es in der Variable dictionary
void createDictionary(struct MinHeapNode* node, string codeword, map<char, string>& dictionary)
{
    if (node == NULL)
    {
        return; // Abbruchbedingung, wenn kein linker oder rechter Teilbaum vorhanden ist
    }
    if (node->symbol != '$') // Wenn der Knoten kein innerer Knoten, also ein Blatt ist
    {
        dictionary.insert(map<char, string>::value_type(node->symbol, codeword)); // Fügt die Kombination aus Symbol und Codewort dem Codebuch hinzu
    }
    createDictionary(node->left, codeword + "0", dictionary); // Rekusiver Aufruf für den linken Teilbaum, das Codesymbol 0 für die linke Kante wird angefügt
    createDictionary(node->right, codeword + "1", dictionary); // Rekusiver Aufruf für den rechten Teilbaum, das Codesymbol 1 für die rechte Kante wird angefügt
}

// 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
MinHeapNode* createHuffmanTree(char symbols[], int frequencies[], int symbolsCount)
{
    struct MinHeapNode* left, * right, * top; // Zeiger auf den linken Kindknoten, rechten Kindknoten und Elternknoten
    priority_queue<MinHeapNode*, vector<MinHeapNode*>, compare> minHeap; // Vorrangwarteschlange für den Min-Heap
    // Fügt die Knoten mit Symbol und Häufigkeit in die Vorrangwarteschlange ein
    for (int i = 0; i < symbolsCount; i++)
    {
        minHeap.push(new MinHeapNode(symbols[i], frequencies[i]));
    }
    // Der HuffmanTree wird schrittweise erzeugt, bis sich alle Knoten einem Baum befinden und nur noch der Wurzelknoten in der Vorrangwarteschlange ist
    while (minHeap.size() != 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();
        // Erzeugt einen neuen inneren Knoten mit der Summe der Häufigkeiten der zwei Knoten
        // Zur Unterscheidung von den Quellsymbolen in den Blättern wird das Symbol '$' verwendet
        top = new MinHeapNode('$', left->frequency + 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
}

// Hauptfunktion die das Programm ausführt
int main()
{
    string inputText;
    cin >> inputText; // Eingabe des Texts über die Konsole
    vector<char> symbolsVector; // Vektor für die verschiedenen Symbole
    vector<int> frequenciesVector; // Vektor für die Häufigkeit der Symbole
    // Die Symbole und die entsprechenden Häufigkeiten werden ermittelt und in den Vektoren gespeichert
    for (int i = 0; i < inputText.length(); i++) // for-Schleife, die die Symbole des Texts durchläuft
    {
        char currentSymbol = inputText[i];
        bool isFound = false;
        int j = 0;
        // Diese while-Schleife durchsucht den Vektor nach dem Symbol. Wenn das Symbol gefunden ist, bricht sie ab.
        while (!isFound && j < symbolsVector.size())
        {
            char symbol = symbolsVector[j];
            if (symbol == currentSymbol) // Wenn Symbol gefunden
            {
                frequenciesVector[j]++; // Häufigkeit um 1 erhöhen
                isFound = true;
            }
            j++;
        }
        if (!isFound) // Wenn Symbol nicht gefunden
        {
            symbolsVector.push_back(currentSymbol); // Symbol hinzufügen
            frequenciesVector.push_back(1); // Häufigkeit 1 hinzufügen
        }
    }
    int symbolsCount = symbolsVector.size();
    char* symbols = new char[symbolsCount]; // Array für die verschiedenen Symbole
    int* frequencies = new int[symbolsCount]; // Array für die Häufigkeit der Symbole
    // Speichert die Elemente der Vektoren in den Arrays
    for (int i = 0; i < symbolsCount; i++)
    {
        symbols[i] = symbolsVector[i];
        frequencies[i] = frequenciesVector[i];
    }
    map<char, string> dictionary; // Dictionary für das Codebuch
    MinHeapNode* huffmanTree = createHuffmanTree(symbols, frequencies, symbolsCount); // Funktionsaufruf für das Erzeugen des Huffman Tree
    createDictionary(huffmanTree, "", dictionary); // Funktionsaufruf für das Erzeugen des Codebuchs
    for (auto iterator = dictionary.cbegin(); iterator != dictionary.cend(); ++iterator) // for-Schleife, die die Elemente des Codebuch (dictionary) durchläuft
    {
        cout << iterator->first << ": " << iterator->second << endl; // Ausgabe des Codebuch auf der Konsole
    }
    for (int i = 0; i < inputText.length(); ++i)
    {
        cout << dictionary[inputText[i]]; // Liest die Codewörter für die einzelnen Symbole aus dem Codebuch (dictionary) aus und gibt den kodierten Text auf der Konsole aus
    }
    cout << endl;
}

OptimalitätBearbeiten

Für mittlere Codewortlänge   eines Huffman-Codes gilt[7]

 

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

  gilt genau dann, wenn alle Wahrscheinlichkeiten Zweierpotenzen sind ( ). In dem Fall sagt man, die Huffman-Kodierung sei optimal bezüglich der Entropie.

Fasst man   Quellsymbole zu einem großen Symbol   zusammen, so gilt für die mittleren Codesymbollängen  

 ,

das heißt, mit zunehmender Anzahl   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.[8][9]

LaufzeitBearbeiten

Sei   die Anzahl der Zeichen des Originaltexts und   die Anzahl der verschiedenen Zeichen. Die erste Anweisung, die die Häufigkeiten der Zeichen zählt, hat die asymptotische Laufzeit  . Die for-Schleife iteriert über die verschiedenen Zeichen im Quellalphabet. Diese Schleife iteriert lediglich   Mal und nicht   Mal. Die while-Schleife beginnt mit einer Vorrangwarteschlange, die   Elemente enthält, und reduziert diese in jeder Iteration um ein Element. Sie iteriert also   Mal. In jeder Iteration ruft sie zweimal die Funktion pop und einmal die Funktion push auf, jeweils mit einer asymptotischen Laufzeit von   bei Verwendung eines Heaps. Alle anderen Operationen innerhalb der while-Schleife sind in konstanter Laufzeit implementierbar. Die Laufzeit der while-Schleife ist also  . Damit ist die Gesamtlaufzeit für die Huffman-Kodierung  .[10]

Adaptive Huffman-KodierungBearbeiten

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 auchBearbeiten

LiteraturBearbeiten

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

WeblinksBearbeiten

EinzelnachweiseBearbeiten

  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
  5. GeeksforGeeks: Huffman Coding
  6. Rosetta Code: Huffman coding
  7. Strutz: Bilddatenkompression, SpringerVieweg, 2009
  8. University of California, Berkeley: Proof of Optimality of Huffman Coding
  9. University of Toronto: Proof of Optimality of Huffman Codes
  10. Justus Piater, Universität Innsbruck: Huffman Coding: Algorithmus und Analyse