Quelltext der Seite Datenkompression: Verlustfreie Verfahren: Statistische Verfahren: Shannon-Fano Codierung

[[Datenkompression|zurück]]

5 [[Datenkompression:_Verlustfreie_Verfahren|Verlustfreie Verfahren]]
{{:Datenkompression:_Verlustfreie_Verfahren:_Statistische_Verfahren:_TOC}}

__NOTOC__
== Shannon-Fano Codierung == 
{{Status|8}}

Die Shannon-Fano-Codierung ist eine Technik, mit der ein sog. Präfix-Code erzeugt werden kann. Es handelt sich um den ersten Algorithmus, durch dessen Anwendung die Konstruktion eines Codes mit variabler Länge möglich ist. Anhand eines Quellalphabets und den Auftretenswahrscheinlichkeiten der einzelnen Symbole des Alphabets (seien sie geschätzt oder gezählt worden) wird ein Baum konstruiert. Dessen Kanten werden mit einem binärem Alphabet markiert. Folgt man den Kanten entlang des Baumes zu dem zu codierenden Zeichen, so erhält man die binäre Repräsentation (den Shannon-Fano-Code) für das zu codierende Zeichen. Mehrere aufeinanderfolgende Quellsymbole werden durch Aneinanderreihung der binären Codeworte codiert. Dieser Bitstrom wird neu gruppiert, bspw. in Gruppen zu je 8 Binärzeichen und in den Ausgabestrom geschrieben. Es erfolgt eine Substitution des Quellzeichens durch einen verbesserten Code, der näher an der Entropie des einzelnen Quellsymbols liegt. Häufiger auftretende Symbole werden durch kürzere Binärworte substituiert, als weniger Häufigere. Die Shannon-Fano Codierung ist demnach eine Form der klassischen Entropie-Codierung.

In einzelnen Fällen ist es möglich mit dem Shannon-Fano-Code die untere Shannonsche Informationsgrenze zu erreichen. Das ist jedoch nur dann möglich, wenn alle Symbole mit Symbolwahrscheinlichkeiten auftreten, die negative Potenzen von 2 sind. 

Die Shannon-Fano-Codierung ist vergleichsweise einfach zu implementieren. Dennoch wird sie nicht sehr häufig verwendet, da das Verfahren von [[Datenkompression: Verlustfreie Verfahren: Statistische Verfahren: Huffman Codierung|Huffman]] in der Regel Codes erzeugt, die effizienter sind, als jene die mit der Shannon-Fano Codierung erzeugt werden.

Nach eigener Auskunft 'APPNOTE.TXT' wird die Shannon-Fano Codierung, in der von PKWare stammenden PKZip-Software verwendet. Die Methode 6 (Imploding) der Kompressionssoftware verwendet zur Codierung der Treffer (Offset, Länge) (Siehe dazu: [[Datenkompression: Verlustfreie Verfahren: Wörterbuchbasierte Verfahren: LZ77|LZ77 Algorithmus]]) einen nachgeschalteten Shannon-Fano Entropiecodierer. Dieser wählt einen von mehreren Shannon-Fano Bäumen (2 oder 3) für die Codierung der einzelnen Treffer-Elemente aus. Das bedeutet, dass Literale mit einem anderen Shannon-Fano Baum codiert werden, als die Längeninformation und/oder die Offsetinformationen. Für genauere Informationen zum LZ77 Verfahren schauen sie in diesem Buch unter [[Datenkompression: Verlustfreie Verfahren: Wörterbuchbasierte Verfahren: LZ77|LZ77]].

===Codierung===

Die Codierung erfolgt in zwei Schritten. Zunächst wird jedem zu codierenden Symbol ein Code in Abhängigkeit von seiner Auftrittswahrscheinlichkeit zugeordnet. Im zweiten Schritt erfolgt die eigentliche Codierung mittels Substitution eines jeden Eingabezeichens durch das zuvor berechnete Code-Symbol. Anschließend werden die codierten Symbole aneinander gereiht und als Bytes ausgegeben.

{{:Datenkompression:_Vorlage:_Algorithmus|Shannon-Fano|
Der Algorithmus arbeitet nach dem folgenden Schema:
# Die Symbole werden zusammen mit ihrer Auftretenswahrscheinlichkeit nach absteigend sortiert.
# Es wird die Gesamtwahrscheinlichkeit der Gruppe der Symbole berechnet. Begonnen wird anfangs mit der Gesamtmenge aller Symbole. Deren Gesamtwahrscheinlichkeit sollte zu Beginn 1.0 betragen.
## Gibt es in dieser Menge exakt ein Symbol, so muss diese Menge nicht geteilt werden und auch keine weitere Binärentscheidung hinzugefügt werden. Der Code für das Symbol ist damit bereits zugeordnet.
## Gibt es in dieser Menge exakt zwei Symbole, so wird dem ersten Symbol der binäre Wert '''0''' und dem zweiten Symbol der binäre Wert '''1''' zugeordnet.
## Gibt es in dieser Menge mehr als zwei Symbole, so muss die Gesamtmenge geteilt werden, wobei der linken Menge der binäre Wert '''0''' und der rechten Menge der binäre Wert '''1''' zugeordnet wird. Die Teilungsgrenze ergibt sich durch die in Punkt 2 berechnete Gesamtwahrscheinlichkeit. Der Wert, der für die Gesamtwahrscheinlichkeit berechnet wird halbiert und als Teilungsgrenze avisiert. Das bedeutet, dass man versucht möglichst nahe an diese Teilungsgrenze heranzukommen. 
# ...
}}


