Dreißig Übungen zum Huffman-Baum — zählen, zusammenfassen, Codewörter ablesen, Sonderfälle.
Dein Fortschritt:
0 / 0 Aufgaben
1
Übungsaufgaben
Dreißig Übungen zum Klicken, Zuordnen, Rechnen und Knobeln — von AFB I bis AFB III. Jede Übung gibt sofort Rückmeldung; wenn Sie nicht weiterkommen, helfen die gestuften Tipps.
A1
Eigenschaften des Huffman-Codes
AFB I
Geben Sie alle Aussagen an, die für jeden Huffman-Code gelten.
Mehrere Antworten sind richtig. Markieren Sie alle zutreffenden und klicken Sie dann auf „Prüfen“.
Die Wurzel trägt die Summe aller Häufigkeiten, also die Textlänge. Welche Bitfolge ein Zeichen bekommt, hängt von der Konvention ab — nur die Länge folgt aus der Häufigkeit.
Ansatz: Denken Sie an den Weg von der Wurzel zum Blatt.
Weiter: Was steht nach dem letzten Zusammenfassen in der Wurzel?
A2
Den Codebaum lesen
AFB I
Aus den Häufigkeiten L 1, T 2, R 3, N 5 und E 9 entsteht der gezeigte Huffman-Baum. Der kleinere Knoten hängt links, links = 0, rechts = 1; bei Gleichstand hängt der zusammengesetzte Knoten links. Lesen Sie am Baum ab: Klicken Sie nacheinander die gefragten Stellen an.
Klicken Sie die gesuchte Stelle an. Mit der Tastatur: Tab oder Pfeiltasten zum Wandern, Enter zum Auswählen.
E ist mit 9 am häufigsten und hängt direkt an der Wurzel: Codewort 0. R liegt dreimal rechts: 111. Für T geht es rechts, rechts, links, rechts: 1101. Der Knoten mit 6 fasst R (3) und den Knoten 3 aus L und T zusammen.
Beginnen Sie an der Wurzel und folgen Sie den roten Beschriftungen an den Kanten: 0 führt nach links, 1 nach rechts.
Das Codewort ist die Folge der Kantenbeschriftungen von der Wurzel bis zum Blatt. Die Summe an einem Knoten gehört zu den beiden Knoten direkt darunter.
A3
Wie stark schrumpft der Text?
AFB IIMix
Ein Text besteht zu 70 % aus A, zu 15 % aus B, zu 10 % aus C und zu 5 % aus D. Er wird nicht mit ASCII (8 Bit je Zeichen), sondern mit einem Huffman-Code gespeichert. Schätzen Sie ab, auf wie viel Prozent der ASCII-Größe der Text schrumpft, und stellen Sie den Regler ein.
Schieben Sie den Regler auf Ihre Schätzung — Pfeiltasten bewegen ihn feiner. Nach dem Prüfen sehen Sie den Trefferbereich.
0 %100 %
Je 100 Zeichen: D + C = 15, 15 + B = 30, 30 + A = 100, also 15 + 30 + 100 = 145 Bit. Das sind 1,45 Bit je Zeichen statt 8 Bit: k = 145 : 800 ≈ 0,181, also gut 18 %.
Nehmen Sie einen Text mit 100 Zeichen und bauen Sie den Huffman-Baum aus den Häufigkeiten 70, 15, 10 und 5.
Die Summe der neuen Knoten ist die Länge in Bit. Teilen Sie sie durch die ASCII-Länge 100 · 8 Bit (Kompressionsverhältnis).
