Huffman-Codierung

Für die Datenkompression von Bildern soll für das Protokoll eine verlustfreie Datenkompression implementiert werden. Um keine weiteren Abhängigkeiten von Bibliotheken zu generieren, werden die Klassen für die Komprimierung autonom von anderen Komponenten erstellt. Ein sehr bekannter und oft in Bildformaten verwendeter Algorithmus zur Datenkompression ist die Huffman-Codierung, eine Form der Entropiekodierung benannt nach David A. Huffman. Abhängig von den Eigenschaften der zu komprimierenden Daten können damit Kompressionsraten von 20% bis 90% erzielt werden.

Die Huffman-Codierung basiert auf einem Greedy-Algorithmus. Dieser betrachtet die Daten als Zeichenketten und verwendet eine Tabelle mit einer Häufigkeitsverteilung der vorkommenden Zeichen, um eine optimale Möglichkeit für die Darstellung jedes Zei-chens als binäre Zeichenkette zu entwickeln.

Präfix-Code

Um eine Bilddatei zu komprimieren, können verschiedene Darstellungsformen verwendet werden. In der Regel werden binäre Zeichencodes (oder kurz Codes) verwendet, in dem jedes Zeichen durch eine eindeutige binäre Zeichenkette dargestellt wird. Bei einem Code fester Länge, werden insgesamt 3 Bits benötigt, um sechs Zeichen darstellen zu können: a = 000, b = 001, c = 010, ..., f = 101. Diese Methode benötigt insgesamt 300000 Bits, um ein Bild mit 100000 Zeichen zu codieren, deren Symbole in der nachfolgenden Tabelle dargestellt sind. Die Huffman-Codierung nutzt dabei einen Code variabler Länge. Dadurch können häufig auftretenden Zeichen kurze Codewörter zugewiesen werden und selten auftretenden Zeichen lange Codewörter. Es ist aber nicht möglich, einzelnen Zeichen einfach Bitfolgen zuzuweisen und diese auszugeben. Wird zum Beispiel das Zeichen a mit der Bitfolge „10“, das Zeichen b mit der Folge „01“ und c mit „0“ ko-diert, dann wird die Zeichenkette abc zu „10010“. Diese Folge wird allerdings auch von der Zeichenkette „aca“ erzeugt. Es ist dadurch nicht mehr eindeutig erkennbar, für welche Zeichenfolge die Bitfolge „10010“ steht. Aus diesem Grunde muss die angestrebte Codierung ein sogenannter Präfix-Code sein. Präfix-Codes sind erstrebenswert, weil sie die Decodierung deutlich vereinfachen. Da kein Codewort Präfix eines anderen ist, ist das Codewort, mit dem ein codiertes Bild beginnt, eindeutig. Dadurch lässt sich das Anfangscodewort einfach identifizieren und in das ursprüngliche Zeichen zurückübersetzen. Anschließend kann der Rest dekodiert werden.

Für den Dekodierungsprozess wird eine geeignete Darstellung des Präfix-Codes gesucht, so dass das Anfangscodewort einfach dargestellt werden kann. Dazu bietet sich ein Graph an, genauer gesagt ein binärer Baum. In dem binären Baum stehen die Blätter für die zu kodierenden Zeichen, während der Pfad von der Wurzel zum Blatt die Bitfolge, d.h. den Code, festlegt.

Huffman-Baum

Die Huffman-Codierung baut einen binären Baum, den Huffman-Baum, auf. Mit Hilfe dieses Baumes werden die Codewörter für die einzelnen Symbole erzeugt. Außerdem fungiert der Baum als visuelle Repräsentation der Symbole, ihrer Wahrscheinlichkeiten und ihrer Codes. Die Blätter des Baumes stellen stets die zu codierenden Symbole bzw. Zeichen dar. Um an ein Codewort zu gelangen, muss der Pfad von der Wurzel zu dem Symbol nachvollzogen werden. Der linke Pfad wird stets durch eine binäre „0“ darge-stellt, der rechte Pfad durch eine binäre „1“. Der Huffman-Baum ist kein binärer Suchbaum, da die Blätter nicht notwendigerweise in sortierten Reihenfolge auftreten, und die inneren Knoten keine Zeichenschlüssel enthalten.

Eine optimale Codierung wird stets durch einen vollständigen binären Baum dargestellt, bei dem jeder innere Knoten zwei Kinder hat. Aus der vorherigen Tabelle ergibt sich für eine Codierung fester Länge der in Abbildung 1 dargestellte Baum. Bei Codierung variabler Länger ergibt sich der Baum in Abbildung 2.

