Shannon Fano Kodierung und Huffman Kodierung sind eine Art der Entropie Kodierung.

Dieser Artikel beschreibt nur, wie zu einem gegebenen Satz von Zeichen- Wahrscheinlichkeits-Paaren die Kodierung erstellt werden kann, wie also die Anforderung der Entropie umgesetzt werden kann.

Da zu einem Entropie Kodierer immer auch ein Modell gehört sollten die zusätzlichen Informationen aus dem Artikel zur Entropiekodierung entnommen werden.

Grundidee

Von der Entropie_Kodierung her ist bekannt, dass Zeichen mit einer unterschiedlichen Anzahl von Bits kodiert werden müssen, wenn man eine speichersparende Darstellung erhalten möchte. Es ist aber nicht möglich den 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" kodiert, dann wird die Zeichenkette ABC zu "10010". Diese Folge wird aber auch von der Zeichenkette "ACA" erzeugt. Es ist also nicht mehr eindeutig erkennbar, für welche Zeichenfolge die Bitfolge "10010" steht.

Um diese Mehrdeutigkeit zu verhindern müssen die den Zeichen zugewiesenen Bitfolgen die Eigenschaft besitzen präfixfrei zu sein, d.h. keine Bitfolge, die für ein einzelnes Zeichen steht, darf am Anfang eines anderen Zeichens stehen. Diese Eigenschaft ist im oberen Beispiel nicht erfüllt, da die Bitfolge "0", die für C steht am Anfang der B zugewiesenen Folge steht.

Wie kann nun ein präfixfreier Code erzeugt werden?

Die Grundidee ist es einen binären Baum für die Darstellung des Codes zu verwenden. In dem Baum stehen die Blätter für die zu kodierenden Zeichen, während die inneren Knoten für die zu schreibenden oder gelesenen Bits stehen.

Das Bild zeigt einen Baum, der von der gewünschten Form ist. Die inneren Knoten sind durchnummeriert um sie benennen zu können.

Um nun die Bitfolge zu ermitteln, die für eines der Zeichen stehen soll muss festgelegt werden, wie die Abzweige kodiert werden sollen. Eine Variante ist es zu sagen, dass linke Teilbäume mit einer 0 und rechte mit einer 1 kodiert werden. Daraus folgen für den Beispielbaum folgende Bitfolgen:

Genauso gut sind aber auch eine Menge von anderen Kodierungen möglich. Hier nur noch ein paar Beispiele:

Will man nun eine Zeichefolge Kodieren, so werden die den entsprechenden Zeichen zugewiesenen Bitfolgen hintereinander ausgegeben. Die Bifolge "ACDC" wird mit der ersten Kodierung zu der Bitfolge "00100101100".

Um diese Bitfolge zu dekodieren wird sie Bit für Bit abgearbeitet. Der Dekodierer muss sich dabei die aktuelle Position im Baum merken. Gestartet wird an der Wurzel, also im Knoten 1. Dann wird das erste Bit gelesen, eine 0. Das bedeutet dieser Kodierung nach links, der aktuelle Knoten wird also 2. Es folgt ein weiteres 0-Bit. Der aktuelle Knoten ist jetzt A. Es wird A ausgegeben und der aktuelle Knoten wieder auf 1 gesetzt. Das als nächstes gelesene 1-Bit führt dazu, dass der aktuelle Knoten die 3 ist, ...

Das zu nun noch zu lösende Problem ist, wie erstellt man einen solchen Baum, bei dem die durchschnittliche Anzahl der Fragen, bis ein Zeichen eindeutig ermittelt ist im Mittel möglichst klein ist, also möglichst dicht an der Entropie liegt.

Shannon-Fano-Kodierung und Huffman-Kodierung sind 2 unterschiedliche Algorithmen zur Konstruktion von diesen Bäumen.

Shannon-Fano

Der nach Claude Shannon und Robert Fano benannte Algorithmus arbeitet mit folgender Vorschrift:

• Sortiere die Zeichen nach ihrer Häufigkeit
• Teile die Zeichen entlang dieser Reihenfolge so in 2 Gruppen, dass die Summe der Häufigkeiten in den beiden Gruppen möglichst gleich ist. Die beiden Gruppen entsprechen dem linken und rechten Teilbaum des zu erstellenden Baumes
• Befindet sich mehr als ein Zeichen in einer der entstandenen Gruppen wende den Algorithmus rekursiv auf diese Gruppe an

