Shannon-Fano-Kodierung

Die Shannon-Fano-Kodierung und Huffman-Kodierung sind eine Art der Entropiekodierung.

Dieser Artikel beschreibt, 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 Entropiekodierer 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?

PraefixCodeBaum.png Die Grundidee ist, 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 Kanten 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, zu sagen, dass linke Teilbäume mit einer 0 und rechte mit einer 1 kodiert werden. Daraus folgen für den Beispielbaum folgende Bitfolgen:

A	B	C	D	E
00	01	100	101	11

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

A	B	C	D	E
10	11	000	001	01
11	10	010	011	00
11	10	001	000	01

Will man nun eine Zeichenfolge kodieren, so werden die den entsprechenden Zeichen zugewiesenen Bitfolgen hintereinander ausgegeben. Die Bitfolge „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 bei 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 usw.

Das 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 zwei unterschiedliche Algorithmen zur Konstruktion dieser Bäume.

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. Die dabei entstandene Partitionierung ist nicht unbedingt die beste, die mit den gegebenen Häufigkeiten zu erreichen ist. Die beste Partitionierung ist auch gar nicht gesucht, da diese nicht zwangsweise zu einem besseren Ergebnis führt. Der Huffman Baum, der weiter unten mit den gleichen Häufigkeiten erzeugt wird, hat sogar eine schlechtere Partitionierung. Worauf es ankommt ist, dass die mittlere Abweichung von der Entropie der Zeichen möglichst klein ist.
Befindet sich mehr als ein Zeichen in einer der entstandenen Gruppen, wende den Algorithmus rekursiv auf diese Gruppe an.

Das wichtige Element an diesem Algorithmus ist der erste Schritt. Dieser sorgt dafür, dass Zeichen mit ähnlichen Wahrscheinlichkeiten oft im selben Teilbaum enden. Das ist wichtig, da Knoten im selben Baum Bitfolgen mit ähnlichen Codelängen erhalten (der maximale Unterschied kann nur die Anzahl der Knoten in diesem Baum betragen). Sind die Wahrscheinlichkeiten nun sehr unterschiedlich kann man keine Bitfolgen mit den notwendigen Längenunterschieden erzeugen. Das führt dazu, dass seltene Zeichen zu kurze Bitfolgen und häufige Zeichen zu lange Bitfolgen erhalten.

Beispiel

ShannonCodeAlg.png

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 fünf zu kodierenden Zeichen haben folgende Häufigkeiten:

! A B C D E 15 7 6 6 5

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 bessere 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

$\frac{2\,{\rm Bit}\cdot(15+7+6) + 3\,{\rm Bit} \cdot (6+5)}{39\, \mathrm{Zeichen}} \approx 2{,}28$ 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:

A	B	C	D	E
00	01	10	110	111

Huffman-Code

Der vom Shannon-Fano-Algorithmus erzeugte 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 ist.

Beispiel

HuffmanCodeAlg.png

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 weiteres 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

$\frac{1Bit*15 + 3Bit*(7+6+6+5)}{39} \approx 2,23$ 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:

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

$\sigma_i \in \Sigma, 0 sind die einzelnen Zeichen des Alphabets. Jedes Zeichen hat eine Wahrscheinlichkeit von p(\sigma) .$

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

$B(T) = \sum_{\sigma \in \Sigma} p(\sigma) l(\sigma)$ 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 zwei Kind-Knoten.

Beweis: Angenommen, es gibt einen Baum $T$ , in dem ein innerer Knoten nur ein Kind hat. Dann lässt sich ein Baum $T'$ konstruieren, indem man diesen Knoten entfernt und stattdessen den Kindknoten an die Stelle des Knoten hängt.

Für diesen neuen Baum gilt: $B(T') = B(T) - \sum_{\sigma \in A} p(\sigma)$ , wobei $A$ alle Zeichen enthält, die in dem verschobenen Teilbaum liegen.

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

Lemma 2: Wenn $\sigma_1$ und $\sigma_2$ die beiden Buchstaben mit den kleinsten Wahrscheinlichkeiten sind, so existiert ein Huffman-Baum, in dem diese beiden Zeichen Kinder desselben Vaters sind.

Beweis: Angenommen es gibt einen Baum $T$ , in dem die beiden Zeichen nicht Nachbarn mit dem gleichen Vater sind. Das Zeichen in der größeren Tiefe im Baum ( $\sigma_1$ ) hat einen Nachbarbaum $T_n$ .

$\sigma_2$ kann nicht in diesem Baum liegen, da es dann entweder der Nachbar von $\sigma_1$ 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 $\sigma_2$ , da der Baum mindestens ein Zeichen enthält und alle Zeichen eine Wahrscheinlichkeit größer oder gleich der von $\sigma_2$ sind.

Tauscht man nun in $T$ den Baum $T_n$ mit dem Zeichen $\sigma_2$ , so erhält man einen Baum $T'$ für den gilt:

$B(T') - B(T) = (l(\sigma_1) - l(\sigma_2))\left(p(\sigma_2) - \sum_{\sigma \in T_n} p(\sigma) \right)$

Der neue Baum hat also eine 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 $\sigma_1$ und $\sigma_2$ Nachbarn. Aus diesem Baum wird ein Baum $T'$ konstruiert, in dem die beiden Zeichen $\sigma_1$ und $\sigma_2$ entfernt werden. Der Vaterknoten wird zu einem Blattknoten, der ein neues Zeichen $\omega$ mit der Wahrscheinlichkeit $p(\omega) = p(\sigma_1) + p(\sigma_2)$ darstellt.

Dieser neue Baum ist ein Huffman-Baum für das modifizierte Alphabet $\Sigma'$ aus dem $\sigma_1$ und $\sigma_2$ entfernt und $\omega$ eingefügt wurde.

Beweis: In Baum $T'$ kann man durch Ersetzen des Knotens für $\omega$ einen Kodebaum für das ursprüngliche Problem erhalten, wobei gilt: $B(T) = B(T') + p(\sigma_1) + p(\sigma_2)$ . 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, dann liefert er auch einen 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: ^*)

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“ liefert einige Ergebnisse)

