Huffman-Code (auch Huffman-Kodierung oder Huffman-Codierung) ist ein 1952 von David A. Huffman entwickeltes Verfahren der Entropiecodierung: Häufig vorkommende Zeichen erhalten kurze Bitfolgen, seltene längere. Dadurch wird die mittlere Codierungslänge minimiert und die Daten lassen sich verlustfrei komprimieren. Der Huffman-Code ist ein Präfixcode — kein Codewort ist der Anfang eines anderen —, sodass die Bitfolge eindeutig und ohne Trennzeichen decodierbar ist.
So entsteht der Code
Zunächst wird gezählt, wie oft jedes Symbol in den Daten vorkommt. Die seltensten Symbole werden paarweise zu einem Knoten zusammengefasst, dessen Gewicht die Summe beider Häufigkeiten ist; das wiederholt sich, bis ein Baum entsteht (Huffman-Baum). Jede Kante nach links bedeutet 0, nach rechts 1. Der Pfad von der Wurzel zu einem Symbol ergibt sein Codewort: Je häufiger das Symbol, desto kürzer der Pfad und damit das Codewort. Die resultierende mittlere Länge kommt der Entropie der Datenquelle so nahe, wie es eine Einzelsymbol-Codierung überhaupt kann — wie Redundanz und Entropie zusammenhängen, erklärt der Artikel Datenkompression.
Eigenschaften
- Optimalität: Unter der Annahme fester Symbolwahrscheinlichkeiten liefert Huffman einen Code mit minimaler mittlerer Länge — kein anderer Präfixcode ist kürzer.
- Präfixfreiheit: Kein Codewort ist Präfix eines anderen, dadurch ist die Decodierung eindeutig und nebenläufig möglich.
- Statisch oder adaptiv: Die Variante mit fester Häufigkeitstabelle braucht die Tabelle im Datenstrom; adaptive Verfahren bauen den Baum während des Lesens auf und sparen diese Übertragung.
Wo Huffman steckt
DEFLATE — das Format hinter ZIP, gzip und PNG — kombiniert das LZ77-Wörterbuchverfahren mit einer Huffman-Codierung der Ausgabesymbole. Auch JPEG nutzt im verlustfreien Modus und bei der Entropiecodierung der DCT-Koeffizienten eine Huffman-artige Codierung, ebenso MP3 im Rahmen der Bitstrom-Codierung. Damit ist der Huffman-Code die am weitesten verbreitete Entropiecodierung überhaupt.
Verwandte Grundlagen: Verlustfreie Kompression, LZ77, Lauflängencodierung.