;Beispiel 1

Als Beispiele für die Konstruktion eines Shannon-Fano-Codes dienen die beiden Folgenden. An diesen beiden Beispielen soll unter anderem gezeigt werden, wie der Code genau entsteht und das der erzeugte Shannon-Fano-Code nur suboptimal ist, indem jeweils ein abweichender Code präsentiert wird, der deutlich weniger Redundanz besitzt.

{| {{Prettytable}} align="left"
|+ Beispiel 1 - Shannon-Fano-Code (Quelle: ThePacker)
|bgcolor=#DDDDFF align="center"|Symbol
|bgcolor=#DDDDFF align="center"|'A'
|bgcolor=#DDDDFF align="center"|'B'
|bgcolor=#DDDDFF align="center"|'C'
|bgcolor=#DDDDFF align="center"|'D'
|bgcolor=#DDDDFF align="center"|'E'
|-
|bgcolor=#DDDDFF align="center"|p(Symbol)
|bgcolor=#ffffdd|0.4
|bgcolor=#ffffdd|0.15
|bgcolor=#ffffdd|0.15
|bgcolor=#ffffdd|0.15
|bgcolor=#ffffdd|0.15
|-
|bgcolor=#DDDDFF colspan="6"| 1. Teilung
|-
|bgcolor=#DDDDDD|
|bgcolor=#ffffdd align="center" colspan="2"|p('A','B') <br> 0.55
|bgcolor=#ffffdd align="center" colspan="3"|p('C','D','E') <br> 0.45
|-
|bgcolor=#DDDDDD|
|bgcolor=#ffffdd align="center" colspan="2"|0
|bgcolor=#ffffdd align="center" colspan="3"|1
|-
|bgcolor=#DDDDFF colspan="6"| 2. Teilung
|-
|bgcolor=#DDDDDD|
|bgcolor=#ffffdd align="center" colspan="2"|0
|bgcolor=#ffffdd align="center" colspan="3"|1
|-
|bgcolor=#DDDDDD|
|bgcolor=#ffffdd align="center"|p('A') <br> 0.4
|bgcolor=#ffffdd align="center"|p('B') <br> 0.15
|bgcolor=#ffffdd align="center"|p('C') <br> 0.15
|bgcolor=#ffffdd align="center" colspan="2"|P('D','E') <br> 0.3
|-
|bgcolor=#DDDDDD|
|bgcolor=#ffffdd align="center"|0
|bgcolor=#ffffdd align="center"|1
|bgcolor=#ffffdd align="center"|0
|bgcolor=#ffffdd align="center" colspan="2"|1
|-
|bgcolor=#DDDDFF colspan="6"| 3. Teilung
|-
|bgcolor=#DDDDDD|
|bgcolor=#ffffdd align="center" colspan="2"|0
|bgcolor=#ffffdd align="center" colspan="3"|1
|-
|bgcolor=#DDDDDD|
|bgcolor=#ffffdd align="center"|0
|bgcolor=#ffffdd align="center"|1
|bgcolor=#ffffdd align="center"|0
|bgcolor=#ffffdd align="center" colspan="2"|1
|-
|bgcolor=#DDDDDD|
|bgcolor=#DDDDFF align="center" colspan="3"|
|bgcolor=#ffffdd align="center"|p('D') <br> 0.15
|bgcolor=#ffffdd align="center"|p('E') <br> 0.15
|-
|bgcolor=#DDDDDD|
|bgcolor=#DDDDFF align="center" colspan="3"|
|bgcolor=#ffffdd align="center"|0
|bgcolor=#ffffdd align="center"|1
|-
|bgcolor=#DDDDFF colspan="6"| Resultierender Codebaum:
|-
|bgcolor=#DDDDDD|
|bgcolor=#ffffdd align="center" colspan="2"|0
|bgcolor=#ffffdd align="center" colspan="3"|1
|-
|bgcolor=#DDDDDD|
|bgcolor=#ffffdd align="center"|0
|bgcolor=#ffffdd align="center"|1
|bgcolor=#ffffdd align="center"|0
|bgcolor=#ffffdd align="center" colspan="2"|1
|-
|bgcolor=#DDDDDD|
|bgcolor=#DDDDFF align="center" colspan="3"|
|bgcolor=#ffffdd align="center"|0
|bgcolor=#ffffdd align="center"|1
|-
|bgcolor=#DDDDDD| 
|bgcolor=#DDDDFF|A
|bgcolor=#DDDDFF|B
|bgcolor=#DDDDFF|C
|bgcolor=#DDDDFF|D
|bgcolor=#DDDDFF|E
|}

; ''Erläuterung des Beispiels 1''

Links sehen Sie die Ableitung des Shannon-Fano-Code Baumes für das Quellenalpahbet <math>S=\{ 'A','B','C','D','E'\}\!</math> mit den angegebenen Wahrscheinlichkeiten. Der erste Schritt des Algorithmus besteht darin, die Symbole der Wahrscheinlichkeit nach absteigend zu sortieren. Anschließend beginnt der iterative Teil des Algorithmus.

