MINT lernen

Übungen: Den Huffman-Baum aufbauen

Zehn Übungen zum Huffman-Baum — zählen, zusammenfassen, Codewörter ablesen, Sonderfälle.

Dein Fortschritt:
0 / 0 Aufgaben
1

Übungsaufgaben

Zehn Ü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
Stimmt's? — Baum und Codewörter
AFB I

Nennen Sie zu jeder Aussage, ob sie stimmt.

5 Aussagen nacheinander. Eine falsche Einschätzung reicht — dann starten Sie die Serie mit „Neue Runde“ neu.
Aussage 1 von 5

Jeder Schritt verringert die Zahl der Bäume um eins: aus \(n\) Blättern werden in \(n-1\) Schritten ein Baum.
Ansatz: Zählen Sie Schritte: Wie viele Bäume gibt es vorher und nachher?
Weiter: Präfix = Anfangsstück.
A3
Der Algorithmus in Schritten
AFB I

Stellen Sie das Huffman-Verfahren in der richtigen Reihenfolge dar.

Ziehen Sie die Karten in die richtige Reihenfolge — mit der Tastatur: ↑/↓ verschiebt, Shift+↑/↓ wechselt nur den Fokus.
1Häufigkeit jedes Zeichens im Text zählen
2für jedes Zeichen ein Blatt mit seiner Häufigkeit anlegen
3die zwei Knoten mit den kleinsten Häufigkeiten unter einen neuen Knoten hängen
4wiederholen, bis nur ein Baum übrig ist
5Kanten mit 0 und 1 beschriften und Codewörter ablesen
Die Beschriftung kommt ganz am Ende — erst wenn der Baum steht, lassen sich die Wege von der Wurzel ablesen.
Ansatz: Womit beginnt man bei einem Text?
Weiter: Codewörter entstehen erst am fertigen Baum.
A4
Häufigkeiten zählen
AFB II

Der Text lautet KOKOSNUSS. Bestimmen Sie die Häufigkeiten und die Häufigkeit der Wurzel.

Füllen Sie alle Felder aus und prüfen Sie dann. Enter in einem Feld prüft ebenfalls.
ZeichenKOSNUWurzel
Häufigkeit
Probe: \(2+2+3+1+1=9\) Zeichen. Die Wurzel des Huffman-Baums trägt immer die Textlänge.
Ansatz: Buchstabe für Buchstabe mit Strichliste.
Weiter: Die Wurzel ist die Summe.
A5
Den Baum Schritt für Schritt
AFB II

Ein Text enthält A 8-mal, B 3-mal, C 2-mal, D 1-mal und E 1-mal. Wenden Sie das Huffman-Verfahren an: Welche Häufigkeit trägt jeder neue Knoten?

Rechnen Sie die Kette Schritt für Schritt: Erst wenn ein Schritt stimmt, wird der nächste freigeschaltet. Enter prüft.
  1. 1. neuer Knoten
  2. 2. neuer Knoten
  3. 3. neuer Knoten
  4. Wurzel
D + E = 2; dann die kleinsten 2 (C) und 2 (DE) → 4; dann 3 (B) + 4 → 7; zuletzt 7 + 8 (A) → 15. Wer im zweiten Schritt B (3) nimmt, hat den neuen Knoten 2 übersehen.
Ansatz: Nach jedem Schritt die Liste neu sortieren.
Weiter: Stand nach Schritt 1: 8, 3, 2, 2.
A6
Codewörter ablesen
AFB II

Für denselben Baum (A 8, B 3, C 2, D 1, E 1) gilt: Der kleinere Knoten hängt links, links = 0; bei Gleichstand hängt der zusammengesetzte Knoten links, bei zwei Blättern das alphabetisch erste. Ermitteln Sie die Codewörter.

Wählen Sie in jedem Menü den passenden Eintrag und prüfen Sie dann alle auf einmal.

A:

B:

C:

D:

E:

Wurzel 15 = 7 (links) + A 8 (rechts) → A = 1. Knoten 7 = B 3 (links) + 4 (rechts) → B = 00. Knoten 4 = DE 2 (links) + C 2 (rechts) → C = 011. Knoten DE = D (links) + E (rechts) → D = 0100, E = 0101. Andere Konventionen ändern die Bits, nicht die Längen 1, 2, 3, 4, 4.
Ansatz: Der kleinere Knoten hängt links: 7 links, 8 rechts.
Weiter: Im Knoten 7: B (3) ist kleiner als 4.
A7
Mias Baum
AFB II

Mia baut den Huffman-Baum für F 5, G 4, H 2, I 1. Überprüfen Sie ihr Protokoll — zwei Schritte sind falsch.

In diesem Text stecken Fehler. Klicken Sie genau die falschen Zeilen an — die richtigen müssen stehen bleiben.
Mia hat den neuen Knoten 3 vergessen. Die Wurzel stimmt trotzdem — die Summe allein beweist nicht, dass der Baum richtig ist.
Ansatz: Nach Schritt 1 liegen 5, 4 und 3 vor.
Weiter: Welche zwei davon sind die kleinsten?
A8
Präfixfrei oder nicht?
AFB II

Ordnen Sie jeden Code danach, ob er präfixfrei ist.

Ziehen Sie jede Karte in den passenden Korb — oder wählen Sie sie mit Enter aus und drücken dann die Ziffer des Korbs (0 legt sie zurück).
1präfixfrei
2nicht präfixfrei
Prüfen Sie jedes Paar: Ist das kürzere Codewort der Anfang des längeren? Bei {01, 10, 011} ist 01 Anfang von 011 — die Bitfolge 011 wäre mehrdeutig.
Ansatz: Kurzes Codewort vorn an das lange halten.
Weiter: {00, 1, 001}: 00 steckt vorn in 001.
A9
Gleich häufige Zeichen
AFB III Trick

Ein Text aus 16 Zeichen enthält W, X, Y und Z je 4-mal. Untersuchen Sie den Huffman-Baum: Wie viele Bit braucht der Text?

Rechnen Sie selbst und tragen Sie das Ergebnis ein — Enter prüft direkt.
Bit
Erst 4 + 4 = 8, dann 4 + 4 = 8, dann 8 + 8 = 16: alle Codewörter haben 2 Bit, zusammen \(16\cdot2=32\) Bit — genauso viel wie ein Code fester Länge. Huffman spart nur bei ungleichen Häufigkeiten.
Ansatz: Welche Knoten sind jeweils die kleinsten?
Weiter: Der Baum wird vollkommen symmetrisch.
A10
Gleichstand beim Zusammenfassen
AFB III Mix

Bei den Häufigkeiten P 2, Q 2, R 2, S 3 gibt es im ersten Schritt mehrere Möglichkeiten. Beurteilen Sie die Aussagen — markieren Sie alle richtigen.

Mehrere Antworten sind richtig. Markieren Sie alle zutreffenden und klicken Sie dann auf „Prüfen“.
Alle erlaubten Bäume sind optimal und liefern dieselbe Gesamtlänge (hier \(2\cdot2+2\cdot2+2\cdot2+3\cdot2=18\) Bit). S gehört nicht zu den zwei kleinsten.
Ansatz: Was schreibt die Huffman-Regel genau vor?
Weiter: Rechnen Sie zwei Varianten durch.