Huffman-Codierung

engl.: Huffman Coding

Themengebiet:

Allgemeine Informatik

Bedeutung:
Ein Quellcodierungsverfahren zur verlustfreien Redundanzreduktion. 1952 entwickelt von David A. Huffman. Dabei handelt es sich um eine Technik, die auf variablen Wortlängen beruht und den häufig vorkommenden Datenmustern kurze und den selteneren längere Codes zuweist. Auf diese Weise ist eine Annäherung an das theoretische Minimum bei der Quellcodierung möglich. Datenreduzierung um 50 % ist keine Seltenheit. Der Algorithmus besteht aus vier Schritten. Es wird dabei ein Binärbaum aufgebaut, bei dem die zu codierenden Symbole als Blätter (Endknoten) auftreten:
- Man schreibe alle zu codierenden Symbole mit ihrer Wahrscheinlichkeit des Auftretens (Häufigkeitsverteilung) auf.
- Man wähle die zwei Symbole mit der geringsten Wahrscheinlichkeit und markiere sie. Man nehme das Symbol mit der nächst höheren Wahrscheinlichkeit und verbinde es über zwei Kanten mit den ersten Symbolen. Danach setze man die Wahrscheinlichkeit beim zuletzt hinzugefügten Symbol auf die Summe der beiden damit verbundenen Symbole.
- Man wiederhole den letzten Schritt, bis alle Symbole bis auf eines (Wurzel) im Baum enthalten sind.
- Die Codierung eines Symboles ergibt sich aus dem Durchlaufen des Baums von der Wurzel aus, wobei an jeder Verzweigung ein Weg mit 0 und einer mit 1 definiert wird. Huffman-Code-Kompression wird in einer Vielzahl von Dateiformaten angewendet, so zum Beispiel bei JPG, MP3, PKZIP und anderen.

Zum Begriff:
Korrekturen/Ergänzungen schreiben
Letzte Änderung: 29.08.2008