Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Huffman-Baum

0 Punkte
81 Aufrufe
​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
Gefragt 3, Feb 2017 in KOD-AI von uodys uodys Lernwillige(r) (870 Punkte)  
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

Eine Antwort

+1 Punkt
 
Beste Antwort
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)
Beantwortet 3, Feb 2017 von ueegv ueegv Tutor(in) (101,440 Punkte)  
ausgewählt 3, Feb 2017 von uodys uodys
Vielen vielen Dank !
...