Huffman-Codierung: Verlustfreie Kompression verstehen

Kurz: Die Huffman-Codierung gibt häufigen Zeichen kurze und seltenen Zeichen lange Bitfolgen, sodass Daten ohne Informationsverlust kleiner werden.

Genauer: Normalerweise belegt jedes Zeichen gleich viele Bits (ASCII: 8). Aber Buchstaben kommen unterschiedlich häufig vor (im Deutschen ist „e“ sehr häufig, „q“ selten). David Huffman (1952) fand das optimale präfixfreie Verfahren: häufige Zeichen → kurze Codes. Es steckt in ZIP/DEFLATE, PNG, JPEG, MP3.

Im Detail

Das Prinzip

1. Häufigkeiten zählen (Wie oft kommt jedes Zeichen vor?).
2. Aus den Zeichen Knoten bauen und immer die zwei seltensten zu einem neuen Knoten zusammenfassen (Summe der Häufigkeiten), bis ein Baum entsteht.
3. Pfad von der Wurzel zum Zeichen: links = 0, rechts = 1 → Code des Zeichens. Präfixfrei: Kein Code ist der Anfang eines anderen, deshalb lässt sich der Bitstrom eindeutig zurückübersetzen, ohne Trennzeichen.

Beispiel

Text „ABRAKADABRA“ (11 Zeichen): A=5, B=2, R=2, K=1, D=1.

1. K(1) + D(1) → KD(2)
2. B(2) + R(2) → BR(4)
3. KD(2) + BR(4) → KDBR(6)
4. A(5) + KDBR(6) → Wurzel(11) Links = 0, rechts = 1 ergibt zum Beispiel: A = 0, K = 100, D = 101, B = 110, R = 111. Bitlänge: 5·1 + 1·3 + 1·3 + 2·3 + 2·3 = 23 Bit statt 11 · 8 = 88 Bit (ohne Codetabelle). Die genauen Codes hängen von der Reihenfolge bei gleichen Häufigkeiten ab; die Gesamtlänge ist optimal.

Eigenschaften

• Verlustfrei: Dekodierung liefert die Originaldaten exakt.
• Optimal unter allen Symbol-für-Symbol-Präfixcodes; Grenze gibt die Entropie (Informationsgehalt). Besser sind Verfahren, die Muster nutzen (LZ77/LZ78, LZW) oder Bruchteile von Bits (arithmetische Codierung, ANS).
• Die Codetabelle (Baum) muss mitgesendet oder adaptiv aufgebaut werden.
• Bei gleichverteilten Zeichen bringt Huffman nichts (zum Beispiel bei schon komprimierten oder verschlüsselten Daten).

Praxis

DEFLATE (ZIP, gzip, PNG) = LZ77 + Huffman. JPEG nutzt nach Transformation und Quantisierung Huffman für die Koeffizienten. Morse-Code hat ein ähnliches Prinzip (häufiges „E“ = ein Punkt). Zum Üben: Zeichenhäufigkeiten eines Textes zählen, Baum zeichnen, Codes ableiten und die Ersparnis berechnen. In Python lässt sich das mit heapq in wenigen Zeilen programmieren. Verlustfrei vs. verlustbehaftet: siehe Kompression.

Siehe auch: Kompression, Heap und Prioritätswarteschlange, ASCII und Zeichensätze, ZIP-Dateien