Der Huffman-Code
Verlustfreie Datenkomprimierung mit präfixfreien Codes variabler Länge – häufig vorkommende Zeichen bekommen kurze Codes, seltene Zeichen längere.
Der Huffman-Algorithmus stellt eine Methode zur verlustfreien Komprimierung von Daten dar. Er wurde 1952 von David A. Huffman entwickelt. Der Algorithmus erzeugt aus Symbolen und deren Verteilung im zu komprimierenden Text Binärbäume, aus welchen präfixfreie Codierungen variabler Länge (Huffman-Codes) gewonnen werden. Diese codieren den Text mit minimalem Speicherplatz. Die Codierung muss verlustlos sein, d. h. die Nachricht muss eindeutig und ohne Verlust von Information decodiert werden können. Häufig vorkommende Buchstaben werden mit kürzeren Codewörtern codiert, selten vorkommende Buchstaben können längere Codewörter haben.
- Initialisierung: Alle Zeichen werden Knoten zugeordnet und nach ihrer Häufigkeit in einer Liste sortiert.
-
Solange die Liste der Knoten noch mehr als ein Element enthält:
- (a) Entnehme die beiden Elemente mit der geringsten Häufigkeit und erzeuge einen Elternknoten.
- (b) Weise dem Elternknoten die Summe der Häufigkeiten der Kinder zu und füge ihn der Liste hinzu.
- (c) Den Zeigern des Elternknotens wird der Code 0, 1 zugeordnet (Reihenfolge prinzipiell beliebig).
- Trage die Buchstaben in die Blätter ein. Deren Häufigkeiten kannst du unter das jeweilige Blatt schreiben.
- Fasse die beiden vaterlosen Blätter mit den geringsten Häufigkeiten in einem Vaterknoten zusammen und addiere die Häufigkeiten der Kinder.
- Führe das Verfahren fort, bis es nur noch einen vaterlosen Knoten gibt (die Wurzel).
- Den linken Kanten wird je eine 0, den rechten je eine 1 zugewiesen (Reihenfolge prinzipiell beliebig).
Beispiel: „ABRAKADABRA"
Schauen wir es uns an einem Beispiel von Alice und Bob an: „ABRAKADABRA". Wir stellen eine Häufigkeitstabelle (Häufigkeitsanalyse) auf:
| Buchstabe | Häufigkeit |
|---|---|
| A | 5 |
| B | 2 |
| D | 1 |
| K | 1 |
| R | 2 |
1 Buchstaben in die Blätter eintragen
Es werden die Buchstaben und ihre Häufigkeiten in die bzw. unter die Blätter eingetragen.
2 Erste Zusammenführung (K + D)
Es gibt noch vaterlose Knoten: A, B, K, D und R. Fasse die beiden vaterlosen Blätter mit den geringsten Häufigkeiten (K und D haben beide den Wert 1) in einem Vaterknoten zusammen, indem die Häufigkeiten der Kinder addiert werden. Trage die Summe 2 im Vaterknoten ein.
3 Zweite Zusammenführung (B + KD)
Es gibt noch vaterlose Blätter: A, B, R. Fasse die zwei Knoten mit den geringsten Häufigkeiten in einem Vaterknoten zusammen (z. B. den Vaterknoten mit dem Wert 2 und Blatt B mit dem Wert 2) und addiere die Häufigkeiten der Kinder. Trage die Summe 4 im Vaterknoten ein.
4 Dritte Zusammenführung (BR + DK)
Es gibt noch einen vaterlosen Blatt: A. Fasse aber zuerst die Knoten mit den geringsten Häufigkeiten zusammen – den Vaterknoten (BR 4) und DK mit dem Wert 2 – in einem Vaterknoten und addiere die Häufigkeiten der Kinder. Trage die Summe 6 im Vaterknoten ein.
5 Wurzel bilden (BDKR + A)
Füge nun Blatt A zum Vaterknoten (BDKR) hinzu. Summiere die Häufigkeiten (Vaterknoten mit Wert 6 und Blatt A mit Wert 5) in einem Vaterknoten. Trage die Summe 11 im Vaterknoten ein – die Wurzel ist erreicht.
6 Codierung ablesen
Es gibt kein vaterloses Blatt mehr und genau einen vaterlosen Knoten (die Wurzel). Den linken Kanten wird je eine 0, den rechten je eine 1 zugewiesen. Nun kann man die Codierung für die verschiedenen Buchstaben ablesen: Starte bei der Wurzel und folge den Kanten bis zu einem Blatt. Schreibe 0 beim Gang nach links und 1 beim Gang nach rechts.
Beispiel „A": Von der Wurzel gehst du erst nach links und erreichst Blatt „A". Also ist das Codewort für „A" = 0. So entsteht die Code-Tabelle.
Zusammenfassung des Algorithmus
- Häufigkeitstabelle aufstellen.
- Erstelle die Huffman-Liste.
- Wiederhole die Zusammenführung der beiden mit der geringsten Häufigkeit beschrifteten Bäume so lange, bis die Huffman-Liste nur noch aus einem Baum – dem Huffman-Baum – besteht.
- Schreibe an den linken Kanten je eine 0 und an den rechten Kanten eine 1 auf (Reihenfolge prinzipiell beliebig).
Dekodierung
Was passiert, wenn Bob eine codierte Nachricht von Alice erhält und diese decodieren will? Um sie decodieren zu können, muss Bob natürlich wissen, wie der Huffman-Baum aussieht – ansonsten weiß er nicht, wie Alice codiert hat. Er geht Bit für Bit durch das codierte Wort und den Baum wie folgt:
- Starte bei der Wurzel.
- Wenn eine 0 im codierten Wort ist, gehe nach links.
- Wenn eine 1 im codierten Wort ist, gehe nach rechts.
- Angekommen bei einem Blatt: Schreibe den Buchstaben im Blatt auf und beginne wieder bei der Wurzel (bei 1.).
