Informationstheorie/Entropiecodierung nach Huffman

1. Informationstheorie
2. Quellencodierung – Datenkomprimierung
3. Entropiecodierung nach Huffman

• Vorherige Seite
• Nächste Seite

• Vorherige Seite
• Nächste Seite

Der Huffman–Algorithmus

Wir setzen nun voraus, dass die Quellensymbole qν einem Alphabet $\{q_μ\}$ = {A, B, C, ...} mit dem Symbolumfang M entstammen und statistisch voneinander unabhängig seien. Beispielsweise gelte für den Symbolumfang $M$ = 8:

David A. Huffman hat 1952 – also kurz nach Shannons bahnbrechenden Veröffentlichungen – einen Algorithmus zur Konstruktion von optimalen präfixfreien Codes angegeben. Dieser Huffman–Algorithmus soll hier ohne Herleitung und Beweis angegeben werden, wobei wir uns hier auf Binärcodes beschränken. Das heißt: Für die Codesymbole gelte stets $c_ν$ ∈ {0, 1}. Hier ist das Rezept:

• Man ordne die Symbole nach fallenden Auftrittswahrscheinlichkeiten.
• Man fasse die zwei unwahrscheinlichsten Symbole zu einem neuen Symbol zusammen.
• Man wiederhole (1) und (2), bis nur mehr zwei (zusammengefasste) Symbole übrig bleiben.
• Man codiert die wahrscheinlichere Symbolmenge mit 1 und die andere Menge mit 0.
• Man ergänzt in Gegenrichtung (also von unten nach oben) die jeweiligen Binärcodes der aufgespaltenen Teilmengen entsprechend den Wahrscheinlichkeiten mit 1 bzw. 0.

Ohne Einschränkung der Allgemeingültigkeit setzen wir voraus, dass die $M$ = 6 Symbole A, ... , F bereits entsprechend ihren Wahrscheinlichkeiten geordnet sind:

Durch paarweises Zusammenfassen und anschießendem Sortieren erhält man in fünf Schritten die folgenden Symbolkombinationen (resultierende Wahrscheinlichkeiten in Klammern):

1. A (0.30), B (0.24), C (0.20), EF (0.14), D (0.12),

2. A (0.30), EFD (0.26), B (0.24), C (0.20),

3. BC (0.44), A (0.30), EFD (0.26),

4. AEFD (0.56), BC (0.44),

5. Root AEFDBC (1.00).

Rückwärts (gemäß den Schritten 5 bis 1) erfolgt dann die Zuordnung zu Binärsymbolen. Ein „x” weist darauf hin, dass in den nächsten Schritten noch Bits hinzugefügt werden müssen:

5. AEFD → 1x, BC → 0x,

4. A → 11, EFD → 10x,

3. B → 01, C → 00,

2. EF → 101x, D → 100,

1. E → 1011, F → 1010.

Die Unterstreichungen markieren die endgültige Binärcodierung.

Zum Begriff „Entropiecodierung”

Wir gehen weiterhin von den Wahrscheinlichkeiten und Zuordnungen des letzten Beispiels aus:

Von den sechs Quellensymbolen werden also drei mit je zwei Bit, eines mit drei Bit und zwei Symbole ( E und F ) mit vier Bit codiert. Die mittlere Codewortlänge ergibt sich damit zu

Aus dem Vergleich mit der Quellenentropie $H$ = 2.365 bit/Quellensymbol erkennt man die Effizienz der Huffman–Codierung.

Es gibt keinen präfixfreien (⇒ sofort decodierbaren) Code, der allein unter Ausnutzung der Auftrittswahrscheinlichkeiten zu einer kleineren mittleren Codewortlänge führt als der Huffman–Code.

In diesem Sinne ist der Huffman–Code optimal. Wären die Symbolwahrscheinlichkeiten

so würde für die Entropie und für die mittlere Codewortlänge gleichermaßen gelten:

Hinweis: Aus Platzgründen ist hier der Logarithmus dualis „log2” mit „ld” bezeichnet. Aus dieser Eigenschaft erklärt sich der Begriff Entropiecodierung. Man versucht bei dieser Form von Quellencodierung, die Länge $L_μ$ der Binärfolge (bestehend aus Nullen und Einsen) für das Symbol $q_μ$ gemäß der Entropieberechnung wie folgt an dessen Auftrittswahrscheinlichkeit $p_μ$ anzupassen:

