Vorlesung Informatik 1 - Teil B: Theorie
2.6 Entropiecodierungen
Auch 'Statistische Codierungen' oder VLC: Variable Length Coding.
Die Grundidee ist im Morse-Code (Samuel Morse 1833) verwirklicht:
Häufige Zeichen werden kurz, seltene lang codiert.
Der Morse-Code hat 3 Zeichen: langer Ton (-), kurzer Ton (.) und Pause.
| A | - |
|---|---|
| E | . |
| O | - - - |
| S | . . . |
| Y | - . - - |
Er eignet sich aber nicht für eine binäre Codierung, da er mit 3 Zeichen arbeitet (lang, kurz, Pause).
Ein primitiver Ansatz für eine VLC Codierung sieht wie folgt aus:
- Sortiere die Zeichen nach absteigender Häufigkeit
- Codiere das häufigste Zeichen als 1, das nächste als 10, dann 100 u.s.w.
- das letzt Zeichen ist genau so lang wie das vorletzte und enthält nur 0-Bits.
Beispiel aus dem letzten Kapitel:
Zeichenvorrat Z= {A, B, C, D} , Datenquelle Q= "AACCCCBD"
Die Entropie hatten wir mit 1,75 bit pro Zeichen berechnet.
Sortiert nach Häufigkeit könnte man folgenden Code erstellen:
| C | 1 |
|---|---|
| A | 01 |
| D | 001 |
| B | 000 |
Die Datenquelle würde also wie folgt codiert:
01011111000100 das sind 14 Bit, also genau 1,75 bit/Zeichen. Das diese Codierung genau die Entropie erreicht, liegt daran dass das Beispiel konstruiert ist.
Der Decoder erkennt das Ende eines Zeichens an einem 1-Bit oder
spätestens nach 3 0-Bits.
Zum Vergleich eine Codierung mit fester Wortlänge würde z.B. so aussehen:
A: 00 B:01 C:10 D:11 und die codierte Datenquelle wäre 0000101010100101.
Der Huffman Code (1951) ist der wichtigste Vertreter der VLC Codierungen. Er ordnet die Zeichen in einem Binärbaum an.
In der Praxis liegt eine Huffman-Codierung meist sehr nahe an der Entropie.
Code-Baum:
Ein Binärcode kann als Binärbaum dargestellt werden. Wenn wir die 4 Zeichen A,B,C,D binär als 00, 01, 10 und 11 codieren, ensteht folgender Code-Baum:
o
/ \ o Knoten
/ \
o o
\ Kanten
/ \
/ \
/ \ / \
A B C D
Geht man von der Wurzel zu einem Blatt und schreibt für jede besuchte linke Kante eine 0 und für jede rechte Kante ein 1, so entsteht der Code.
Im Codebaum einer Codierung mit fester Wortlänge liegen die codierten Zeichen alle auf der untersten Ebene.
Der Huffman Codebaum ist unbalanciert, die Zeichen liegen auf unterschiedlichen Ebenen.
Der Huffman Algorithmus besteht aus wenigen Schritten:
- Erstelle für jedes Zeichen einen Baum, der nur aus der Wurzel besteht.
Speichere darin die Häufigkeit des Zeichens. - Füge die beiden Bäume mit der geringsten Häufigkeit zu einem Binärbaum zusammen.
Speichere in der Wurzel die Summe der beiden Häufigkeiten. - Wiederhole Schritt 2 bis nur noch ein Baum übrig bleibt.
Beispiel:
Die Zeichen {A,B,C,D,E,F,G} kommen in einer Datei mit unterschiedlicher Häufigkeit (Frequenz) f vor. In Spalte 2 steht eine mögliche Codierung mit fester Wortlänge (3 Bit pro Zeichen) und in Spalte 3 wird aufsummiert, wie viele Bits dabei insgesamt verbraucht werden. In den letzten beiden Spalten steht für jedes Zeichen die Wahrscheinichkeit p und das Produkt aus p und Informationsgehalt H:
| f | code | bits | p | p*H | |
|---|---|---|---|---|---|
| A | 10 | 000 | 30 | 0,172 | 0,437 |
| B | 15 | 001 | 45 | 0,259 | 0,505 |
| C | 12 | 010 | 36 | 0,207 | 0,470 |
| D | 3 | 011 | 9 | 0,052 | 0,221 |
| E | 4 | 100 | 12 | 0,069 | 0,266 |
| F | 13 | 101 | 39 | 0,224 | 0,484 |
| G | 1 | 110 | 3 | 0,017 | 0,101 |
| 58 | 174 | 1 | 2,484 |
Die Entropie beträgt 2,484 Bit/Zeichen, d.h. es muss eine VLC Codierung geben, die nahe an dieser Schranke liegt.
Wendet man den Huffman Algorithmus auf diese Zeichen an, bekommt man folgenden Code:
| f | code | bits | |
|---|---|---|---|
| A | 10 | 001 | 30 |
| B | 15 | 01 | 30 |
| C | 12 | 10 | 24 |
| D | 3 | 00000 | 15 |
| E | 4 | 0001 | 16 |
| F | 13 | 11 | 26 |
| G | 1 | 00001 | 5 |
| 58 | 146 |
Der Code verbraucht 146 Bit für 58 Zeichen, also 2,517 Bit/Zeichen, das liegt ca. 1,4% über der Entropie. Zwei weitere Entropiecodierungen sind der Shannon-Fano Code und die Arithmetische Codierung
Beim Shannon Fano Code sortiert man die Zeichen in absteigender Auftrittswahrscheinlichkeit und teilt sie in zwei Mengen, deren Summe der Wahrscheinlichkeiten etwa gleich groß sind. Die Codes in der linke Menge beginnen mit einem 0-bit, die in der rechten mit einem 1-bit., die Aufteilung in Mengen wird so lange wiederholt bis jede Menge ein Element enthält. In der Praxis ist der vom Schüler Fanos entwickelte Huffman Code immer besser.
Die Arithmetische Codierung bildet eine Datenquelle auf eine reelle Zahl zwischen 0 und 1 ab. Dabei bekommt jedes zu codierende Zeichen ein Subintervall dieses Bereichs. Je häufiger das Zeichen ist, desto größer ist das Subintervall. Obwohl dieses Verfahren optimal ist, also immer sehr nahe an die Entropie heranreicht, ist es in der Praxis von geringer Bedeutung, das es sehr rechen aufwändig ist und die meisten Implementierungen patentiert sind.