Informationstheorie/Weitere Quellencodierverfahren

1. Informationstheorie
2. Quellencodierung – Datenkomprimierung
3. Weitere Quellencodierverfahren

• Vorherige Seite
• Nächste Seite

• Vorherige Seite
• Nächste Seite

Der Shannon–Fano–Algorithmus

Die Huffman–Codierung aus dem Jahr 1952 ist ein Sonderfall der Entropiecodierung. Dabei wird versucht, das Quellensymbol $q_μ$ durch ein Codesymbol $c_μ$ der Länge $L_μ$ darzustellen, wobei folgende Konstruktionsvorschrift angestrebt wird:

Da $L_μ$ im Gegensatz zu log2(1/ $p_μ$) ganzzahlig ist, gelingt dies nicht immer. Bereits drei Jahre vor David A. Huffman haben Claude E. Shannon und Robert Fano einen ähnlichen Algorithmus angegeben, nämlich:

1. Man ordne die Quellensymbole nach fallenden Auftrittswahrscheinlichkeiten (identisch mit Huffman).
2. Man teile die sortierten Zeichen in zwei möglichst gleichwahrscheinliche Gruppen.
3. Der ersten Gruppe wird das Binärsymbol 1 zugeordnet, der zweiten die 0 (oder umgekehrt).
4. Sind in einer Gruppe mehr als ein Zeichen, so ist auf diese der Algorithmus rekursiv anzuwenden.

Wir gehen wie im Einführungsbeispiel für den Huffman–Algorithmus zu Beginn von Kapitel 2.3 von $M$ = 6 Symbolen und den folgenden Wahrscheinlichkeiten aus:

Dann lautet der Shannon–Fano–Algorithmus:

1. AB → 1x (Wahrscheinlichkeit 0.54), CDEF → 0x (Wahrscheinlichkeit 0.46),
2. A → 11, B ⇒ 10,
3. C → 01, (Wahrscheinlichkeit 0.20), DEF → 00x, (Wahrscheinlichkeit 0.26),
4. D → D, (Wahrscheinlichkeit 0.12), EF → 000x (Wahrscheinlichkeit 0.14),
5. E → 0001, F → 0000.

Anmerkung: Ein „x” weist wieder darauf hin, dass in nachfolgenden Codierschritten noch Bits hinzugefügt werden müssen. Es ergibt sich hier zwar eine andere Zuordnung als bei der Huffman–Codierung, aber genau die gleiche mittlere Codewortlänge:

Mit den Wahrscheinlichkeiten entsprechend dem Beispiel 1 (auf der letzten Seite) führt der Shannon–Fano–Algorithmus zur gleichen mittleren Codewortlänge wie die Huffman–Codierung. Ebenso sind bei vielen (eigentlich: den meisten) anderen Wahrscheinlichkeitsprofilen Huffman und Shannon–Fano aus informationstheoretischer Sicht äquivalent. Es gibt aber durchaus Fälle, bei denen sich beide Verfahren hinsichtlich der (mittleren) Codewortlänge unterscheiden, wie das folgende Beispiel zeigt.

Wir betrachten $M$ = 5 Symbole mit folgenden Wahrscheinlichkeiten:

Die Grafik zeigt die jeweiligen Codebäume für Shannon–Fano (links) bzw. Huffman (rechts). Die Ergebnisse lassen sich wie folgt zusammenfassen:

• Der Shannon–Fano–Algorithmus führt zum Code A → 11, B → 10, C → 01, D → 001, E → 000 und damit zur mittleren Codewortlänge

• Mit dem Huffman–Algorithmus erhält man A → 1, B → 001, C → 010, D → 001 sowie E → 000 und eine etwas kleinere mittlere Codewortlänge:

• Es gibt keinen Satz von Wahrscheinlichkeiten, bei denen Shannon–Fano ein besseres Ergebnis liefert als der Huffman–Algorithmus, der den bestmöglichen Entropiecodierer bereitstellt.
• Die Grafik zeigt zudem, dass die Algorithmen im Baumdiagramm in unterschiedlichen Richtungen vorgehen, nämlich einmal von der Wurzel zu den Einzelsymbolen (Shannon–Fano), zum anderen von den Einzelsymbolen zur Wurzel (Huffman).

Arithmetische Codierung

Eine weitere Form der Entropiecodierung ist die arithmetische Codierung. Auch bei dieser müssen die Symbolwahrscheinlichkeiten pμ bekannt sein. Für den Index gelte weiter μ = 1, ... , M. Hier nun ein kurzer Abriss über die Vorgehensweise:

• Im Gegensatz zur Huffman– und Shannon–Fano–Codierung wird bei arithmetischer Codierung eine Symbolfolge der Länge N gemeinsam codiert. Wir schreiben abkürzend Q = 〈q1, q2, ... , qN〉.
• Jeder solchen Symbolfolge Qi wird ein reelles Zahlenintervall Ii zugewiesen, das durch den Beginn Bi und die Intervallbreite Δi gekennzeichnet ist.
• Der „Code” für die gesamte Folge Qi ist die Binärdarstellung eines reellen Zahlenwertes aus diesem Intervall: ri ∈ Ii = [Bi, Bi + Δi). Diese Notation besagt, dass zwar Bi zum Intervall Ii gehört (eckige Klammer), aber Bi + Δi gerade nicht mehr (runde Klammer).
• Es gilt stets 0 ≤ ri < 1. Sinnvollerweise wählt man ri aus dem Intervall Ii derart, dass der Wert mit möglichst wenigen Bits darstellbar ist. Es gibt aber eine Mindestbitanzahl, die von der Intervallbreite Δi abhängt.

Der Algorithmus zur Bestimmung der Intervallparameter Bi und Δi wird auf der nächsten Seite an einem Beispiel erläutert, ebenso eine Decodiermöglichkeit. Zunächst folgt ein kurzes Beispiel zur Auswahl der reellen Zahl ri in Hinblick auf minimale Bitanzahl. Genauere Informationen hierzu finden Sie zum Beispiel in [BCK02] und bei der Beschreibung zur Aufgabe A1.12. Beispiel: Für folgende Parameter des arithmetischen Codieralgorithmus ergeben sich folgende reelle Ergebnisse ri und folgende Codes, die zum zugehörigen Intervall Ii gehören: Bi = 0.25, Δi = 0.10 ⇒ Ii = [0.25, 0.35):

Bi = 0.65, Δi = 0.10 ⇒ Ii = [0.65, 0.75); zu beachten: 0.75 gehört nicht zum Intervall:

Um den sequentiellen Ablauf zu organisieren, wählt man allerdings die Bitanzahl konstant zu

Mit der Intervallbreite Δi = 0.10 ergibt sich NBit = 5. Die tatsächlichen arithmetischen Codes wären also 01000 bzw. 10110.