Einen Huffmanbaum malen und eine Nachricht damit codieren

Gegeben ist eine Nachricht. Da werden zunächst die Zeichen (Buchstaben) gezählt und in einer Menge als Paare aus Zeichen und Häufigkeit aufsteigend nach der Häufigkeit angeordnet.

Dann nimmt man die zwei jeweils nach der Häufigkeit kleinsten Paare und packt sie zusammen. Es entsteht wieder ein Paar, wobei die Zeichen nun eine Menge sind und die Häufigkeit die Summe aus den Einzelhäufigkeiten ist. Die Zeichnung geht dann von unten nach oben. Ganz oben hat man dann die Gesamthäufigkeit und die Menge aller vorhandenen Zeichen.

Dann kriegen alle linken Äste eine 0 und alle rechten eine 1.

Die Codierung geht dann, indem man pro Buchstabe/Zeichen oben anfängt und die Nullen und Einsen auf dem Weg von oben nach unten notiert.


Keine Kommentare:

Kommentar veröffentlichen