Die erste Teilung erfolgt nach der Sortierung zwischen den beiden Symbolen 'B' und 'C', da die Teilungsregel vorschreibt, dass die Summenwahrscheinlichkeit der ersten Teilgruppe möglichst nahe an der Mitte der kumulierten Wahrscheinlichkeit liegen soll. Die Gesamtwahrscheinlichkeit ist '1'. Demnach liegt die exakte Teilungsgrenze bei '0.5'. Dass eine Teilung nicht zwischen den Symbolen 'A' und 'B' erfolgte lässt sich erklären. Die Differenz zwischen der Mitte und der Teilungsgrenze ('A','B') ist größer, als die Differenz bei einer Teilung zwischen ('B','C'). Mathematisch: <math>\left| 0.4 - 0.5\right| \ge \left| 0.55-0.5\right| </math>.

Die zweite Teilung zwischen den Buchstaben 'A' und 'B' ergibt sich aus reiner Zweckmäßigkeit. Da mehr als ein Symbol für diesen Teilbaum vorhanden ist, jedoch weniger als drei, wird dem linken Code eine Binärziffer ('''0''') zugeordnet und dem rechten Code die Andere ('''1'''). Damit ergibt sich der Gesamtcode für das Zeichen <math>A\rightarrow 00</math> und der des Zeichens <math>B\rightarrow 01</math>. Die rechte Teilgruppe besteht aus den drei Symbolen 'C', 'D' und 'E'. Da mehr als zwei Zeichen in dieser Menge vorhanden sind, muss diese erneut geteilt werden. Die kumulierte Wahrscheinlichkeit der Symbole beträgt 0.45 die Mitte liegt liegt demnach bei 0.225. Es muss anhand der Teilungsregel wieder entschieden werden, ob die Trennung zwischen dem Element 'C' und 'D' oder ob eine Teilung zwischen den Symbolen 'D' und 'E' erfolgt. In diesem Fall das Ergebnis beider Teilungsoperationen gleich schlecht <math>\left| 0.15-0.225\right| \ge \left| 0.3-0.225 \right|</math>. Ist der erste Fall genau so schlecht wie der Zweite, so entscheidet man zugunsten der Trennung zwischen 'C' und 'D'. Damit ergibt sich für das Element 'C' die folgende Substitutionsvorschrift:
<math>C\rightarrow 10</math>.

Die dritte Teilung findet für die letzte und verbliebene Menge 'D' und 'E' statt. Bei zwei Symbolen wird dem Einen der Binärcode '''0''' und dem Anderen der Binärcode '''1''' zugeordnet. Damit sind die Substitutionsvorschriften für 'D' und 'E' komplett: <math>D\rightarrow 110</math> und <math>E\rightarrow 111</math>.

Berechnet man die mittleren Codewortlänge, bei Benutzung der links angegebenen Wahrscheinlichkeiten, des hergeleiteten Shannon-Fano-Codes so ergibt sich ein Wert von '''2.3 [Bit/Symbol]'''.

<math>2\cdot(0.4 + 0.15 + 0.15) + 3\cdot(0.15 + 0.15) = 2.3</math>

Vergleicht man die mittlere Codewortlänge mit der Entropie nullter Ordnung so ergibt sich der reale Informationsgehalt der Nachricht mit '''2.171 [Bit/Symbol]''':

<math>0.4\cdot \operatorname{ld}\left(\frac{1}{0.4}\right) + 4 \cdot 0.15\cdot \operatorname{ld}\left(\frac{1}{0.15}\right)=0.4\cdot 1.322 + 0.6\cdot 2.737 = 0.5288 + 1.6422= 2.171</math>

Das bedeutet, dass dieser Code eine Redundanz von '''0.129 [Bit/Symbol]''' besitzt und deswegen nicht optimal ist. Das bedeutet ebenso, dass auf eine Million zu übertragender Symbole eine Kapazität von fast 60.000 Symbolen ignoriert wird.

('''!Achtung!''': Für das Beispiel wird angenommen, dass die zu codierenden Symbole statistisch unabhängig voneinander sind.)
{{Clear}}


{| {{Prettytable}} align="left"
|+ Beispiel 1 - Alternativer Codebaum (Quelle: ThePacker)
|bgcolor=#DDDDFF align="center"|Symbol
|bgcolor=#DDDDFF align="center"|'A'
|bgcolor=#DDDDFF align="center"|'B'
|bgcolor=#DDDDFF align="center"|'C'
|bgcolor=#DDDDFF align="center"|'D'
|bgcolor=#DDDDFF align="center"|'E'
|-
|bgcolor=#DDDDFF align="center"|p(Symbol)
|bgcolor=#ffffdd|0.4
|bgcolor=#ffffdd|0.15
|bgcolor=#ffffdd|0.15
|bgcolor=#ffffdd|0.15
|bgcolor=#ffffdd|0.15
|-
|bgcolor=#DDDDFF colspan="6"| Besserer Codebaum:
|-
|bgcolor=#DDDDDD|
|bgcolor=#ffffdd align="center"|0
|bgcolor=#ffffdd align="center" colspan="4"|1
|-
|bgcolor=#DDDDDD|
|bgcolor=#DDDDFF align="center"|
|bgcolor=#ffffdd align="center" colspan="2"|0
|bgcolor=#ffffdd align="center" colspan="2"|1
|-
|bgcolor=#DDDDDD|
|bgcolor=#DDDDFF align="center"|
|bgcolor=#ffffdd align="center"|0
|bgcolor=#ffffdd align="center"|1
|bgcolor=#ffffdd align="center"|0
|bgcolor=#ffffdd align="center"|1
|-
|bgcolor=#DDDDDD|
|bgcolor=#DDDDFF|A
|bgcolor=#DDDDFF|B
|bgcolor=#DDDDFF|C
|bgcolor=#DDDDFF|D
|bgcolor=#DDDDFF|E
|}

