Verlauf
Alle Kapitel anzeigen
voriges Kapitel
Das Grundprinzip der Huffman-Kodierung sieht folgendermaßen aus:
Ausgegangen wird von einer Häufigkeitszuordnung aller vorkommenden Zeichen, beispielsweise eine Tabelle wie diese:
| String: | Walter_war_alt (_ steht für Leerzeichen) | |||||||
| Zeichen: | W | a | l | t | e | r | w | _ |
| Häufigkeit: | 1 | 3 | 2 | 2 | 1 | 2 | 1 | 2 |
| In %: | 7,15 | 21,43 | 14,29 | 14,29 | 7,15 | 14,29 | 7,15 | 14,29 |
Dann werden im Baum jeweils die Endknoten mit der geringsten Auftrittswahrscheinlichkeit einem neuen Überknoten zugeordnet, dem die Summe der beiden Wahrscheinlichkeiten zugewiesen wird (hier gibt es oft mehrere Möglichkeiten den Baum aufzubauen, innerhalb eines fertigen Kodierbaumes sind die Codes aber natürlich eindeutig).
Das wiederholt sich so lange bis es einen Wurzelknoten gibt, in dem alle Knoten zusammengeführt werden. Um den Code für jedes Zeichen zu bekommen, beginnt man bei der Wurzel, also hier dem Knoten mit der Beschriftung 14 (= die Länge des Strings), den Weg bis zu dem benötigten Zeichen zurückzuverfolgen und notiert dabei immer die 0 oder 1 an der Verbindung zwischen den Knoten.
Den Vorgang für das Stringbeispiel "Walter war alt" sehen Sie in folgender Animation:
