IMP 9 · Algorithmen und Daten
Datenkompression
Im Rechner bekommt normalerweise jedes Zeichen gleich viele Bits. Das ist Verschwendung, wenn manche Zeichen viel häufiger sind als andere. Die Idee der Huffman-Codierung: Häufige Zeichen bekommen kurze Codes, seltene lange. Der Code entsteht aus einem Baum, den du hier Schritt für Schritt baust.
So gehst du vor
- 1Gib einen Text ein oder wähle einen Beispieltext. Die Kreise zeigen, wie oft jedes Zeichen vorkommt.
- 2Überlege, welche zwei Kreise als Nächstes verbunden werden, und tippe dann auf „Verbinden“. Es sind immer die zwei kleinsten Zahlen.
- 3Am fertigen Baum liest du den Code ab: Gehe von oben zum Zeichen und notiere die Bits auf dem Weg.
- 4Vergleiche unten die Bitzahl mit einem Code fester Länge.
Text
11 von 200 Zeichen
Bau des Baums: Schritt 1 von 4
Die zwei kleinsten Zahlen sind 1 und 1. Sie werden zu einem neuen Knoten mit 2 verbunden.
Häufigkeiten und Codes
| Zeichen | Anzahl | Huffman-Code | Bits gesamt | Feste Länge |
|---|---|---|---|---|
| A | 5 | ? | ? | 000 |
| B | 2 | ? | ? | 001 |
| R | 2 | ? | ? | 010 |
| C | 1 | ? | ? | 011 |
| D | 1 | ? | ? | 100 |
Vergleich der Bitzahl
Der Vergleich erscheint, sobald der Baum fertig ist. Überlege vorher: Wie viele Bits braucht ein Code fester Länge für deinen Text?
Aufträge
- Wähle ABRACADABRA. Zähle die Zeichen selbst und baue den Baum auf Papier, bevor du auf „Verbinden“ tippst. Bestimme dann die Bitzahl.
- Entschlüssle mit den Codes aus dem letzten Auftrag die Bitfolge 1100111.
- Die Bitfolge enthält keine Trennzeichen. Warum ist sie trotzdem eindeutig? Überlege dir das am Baum.
- Wähle ABCD. Warum spart Huffman hier nichts? Gib einen längeren Text an, bei dem dasselbe passiert.
- Wähle AAAAAAAB. Das A kommt siebenmal vor, trotzdem ist Huffman nicht besser als die feste Länge. Woran liegt das?
- Bei Gleichstand gibt es mehrere Möglichkeiten, zwei Knoten zu wählen. Baue bei ABRACADABRA auf Papier einen anderen Baum, indem du anders entscheidest. Was ändert sich, was nicht?
- Wer die Bitfolge entschlüsseln soll, braucht auch die Codetabelle. Für welche Texte lohnt sich die Huffman-Codierung deshalb, für welche nicht?