Um die Anzahl der zur Codierung benötigten Bits zu berechnen, kann zu einem gege-benen Baum T eine Formel verwendet werden. Für jedes Zeichen c aus dem Alphabet C bezeichnet man die Häufigkeit von s in der Datei mit f(c) und die Tiefe des Blattes s im Baum mit d_T (c). Die Funktion d_T (c) gibt auch die Länge des Codewortes an. Die An-zahl der für die Codierung der Datei benötigten Bits ergibt sich somit zu

was auch als Kosten des Baumes T definiert wird.

Für die Konstruktion eines optimalen Huffman-Baumes kann der Greedy-Algorithmus verwendet werden. Aus einer Menge C mit n Zeichen ist jedes Zeichen c ∈ C und tritt mit einer definierten Häufigkeit von f[c] auf. Der Algorithmus erzeugt einen der optimalen Codierung entsprechenden binären Baum T nach dem „bottom-up“ Verfahren. Beginnend mit einer Menge von |C| Blättern werden |C| - 1 „Verschmelzungsoperationen“ durchgeführt, um einen fertigen binären Huffman-Baum zu erstellen. Der Algorithmus baut auf einer Min-Prioritätswarteschlange Q auf, der die Schlüssel f verwaltet, um die Elemente zu identifizieren, die am seltensten vorkommen. Nach der Verschmelzung entsteht ein innerer Knoten, dessen Häufigkeit durch die Summe der beiden verschmolzenen Objekte gegeben ist.

Für die Tabelle soll der Huffman-Baum schrittweise erstellt werden. Dazu werden zunächst die beiden Zeichen oder Symbole entnommen, die am seltensten auftreten. Es handelt sich um das Zeichen f und e. Daraus resultiert der erste Teilbaum, der in Abbildung zu sehen ist.

Im zweiten Schritt werden erneut die beiden Elemente in der Min-Prioritätswarteschlange Q gesucht, die am seltensten auftreten. Dabei muss beachtet werden, dass zu den gesuchten Elementen auch die neu erstellten Teilbäume gehören. Im ersten Teilbaum ist das ein Element mit der Häufigkeit 14. Da aber mit dem Zeichen b und c zwei Zeichen mit einer kleineren Häufigkeit, nämlich 12 und 13 vorzufinden sind, wird zunächst ein zweiter Teilbaum erstellt, was zu dem Resultat in der nachfolgenden Abbildung führt.

Im dritten Schritt wird das Zeichen d mit dem zweiten Teilbaum verschmolzen.

Der vierte Schritt verschmilzt die beiden Teilbäume zu einem neuen Baum.

Der letzte Schritt führt abschließend zum Endergebnis und zum fertigen Huffman-Baum, wie er in der Abbildung am Anfang vom Kapitel präsentiert wurde. Insgesamt wurden sechs Zeichen in der Warteschlange bearbeitet. Das führte zu insgesamt fünf Verschmelzungsoperationen, die den endgültigen Baum mit den optimalen Präfix-Codes darstellt. Das Codewort für einen Buchstaben ist die Sequenz der Kantenmarkierungen auf dem Pfad von der Wurzel zum jeweiligen Zeichen. Abschließend wird der Pseudocode zur Generierung eines Huffman-Baums erläutert.

n ← |C|
Q ← C
for i ← 1 to n - 1
   do Allocate new node z
       left[z] ← x ← EXTRACT-MIN(Q)
       right[z] ← y ← EXTRACT-MIN(Q)
       f[z] ← f[z] + f[y]
       INSERT(Q, z)
return EXTRACT-MIN(Q)

In der Schleife wird zunächst ein Knoten erstellt. Die beiden seltensten Zeichen werden aus der Warteschlange extrahiert und zum linken und rechten Kind. Die beiden Häufig-keiten werden anschließend addiert und der Teilbaum zurück in die Warteschlange ge-schoben. Nach n - 1 Verschmelzungen bildet der eine, noch in der Warteschlange ver-bliebene Knoten die Wurzel des Codebaumes, die in Zeile 9 zurückgegeben wird.

D-Heap

Für die Realisierung des vorgestellten Huffman-Algorithmus wird eine Min-Prioritätswarteschlange benötigt. In C++ stellt die STL mit der Klasse std::priority_queue eine entsprechende Warteschlange zur Verfügung. Die STL-Variante basiert allerdings auf einer Max-Prioritätswarteschlange, so dass für den Template-Parameter Compare eine eigene Funktion implementiert werden muss. Dieser Schritt geht allerdings zu Lasten der Laufzeit, so dass es sich an dieser Stelle anbietet einen binären Min-Heap eigenständig zu implementieren.