; ''Ein alternativer Code für das Beispiel 1''

Der alternative Code besitzt eine mittlere Codewortlänge von '''2.2 [Bit/Symbol]''', unter Berücksichtigung der angegebenen Wahrscheinlichkeiten:

<math>1\cdot(0.4) + 3\cdot(0.15 + 0.15 + 0.15 + 0.15) = 2.2</math>

Dieser alternative Code kann verglichen mit dem Shannon-Fano Code eine Redundanz von '''0.1 [Bit/Symbol]''' vermeiden. Die  Gesamtredundanz der durch diesen Code dargestellten Information, beträgt '''0.029 [Bit/Symbol]'''.

{{Clear}}

;Beispiel 2

{| {{Prettytable}} align="left"
|+ Beispiel 2 - Shannon-Fano-Code (Quelle: ThePacker)
|bgcolor=#DDDDFF align="center"|Symbol
|bgcolor=#DDDDFF align="center"|'A'
|bgcolor=#DDDDFF align="center"|'B'
|bgcolor=#DDDDFF align="center"|'C'
|bgcolor=#DDDDFF align="center"|'D'
|bgcolor=#DDDDFF align="center"|'E'
|bgcolor=#DDDDFF align="center"|'F'
|bgcolor=#DDDDFF align="center"|'G'
|-
|bgcolor=#DDDDFF align="center"|p(Symbol)
|bgcolor=#ffffdd|0.4
|bgcolor=#ffffdd|0.1
|bgcolor=#ffffdd|0.1
|bgcolor=#ffffdd|0.1
|bgcolor=#ffffdd|0.1
|bgcolor=#ffffdd|0.1
|bgcolor=#ffffdd|0.1
|-
|bgcolor=#DDDDFF colspan="8"|Resultierender Codebaum
|-
|bgcolor=#DDDDDD|
|bgcolor=#ffffdd colspan="2" align="center"|0
|bgcolor=#ffffdd colspan="5" align="center"|1
|-
|bgcolor=#DDDDDD|
|bgcolor=#ffffdd align="center"|0
|bgcolor=#ffffdd align="center"|1
|bgcolor=#ffffdd align="center" colspan="2"|0
|bgcolor=#ffffdd align="center" colspan="3"|1
|-
|bgcolor=#DDDDDD|
|bgcolor=#DDDDFF colspan="2"|
|bgcolor=#ffffdd align="center"|0
|bgcolor=#ffffdd align="center"|1
|bgcolor=#ffffdd align="center"|0
|bgcolor=#ffffdd align="center" colspan="2"|1
|-
|bgcolor=#DDDDDD|
|bgcolor=#DDDDFF colspan="5"|
|bgcolor=#ffffdd align="center"|0
|bgcolor=#ffffdd align="center"|1
|-
|bgcolor=#DDDDDD|
|bgcolor=#DDDDFF|A
|bgcolor=#DDDDFF|B
|bgcolor=#DDDDFF|C
|bgcolor=#DDDDFF|D
|bgcolor=#DDDDFF|E
|bgcolor=#DDDDFF|F
|bgcolor=#DDDDFF|G
|}

; ''Erläuterung des Beispiels 2''

Das zweite Beispiel, welches links zu sehen ist, ist ein weiteres Beispiel für einen Shannon-Fano-Code. Der Anhand der in der Tabelle vorgegebenen Wahrscheinlichkeiten berechnet wird.

Bei Benutzung dieses Codes mit den vorgegebenen Wahrscheinlichkeiten lässt sich eine mittlere Codewortlänge von '''2.7 [Bit/Symbol]''' berechnen.

<math>2\cdot(0.4 + 0.1) + 3\cdot(0.1 + 0.1 + 0.1) + 4\cdot(0.1 + 0.1) = 2.7</math>

Berechnet man den Informationsgehalt der ursprünglichen Nachricht, so ergibt sich ein Informationsgehalt von '''2.522 [Bit/Symbol]'''. Das bedeutet, dass sich eine Redundanz von '''0.178 [Bit/Symbol]''' in der codierten Nachricht befindet. Die Redundanz ergibt sich aus der Differenz der mittleren Codewortlänge und dem mittleren Informationsgehalt der ursprünglichen Nachricht.

<math>0.4\cdot 1.322 + 6\cdot 0.1\cdot 3.322 = 2.522\!</math>

('''!Achtung!''' Auch hier wird angenommen, dass die zu codierenden Symbole statistisch unabhängig voneinander sind.)


{{Clear}}