Natürlich gelingt das nicht immer, sondern nur dann, wenn alle Auftrittswahrscheinlichkeiten $p_μ$ in der Form $2^{–k} ( $k$ = 1, 2, 3, ... ) dargestellt werden können. In diesem Sonderfall – und nur in diesem – stimmt die mittlere Codewortlänge $L_M$ exakt mit der Quellenentropie $H$ überein (siehe zweites Zahlenbeispiel). Nach dem Quellencodierungstheorem gibt es keinen (decodierbaren) Code, der im Mittel mit weniger Binärzeichen pro Quellensymbol auskommt. =='"`UNIQ--h-2--QINU`"'Darstellung des Huffman–Codes als Baumdiagramm== Häufig wird für die Konstruktion des Huffman–Codes eine '''Baumstruktur''' verwendet.Für das bisher betrachtete Beispiel zeigt diese die folgende Grafik: Man erkennt: *Bei jedem Schritt des Huffman–Algorithmus werden die beiden Zweige mit den jeweils kleinsten Wahrscheinlichkeiten zusammengefasst. Der Knoten im Schritt 1 fasst die zwei Symbole '''E''' und '''F''' mit den aktuell kleinsten Wahrscheinlichkeiten zusammen. Dieser Knoten ist mit $p_E$ + $p_F$ = 0.14 beschriftet. *Der vom Symbol mit der kleineren Wahrscheinlichkeit (hier '''F''') zum Summenknoten verlaufende Zweig ist blau eingezeichnet, der andere rot. Nach fünf Schritten ist man bei der Baumwurzel („Root”) mit der Gesamtwahrscheinlichkeit 1 angelangt. Verfolgt man nun den Verlauf von der Wurzel (in obiger Grafik mit gelber Füllung) zu den einzelnen Symbolen zurück, so kann man aus den Farben der einzelnen Zweige die Symbolzuordnung ablesen. Mit den Zuordnungen „rot” → '''1''' und „blau” → '''0''' ergibt sich beispielsweise von der Wurzel zu Symbol * '''A''': rot, rot → '''11''', *'''B''': blau, rot → '''01''', *'''C''': blau, blau → '''00''', *'''D''': rot, blau, blau → '''100''', *'''E''': rot, blau, rot, rot → '''1011''', *'''F''': rot, blau, rot, blau → '''1010'''. Die Zuordnung „rot” → 0 und „blau” → 1 würde ebenfalls zu einem optimalen präfixfreien Huffman–Code führen. Die folgende Grafik zeigt die Huffman–Codierung von 49 Symbolen $q_ν$ ∈ { '''A''', '''B''', '''C''', '''D''', '''E''', '''F'''} mit der auf der letzten Seite hergeleiteten Zuordnung. Die binäre Codesymbolfolge weist die mittlere Codewortlänge $L_M$ = 125/49 = 2.551 auf. Die Farben dienen ausschließlich zur besseren Orientierung. Aufgrund der kurzen Quellensymbolfolge ( $N$ = 49 ) weichen die Auftrittshäufigkeiten $h_A$, ... , $h_F$ der simulierten Folgen signifikant von den vorgegebenen Wahrscheinlichkeiten $p_A$, ... , $p_F$ ab: Damit ergibt sich ein etwas größerer Entropiewert: Würde man den Huffman–Code mit diesen „neuen” Wahrscheinlichkeiten $h_A$, ... , $h_F$ bilden, so ergäben sich folgende Zuordnungen: Nun würden nur '''A''' und '''C''' mit zwei Bit dargestellt, die anderen vier Symbole durch jeweils drei Bit. Die Codesymbolfolge hätte dann eine Länge von (16 + 9) · 2 + (7 + 7 + 5 + 5) · 3 = 122 Bit, wäre also um drei Bit kürzer als nach der bisherigen Codierung. Die mittlere Codewortlänge wäre dann $L_M$ = 122/49 ≈ 2.49 bit/Quellensymbol anstelle von $L_M$ ≈ 2.55 bit/Quellensymbol. Dieses Beispiel lässt sich wie folgt interpretieren: *Die Huffman–Codierung lebt von der (genauen) Kenntnis der Symbolwahrscheinlichkeiten. Sind diese sowohl dem Sender als auch dem Empfänger bekannt, so ist die mittlere Codewortlänge $L_M$ oft nur unwesentlich größer als die Quellenentropie $H$. *Insbesondere bei kleinen Dateien kann es zu Abweichungen zwischen den (erwarteten) Symbolwahrscheinlichkeiten $p_μ$ und den (tatsächlichen) Symbolhäufigkeiten $h_μ$ kommen. Besser wäre es hier, für jede Datei einen eigenen Huffman–Code zu generieren, der auf den tatsächlichen Gegebenheiten ( $h_μ$ ) basiert.

• In diesem Fall muss aber dem Decoder auch der spezifische Huffman–Code mitgeteilt werden. Dies führt zu einem gewissen Overhead, der nur wieder bei längeren Dateien vernachlässigt werden kann. Bei kleinen Dateien lohnt sich dieser Aufwand nicht.