Die Shannon-Fano-Kodierung ist eine Entropiekodierung. Dabei kodiert man Zeichen entsprechend ihrer Auftrittshäufigkeit so, dass sie eine möglichst kleine mittlere Wortlänge besitzen. Durch die Entropie – der mittlere Informationsgehalt je Symbol – ist eine untere Schranke gegeben (Quellencodierungssatz).

Grundidee

Von der Entropiekodierung 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 beliebige 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 präfixfrei 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.

Die Grundidee ist, einen vollen 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 der Pfad von der Wurzel zum Blatt die Bitfolge bestimmt.

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:

Genauso gut sind aber auch viele andere Kodierungen möglich. Hier nur noch ein paar Beispiele:

Will man nun eine Zeichenfolge kodieren, so werden die den entsprechenden Zeichen zugewiesenen Bitfolgen hintereinander ausgegeben. Die Zeichenfolge „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 zu lösende Problem ist es, einen solchen Baum zu erstellen, 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. Im Gegensatz zur Huffman-Kodierung ist die Shannon-Fano-Kodierung nicht immer optimal.

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 zwei 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 Shannon-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. 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.

Pseudocode

Die folgenden Beispiele in Pseudocode zeigen Funktionen für die Generierung der Shannon-Fano-Kodierung.

/**
 * nodes // Array für das Codebuch
 * sum1 // Summe der Wahrscheinlichkeiten von leftIndex bis zum rechten Ende von nodes
 * sum2 // Summe der Wahrscheinlichkeiten von rightIndex bis zum linken Ende von nodes
 * difference1 //
 * difference2 //
 */
 function createDictionary(leftIndex, rightIndex, nodes)
 {
   sum1 := 0, sum2 := 0, difference1 := 0, difference2 := 0
   if (leftIndex + 1 = rightIndex or leftIndex = rightIndex or leftIndex > rightIndex)
   {
       if (leftIndex = rightIndex or leftIndex > rightIndex)
       {
           return
       }
       nodes[rightIndex].codeword[++(nodes[rightIndex].length)] = 0
       nodes[leftIndex].codeword[++(nodes[leftIndex].length)] = 1
       return
   }
   else
   {
       for i := leftIndex to rightIndex - 1 do
       {
           sum1 := sum1 + nodes[i].probability
       }
       sum2 := sum2 + nodes[rightIndex].probability
       difference1 := sum1 - sum2
       if (difference1 < 0)
       {
           difference1 := -difference1
       }
       j := 2
       while (j <> rightIndex - leftIndex + 1)
       {
           k := rightIndex - j
           sum1 = sum2 = 0
           for i := leftIndex to k - 1 do
           {
               sum1 := sum1 + nodes[i].probability
           }
           for i := rightIndex downto k + 1 do
           {
               sum2 := sum2 + nodes[i].probability
           }
           difference2 := sum1 - sum2
           if (difference2 < 0)
           {
               difference2 := difference2 * -1
           }
           if (difference2 >= difference1)
           {
               break
           }
           difference1 := difference2
           j = j + 1
       }
       k++;
       for i := leftIndex to k do
       {
           nodes[i].codeword[++(nodes[i].length)] = 1
       }
       for i := k + 1 to rightIndex do
       {
           nodes[i].codeword[++(nodes[i].length)] = 0
       }
       shannonFanoCoding(leftIndex, k, nodes) // Rekusiver Aufruf für den linken Teilbaum
       shannonFanoCoding(k + 1, rightIndex, nodes) // Rekusiver Aufruf für den rechten Teilbaum
   }
 }

Siehe auch

• Arithmetisches Kodieren

Weblinks

• LNTwww: Huffman- und Shannon-Fano-Codierung
• Georgia Institute of Technology: Shannon-Fano-Elias Code, Arithmetic Code

Einzelnachweise

1. ↑ Tatsächlich müssen sie nur eindeutig sein, aber für jeden eindeutigen Code existiert auch ein präfixfreier Code mit identischer Codewortlänge