Die Huffman-Kodierung

Hintergrund

Huffman-Codes stellen ein vergleichsweise einfaches Mittel zur Datenkompression dar. Ähnlich wie beim Morse-Code liegt eine statistische Analyse der zu kodierenden Zeichen zu Grunde, die dazu dient, häufig vorkommenden Zeichen kürzere Codes zuzuweisen als solchen Zeichen, die seltener vorkommen. Das führt zu einem optimalen Code für genau die Daten, die analysiert wurden. Der Morse-Code hingegen beruht auf einer einmalig erfolgten Analyse (angeblich durch Auszählen der Lettern im Setzkasten der örtlichen Zeitung in Morristown, New Jersey) und ist für typische englische Texte optimiert.

Anders als beim Morse-Code wird beim Huffman-Code kein Trennzeichen zwischen den Symbolen benötigt. Es handelt sich um einen präfixfreien Code, das heißt kein Symbol ist Bestandteil eines längeren Symbols (wie z.B. "Bau" ein Präfix von "Baum" ist). Das ergibt sich aus der Art, auf die ein konkreter Huffman-Code erzeugt wird.

Eine fundamentale Einschränkung des Verfahrens ist, dass Sender und Empfänger über das gleiche Code-Wörterbuch verfügen müssen, d.h. dieses auf irgendeine Art und Weise mit übertragen werden muss (anders als es etwa bei LZW der Fall ist).

Huffman-Bäume

Die Erzeugung eines konkreten Huffman-Codes besteht aus folgenden Schritten:

1. Statistische Analyse: bestimmen wie häufig jedes Zeichen vorkommt
2. Konstruktion eines Huffman-Baums
3. Zuweisung der Codes (= Erstellung des Code-Wörterbuchs)

In Huffman-Bäumen stellen die Blätter Zeichen aus dem Eingabealphabet dar, während innere Knoten lediglich der Verbindung dienen. Wie viele Kinder jeder innere Knoten haben darf hängt davon ab welche Art von Codes man erzeugen möchte -- für die Erzeugung von Binärcodes muss jeder innere Knoten genau zwei Kinder besitzen.

Die Codes der Blätter ergeben sich aus ihrer Position innerhalb des Baums und stellen gewissermaßen Wegbeschreibungen aus Sicht der Wurzel dar. Angenommen die linken Kinder werden durch 0 und die rechten Kind durch 1 adressiert, so bezeichnet der Code 1011 jenes Zeichen, das von der Wurzel aus durch den Pfad rechts-links-rechts-rechts erreicht wird.

Dadurch, dass für die Repräsentation von Zeichen nur Blätter zulässig sind, ergibt sich die Präfixfreiheit der Codes: solange die Folge unvollständig ist, endet die Wegbeschreibung auf einem inneren Knoten und keinem Blatt.

Damit der Code auch optimal ist, müssen die Zeichen (Blätter) so verteilt werden, dass seltener auftretende Zeichen tiefer hängen als solche Zeichen, die oft vorkommen. Dadurch sind die Wege (und damit die Codes) zu den selteneren Zeichen länger als für die häufiger auftretenden Zeichen. Der Algorithmus zur Erstellung solcher Bäme lautet:

1. Erstelle für jedes Zeichen einen Knoten, weise ihm als Wertigkeit die Auftrittshäufigkeit des Zeichens zu
2. Nimm die beiden Knoten (Teilbäume) mit der geringsten Wertigkeit, kombiniere sie zu einem neuen Baum und weise ihm die Summe der Wertigkeiten seiner Kinder zu
3. Wiederhole Schritt 2 bis nur noch ein Baum übrig ist

Durch diesen Algorithmus werden die seltenen Zeichen zuerst verbaut und hängen im fertigen Baum stets tiefer als die häufigen Zeichen. Die Summenbildung berücksichtigt die Tatsache, dass große Teilbäume viele verschiedene, für sich genommen seltene, Zeichen beinhalten und somit die Wahrscheinlichkeit größer ist, dass irgendeins dieser Zeichen vorkommt. Wenn man ein paar Bäme von Hand aufzeichnet und damit experimentiert leuchtet das schnell ein.

Ein Beispiel

Als Beispiel soll ein Huffman-Baum für den Satz "Das Pferd frisst keinen Gurkensalat" erstellt werden. Um das Beispiel kürzer zu halten soll auf die Unterscheidung von Groß- und Kleinbuchstaben verzichtet werden. Das Eingabealphabet hat also 15 Zeichen die sich wie folgt verteilen (in Reihenfolge des ersten Auftretens):

Die folgende Animation soll den Aufbau eines entsprechenden Huffman-Baums veranschaulichen.

In diesem Beispiel gibt es eine Reihe von Entscheidungen die scheinbar willkürlich getroffen werden. Dazu zählt die initiale Anordnung der Zeichen gleicher Wertigkeit und darauf folgend das Einsortieren neu gebildeter Teilbäume. Da lediglich die Wertigkeit entscheidend ist, sind alle diese Entscheidungen äquivalent. Sie führen jedoch zu unterschiedlichen Bäumen und somit auch zu unterschiedlichen Codes. Das ist problematisch, wenn sowohl Sender als auch Empfänger einer kodierten Nachricht die Bäume bzw. Codes aus der Häufigkeitsverteilung der Zeichen ableiten, aber unterschiedliche Entscheidungen treffen. Daher muss entweder sichergestellt werden, dass der Algorithmus ähnlich implementiert ist, oder der fertige Baum bzw. das daraus resultierende Code-Wörterbuch mit übertragen wird.

Die Binärcodes aus obigem Beispiel lauten:

Die Länge der Codes in Abhängigkeit zur Auftrittshäufigkeit ist gut erkennbar. Aber macht dieser Code die Nachricht tatsächlich kürzer?

Kodierter Text:
00110000 11011110 11001101 00000100 11111011 00001011 11101100 10011101 01100011 10010100 00101111 01111010 00001010 11000010 11000001 01010000 0100

Das sind 132 Bits (16,5 Bytes) für 35 Zeichen. Aber es wäre unfair für die normale Übertragung 1 Byte pro Zeichen anzusetzen, weil das Beispiel von Vornherein auf Kleinbuchstaben und Leerzeichen, also 27 Zeichen, eingeschränkt war. Mit einem "normalen" Binärcode wären hier 5 Bits pro Zeichen ausreichend. Aber auch damit wäre man bei 35 * 5 = 175 Bit (ca. 22 Bytes), d.h. der Huffman-Code hätte rund 25% eingespart.

Das Einsparpotenzial wächst mit den Unterschieden in der Häufigkeitsverteilung und findet sein Maximum, wenn ganz viele Zeichen überhaupt nicht auftreten, wohingegen normale Codes quasi jederzeit auf alle möglichen Zeichen vorbereitet sein müssen.

Echte Daten

Ich habe ein Beispiel-Programm erstellt, das anhand einer Eingabedatei einen Huffman-Baum plus Code-Wörterbuch erstellt und berechnet, wie viel Platz die kodierten Daten benötigen würde. Die folgende Tabelle zeigt die Ergebnisse für eine Reihe gängiger Dateitypen.

Man sieht recht schön, dass sich bereits komprimierte Dateien (PDF, JPEG, MP3, ZIP-Archive) erheblich schlechter komprimieren lassen als Rohdaten (ASCII, Bitmap, WAVE). Das ergibt durchaus Sinn, denn andere Kompressionsverfahren beruhen ebenfalls darauf, Redundanz zu vermeiden und somit Dateien zu erzeugen, die den Wertebereich der 8-Bit-Bytes optimal ausnutzen.

Downloads