Die Huffman-Codierung

Bei der Huffman-Codierung handelt es sich um eine einfache Datenkompression. Dabei macht man sich zu Nutze, daß bei den meisten Daten nicht alle Zeichen gleich häufig enthalten sind. Ähnlich wie beim Morse-Code die häufig vorkommenden Buchstaben mit kürzeren Codes dargestellt werden, als Zeichen die weniger oft vorkommen, wird beim Huffman-Code auch ein Code passend zu einer bestimmten Zusammensetzung der Eingangsdaten bestimmt.

Ein für bestimmte Daten ermittelter Huffman-Code führt immer zu einer optimalen Kompression dieser Daten mittels Huffman-Codierung. Anders ausgedrückt: ein durch statistische Analyse ermittelter Code ist für genau die untersuchten Daten optimal, es gibt keinen besseren. Jedoch ist natürlich nicht ausgeschlossen, daß ein anderes Kompressions-Verfahren bessere Ergebnisse liefert. Der LZW-Algorithmus beispielsweise macht sich zu Nutze, daß sich bestimmte Zeichenfolgen wiederholen, während beim Huffman-Algorithmus nur einzelne Zeichen betrachtet werden können. (Das ist nicht ganz wahr, man könnte Blöcke zu mehreren Zeichen bilden, was allerdings nur am Begriff "Zeichen" herumdreht, nicht aber an der eigentlichen Tatsache, daß einzelne Zeichen codiert werden.)

Beim Huffman-Code handelt es sich um einen präfixfreien Binärcode. Das bedeutet, daß keine Bitfolge der Beginn einer längeren Bitfolge sein kann. Damit erspart man sich die Notwendigkeit für ein Trennzeichen, wie beim Morse-Code z.B. die Pausen zwischen den einzelnen Buchstaben. Diese Präfixfreiheit wird dadurch erreicht, daß ein Binärbaum aufgebaut wird, bei dem ausschließlich die Blätter eine Bezeichnung erhalten. Man kann nun definieren, daß ein linker Zweig mit einer 0 und ein rechter Zweig mit einer 1 "adressiert" wird, und die damit erzeugten Codes eine Art Wegbeschreibung darstellen. Liest man nun aus dem Bitstrom einzelne Bits heraus, und folgt dieser Beschreibung, stößt man irgendwann auf ein Blatt, und das dort zugeordnete Zeichen ist das durch den Huffman-Code beschriebene. Das nächste Bit ist der Beginn der nächsten Wegbeschreibung, d.h. es wird wieder an der Wurzel angesetzt.

Ein Beispiel

Wir wollen den folgenden Text codieren: "Das Pferd frisst keinen Gurkensalat" (da ich ursprünglich aus Friedrichsdorf stamme bin ich wohl ein wenig vorgeschädigt). Zunächst muß die Häufigkeit der Eingabezeichen bestimmt werden (im Folgenden wird das Leerzeichen der besseren Lesbarkeit wegen als "_" dargestellt). Um die gleichen Codes wie das Beispielprogramm zu erhalten wird diese Liste zusätzlich zunächst einmal nach aufsteigenden Zeichencodes sortiert. Dies hat keinen besonderen Grund, außer daß im Programm ein Array verwendet wird, bei dem das Zeichen als Index verwendet wird, und sich beim sequentiellen Auslesen des Arrays, was später beim Aufbauen des Baums passiert, automatisch diese Reihenfolge ergibt.

Als nächstes wird diese Liste nach den Häufigkeiten der Zeichen sortiert, wobei die Reihenfolge der Einträge mit gleicher Häufigkeit erhalten bleibt (wieder um mit dem Programm gleichzuziehen, für die Qualität der erzeugten Codes ist nur die Sortierung nach Häufigkeit relevant):

Jetzt kann daraus ein Baum gebaut werden. In meinem Programm gehe ich dabei so vor, daß ich aus der sortierten Liste (praktischerweise sind dort die Einträge schon als Baumknoten gespeichert) zwei Einträge herausnehme, diese als Kindknoten an einen neuen Knoten anhänge, diesem kombinierten Knoten als Häufigkeitszähler die Summe der beiden Kind-Einträge zuweise, und wieder einfüge. Damit wird die Zahl der Knoten in der Liste mit jedem Schritt um eins verringert, und die dort enthaltenen Baum-Fragmente zusehends größer. Herausgenommen wird hinten, d.h. die Knoten mit den kleinsten Häufigkeits-Zählern werden zuerst verbaut, und wandern damit an die tiefsten Stellen des Baums (um später die längsten Codes zu erhalten). Wenn nur noch ein Eintrag in der Liste vorhanden ist, ist der Aufbau des Baums abgeschlossen.