{| {{Prettytable}} align="left"
|+ Beispiel 2 - Alternativer Code (Quelle: ThePacker)
|bgcolor=#DDDDFF align="center"|Symbol
|bgcolor=#DDDDFF align="center"|'A'
|bgcolor=#DDDDFF align="center"|'B'
|bgcolor=#DDDDFF align="center"|'C'
|bgcolor=#DDDDFF align="center"|'D'
|bgcolor=#DDDDFF align="center"|'E'
|bgcolor=#DDDDFF align="center"|'F'
|bgcolor=#DDDDFF align="center"|'G'
|-
|bgcolor=#DDDDFF align="center"|p(Symbol)
|bgcolor=#ffffdd|0.4
|bgcolor=#ffffdd|0.1
|bgcolor=#ffffdd|0.1
|bgcolor=#ffffdd|0.1
|bgcolor=#ffffdd|0.1
|bgcolor=#ffffdd|0.1
|bgcolor=#ffffdd|0.1
|-
|bgcolor=#DDDDFF colspan="8"|Verbesserter Codebaum
|-
|bgcolor=#DDDDDD|
|bgcolor=#ffffdd align="center"|0
|bgcolor=#ffffdd align="center" colspan="6"|1
|-
|bgcolor=#DDDDDD|
|bgcolor=#DDDDFF|
|bgcolor=#ffffdd align="center" colspan="2"|0
|bgcolor=#ffffdd align="center" colspan="4"|1
|-
|bgcolor=#DDDDDD|
|bgcolor=#DDDDFF|
|bgcolor=#ffffdd align="center"|0
|bgcolor=#ffffdd align="center"|1
|bgcolor=#ffffdd align="center" colspan="2"|0
|bgcolor=#ffffdd align="center" colspan="2"|1
|-
|bgcolor=#DDDDDD|
|bgcolor=#DDDDFF colspan="3"|
|bgcolor=#ffffdd align="center"|0
|bgcolor=#ffffdd align="center"|1
|bgcolor=#ffffdd align="center"|0
|bgcolor=#ffffdd align="center"|1
|-
|bgcolor=#DDDDDD|
|bgcolor=#DDDDFF|A
|bgcolor=#DDDDFF|B
|bgcolor=#DDDDFF|C
|bgcolor=#DDDDFF|D
|bgcolor=#DDDDFF|E
|bgcolor=#DDDDFF|F
|bgcolor=#DDDDFF|G
|}

; ''Ein alternativer Code für das Beispiel 2''

Es wurde auch für das zweite Beispiel ein Code gefunden, der bei der Verwendung der links angegebenen Symbolwahrscheinlichkeiten eine kleinere mittlere Codewortlänge besitzt, als die des Shannon-Fano-Codes statt den '''2.7 [Bit/Symbol]'''. Es ist möglich eine mittlere Codewortlänge zu erreichen, die bei '''2.6 [Bit/Symbol]''' liegt.

<math>1\cdot(0.4) + 3\cdot(0.1 + 0.1) + 4\cdot(0.1 + 0.1 + 0.1 + 0.1) = 2.6</math>

Wie man nun erkennen kann, ist die Verwendung des alternativen Codes um 0.1 [Bit/Symbol] besser. Damit reduziert sich die Redundanz um 0.1 Bit pro übertragenem Symbol. Das scheint eine sehr kleine Größe zu sein, aber es sollte bedacht werden, dass es sich um einen Verschnitt von etwa 4 Prozent handelt, der das Codierverfahren in keiner Weise verbessert. Gemeint ist, dieser Verschnitt macht das Verfahren nicht schneller und es macht das Verfahren nicht weniger aufwändig. Das bedeutet, es ist ohne zusätzlichen Aufwand möglich 4 Prozent einzusparen, wenn der verwendete Code durch ein besseres Verfahren erzeugt werden würde.

{{Clear}}

Die beiden Beispiele zeigen zum einen, dass der Code nicht immer optimal gewählt wird. Insbesondere, weil es zum Teil starke Abweichungen vom realen Informationsgehalt gibt. Ein anderes Problem besteht darin, dass der verwendete Codebaum, oder die Auftretenswahrscheinlichkeiten an den Empfänger übertragen werden müssen, es sei denn, man entscheidet sich für ein adaptives Verfahren, welches in einem späteren Abschnitt eingeführt wird.

Offensichtlich besitzt der Shannon-Fano-Algorithmus eine Schwachstelle, die dafür sorgt, dass die falschen Symbole miteinander kombiniert werden. Wenn man sich die beiden Codebäume ansieht, so kann man feststellen, dass das Element 'B' im Baum in beiden Beispielen auf der rechten Seite besser aufgehoben ist, als auf der linken Seite. Dieses Element scheint demnach das eigentliche Problem zu sein. Im ersten Beispiel gelang es nicht, die Teilung an der Stelle 0.5 vorzunehmen und man könnte vermuten, dass eine ungenaue Teilung das eigentliche Problem ist. Jedoch wurde das Beispiel 2 bewusst wo gewählt, dass eine optimale Trennung für die erste Teilung möglich war. Auch dann ist es offenbar nicht möglich, einen optimalen Codebaum zu erzeugen. Wenn in beiden Fällen eine Teilung bereits nach dem Symbol 'A', also der Wahrscheinlichkeit 0.4, erfolgt wäre, dann wäre der resultierende Code-Baum um 0.1 [Bit/Symbol] besser gewesen. Das Problem bei diesem Verfahren scheint also die Frage nach der optimalen Teilung zu sein. Die Summenwahrscheinlichkeit stellt demnach nicht das korrekte Maß dar, welches die Teilung in einen linken oder rechten Codebaum korrekt begründet. Ein weiterer Erklärungsansatz läge darin, den Entscheidungsgehalt der Symbole 'A' (1.322 Bit) und 'B' (3.322 Bit) zu betrachten, die beide sehr stark voneinander abweichen unde deswegen nicht zusammen codiert werden sollten.

