Entropiecodierung nach Huffman
Inhaltsverzeichnis
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.