Nun sind alle mit der Häufigkeit 1 verschwunden und zwei neue Teilbäume mit jeweils zwei Elementen der Häufigkeit 1 und somit einem Gesamtwert von 2 hinzugekommen. Bitte zu beachten, daß bei meiner Implementierung der zuerst entnommene (also ganz rechte) Eintrag auf die linke Seite des neuen Baums gehängt wird, daher diese Verdrehung. Beim Einhängen in die Liste wird er an die rechteste Position die seinem Gesamtwert noch gerecht wird platziert. Im nächsten Schritt werden alle Bäume mit einem Wert von 2 miteinander verhängt.

Nun sind erstmal alle Knoten verhängt, die einen Gesamtwert kleiner oder gleich 4 erhalten. Wenn als nächstes die 3 und die 2 verknüpft werden, muß das Ergebnis erstmals zu Beginn der Liste eingefügt werden. Beim darauffolgenden Verknüpfen der beiden 3er die dann hinten an stehen werden, entsteht ein Baum mit einem Gesamtwert von 6, der wiederum ganz vorne eingeordnet wird.

Es ist recht schwierig die Zugehörigkeit der Kindknoten in textueller Form darzustellen, ich hoffe das mit den Kommas ist verständlich. Ein solcher Ausdruck zerfällt immer in einen linken und einen rechten Teil der längsten Kommakette, dessen Kindknoten die Teilausdrücke sind. Dies ist dann rekursiv weiter zu führen, bis keine Kommas mehr enthalten sind. Am Ende der Transformationen wird dies nochmal am fertigen Baum verdeutlicht. Ansonsten ist es eine große Hilfe, jede Menge Papier vollzumalen, und sich als Skizze die Binärbäume wie gewohnt aufzuzeichnen. Die Tabellen hier sollen lediglich der Kontrolle dienen.

Es ist übrigens ein extrem gutes Zeichen, daß der Gesamtwert der Anzahl der Zeichen im Eingabetext entspricht, das bedeutet nämlich, daß unterwegs nichts verloren gegangen ist. Als nächstes werden die Codes an die Blätter des Baums angeheftet. Wie bereits beschrieben wird von der Wurzel ausgehend bei jedem Schritt nach links eine 0 und bei jedem Schritt nach rechts eine 1 an den bisherigen Code angehängt, solange bis ein Blatt erreicht wird, dem dieser Code zugeordnet wird. Wenn alles richtig gemacht wird kommt sowas raus:

Jetzt steht dem Codieren nichts mehr im Wege. Zunächst sollen exemplarisch die ersten 9 Zeichen des Textes codiert werden, danach wird das Ergebnis der Codierung der ganzen Zeichenkette angegeben (wie sie auch vom Beispielprogramm erzeugt wird), als Kontrolle für diejenigen, die den Rest selbst codieren möchten, oder sich an das ebenfalls jetzt sehr einfache Decodieren wagen wollen.

Von dem letzten 'c' gehören nur die oberen beiden Bits dazu. Diese Information steht dem Programm zum Decodieren auch implizit zur Verfügung (die Zahl der enthaltenen Zeichen geht dem Bitstrom voraus). Wie man sieht konnten 35 Zeichen in knapp 17 Byte dargestellt werden, das ist ungefähr um die Hälfte kürzer als wenn es direkt in ASCII gespeichert worden wäre. Allerdings muß man dazusagen, daß hier nur wenige Zeichen verwendet wurden, und damit relativ viele Bits ungenutzt bleiben, wenn man ASCII verwendet. Die tatsächlich erzielbaren Kompressionsraten hängen im Wesentlichen davon ab, wie unterschiedlich verteilt die Häufigkeit der vorkommenden Zeichen ist. Dadurch, daß nicht alle möglichen Binärcodes verwendet werden können (es dürfen ja keine Mehrdeutigkeiten bezüglich der Präfixe entstehen), ist es durchaus möglich, daß die Huffman-codierten Daten mehr Speicher brauchen als die Eingangsdaten.

Downloads

Zurück zur Hauptseite