Huffman-Kodierung

Dezember 2016

Huffman-Kodierung


David Huffman schlug 1952 eine statistische Methode vor, die die Zuweisung eines binären Code-Wortes zu verschiedenen zu komprimierenden Symbolen (Pixel oder Zeichen zum Beispiel) ermöglicht. Die Länge eines jeden Code-Wortes ist nicht identisch für alle Symbole: die häufigsten Symbole (die am häufigsten erscheinen) sind mit kleinen Code-Wörtern kodiert, während die seltensten Symbole längere binäre Codes erhalten. Man spricht von einer Kodierung mit variabler Länge (auf Englisch VLC für variable code length)
, die vorangestellt ist, um diesen Kodierungstyp zu bestimmen, denn kein Code ist Präfix eines anderen. So ist die Folge von kodierten Wörtern mit variabler Länge durchschnittlich kürzer als mit einer Kodierung von konstanter Größe.

Der Huffman-Kodierer legt einen geordneten Baum auf der Grundlage aller Symbole und ihrer Erscheinungshäufigkeit an. Die Zweige werden rekursiv begonnen mit den seltensten Symbolen konstruiert.

Die Konstruktion des Baumes erfolgt zuerst durch Anordnung der Symbole nach ihrer Erscheinungsfrequenz. Nacheinander werden die zwei Symbole mit der schwächsten Erscheinungsfrequenz aus der Liste entfernt und an einen Knoten geknüpft, dessen Gewicht der Summe der Häufigkeiten der beiden Symbole entspricht. Das Symbol mit dem niedrigsten Gewicht wird Zweig 1 zugeteilt, der nächste Zweig 0 und so weiter. Dabei wird jeder angelegte Knoten als neues Symbol angesehen, bis man einen einzigen Vorgängerknoten erreicht, der sich Wurzel nennt.
Der Code jedes Symbols enspricht der Folge des Codes am Weg entlang von diesem Zeichen aus bis zur Wurzel. Je "tiefer" das Symbol im Baum verwurzelt ist, des länger ist das Code-Wort.

Wie zum Beispiel der folgende Satz: "COMMENT_CA_MARCHE". Hier sind die Erscheinungshäufigkeiten der Buchstaben

MACE_HONTR
3222211111



Hier der entsprechende Baum :

arbre de huffman



Die jedem Zeichen entsprechenden Codes sind so, dass die häufigsten Codes kurz sind und diejenigen, die den seltensten Symbolen entsprechen, lang sind :

MACE_HONTR
001001100100111110111110101011010111



Die auf diesem Kodierungstyp basierten Komprimierungen ergeben gute Komprimierungssätze, besonders für monochrome Bilder (Faxe zum Beispiel). Man benutzt ihn vor allem bei den Empfehlungen T4 und T5 von ITU-T


Lesen Sie auch :


Huffman coding
Huffman coding
Código Huffman
Código Huffman
Codage de Huffman
Codage de Huffman
Codifica di Huffman
Codifica di Huffman
Codificação de Huffman
Codificação de Huffman
Das Dokument mit dem Titel « Huffman-Kodierung » aus CCM (de.ccm.net) wird zur Verfügung gestellt unter den Bedingungen der Creative Commons Lizenz. Sie dürfen das Dokument verwenden, verändern sowie Vervielfältigungen dieser Seite erstellen, unter den Bedingungen, die in der vorgenannten Lizenz erwähnt sind und unter der gleichzeitigen Bedingung, dass Sie im Rahmen Ihrer Verwendung, Veränderung oder Vervielfältigung nach außen hin klar und deutlich auf den Urheber (= de.ccm.net) des Dokuments hinweisen.