Huffman-Komprimierung
Häufige Zeichen bekommen kurze Codes, seltene lange: Zähle die Zeichen eines Textes, baue daraus den Huffman-Baum, codiere den Text und entschlüssele eine Bitfolge – Schritt für Schritt von Hand oder automatisch.
Daten & Codierung – Kursstufe🎯 Worum geht's? Klasse 11–13 · 1–2 Unterrichtsstunden
Nach dieser Seite kannst du …
- die Häufigkeitsverteilung der Zeichen eines Textes bestimmen
- einen Huffman-Baum Schritt für Schritt aufbauen und begründen, warum immer die zwei kleinsten Häufigkeiten zusammengefasst werden
- einen Text mit dem Baum codieren und die Kompressionsrate gegenüber 8 Bit je Zeichen berechnen
- eine Bitfolge mit dem Baum decodieren und erklären, warum dafür keine Trennzeichen nötig sind (präfixfreier Code)
Vorwissen: Binärzahlen, Codierung mit fester Länge (z. B. ASCII), Bäume (Wurzel, Knoten, Blatt)
📘 So funktioniert der Huffman-Algorithmus
- Zählen: Für jedes Zeichen des Textes wird gezählt, wie oft es vorkommt. Jedes Zeichen wird ein Blatt mit seiner Häufigkeit.
- Zusammenfassen: Die zwei Teilbäume mit den kleinsten Häufigkeiten werden zu einem neuen Knoten verbunden. Er bekommt die Summe der beiden Häufigkeiten.
- Wiederholen, bis nur noch ein Baum übrig ist – das ist der Huffman-Baum.
- Codes ablesen: Von der Wurzel bis zu einem Blatt: nach links =
0, nach rechts =1. Häufige Zeichen liegen nah an der Wurzel und haben deshalb kurze Codes. - Decodieren: Bit für Bit von der Wurzel aus durch den Baum gehen. An einem Blatt steht das nächste Zeichen, dann geht es wieder an der Wurzel los. Weil kein Code der Anfang eines anderen ist (präfixfrei), braucht man keine Trennzeichen.
Auf dieser Seite gilt: Der zuerst gewählte Teilbaum kommt nach links (0), der zweite nach rechts (1). Gibt es mehrere gleich kleine Häufigkeiten, darfst du frei wählen – es entstehen andere Codes, aber gleich gute.
1 · Text eingeben
Gib einen Satz ein oder lade einen Beispieltext bzw. eine eigene Textdatei mit mehreren Sätzen.