;Codierung des Ausgabestroms

Betrachtet man den Beispieltext ('ABBABACCACADDADAEEAE') mit einer Verteilung, der der des Beispiels 1 entspricht, so erfolgt die Codierung durch Subsitution: <math>A\rightarrow 00</math>, <math>B\rightarrow01</math>, <math>C\rightarrow10</math>, <math>D\rightarrow 110</math> und <math>E\rightarrow 111</math>. 

{| {{Prettytable}} align="left"
|+ Substitution der Beispielnachricht durch einen Code variabler Länge
|-
|A||B||B||A||B||A||C||C||A||C||A||D||D||A||D||A||E||E||A||E
|-
|00||01||01||00||01||00||10||10||00||10||00||110||110||00||110||00||111||111||00||111
|-
|}

Nach der Subsitution werden die codierten Zeichen in ohne jedes Trennsymbol (bspw. Leerzeichen) zusammengefasst und in 8-er Gruppen getrennt, wobei das letzte Zeichen im Zweifelsfall aufgefüllt werden muss (bspw 0). In der Binärdarstellung sieht die codierte Zeichenkette wie folgt aus: '''''00010100''''', '''''01001010''''', '''''00100011''''', '''''01100011''''', '''''00011111''''' und '''''100111**''''' in einer hexadezimalen Darstellung '''''1F 8A 23 63 1F 9A'''''. Die beiden mit (*) dargestellten fehlenden Symbole wurden durch zwei Nullen ersetzt. 

{{clear}}

;Effizienz des Ausgabestroms

Verwendet man statt dessen die alternative Codierung aus dem 1. Beispiel für die gleiche Zeichenfolge, so erhielten wir die folgende Lösung.

{| {{Prettytable}} align="left"
|+ Substitution der Beispielnachricht durch einen effizienteren Code
|-
|A||B||B||A||B||A||C||C||A||C||A||D||D||A||D||A||E||E||A||E
|-
|0||100||100||0||100||0||101||101||0||101||0||110||110||0||110||0||111||111||0||111
|-
|}

Die Zeichenkette würde in 8-er Gruppen von binären Zahlen wie folgt aussehen: '''''01001000''''', '''''10001011''''', '''''01010101''''', '''''10110011''''', '''''00111111''''' und  '''''0111****''''', welche in einer hexadezimalen Schreibweise so aussehen würden: '''''48 8B 55 B3 3F 70'''''. Wie man erkennen kann, müssen bei diesem Code mehr Füllzeichen verwendet werden, das heißt, dass die gleiche Information in einer kürzeren Binärkette dargestellt worden ist. Der eigentliche Gewinn findet aber erst bei Texten statt, die mehrere tausend Zeichen lang sind. Wenn jedes mal ein Bit oder zwei eingespart werden kann, summiert sich der Gewinn nach und nach. Der Gewinn von '''G=0.1 [Bit/Symbol]''' summiert sich bei 20 Symbolen auf 2 Bit. Das sind die beiden Bit, die durch die beiden zusätzlichen '''''*''''' Symbole aufgefüllt werden mussten.

{{clear}}

;Aufgaben
{{:Datenkompression: Vorlage: Aufgaben|Shannon-Fano Codierung|
*'''[M10]''' Vergleichen Sie die Varianz der Codewortlängen der beiden Shannon-Fano Codes mit deren alternativen Codierungen. Zu welchen Ergebnissen kommen Sie?
*'''[15]''' Welchen Vorteil hat eine geringere Varianz der Codewortlänge? (gleichmäßigere Bitraten, bei kontinuierlicher Übertragung.)
}}

===Decodierung===
Während der Codierung wurden die Symbole durch einen Code substituiert. Jedes Eingabesymbol wurde durch einen Code variabler Länge substituiert und anschließend in Gruppen von 8 Bit ohne jedes Trennsymbol gespeichert. Die Decodierung erfolgt ähnlich. Man trennt die codierten Symbole voneinander und substituiert den jeweiligen Code durch das ursprüngliche Eingabesymbol.

Damit die codierten Daten korrekt decodiert werden, muss dem Empfänger der codierten Daten der verwendete Code bekannt sein, mit dem die Daten codiert wurden. Zunächst sei dem Empfänger der verwendete Code bekannt, so erfolgt die Decodierung der Nachricht wie im folgenden Algorithmus.

{{:Datenkompression: Vorlage: Algorithmus|Shannon-Fano Decodierung|

# (TODO)

}}


; Beispiel