Beispiel

Shannon-Fano-Beispiel

Das Beispiel zeigt die Konstruktion des Shannon Codes für ein kleines Alphabet. Die Gleichen Werte werden weiter unten auch für den Huffman Code verwendet, damit die Ergebnisse vergleichbar sind. Die 5 zu kodierenden Zeichen haben folgende Häufigkeiten

Sortiert sind die Werte schon, also direkt zu Schritt 2, dem Partitionieren. Am Anfang sind alle Zeichen in einer Partition (im Bild a).

Die exakte Mitte läge bei 19.5 Zeichen. 15 ist 4.5 unter dem Mittelwert, 15+7 hingegen nur 2.5 drüber - eine besser Partitionierung gibt es nicht. Das Alphabet wird also so in 2 Teile unterteilt, dass der eine Teil die Zeichen A und B und der andere Teil den Rest (C, D und E) enthält (Bild b). Beide Partitionen enthalten noch mehr als 1 Zeichen müssen also weiter zerteilt werden. Die Partition mit A und B kann nur in 2 Teile mit je einem Zeichen zerlegt werden. Die andere Gruppe hat 2 Möglichkeiten. 6+6 ist weiter von der Mitte entfernt, als 6 alleine. Also wird in die 2 Partitionen mit C und D+E unterteilt (Bild c). Schließlich wird noch D und E zerteilt. Der entstandene Entscheidungsbaum ist im Bild Abschnitt d dargestellt.

Die Bitlängen für die einzelnen Zeichen betragen also

2 Bits für A, B und C und je 3 Bits für D und E. Das ergibt eine durchschnittliche Bitzahl von

Bits pro Zeichen.

Da die Zuweisung, wie oben besprochen, nicht eindeutig ist, hier nur ein Beispiel für eine mögliche Kodierung aufgrund dieses Baumes

Huffman Code

Der vom Shannon-Fano-Algorithmus erzeugt Baum ist nicht immer optimal, deshalb wurde ein anderer Algorithmus gesucht. David A. Huffman, hat ihn 1952 gefunden. Dieser Algorithmus liefert beweisbar immer einen optimalen Baum für die gegebenen Wahrscheinlichkeiten.

Während der Shannon-Fano-Baum von der Wurzel zu den Blättern erstellt wird arbeitet der Algorithmus zur konstruktion des Huffman Baums in entgegengesetzter Richtung.

• Erstelle einen "Wald" mit Bäumen, für jedes Zeichen. Diese Bäume enthalten nur einen Knoten: das Zeichen
• suche die beiden Bäume im Wald, die für die Zeichen mit der kleinsten Wahrscheinlichkeit stehen. Entferne diese Bäume aus dem Wald. Erstelle einen neuen Baum, der die beiden entfernten Bäume als Subbaum hat. Füge diesen Baum in den Wald ein. Benutze dabei die Summe der Wahrscheinlichkeiten der Unterbäume.
• Wiederhole, bis nur noch ein Baum übrig.

Beispiel

Huffmann-Code-Beispiel

Das gleiche Beispiel wie bei Shannon-Fano Code führt zu folgenden Schritten.

Der Wald wird erstellt. Im Bild ist in Abschnitt a der Zustand zu sehen. am oberen Ende sind immer die Häufigkeiten für die Bäume angezeigt, da diese Vom algorithmus benötigt werden.

Die beiden Bäume mit den geringsten Häufigkeiten sind E und C oder D. Diese werden entfernt (im Beispiel D und E) ein neuer Baum mit einer Häufigkeit von 5+6=11 wird erstellt und in den Wald eingefügt (Bild b).

Als nächstes werden B und C zusammengefasst. Der neue Baum hat die Häufigkeit 13 (Bild c).

Nun werden die 2 bereits zusammengefassten Bäume ein weiteren mal verbunden (Bild d)

Schließlich wird A mit dem Rest zu einem Baum verbunden (Bild e). Der Algorithmus ist hiermit beendet, da nur noch ein Baum im Wald vorhanden ist.