Daneben gibt es auch noch andere Ansätze, 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 anpassen (siehe splay-trees).

Übertragung des Baumes

Muss so ein Kodierungsbaum in der kodierten Datei mit an den Decoder übergeben werden, wie es bei statistischen 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 demjenigen 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 hexadezimalen ASCII Code yy). Diese Zeichenkette wird folgendermaßen 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 3, diese folgen.

Dieses Verfahren wird z. B. von JPEG bei der optimierten Ausgabe von Bildern benutzt. Hier wird anstatt einer 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.

Verbesserungsmöglichkeiten

Die vorgestellten Algorithmen verwenden immer eine ganzzahlige Anzahl von Bits, um ein Zeichen darzustellen. Das führt zwangsweise zu einer nicht optimalen Kodierung (im Sinne der Entropie), außer für den sehr seltenen Fall, dass die Wahrscheinlichkeiten aller Zeichen $\frac{1}{2^n}$ ist.

Die verwendeten Verfahren weichen unter folgenden Bedingungen besonders vom Optimum ab:

Die Wahrscheinlichkeit eines Zeichens ist größer als 0,5. Da die kürzeste mögliche Bitfolge 1 Bit lang ist, ist diese zu lang, was sich bei einem sehr häufigen Zeichen natürlich besonders auswirkt.
Die Wahrscheinlichkeit eines Zeichens ist sehr klein. So klein, dass die von der Entropie vorgeschriebene Bitzahl größer als die Anzahl der Zeichen im Alphabet ist. Da die maximale Bitlänge für ein Zeichen im Baum nicht länger als die Anzahl der Zeichen sein kann, muss diesen Zeichen eine zu kurze Bitfolge zugewiesen werden.
Außerdem gehen bei jedem Zeichen einige Bruchteile von Bits verloren, wenn die Wahrscheinlichkeit des Zeichens nicht genau $\frac{1}{2^n}$ ist, da diese dann mit einer nicht ganzen Anzahl von Bits kodiert werden müssten.

Diese Probleme können mit einer „Umstrukturierung“ des Alphabets vermindert werden.

Man kann die Wahrscheinlichkeit von Zeichen senken, indem man neue Zeichen in das Alphabet einfügt, die für mehrere dieser häufigen Zeichen stehen oder für die Verknüpfung des häufigen Zeichens mit einem weiteren.
Extrem seltenen Zeichen kann man nur gerecht werden, indem man das Alphabet mit neuen Zeichen, die für nützliche Zeichengruppen stehen, vergrößert, bis die Größe des Alphabets ausreicht, um Bäume mit der notwendigen Tiefe zu erstellen. Diese neuen Zeichen sollten Wahrscheinlichkeiten haben, die zwischen dem niedrigen Wert und den Werten der anderen Zeichen liegen.
Um den Verschnitt zu senken, der zwangsläufig auftritt durch die Tatsache, dass ein Zeichen immer mit einer ganzzahligen Bitlänge gespeichert wird, kann man auch neue Zeichen einfügen, die für Zeichenketten stehen. Im einfachsten Fall erstellt man ein neues Alphabet, in dem jedes Zeichen für genau 2 Zeichen des Originalalphabets steht. „MISSISSIPPI!“ wird also als MI SS IS SI PP I! behandelt.

Oder man vermeidet diese Probleme und verwendet Arithmetisches Kodieren.

Weblinks

Kompressionsalgorithmus

Gourt Home::Gourt :: Shannon-Fano-Kodierung

Grundidee

Shannon-Fano

Beispiel

Huffman-Code

Beispiel

Beweis der Optimalität des Huffman-Baumes

Implementationsdetails

Dynamische Huffman-Bäume

Übertragung des Baumes

Verbesserungsmöglichkeiten

Weblinks