|
Bei dem Erzeugen des Huffman-Codes kommt es in erster Linie darauf an wieviel Zeichen zu decodieren sind plus Leerzeichen. Nun ermittelt das folgende Programm die unterschiedliche Häufigkeit der Buchstaben eines Zeichenfeldes, und trägt sie dann in ein Feld count[0-26] ein.
Nun wieder ein Beispiel das wir kodieren , die Zeichenfolge lautet:
"A SIMPLE STRING TO BE ENCODED USING A MINIMAL NUMBERS OF BITS".
Der erste Schritt ist der Aufbau eines Tries entsprechend seiner Häufigkeiten, dazu sollte man
sich eine Buchstabentabelle machen.
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
k 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
count [k] 11 3 3 1 2 5 1 2 0 6 0 0 2 4 5 3 1 0 2 4 3 2 0 0 0 0 0
Danach kann man schon mit dem Trie beginnen Man fängt an, in dem man die Buchstaben (Knoten) mit der Häufigkeit 0 wegläßt, und alle anderen Knoten mit ihrer Häufigkeit in einer Ebene darstellt. Nun nimmt man die Knoten mit den niedrigsten Häufigkeiten und fasse sie zusammen. Man nimmt nun die nächst höhere Häufigkeit und fasse sie wieder zusammen, dies geht so lange weiter bis alle Häufigkeiten in einem Baum dargestellt sind.
Beachten muß man jedoch, daß sich die Knoten mit geringer Häufigkeit weit unten und Knoten mit hoher Häufigkeit weit oben im Baum befinden.
Die quadratischen Knoten sind Häufigkeitszähler und die runden Knoten sind Summen Knoten und lassen sich durch ihre Nachfolger wieder darstellen.
|
