Bestimmung der Zeichenhäufigkeiten:

Die dynamische Bestimmung der Zeichenhäufigkeiten ergibt:

`a':

5 mal

`b':

2 mal

`r':

2 mal

`k':

1 mal

`d':

1 mal

Die beiden seltensten Zeichen in ,,abrakadabra`` sind `k' und `d'. Zur Ermittlung der Huffman-Codierung -wenige Bits für häufige Zeichen, viele Bits für seltene Zeichen - bauen wir einen Binärbaum auf. Dazu beginnen wir mit den beiden seltensten Zeichen und codieren diese mit 0 und 1. Codieren wir also k mit 0 und d mit 1. Die Codierung lautet bis jetzt:

`k':

0

`d':

1

Nun fassen wir die Häufigkeiten dieser beiden Zeichen zusammen und suchen wieder die beiden seltensten. Das sind dann `r' und `k' mit `d' zusammen. Hiervon wird wieder eines mit 0, das andere mit 1 codiert. Existiert für ein Zeichen schon ein Code, so wird die 0 oder 1 einfach davorgestellt. Die Codierung lautet dann, wenn wir `r' mit 0 codieren und vor `k' und `d' folglich eine 1 stellen:

`r':

0

`k':

10

`d':

11

Wieder werden die Häufigkeiten zusammengefaßt: `r', `k' und `d' treten zusammen 4 mal auf. Die beiden seltensten Zeichen sind nun `b' und `r', `k' und `d' zusammen. Das b codieren wir mit 0, die anderen Codes bekommen jeweils eine 1 vorangestellt und wir erhalten:

`b':

0

`r':

10

`k':

110

`d':

111

Bei der letzten Wiederholung dieses Verfahrens wird `a' mit 0 codiert und alle anderen erhalten eine vorangestellte 1:

`a':

0

`b':

10

`r':

110

`k':

1110

`d':

1111

Das Wort ,,abrakadabra`` wird dann also mit 01011001110011110101100 codiert.

Bei der eben dargestellen Codierung können wir den folgenden Binärbaum aufgestellen, wobei ein Pfad nach links einer Kodierung mit 0 und ein Pfad nachrechts einer Kodierung mit 1 entspricht:

=6cmbibaumtgif.eps

Zur Decodierung lesen wir einfach Bit für Bit ein und wandern dabei durch den Binärbaum. Wenn wir ein Zeichen als Blatt gefunden haben, ist dieses decodiert und wir fangen mit dem nächsten Bit wieder an der Wurzel des Baumes an.

Diese Codierung benötigt für das Wort ,,abrakadabra`` 23 Bit:
01011001110011110101100

Eine Codierung in 8-Bit ASCII verschlingt 88 Bit.
01100001 01100010 01110010 01100001 01101011 01100001 01100100 01100001 01100010 01110010 01100001