Huffman-Baum

Question

​Hallo,

ist es richtig wenn ich das erste Teil des Baums so skizze:

erstmal alle Buchstaben mit der Häufigkeit 1 paarweise zu 2er-Knoten

​und dann alle Buchstaben mit der Häufigkeit 2 paarweise zu 4er-Knoten

​Dann die erzeugten 2er -Knoten jeweils mit den Buchstaben R und U (diese haben eine abs. Häufigkeit von 3 jede)

oder stimmt hier was nicht ?

Weil ich komme oft nicht zu Bäume wie in Lösungen.

 

Danke schön

​mit vielen Grüssen

Comments

Ich glaube dass es falsch ist weil meine Codelänge grösser als die von der Lösung ist. Ich habe die Codelängen berechnet nur zu überprüfen. Aber ich sehe den Fehler in meiner Vorgehensweise nicht. Ich habe doch die geringsten Häufigkeiten zuerst zusammengefasst

Answer 1

Hallo uodys,

Die ersten zwei Schritte stimmen bei dir noch, dann hast du einen kleinen Fehler. Insgesamt würde ich dir außerdem empfehlen, lieber der Reihe nach vorzugehen als gleich mehrere Verknüpfungen auf einmal durchzuführen!

Nach dem Algorithmus werden stets die beiden Knoten mit den kleinsten Häfuigkeiten "zusammengefasst" (hier: Zu Beginn zwei Knoten mit Häufigkeit 1 zu einem Knoten mit Häufigkeit  2).
Danach werden erneut die beiden Knoten mit geringsten Häufigkeiten "zusammengefasst", also hier wieder zwei Knoten mit Häufigkeit 1 zu einem Knoten mit Häufigkeit 2).
Nun gibt es also aktuell sechs Knoten mit Häufigkeit 2, von denen jeweils zwei miteinander verknüpft werden. Damit ergeben sich drei Knoten mit Häufigkeit 4.
An dieser Stelle sind die beiden Knoten mit kleinsten Häufigkeiten die 3er, welche wir zu einem Knoten mit Häufigkeit 6 "zusammenfassen" usw.

Versuche also mal, das Schritt für Schritt durchzugehen und stets die Knoten mit den kleinsten Häufigkeiten miteinander zu verknüpfen, dann sollte es klappen.

Wichtig ist außerdem, dass eine Huffman-Kodierung nicht unbedingt eindeutig ist! D.h. häufig gibt es mehrere Verknüpfungsmöglichkeiten, die zu unterschiedlichen Kodierungen führen, welche jedoch alle äquivalent sind und eine minimale Länge aufweisen.

Viele Grüße

Monika (Tutorin)

Comments

Vielen vielen Dank !