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.)

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz sprachen minimierung nichtdeterministisch huffman fehler-in-aufgabe chomsky-normalform anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik huffman-kodierung hauptklausur fehlererkennbarkeit vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy konjunktive-normalform pipelining zustände saalübung leeres-wort endliche-automaten ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit klausureinsicht disjunktive-normalform pumping-lemma info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen von-neumann-rechner binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

0 Pluspunkte 0 Minuspunkte
114 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
in KOD-AI von uodys uodys Lernwillige(r) (870 Punkte)  
0 0
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

1 Eine Antwort

1 Pluspunkt 0 Minuspunkte
 
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)
von ueegv ueegv Tutor(in) (101k Punkte)  
ausgewählt von uodys uodys
0 0
Vielen vielen Dank !
...