Vorgehen
- Zählen der einzelnen Zeichen im gegebenen Text
- Konstruieren eines Binärbaums
- Beginnend mit den zwei niedrigsten Elementen verbindet man diese und addiert die Anzahl
- Nun wird das nächst unwahrscheinlichste Zeichen an den Binärbaum angehangen bis alle Zeichen verwendet wurden
- Alle linken Pfade werden mit einer und alle rechten Pfade mit einer beschriftet
- Codierung entlang der Pfade ablesen
Wenn sich bei der Konstruirung die nächst beiden unwahrscheinlichsten Zeichen in Summe niedriger als die Wurzel ergibt, können diese auch verbunden werden und die somit die beiden Wurzeln zu einer verbunden werden.
Beispiel
Wort: MISSISSIPPI
Anzahl der Zeichen:
- M: 1
- I: 4
- S: 4
- P: 2
Binärbaum:
Codierung:
- M:
- I:
- S:
- P: