MINT lernen

Abituraufgaben: Den Huffman-Baum aufbauen

Zwei Abituraufgaben zum Aufbau von Huffman-Bäumen — mit Hinweisen und Erwartungshorizont.

Dein Fortschritt:
0 / 0 Aufgaben
1

ABRAKADABRA

AFB I–II

Das Wort ABRAKADABRA soll mit einem Huffman-Code übertragen werden. Konvention: Der Knoten mit der kleineren Häufigkeit hängt links, linke Kanten tragen die 0. Bei Gleichstand hängt der zusammengesetzte Knoten links, bei zwei Blättern das alphabetisch erste.

  1. Bestimmen Sie die Häufigkeiten der Zeichen.
  2. Zeichnen Sie den Huffman-Baum.
  3. Geben Sie die Codewörter und die Länge des codierten Wortes an.
  4. Begründen Sie, warum ein aus einem Baum abgelesener Code immer präfixfrei ist.

Hinweise

Hinweis zu Aufgabe a)
Strichliste; Probe über die Wortlänge.
Hinweis zu Aufgabe b)
Erster Schritt: die beiden Einsen. Danach gibt es drei Knoten mit Häufigkeit 2.
Hinweis zu Aufgabe c)
Weg von der Wurzel ablesen, dann \(\sum h\cdot l\).
Hinweis zu Aufgabe d)
Wo stehen die Zeichen im Baum?Begründen: Sachverhalte auf Regeln, Gesetzmäßigkeiten bzw. kausale Zusammenhänge zurückführen und mit Argumenten stützen.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

A 5, B 2, R 2, K 1, D 1 — zusammen 11.

Erwartungshorizont zu Aufgabe b)

D + K = 2 (D links). Kleinste jetzt: 2 (DK), 2 (B), 2 (R) → DK + B = 4 (DK links, zusammengesetzt). Dann R 2 + 4 = 6 (R links). Zuletzt A 5 + 6 = 11 (A links). Wurzel 11.

10100110BRKAD
Erwartungshorizont zu Aufgabe c)

A 0, R 10, B 111, D 1100, K 1101. Länge: \(5\cdot1+2\cdot2+2\cdot3+1\cdot4+1\cdot4=23\) Bit (fester Code mit 3 Bit: 33 Bit).

Erwartungshorizont zu Aufgabe d)

Alle Zeichen stehen in Blättern. Ein Codewort ist Präfix eines anderen genau dann, wenn sein Knoten auf dem Weg zum anderen liegt — dann wäre er kein Blatt. Also ist kein Codewort Anfang eines anderen.

2

Sechs Zeichen mit Häufigkeitsanteilen

AFB II–III

In einer Nachrichtenquelle treten nur sechs Zeichen auf, mit den relativen Häufigkeiten

ZeichenENISRT
Anteil40 %20 %15 %10 %10 %5 %
  1. Erstellen Sie einen Huffman-Baum und geben Sie die Codewortlängen an.
  2. Berechnen Sie die mittlere Codewortlänge.
  3. Vergleichen Sie mit einem Code fester Länge.
  4. Entwerfen Sie Häufigkeiten für vier Zeichen, bei denen der Huffman-Code gegenüber einem 2-Bit-Code nichts einspart, und begründen Sie.

Hinweise

Hinweis zu Aufgabe a)
Mit Prozentwerten rechnen wie mit Häufigkeiten.
Hinweis zu Aufgabe b)
\(\bar l=\sum p(z)\cdot l(z)\).
Hinweis zu Aufgabe c)
Wie viele Bit braucht man für 6 Zeichen?
Hinweis zu Aufgabe d)
Wann entsteht ein symmetrischer Baum?Entwerfen/Entwickeln: Nach vorgegebenen Bedingungen ein Modell oder einen Algorithmus selbstständig planen bzw. erarbeiten.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

T 5 + S 10 = 15 (bei Gleichstand R/S frei); R 10 + 15 = 25 (oder R + I); I 15 + N 20 = 35; 25 + 35 = 60; E 40 + 60 = 100. Längen: E 1, N 3, I 3, R 3, S 4, T 4 (andere erlaubte Wahl liefert dieselbe mittlere Länge).

Erwartungshorizont zu Aufgabe b)

\(0{,}4\cdot1+0{,}2\cdot3+0{,}15\cdot3+0{,}1\cdot3+0{,}1\cdot4+0{,}05\cdot4=2{,}35\) Bit je Zeichen.

Erwartungshorizont zu Aufgabe c)

6 Zeichen → 3 Bit. \(k=\tfrac{2{,}35}{3}\approx78\,\%\); Huffman spart gut 21 % (ohne Codetabelle).

Erwartungshorizont zu Aufgabe d)

Zum Beispiel 30 %, 30 %, 20 %, 20 %: 20 + 20 = 40, 30 + 30 = 60, 40 + 60 = 100 — alle Blätter in Tiefe 2, mittlere Länge 2 Bit. Allgemein: Sind die Häufigkeiten so ausgeglichen, dass die zwei kleinsten zusammen mehr ergeben als die größte, entstehen nur Codewörter der Länge 2.