Ein d-närer Heap ist eine Datenstruktur, die als vollständiger binärer Baum angesehen werden kann. Der Baum ist auf allen Ebenen vollständig gefüllt, außer möglicherweise auf der niedrigsten, die von links her bis zu einem bestimmten Punkt aufgefüllt ist. Der d-näre Heap kann auf effiziente Art und Weise als ein Array A, siehe Abbildung, dargestellt werden. Die Wurzel des Baums wird an der ersten Position im Array gespeichert. Bei einer Array-Indizierung beginnend mit 1 werden die beiden Nachfolger eines Knotens an der i-ten Position an der 2i-ten und 2i+1-ten Position gespeichert, entsprechend der Kekule-Nummerierung. Analog dazu sind die Nachfolger von dem Knoten mit Index i an der 2i+1-ten und 2i+2-ten Position gespeichert, wenn die Array-Indizierung mit 0 beginnt. Mit einem Array beansprucht jede Heap-Operation eine Worst-Case-Laufzeit von O(log n). Für die Gesamtlaufzeit des Huffman-Algorithmus auf einer Menge von n Zeichen ergibt das die Komplexität O(n log n).

Der d-näre Heap hat insgesamt d Kinder und wird als Template-Klasse mit dem Namen PriorityQueue implementiert. In dem nachfolgenden Abschnitt ist die PriorityQueue als Klasse vollständig abgebildet. Die Klasse arbeitet mit Zeigern, so dass effiziente und speicherschonende Operationen möglich sind. Für Vergleiche werden die Zeiger intern dereferenziert. Sobald ein Element aus der Warteschlange entnommen wird oder ein neues Element hinzukommt, muss der Heap neu sortiert werden. Dazu stehen zwei interne Methoden zur Verfügung, die rekursiv aufgerufen werden.

template<class T>
class PriorityQueue
{
public:
    PriorityQueue(int32_t d = 2);
    ~PriorityQueue();
    void push(T* x);
    void pop();
    T* top() const;
    bool empty() const;
    uint32_t size() const;
 
private:
    int32_t m_d;                           
    std::vector<T*> m_heap;                 
    void sortHeapUp(int32_t, int32_t); 
    void sortHeapDown(int32_t, int32_t);       
    typename std::vector<T*>::size_type m_lastIter;
    static const unsigned int STEPSIZE = 256;    
};
 
template<class T>
PriorityQueue<T>::PriorityQueue(int32_t d)
    : m_d(d), m_lastIter(0), m_heap(STEPSIZE)
{
    // Mininum 2 children
    if(m_d < 2) {
        m_d = 2;
    }
}
 
template<class T>
PriorityQueue<T>::~PriorityQueue()
{
}
 
template<class T>
bool PriorityQueue<T>::empty() const
{
    return (m_lastIter <= 0);
}
 
template<class T>
void PriorityQueue<T>::pop()
{
    m_heap[0] = m_heap[--m_lastIter];
    sortHeapDown(0, m_lastIter - 1);
}
 
template<class T>
T* PriorityQueue<T>::top() const
{
    return m_heap[0];
}
 
template<class T>
void PriorityQueue<T>::push(T* x)
{
    if(m_lastIter >= m_heap.size()) {
        m_heap.resize(m_lastIter + STEPSIZE);
    }
 
    m_heap[m_lastIter++] = x;   // Add x to queue
    sortHeapUp(0, m_lastIter - 1);
}
 
template<class T>
void PriorityQueue<T>::sortHeapUp(int32_t root, int32_t bottom)
{
    int32_t parent = 0;
 
    if(bottom > root) {
        parent = (bottom - 1) / m_d;
 
        if(*m_heap[parent] > *m_heap[bottom]) {
            std::swap(m_heap[parent], m_heap[bottom]);
            sortHeapUp(root, parent);
        }
    }
}
 
template<class T>
void PriorityQueue<T>::sortHeapDown(int32_t root, int32_t bottom)
{
    int32_t minchild = 0, firstchild = 0, child = 0;
 
    firstchild = root * m_d + 1;
 
    if(firstchild <= bottom) {
        minchild = firstchild;
 
        // Loop through all childs and find the minchild
        for(int i = 2; i <= m_d; ++i) {
            child = root * m_d + i;
            if(child <= bottom) {
                if(*m_heap[child] < *m_heap[minchild]) {
                    minchild = child;
                }
            }
        }
 
        if(*m_heap[root] > *m_heap[minchild]) {
            std::swap(m_heap[root], m_heap[minchild]);
            sortHeapDown(minchild, bottom);
        }
    } 
}
 
template<class T>
uint32_t PriorityQueue<T>::size() const
{
    return m_lastIter;
}

Die Klassen „Deflater“ und „Inflater“

