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 Wurzelnennt.
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
| M | A | C | E | _ | H | O | N | T | R |
| 3 | 2 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 1 |
Hier der entsprechende Baum :
Die jedem Zeichen entsprechenden Codes sind so, dass die häufigsten Codes kurz sind und diejenigen, die den seltensten Symbolen entsprechen, lang sind :
| M | A | C | E | _ | H | O | N | T | R |
| 00 | 100 | 110 | 010 | 011 | 1110 | 1111 | 1010 | 10110 | 10111 |
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
Letzte Änderung am Mittwoch 1 April 2009 à 14:16:20.