{| {{Prettytable}} align="left"
|+ Beispiel zur Decodierung eines Shannon-Fano-Codes
| Schritt
| colspan="6"|Binärcode
| Ausgabe
|-
|     || 00010100 || 01001010 || 00100011 || 01100011 || 00011111 || 100111** || (keine Ausgabe)
|-
| 1.  || '''00'''010100 || 01001010 || 00100011 || 01100011 || 00011111 || 100111** || A
|-
| 2.  || __'''01'''0100 || 01001010 || 00100011 || 01100011 || 00011111 || 100111** || B
|-
| 3.  || ____'''01'''00 || 01001010 || 00100011 || 01100011 || 00011111 || 100111** || B
|-
| 4.  || ______'''00''' || 01001010 || 00100011 || 01100011 || 00011111 || 100111** || A
|-
| 5.  || ________ || '''01'''001010 || 00100011 || 01100011 || 00011111 || 100111** || B
|-
| 6.  || ________ || __'''00'''1010 || 00100011 || 01100011 || 00011111 || 100111** || A
|-
| 7.  || ________ || ____'''10'''10 || 00100011 || 01100011 || 00011111 || 100111** || C
|-
| 8.  || ________ || ______'''10''' || 00100011 || 01100011 || 00011111 || 100111** || C
|-
| 9.  || ________ || ________ || '''00'''100011 || 01100011 || 00011111 || 100111** || A
|-
| 10. || ________ || ________ || __'''10'''0011 || 01100011 || 00011111 || 100111** || C
|-
| 11. || ________ || ________ || ____'''00'''11 || 01100011 || 00011111 || 100111** || A
|-
| 12. || ________ || ________ || ______'''11''' || '''0'''1100011 || 00011111 || 100111** || D
|-
| 13. || ________ || ________ || ________ || _'''110'''0011 || 00011111 || 100111** || D
|-
| 14. || ________ || ________ || ________ || ____'''00'''11 || 00011111 || 100111** || A
|-
| 15. || ________ || ________ || ________ || ______'''11''' || '''0'''0011111 || 100111** || D
|-
| 16. || ________ || ________ || ________ || ________ || _'''00'''11111 || 100111** || A
|-
| 17. || ________ || ________ || ________ || ________ || ___'''111'''11 || 100111** || E
|-
| 18. || ________ || ________ || ________ || ________ || ______'''11''' || '''1'''00111** || E
|-
| 19. || ________ || ________ || ________ || ________ || ________ || _'''00'''111** || A
|-
| 20. || ________ || ________ || ________ || ________ || ________ || ___'''111'''** || E
|-
|}
; ''Erläuterung des Beispiels''

Die Decodierung erfolgt bei der Codierung von links nach rechts. Hier wird eine variable Anzahl von Binärsymbolen durch ein Zeichen des ursprünglichen Alphabets ersetzt. Dabei wird die Zuordnung der Symbole des Quell und des Zielalphabets umgekehrt. Die Umkehr dieser Abbildung ergibt die folgende Zuordnung: <math>00\rightarrow A\!</math>, <math>01\rightarrow B\!</math>, <math>10\rightarrow C\!</math>, <math>110\rightarrow D\!</math> und <math>111\rightarrow E\!</math>.

Die Decodierung erfolgt, indem der noch nicht decodierte Teil von links nach rechts gelesen wird. Das erste Zeichen ist eine '''0''', diese ist jedoch Beginn zweier Symbole (<math>00\rightarrow A\!</math> und <math>01\rightarrow B\!</math>) die Entscheidung, um welches Symbol (A,B) es sich ursprünglich gehandelt hat, kann durch das lesen des ersten Zeichens noch nicht eindeutig beantwortet werden. Deswegen muss diese Entscheidung verzögert werden und das Folgesymbol betrachtet werden. In diesem Falll ist es ebenfalls eine '''0'''. Das einzige Symbol, dass durch eine Folge zweier Nullen ein Symbol des Quellalphabets ergibt ist das Symbol '''A'''. Die Zeichenfolge '''00''' ist die kleinstmögliche eindeutige Übereinstimmung mit einem Code aus der Codierung. Diese beiden Symbole werden als gelesen markiert und das Element aus der Rückabbildung ausgegeben.

Die bereits zu einem Ausgabesymbol transformierten Zeichen werden für die weitere Decodierung nicht mehr herangezogen oder benötigt. Deswegen werden sie in der Notation links in Form des Symbols '''_''' dargestellt.

Im zweiten Schritt ist die kleinstmögliche eindeutige Übereinstimmung mit der Rückabbildungsvorschrift die Zeichenkette '''01''', deswegen wird ein '''B''' ausgegeben.

Im Schritt 12 ist die kleinstmögliche eindeutige Übereinstimmung 3 Zeichen lang. Auf diese Art kann das Zeichen '''D''' eindeutig decodiert werden.

Reiht man die Ausgaben des 1. Schrittes bis zum 20. Schritt aneinander, so erhält man die Symbolkette ('''"ABBABACCACADDADAEEAE"'''). Diese ist identisch mit der Eingabe für das erste Beispiel.

Sind sowohl die codierte Nachricht, als auch der Code bekannt, so kann die Nachricht offenbar eindeutig decodiert werden. Damit der Decodierer korrekt arbeiten kann, muss der verwendete Code an den Decodierer übertragen werden, damit die ursprüngliche Nachricht rekonstruiert werden kann.
{{clear}}


Die Übertragung der Gesamtnachricht vom Sender zum Empfänger erfolgt durch eine zweigeteilte Nachricht. Die erste Teilnachricht beschreibt den verwendeten Code. Das heißt der Empfänger der Nachricht wird über den verwendeten Code informiert. Die zweite Teilnachricht enthält die eigentlich codierte Nachricht. Wie der verwendete Code an den Empfänger der Nachricht übertragen werden kann, erfordert einiges Zusatzverständnis über den erzeugten Shannon-Fano-Codebaum.