Die Codelängen für die einzelnen Zeichen sind diesmal 1 Bit für A und 3 Bit für alle anderen Zeichen. Dies führt zu einer durchschnittlichen Bitzahl von

Bits pro Zeichen.

Im Vergleich zu 2.28 Bits pro Zeichen, wie bei Shannon Fano ist das eine Verbesserung.

Beweis der Optimalität des Huffman Baumes

Dazu zuerst ein paar Definitionen:

? ist das Alphabet, für das der Code erstellt werden soll. Es enthält | ? | = n Zeichen

sind die einzelnen Zeichen des Alphabets. Jedes Zeichen hat eine Wahrscheinlichkeit von p(?)

l(?) ist die Länge des zu verwendenden Codes, bzw. die Tiefe des Zeichens im Baum.

ist die durchschnittliche Codelänge für das gesamte Alphabet für einen bestimmten Baum T. B(T) ist die Größe, die für den Huffman Baum minimal sein soll.

Da es nur endlich viele verschiedene Binärbäume mit n Blättern gibt existiert somit auch ein Baum T, für den B(T) minimal ist.

Für den Beweis werden 2 Hilfssätze benötigt:

Lemma 1: Jeder innere Knoten hat in einem Huffman Baum 2 Kind-Knoten.

Beweis: Angenommen es gibt einen Baum T in dem ein innerer Knoten nur ein Kind hat. Dann läßt sich ein Baum B(T') konstruieren, indem man diesen Knoten entfernt und statt dessen den Kindknoten an die Stelle des Knoten hängt.

Für diesen neuen Baum gilt: , wobei A alle Zeichen enhält, die in dem verschobenen Teilbaum liegen.

Da die Wahrscheinlichkeiten größer 0 sind gilt B(T') < B(T) was im Wiedersprich zur Annahme steht.

Lemma 2: Wenn ?₁ und ?₂ die beiden Buchstaben mit den kleinsten Wahrscheinlichkeiten sind, so existiert ein Huffman-Baum in dem diese beiden Zeichen Kinder des selben Vaters sind.

Beweis: Angenommen es gibt eine Baum T in dem die beiden Zeichen nicht Nachbarn mit dem gleiche Vater sind. Das Zeichen in der größeren Tiefe im Baum (?₁) hat einen Nachbarbaum T_n.

?₂ kann nicht in diesem Baum liegen, da es dann entweder der Nachbar von ?₁ wäre oder seine Tiefe größer wäre, was wir ausgeschlossen hatten.

Die Summe der Häufigkeiten aller Zeichen in T_n ist größer oder gleich der Wahrscheinlichkeit von ?₂, da der Baum mindestens ein Zeichen enthält und alle Zeichen eine Wahrscheinlichkeit größer oder gleich der von ?₂ sind.

Tauscht man nun in T den Baum T_n mit dem Zeichen ?₂ so erhält man einen Baum T' für den gilt:

Der neue Baum hat also durchschnittliche Codelänge gleich oder kürzer der des originalen Baumes. Damit ist auch der Baum ein Huffman Baum.

Lemma 3: In einem gegebenen Huffman Baum T sind die beiden seltensten Zeichen ?₁ und ?₂ Nachbarn. Aus diesem Baum wird ein Baum T' konstruiert, in dem die beiden Zeichen ?₁ und ?₂ entfernt werden. Der Vaterknoten wird zu einem Blattknoten, der ein neues Zeichen ? mit der Wahrscheinlichkeit p(?) = p(?₁) + p(?₂) darstellt.

Dieser neue Baum ist ein Huffman Baum für das modifizierte Alphabet ?' aus dem ?₁ und ?₂ entfernt und ? eingefügt wurde.

Beweis: In Baum T' kann man durch ersetzen des Knotens für ? einen Kodebaum für das ursprüngliche Problem erhalten, wobei gilt: B(T) = B(T') + p(?₁) + p(?₂). Ist nun T' kein Huffman Baum, so existiert nun ein Baum T'', in dem B(T'') < B(T') ist. Dies kann aber nicht sein, da die Konstruktion eines Baumes für das Originalproblem aus T'' zu einem effizienteren Baum führen würde, als der Ursprungsbaum, der bereits optimal war.

