MINT üben

Den Huffman-Baum aufbauen

Dreißig Übungen zum Huffman-Baum: Häufigkeiten zählen, Knoten zusammenfassen, Codewörter ablesen und den Nutzen beurteilen.

Ihr Fortschritt:
0 / 0 Aufgaben
1

Übungsaufgaben

Dreißig Übungen in gemischter Reihenfolge — Sie klicken, ziehen, ordnen, rechnen und knobeln. Jede Übung gibt Ihnen sofort eine Rückmeldung, und zu jeder Aufgabe gibt es zwei gestufte Tipps: Der erste zeigt die Richtung, der zweite den entscheidenden Schritt. Die Chips zeigen das Anforderungsniveau: AFB I heißt wiedergeben und direkt anwenden, AFB II selbst entscheiden und verknüpfen, AFB III begründen, beurteilen oder eine Falle durchschauen. Aufgaben mit dem Chip Mix verbinden Wissen aus früheren Unterkapiteln, bei Trick steckt eine Falle drin. Fahren Sie über ein unterstrichenes Arbeitswort, sehen Sie, was es genau von Ihnen verlangt.

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

01010101E9N5L1T23R361120
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.
A2
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.
A3
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.