Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


22. Datenkomprimierung



Erzeugung des Huffman-Codes

Der erste Schritt bei der Erzeugung des Huffman-Codes besteht darin, durch Zählen die Häufigkeit jedes Zeichens innerhalb der zu kodierenden Zeichenfolge zu ermitteln. Das folgende Programm ermittelt die Buchstabenhäufigkeiten eines Zeichenfeldes a[1..M] und trägt diese in ein Feld count[0..26] ein. (Die Funktion index aus Kapitel 19 dient hier dazu, daß der Häufigkeitswert für den i-ten Buchstaben des Alphabets in dem Eintrag count[i] eingetragen wird, wobei wie üblich der Index 0 für das Leerzeichen verwendet wird.)

    for i:=0 to 26 do count[i]:=0;
    for i:=1 to M do
      count[index(a[i])]:=count[index(a[i])]+1;

Nehmen wir zum Beispiel an, daß wir die Zeichenfolge »A SIMPLE STRING TO BE ENCODED USING A MINIMAL NUMBER OF BITS« kodieren möchten. Abbildung 22.3 zeigt die erzeugte Häufigkeitstabelle: Es sind elf Leerzeichen, drei A, drei B usw. vorhanden.

Abbildung 22.3
Abbildung 22.3 Häufigkeiten für A SIMPLE STRING TO BE ENCODED ...

Der nächste Schritt ist der Aufbau des Kodierungs-Tries entsprechend den Häufigkeiten. Während der Erzeugung des Trie betrachten wir ihn als einen binären Baum mit Häufigkeiten, die in den Knoten gespeichert sind; nach seiner Erzeugung betrachten wir ihn dann als einen Trie für die Kodierung in der oben beschriebenen Weise. Zunächst wird für jede von null verschiedene Häufigkeit ein Knoten des Baumes erzeugt, wie es in der ersten Zeile links von Abbildung 22.4 dargestellt ist (die Reihenfolge, in der die Knoten erscheinen, wird durch die Dynamik des im folgenden beschriebenen Algorithmus bestimmt, ist jedoch für die folgenden Erläuterungen nicht besonders wesentlich). Danach werden die beiden Knoten mit den kleinsten Häufigkeiten ausgewählt, und es wird ein neuer Knoten erzeugt, der diese beiden Knoten als Nachfolger hat und dessen Häufigkeit einen Wert hat, der gleich der Summe der Werte für seine Nachfolger ist. Dies ist in der ersten Zeile von Abbildung 22.4 rechts dargestellt. (Falls mehr als zwei Knoten mit der kleinsten Häufigkeit vorhanden sind, ist es gleichgültig, welche benutzt werden.) Danach werden die beiden Knoten mit der kleinsten Häufigkeit in diesem Wald ermittelt, und ein neuer Knoten wird auf die gleiche Weise erzeugt, wie es in der zweiten Zeile von Abbildung 22.4 links dargestellt ist. Indem wir in dieser Weise fortfahren, stellen wir immer größere Unterbäume her und verringern gleichzeitig bei jedem Schritt die Anzahl der Bäume im Wald um eins (wir entfernen zwei und fügen einen hinzu). Am Schluß sind alle Knoten miteinander zu einem einzigen Baum verbunden.

Abbildung 22.4
Abbildung 22.4 Erzeugung eines Huffmann-Baumes.

Beachten Sie, daß sich am Ende Knoten mit geringen Häufigkeiten weit unten im Baum befinden, Knoten mit großen Häufigkeiten in der Nähe der Wurzel des Baumes. Die Zahlen, mit denen die äußeren (quadratischen) Knoten in diesem Baum gekennzeichnet sind, sind Häufigkeitszähler, während die Zahl, mit der jeder innere (runde) Knoten gekennzeichnet ist, die Summe der Kennzeichnungen seiner beiden Nachfolger darstellt.

Nunmehr kann der Huffman-Code abgeleitet werden, indem die Häufigkeiten an den unteren Knoten einfach durch die zugehörigen Buchstaben ersetzt werden und der Baum dann als ein Trie für die Kodierung angesehen wird, wobei, genau wie oben, »links« einem Bit 0 und »rechts« einem Bit 1 im Code entspricht. Den Trie für unser Beispiel zeigt Abbildung 22.5. Der Code für N ist 000, der Code für I ist 001, der Code für C ist 110100 usw. Die kleine Zahl oberhalb jedes Knotens in diesem Baum ist der Index für das Feld count, der angibt, wo die Häufigkeit gespeichert ist. Diese Angabe benötigen wir, um uns bei der Untersuchung des Programms, das den untenstehenden Baum erzeugt, darauf beziehen zu können. Folglich ist für unser Beispiel count[33] gleich 11, der Summe der Häufigkeitszähler für N und I (siehe auch Abbildung 22.4) usw.

Abbildung 22.5
Abbildung 22.5 Trie für die Huffmann-Kodierung von A SIMPLE STRING TO BE ENCODED ...

Es ist klar, daß sich Buchstaben mit großen Häufigkeiten näher bei der Wurzel des Baumes befinden und mit weniger Bits verschlüsselt werden, so daß dies ein guter Code ist; doch warum ist es der beste Code?

Eigenschaft 22.1 Die Länge der kodierten Zeichenfolge ist gleich der gewichteten äußeren Pfadlänge des Huffman-Baumes.

Die »gewichtete äußere Pfadlänge« eines Baumes ist gleich der über alle äußeren Knoten gebildeten Summe der Produkte des »Gewichts« (zugehöriger Häufigkeitszähler) mit der Entfernung von der Wurzel. Dies ist offensichtlich eine Möglichkeit, die Länge der kodierten Zeichenfolge zu berechnen; sie ist äquivalent zu der über alle Buchstaben gebildeten Summe der Produkte der Häufigkeit des Auftretens eines Buchstaben mit der Anzahl der Bits bei jedem Auftreten. w.z.b.w.

Eigenschaft 22.2 Kein Baum mit den gleichen Häufigkeiten bei den äußeren Knoten hat eine kleinere gewichtete äußere Pfadlänge als der Huffman-Baum.

Mit Hilfe des gleichen Prozesses kann ein beliebiger Baum rekonstruiert werden, den wir benutzt haben, um den Huffman-Baum zu erzeugen, doch ohne bei jedem Schritt unbedingt die zwei Knoten mit dem kleinsten Gewicht auszuwählen. Mittels Induktion läßt sich beweisen, daß keine Strategie zu einem besseren Ergebnis führen kann, als die, bei der zuerst die beiden kleinsten Gewichte ausgewählt werden. w.z.b.w.

Die obige Beschreibung liefert eine allgemeine Vorstellung davon, wie der Huffman-Code anhand der algorithmischen Operationen, die wir untersucht haben, zu berechnen ist. Wie gewöhnlich ist der Schritt von einer solchen Beschreibung zu einer wirklichen Implementation sehr instruktiv, so daß wir nunmehr die Einzelheiten der Implementation betrachten wollen.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]