Der eigentliche Beweis läuft nun über vollständige Induktion.

Induktionsanfang: Der Algorithmus liefert offensichtlich einen optimalen Baum für 2 Zeichen.

Induktionsschritt: Wird durch Lemma 3 bewiesen. Angenommen der Algorithmus liefert einen optimalen Baum für das Vorhandene Problem mit den 2 seltensten Zeichen ersetzt, dann liefert er es auch für das gegebene Problem, da er genau diese Ersetzung durchführt.

Implementationsdetails

Die Zeiteffiziente Implementation scheitert oft an den vielen Bitoperationen die notwendig sind, um Bytes aus den einzelnen Bits zu bilden, die einzelnen Bits beim dekodieren Auszuwerten und den Weg im Baum nachzuvollziehen.

Es gibt aber effiziente Algorithmen, um diese Prozesse zu beschleunigen (siehe zlib Bibliothek: [1] (http://www.gzip.org/zlib/))

Dynamische Huffman Bäume

Soll ein Kodierer programmiert werden, der mit einem dynamischen Modell arbeitet, so muss der Baum regelmäßig für das neue Modell neu erstellt, oder aktualisiert werden. Auch dafür gibt es effiziente Algorithmen, die die häufigste Veränderung, die Erhöhung der Häufigkeit eines Zeichens um 1, effizient am Huffman Baum ausführen können, ohne den gesamten Baum neu erstellen zu müssen. (Die Suche nach "dynamic Huffman" liefern einige Ergebnisse)

Daneben gibt es auch noch andere Ansätzte, die nicht mit Huffman-Bäumen arbeiten, sondern die Zeichen durch die von den AVL-Bäumen her bekannten rotations-Operationen in ihrer Höhe den aktuellen Häufigkeiten anzupassen (siehe splay-trees)

Übertragung des Baumes

Muss so ein Kodierungsbaum in der Kodierten Datei mit an den Decoder übergeben werden, wie es bei statischen Verfahren (siehe Entropiekodierung) notwendig ist, braucht man eine möglichst kompakte Repräsentation.

Dazu werden ein paar Beobachtungen ausgenutzt.

• Die genaue Lage eines Zeichens im Baum ist nicht von Bedeutung, so lange die Tiefe, also der Abstand von der Wurzel derjenigen im Huffman Baum entspricht.

• Durch Austauschen von Knoten kann man den Baum immer in eine Form bringen, bei der die Knoten von links nach rechts in ihrer Tiefe aufsteigend angeordnet sind.

• Diese Operationen verändern zwar die den Zeichen zugewiesenen Bitfolgen, nicht aber die Optimalität des Codes.

Ein auf diese Art sortierter Baum kann ausgegeben werden, indem man nur ausgibt welche Zeichen mit wie vielen Bits verschlüsselt werden. Die innere Struktur des Baumes wird dadurch vollständig beschrieben.

Im Beispielfall vom Huffman Algorithmus müsste man also ausgeben, dass es 1 Zeichen mit Länge 1, nämlich A, und 4 Zeichen mit Länge 3 gibt. Das könnte man mit der Zeichenkette "\x01A\x00\x04BCDE" erledigen (C-Syntax: \xyy steht für das Zeichen mit dem ASCII Code xx). Diese Zeichenkette wird folgendermaßten interpretiert. \x01 bedeutet, dass es ein Zeichen mit Kodelänge 1 gibt. Das Zeichen folgt: A. \x00 bedeutet, dass es kein Zeichen mit Kodelänge 2 gibt. \x04: es gibt 4 Zeichen mit Kodelänge 4, diese folgen.

Diese Verfahren wird z.B. von JPEG bei der optimierten Ausgabe von Bildern benutzt. Hier wird anstatt eine der vorgegebenen festen Kodierungen ein optimaler Code (Huffman) erzeugt und auf diese Weise dem Dekodierer mitgegeben. In den Spezifikationen von ISO steht mehr zu diesem Thema

Weblinks

• Schöne Erläuterung der Quellencodierung mit binären Bäumen (http://speedy.et.unibw-muenchen.de/Applets/labAlive2_3/ET3/labAliveApplets/coder23/coder23_info.html)