Über dieses Experiment
Jede ZIP-Datei, jedes PNG-Bild und jeder MP3-Titel ist kleiner als die Rohdaten, weil Wiederholungen entfernt werden. Probiere zwei klassische verlustfreie Methoden mit deiner eigenen Nachricht aus. Bei der Lauflängenkodierung wird eine Folge identischer Symbole durch eine Anzahl ersetzt. Das eignet sich hervorragend für einfache Bilder und ist für gewöhnliche Texte nutzlos. Die Huffman-Kodierung weist häufigen Symbolen kurze und seltenen Symbolen lange Codes zu. Diese werden Schritt für Schritt aus einem Baum aufgebaut. So liegt das Ergebnis höchstens ein Bit pro Symbol über der theoretischen Grenze, die Claude Shannon 1948 entdeckt hat.
Lernziele
- Erkläre den Unterschied zwischen verlustfreier und verlustbehafteter Kompression
- Kodiere und decodiere eine Nachricht mit Lauflängenkodierung und erkläre, wann sie nützlich ist
- Erstelle einen Huffman-Baum, indem du wiederholt die beiden Symbole mit der niedrigsten Häufigkeit zusammenführst
- Lies die Codewörter aus dem Baum ab und erkläre, warum kein Codewort den Anfang eines anderen bildet
- Vergleiche die komprimierten Größen mit der Entropiegrenze und berechne eine Kompressionsrate
Anleitung
- 1Wähle die Pixel-Zeile und Lauflängenkodierung aus. Wie viele Bits benötigt die Zeile vorher und nachher? Warum funktioniert das so gut?
- 2Wechsle bei der Lauflängenkodierung zu Hamlet. Warum wird die Nachricht größer?
- 3Wähle Mississippi aus und klicke auf „Baum erstellen“. Welche beiden Bäume werden bei jedem Schritt zusammengeführt und warum?
- 4Wenn der Baum fertig ist, finde das Codewort des häufigsten und des seltensten Buchstabens. Zähle die Bits.
- 5Dekodiere die ersten paar Bits der kodierten Nachricht von Hand, indem du vom Wurzelknoten aus den Baum entlanggehst.
- 6Gib eine Nachricht ein, die nur einen Buchstaben verwendet, und dann eine, in der jeder Buchstabe anders ist. Vergleiche in beiden Fällen die Huffman-Kodierung mit der Entropiegrenze.
Das Modell
Annahmen
- Die ursprüngliche Nachricht verwendet 8 Bits pro Zeichen, wie bei ASCII.
- Jedes Lauflängen-Paar wird als 8-Bit-Zähler und 8-Bit-Zeichen gespeichert, daher werden Läufe mit mehr als 255 Zeichen aufgeteilt.
- Die Huffman-Größe zählt nur die codierte Nachricht. Eine echte Datei muss auch die Codetabelle oder die Häufigkeiten speichern, was bei kurzen Nachrichten eine Rolle spielt.
- Haben zwei Bäume dasselbe Gewicht, wird der zuerst erstellte zuerst ausgewählt, und der leichtere Baum wird zum 0-Zweig. Andere Regeln für Gleichstände ergeben andere Codes derselben Gesamtlänge.
Im Unterricht ausprobieren
- Q1Codiere BBBBBWWWBBBBBBBB mit Lauflängencodierung. Wie viele Bytes werden benötigt?
- Q2Erstelle den Huffman-Baum für die Häufigkeiten A 5, B 2, R 2, C 1, D 1 und ermittle die Gesamtzahl der Bits für ABRACADABRA.
- Q3Warum muss ein Huffman-Code ein Präfixcode sein? Was würde schiefgehen, wenn A den Code 0 und B den Code 01 hätte?
- Q4Ein Text verwendet 8 verschiedene Buchstaben gleich häufig. Wie hoch ist seine Entropie, und kann Huffman ihn komprimieren?
- Q5JPEG und MP3 komprimieren viel stärker als die Huffman-Codierung. Worauf verzichten sie dafür?
Häufig gestellte Fragen
Wo wird die Huffman-Codierung heute verwendet?
In vielen gängigen Formaten: ZIP und gzip (das DEFLATE-Verfahren), PNG-Bilder, JPEG-Bilder nach dem verlustbehafteten Schritt und MP3-Audio. Meist ist es die letzte Stufe, nachdem ein anderes Verfahren Wiederholungen in Zahlen umgewandelt hat.
Lässt sich jede Datei komprimieren?
Nein. Ein verlustfreies Verfahren, das jede Datei verkleinern würde, ließe sich immer wieder auf das Ergebnis anwenden. Das ist unmöglich, denn es gibt weniger kurze als lange Dateien. Zufallsdaten und bereits komprimierte Dateien werden normalerweise nicht kleiner.
Ist der Huffman-Baum eindeutig?
Nicht immer. Bei gleichen Häufigkeiten führen verschiedene Entscheidungen zu unterschiedlichen Bäumen und Codewörtern, aber jeder Huffman-Baum für dieselben Häufigkeiten ergibt dieselbe Gesamtzahl an Bits.