Wikipedia · einfach zusammengefasst · Stand
Huffman-Kodierung
Die Huffman-Kodierung ist eine Form der Entropiekodierung, die 1952 von David A. Huffman entwickelt und in der Abhandlung A Method for the Construction of …
Inhalt6 Abschnitte
Grundidee und Bedeutung
Die Huffman-Kodierung ist eine Entropiekodierung zur verlustfreien Kompression. Sie wurde 1952 von David A. Huffman entwickelt und ordnet einer festen Anzahl von Quellsymbolen Codewörter mit variabler Länge zu. Häufig vorkommende Zeichen erhalten kurze Codewörter, selten vorkommende Zeichen längere. Dadurch können Daten oft kürzer dargestellt werden als mit einer Kodierung, die für jedes Symbol gleich viele Bits verwendet.
Ein Huffman-Code ist ein Präfixcode: Kein Codewort darf der Anfang eines anderen Codewortes sein. Deshalb braucht man, anders als beim Morsecode, keine Trennzeichen zwischen den Codewörtern. Für die eindeutige Dekodierung muss der Code außerdem die Kraftsche Ungleichung erfüllen. Die Länge der Codewörter soll möglichst dem Informationsgehalt der Symbole entsprechen.
Die Darstellung erfolgt mit einem k-nären Wurzelbaum, dem Huffman-Baum. Die Blätter stehen für die Quellsymbole, der Pfad von der Wurzel zu einem Blatt ergibt das jeweilige Codewort. Im Gegensatz zur Shannon-Fano-Kodierung wird der Baum von den Blättern zur Wurzel aufgebaut, also bottom-up. Der entstehende Baum liefert garantiert eine optimale präfixfreie Kodierung unter der Voraussetzung, dass die Auftrittswahrscheinlichkeiten der Symbole bekannt sind.
Begriffe und Konstruktion
Für den Algorithmus werden einige Begriffe verwendet: Das Quellalphabet X ist der Zeichenvorrat der Quellsymbole. p_x ist die A-priori-Wahrscheinlichkeit beziehungsweise relative Häufigkeit eines Symbols x. Das Codealphabet C ist der Zeichenvorrat der Codewörter. m ist die Mächtigkeit |C| des Codealphabetes, also die Anzahl seiner verschiedenen Zeichen.
Zuerst wird für jedes Quellsymbol die relative Häufigkeit bestimmt: Man zählt, wie oft jedes Zeichen vorkommt, und teilt durch die Anzahl aller Zeichen. Dann wird für jedes Quellsymbol ein einzelner Knoten erzeugt, in dem die Häufigkeit gespeichert ist. Anschließend werden wiederholt m Teilbäume mit den m geringsten Häufigkeiten in ihrer Wurzel ausgewählt, zu einem neuen Teilbaum zusammengefasst und in dessen Wurzel die Summe der Häufigkeiten notiert. Diese Auswahl ist im Allgemeinen nicht eindeutig. Der Vorgang endet, wenn nur noch ein einziger Baum übrig ist.
Für das Codebuch wird jedem Kind eines Knotens eindeutig ein Zeichen aus dem Codealphabet zugeordnet. Für jedes Quellsymbol, also jedes Blatt im Baum, liest man das Codewort ab, indem man an der Wurzel beginnt und die Codezeichen auf den Kanten des Pfades von oben nach unten sammelt. Zum Kodieren wird dann jedes Quellsymbol eingelesen, im Codebuch nachgeschlagen und durch das zugehörige Codewort ersetzt.
Mittlere Wortlänge und Beispiel
Die mittlere Länge eines Codeworts kann als gewichtete Summe der Codewortlängen berechnet werden: {\overline {l}}=\sum _{x\in X}p_{x}l_{x}. Dabei wird die Länge eines Codeworts mit der Häufigkeit seines Symbols gewichtet. Alternativ kann man die Auftrittswahrscheinlichkeiten an allen Zwischenknoten des Huffman-Baums summieren. Bei ausschließlich gleicher Häufigkeit der zu codierenden Elemente gilt l=\log _{2} m, wobei m\in N die Anzahl der zu codierenden Elemente ist.
Ein Beispiel verwendet das Quellalphabet X:=\{a,b,c,d\}, das binäre Codealphabet C:=\{0,1\} und m=|C|=2. Der Text aababcabcd hat die relativen Häufigkeiten p_a=0{,}4, p_b=0{,}3, p_c=0{,}2 und p_d=0{,}1. Aus dem Huffman-Baum ergibt sich das Codebuch: a\rightarrow 1, b\rightarrow 01, c\rightarrow 001, d\rightarrow 000.
Damit wird der Text als Folge der Codewörter kodiert: a, a, b, a, b, c, a, b, c, d wird zu 1, 1, 01, 1, 01, 001, 1, 01, 001, 000. Die mittlere Codewortlänge beträgt {\overline {l}}=0{,}4\cdot1+0{,}3\cdot2+0{,}2\cdot3+0{,}1\cdot3=1{,}9 Bit. Eine naive Kodierung der 4 Symbole würde \log_2(4)=2 Bit pro Symbol benötigen. Die Entropie liegt bei ungefähr H(X)\approx1{,}846 Bit je Symbol; weil der Informationsgehalt je Quellsymbol keine ganze Zahl ist, bleibt eine Rest-Redundanz.
Dekodierung und Pseudocode-Idee
Zur Dekodierung eines klassisch Huffman-kodierten Datenstroms benötigt man das im Kodierer erzeugte Codebuch. Der Dekodierer baut den Huffman-Baum wieder auf. Dann wird jedes eingehende Bit verarbeitet, indem man von der Wurzel aus dem entsprechenden Pfad im Baum folgt. Sobald ein Blatt erreicht ist, ist dessen Symbol das gesuchte Quellsymbol. Danach beginnt die Dekodierung des nächsten Symbols wieder an der Wurzel.
Im Beispiel mit dem Codebuch a\rightarrow1, b\rightarrow01, c\rightarrow001, d\rightarrow000 wird die empfangene Nachricht 1101101001101001000 schrittweise gelesen. Weil der Code präfixfrei ist, erkennt der Dekodierer eindeutig, wann ein Codewort endet. Daraus entsteht der dekodierte Text aababcabcd.
Der Pseudocode beschreibt den Aufbau des Huffman-Baums mit einem Min-Heap und einer Vorrangwarteschlange. Zuerst werden alle Knoten mit Symbol und Häufigkeit eingefügt. Solange mehr als ein Knoten in der Warteschlange liegt, werden die zwei Knoten mit der kleinsten Häufigkeit entfernt, zu einem neuen inneren Knoten mit der Summe ihrer Häufigkeiten verbunden und wieder eingefügt. Am Ende bleibt der Wurzelknoten. Das Codebuch wird rekursiv erzeugt: Beim Gang nach links wird zum Codewort „0“ angefügt, beim Gang nach rechts „1“. Wird ein Blatt erreicht, wird die Kombination aus Symbol und Codewort gespeichert.
Optimalität und Laufzeit
Für die mittlere Codewortlänge {\overline {l}} eines Huffman-Codes gilt \mathrm{H}(X)\leq {\overline {l}}\leq \mathrm{H}(X)+1. Im Mittel benötigt jedes Codesymbol also mindestens so viele Stellen wie sein Informationsgehalt, höchstens jedoch eine mehr. Genau {\overline {l}}=\mathrm{H}(X) gilt dann, wenn alle Wahrscheinlichkeiten Zweierpotenzen sind, also 2^{-m_x} mit m_x\in\mathbb{N}^{+}. Dann ist die Huffman-Kodierung optimal bezüglich der Entropie.
Wenn man n Quellsymbole zu einem großen Symbol y zusammenfasst, gilt für die mittleren Codesymbollängen {\overline {l}}_y: \mathrm{H}_n(X)\leq {\overline {l}}_y\leq \mathrm{H}_n(X)+\frac{1}{n}. Mit wachsender Anzahl gemeinsam kodierter Quellsymbole nähert sich die mittlere Codewortlänge asymptotisch der Entropie; die Huffman-Kodierung ist also asymptotisch optimal. Die Optimalität kann mit vollständiger Induktion bewiesen werden.
Für die Laufzeit sei n die Anzahl der Zeichen des Originaltexts und d die Anzahl der verschiedenen Zeichen. Das Zählen der Häufigkeiten braucht O(n), weil jedes Zeichen betrachtet wird. Die Verarbeitung der verschiedenen Zeichen läuft O(d)-mal. Die while-Schleife arbeitet mit einer Vorrangwarteschlange aus d Elementen und benötigt O(d) Iterationen. Bei Verwendung eines Heaps kosten die Operationen pop und push jeweils O(\log(d)). Insgesamt ergibt sich für die Huffman-Kodierung die Laufzeit O(n+d\cdot\log(d)).
Adaptive Variante
Bei der adaptiven Huffman-Kodierung wird der Baum laufend aktualisiert. Zu Beginn wird eine Wahrscheinlichkeitsverteilung für alle Quellsymbole angenommen; bei völliger Unkenntnis der Quelle ist das eine Gleichverteilung. Mit jedem neuen Quellsymbol wird der Baum angepasst, wodurch sich auch die Codesymbole ändern können.
Der Dekodierer kann dieselben Aktualisierungsschritte nachvollziehen. Deshalb muss bei dieser Methode kein Codebuch übertragen werden. Ein Datenstrom kann dadurch on-the-fly kodiert werden. Der Nachteil ist die deutlich höhere Anfälligkeit für Übertragungsfehler: Ein einzelner Fehler kann ab der Fehlerstelle zu einer komplett falschen Dekodierung führen.