Der Huffman-Algorithmus wird in der Klasse Huffman realisiert. Die Klasse Huffman nutzt zur Bildung eines Huffman-Baumes, eine eigene Template-Klasse mit dem Namen HuffmanTree. Diese Klasse wird mit dem Datentypen der vorkommen-den Zeichen instanziiert. Die IO-Klassen ByteArrayOutputStream und Byte-ArrayInputStream werden genutzt um direkt die Streams zu beschreiben oder zu lesen. Huffman stellt die zwei statischen Methoden encode() und decode() zur Verfügung. Diese Methoden komprimieren und dekomprimieren ein übergebenes ByteArray.

Der in Listing 5.2 vorgestellte Pseudocode wird mit einer auf einem d-nären Heap basierenden PriorityQueue in C++ realisiert. In dem Listing wird zunächst die Warteschlange mit einem Huffman-Baum parametrisiert. Anschließend wird die Frequenztabelle geschrieben, die die Häufigkeiten der auftretenden Symbole enthält. Für jedes Symbol wird dann ein Teilbaum neu allokiert und über eine Zeiger an den D-Heap übergeben. Nun wird entsprechend des Huffman-Algorithmus der vollständige Baum generiert. Die Schleife beendet, sobald die Warteschlange leer ist.

PriorityQueue<HuffmanTree<unsigned char>> q(3);
HuffmanTree<unsigned char>* tree;
 
for(int i = 0; i < 256; ++i) {
    // Write frequency table to stream
    ostream << freqTable[i];
 
    // Create single sub-trees, send freq-symbol pairs to 
    // the priority heap
    if(freqTable[i] > 0) {
        tree = new HuffmanTree<unsigned char>();
        tree->setFrequency(freqTable[i]);
        tree->setSymbol(static_cast<unsigned char>(i));
        q.push(tree);
    }
}
 
// Create the main Huffman tree from the sub-trees
HuffmanTree<unsigned char> *tree2, *tree3;
 
// Loop until all sub-trees are combined into one single tree
do {
    tree = q.top();
    q.pop();
 
    if( !q.empty()) {
        // Extract the two lowest frequency Huffman trees, combine
        // them into one tree and put the tree back into the priority queue
        tree2 = q.top();
        q.pop();
        tree3 = new HuffmanTree<unsigned char>();
        tree3->setFrequency(tree->frequency() + tree2->frequency());
        tree3->setLeftChild(tree->root());
        tree3->setRightChild(tree2->root());
        q.push(tree3);
    }
} while( !q.empty());

Der Huffman-Algorithmus liefert nicht zwangsläufig bereits nach der ersten Anwendung die optimale Kompression. In der Regel muss encode() deshalb mehrmals aufgerufen werden. Da in C++ nur byteweise geschrieben und gelesen werden kann, verfügt die Klasse Huffman über zwei interne Hilfsfunktionen, die es ermöglichen bitweise zu lesen und zu schreiben.

Die endgültige Kompression wird von den Klassen Inflater und Deflater vorgenommen. Beide Klassen abstrahieren den Kompressionsalgorithmus, so dass dieser bei Bedarf auch durch neue Algorithmen ersetzt werden kann. Die Datenkompression ist im Namensraum CodePlanet.Articles.Zip eingebettet und kann in der Anwendung über die Methoden inflate() und deflate() der jeweiligen Klassen genutzt werden.

Der nachfolgende Codeausschnitt zeigt die Verwendung der Klasse Deflator mit der Daten komprimiert werden können. Der Konstruktor kann verschiedene Strategien übernehmen, unter anderem für eine schnelle oder bestmögliche Kompression.

ByteArray input, output;
 
// Fill input array with data...
 
Deflater def(Deflater::BEST_COMPRESSION);
def.setInput(input);
def.finish();
unsigned int compressedDataLength = def.deflate(compressedOutput);

Die Klasse Deflater schreibt neben den komprimierten Daten einen kleinen Kopfbereich (engl. Header) in das ByteArray. Der Kopfbereich dient dem Dekodierer bzw. dem Inflater dazu, die Anzahl der Komprimierungsrunden und eventuell gesetzte Modi zu erkennen.

Schluss

In diesem Artikel wurde mit dem Huffman-Verfahren eine sehr wirkungsvolle Art der Datenkompression vorgestellt. Der Code stellt keinen Anspruch an eine größtmögliche Effizienz und steht auch nicht in Konkurrenz zu modernen Datenkompressionsprogrammen, wie WinRAR oder 7-Zip. Vielmehr kann er als theoretisches Beispiel oder als Grundlage für die Entwicklung eigener Programme zur Datenkompression betrachtet werden. Die fertige Anwendung kann im Forum heruntergeladen werden.