{| {{Prettytable}} align="left"
|+ Aufbau einer vollständigen Nachricht
|-
|bgcolor="#eeffee"|Codebeschreibung
|bgcolor="#ffffee"|Codierte Nachricht
|-
|colspan="2" align="center"|Gesamtnachricht
|}

Die '''Codebeschreibung''' enthält die für den Decodiervorgang benötigten Ersetzungsregeln. Die '''Codierte Nachricht''' ist das Resultat der Codierung einer Nachricht mit dem zuvor berechneten Code. Sie kann nur dann korrekt decodiert werden, wenn die gleiche Codiervorschrift sowohl vom Sender der Nachricht, als auch vom Empfänger der Nachricht bekannt ist.

{{clear}}

; Übertragung des Code

Zunächst sollte man klarstellen, dass andere Verteilungen ebenso zu einem Shannon-Fano Code führen, der mit dem Code des ersten Beispiels identisch ist. Eine Verteilung von <math>P(A)=0.25\!</math>, <math>P(B)=0.25\!</math>, <math>P(C)=0.25\!</math>, <math>P(D)=0.125\!</math> und <math>P(E)=0.125\!</math> führt zu exakt demselben Code. Dieser Code ist für diese Verteilung optimal und es gibt zwischen der mittleren Codewortlänge und der Entropie dieser Information keine Differenz.

Diese Überlegung zielt darauf ab, dass verschiedene Verteilungen auf den gleichen Code abgebildet werden. Manchmal ist er optimal und meistens ist er hinreichend effizient. Diese Schlussfolgerung zielt ebenso darauf ab, dass die exakte Sortierung nach Wahrscheinlichkeiten nur im allerersten Schritt benötigt wird, um einen Code nahe am Optimum zu finden.

Es spielt außerdem keine Rolle, welche konkrete Codesequenz für ein Eingabesymbol verwendet wird, solange der Code eindeutig decodierbar ist und die Codelängen exakt mit den berechneten Codelängen übereinstimmen. Das heißt die Effizienz des Codes verändert sich nicht, wenn man für jede '''0''' eine '''1''' substituiert und umgekehrt.

(TODO)


; Extrem effiziente Decodierverfahren für Codes variabler Länge (VLC)

Oft wird behauptet, die Decodierung könne nicht schnell vorgenommen werden, da die Daten bitweise verarbeitet werden müssten. Der obige Algorithmus legt diese Interpretation anfangs sehr nahe. (TODO)


;Aufgaben
{{:Datenkompression: Vorlage: Aufgaben|Shannon-Fano Decodierung|

# '''[A15]''' Wie kann der Shannon-Fano Codebaum effizient vom Codierer zum Decodierer übertragen werden?
# '''[A15]''' Verwenden Sie eine Shannon-Fano Codierung zur Codierung des Shannon-Fano-Baumes.

}}


;Objektive Ergebnisse
Hier werden die Kompressionsergebnisse des Algorithmus mit dem Calgary Corpus überprüft. Dezeit liegen mir noch keine Ergebnisse mit dem Calgary Corpus vor deswegen bleibt dieser Teil vorerst leer. (TODO)


;Bewertung
Dieser Algorithmus ist relativ schlicht und er ist aufgrund seiner simplen Arbeitsweise einfach zu implementieren. Somit eignet er sich für Anfänger auf diesem Gebiet sehr gut. Die Kompressionsergebnisse dieses Algorithmus sind nicht optimal. Einerseits weil jedes der Code-Symbole eine ganzzahlige Länge hat. Der Fall der Optimalität tritt nur dann auf, wenn alle auftretenden Symbole des Quellalphabets eine Symbolwahrscheinlichkeit haben, die eine negative Potenz von 2 darstellt. Im Regelfall ist das nicht der Fall, weswegen es zu Codierverlusten wegen der ganzzahligen Codewortlängen kommt. Andererseits kann dieser Code nicht den bestmöglichen Code-Baum zu erzeugen, wie die Beispiele es demonstriert haben. Wenn es aber nicht auf ein Zehntel eines Bits ankommt, ist dieser Algorithmus sehr einfach zu implementieren und für den Einstieg in die Welt der Datenkompression gut geeignet. Der algorithmische Aufwand ist nahezu vernachlässigbar gering und kann von selbst von Geräten implementiert werden, die über fast keine Rechenleistung verfügen. In diesem Fall ist die eingesparte Energie gegenüber der Kompressionsleistung vorzuziehen. 

Eine kleine Schwierigkeit für Anfänger könnte sein, dass er den verwendeteten Code an den Empfänger übermitteln muss, und er sich darüber Gedanken machen muss, wie der Codebaum am besten zum Empfänger der Nachricht übermittelt werden kann. Letzten Endes stellt dieses den ersten Schritt für ein Datenkompressionsprogramm dar, weil das Kompressionsprogramm fast immer einen Teil seiner Informationen zum verwendeten Verfahren dem Decodierer übertragen muss.


;Quellenangaben

* [http://www.pkware.com/business_and_developers/developer/appnote/ APPNOTE von PKWare] - Beschreibung des Kompressionsformates PKZip von PKWare