Huffman-Codierung einfach erklärt

Bei einem Code mit fester Länge besitzt jedes Zeichen gleich viele Bits. Die Grenzen zwischen den Codewörtern sind dadurch klar. Für fünf verschiedene Zeichen werden mindestens drei Bits pro Zeichen benötigt.

Variable Codewortlängen können Speicherplatz sparen. Sie müssen aber so gewählt werden, dass beim Lesen keine Mehrdeutigkeit entsteht.

Das Gegenbeispiel a→0, b→01, c→1 ist nicht präfixfrei: 0 ist der Anfang von 01. Deshalb kann 01 sowohl als b als auch als ac gelesen werden.

Der Code a→0, b→10, c→11 ist dagegen präfixfrei. Nach 0 steht sofort a fest; nach einer führenden 1 entscheidet das nächste Bit zwischen b und c.

Ausgangspunkt sind die absoluten Häufigkeiten der Zeichen. Jedes Zeichen beginnt als Blatt mit seinem Gewicht.

Der binäre Huffman-Algorithmus arbeitet anschließend von unten nach oben:

1. Wähle die beiden Wurzeln mit den kleinsten Gewichten.
2. Verbinde sie unter einem neuen Knoten.
3. Addiere ihre Gewichte und schreibe die Summe an den neuen Knoten.
4. Ordne den neuen Teilbaum wieder bei den übrigen Knoten ein.
5. Wiederhole das Verfahren, bis nur noch eine Wurzel übrig ist.
6. Beschrifte an jedem Knoten eine Kante mit 0 und die andere mit 1.

Weil der Algorithmus in jedem Schritt die aktuell kleinsten Gewichte auswählt, ist er ein Greedy-Algorithmus.

Bei gleichen Gewichten darfst du zwischen mehreren Knoten wählen. Dadurch können andere Bäume und Codewörter entstehen. Sie bleiben korrekt, wenn die Konstruktion vollständig durchgeführt wird und die Kanten an jedem Knoten eindeutig mit 0 und 1 beschriftet sind.

Beim Codieren ersetzt du jedes Zeichen der Reihe nach durch sein Codewort. Du benötigst dafür das fertige Codebuch.

Zum Decodieren brauchst du denselben Baum oder dasselbe Codebuch:

1. Starte an der Wurzel.
2. Folge für jedes Bit der Kante mit derselben Beschriftung.
3. Gib beim Erreichen eines Blattes das zugehörige Zeichen aus.
4. Starte für das nächste Bit wieder an der Wurzel.

Im Beispiel zerfällt der Anfang 010110 eindeutig in 0 | 10 | 110. Das ergibt a | b | r.

Die Länge eines codierten Textes erhältst du, indem du für jedes Zeichen seine Häufigkeit mit seiner Codewortlänge multiplizierst und alle Produkte addierst.

Für abrakadabra gilt:

$$B = 5 \cdot 1 + 2 \cdot 2 + 2 \cdot 3 + 1 \cdot 4 + 1 \cdot 4 = 23$$

Der Huffman-Code benötigt für den eigentlichen codierten Text also 23 Bit.

Ein fester Code braucht bei fünf verschiedenen Zeichen drei Bits pro Zeichen. Für die elf Zeichen wären das:

$$11 \cdot 3 = 33\text{ Bit}$$

Beim codierten Text werden somit 10 Bit eingespart. Die mittlere Codewortlänge beträgt:

$$\bar l = \frac{23}{11} \approx 2{,}09\text{ Bit pro Zeichen}$$

Huffman minimiert die gewichtete mittlere Codewortlänge unter den betrachteten symbolweisen Präfixcodes, wenn die Symbolhäufigkeiten bekannt sind. Diese Aussage bedeutet nicht, dass Huffman jedes andere denkbare Kompressionsverfahren übertrifft.

Die Greedy-Entscheidung ist hier erfolgreich: Die beiden seltensten Symbole dürfen in einem optimalen Baum besonders tief als Geschwister liegen. Nach ihrem Zusammenfassen entsteht dasselbe Optimierungsproblem mit einem Symbol weniger. Durch diese wiederholte Reduktion entsteht ein optimaler Präfixbaum.

Trotzdem wird nicht jede Datei insgesamt kleiner:

• Sind die Zeichen fast gleich häufig, unterscheiden sich die Codewortlängen nur wenig.
• Bei kurzen Daten kann das zusätzlich benötigte Codebuch mehr Platz beanspruchen als eingespart wird.
• Ein statischer Huffman-Code passt zu den Häufigkeiten, aus denen er konstruiert wurde. Bei einer stark anderen Verteilung kann er ungeeignet sein.
• Verfahren, die ganze Zeichenfolgen oder andere Datenmuster ausnutzen, betrachten ein anderes Optimierungsproblem.