Bei der herkömmlichen Text-Codierung mithilfe der ASCII-Tabelle besitzt jedes Zeichen eine Codelänge von genau 8 Bit. Die Idee hinter der Huffman-Codierung ist die, dass häufig vorkommende Zeichen mit einer kürzeren Codelänge auskommen als weniger häufig vorkommende Zeichen.
Ein Beispiel kennst du bereits: Morsecode verwendet als Code für das häufig vorkommende E
lediglich ein •
wohingegen ein Q
in den den deutlich längeren Morsecode −−•−
übersetzt wird.
Beim Morsen muss man neben den beiden Symbolen "kurz" und "lang" auch noch mit Pausen arbeiten, um die unterschiedlichen Zeichen unterscheiden zu können. Das ist nötig, da der Morsecode nicht präfixfrei ist, das bedeutet, dass es Codes von Zeichen gibt, die gleichzeitig auch als Anfang eines anderen Codes interpretiert werden können.
Beispiel: Das E
mit seinem Code •
ist gleichzeitig auch der Anfang des Zeichens A
mit dem Code •−
. Damit ist der Morsecode ohne zusätzliche Pause (also einem dritten Zeichen) nicht mehr eindeutig entzifferbar:
. - - . . . - . - .
= ABC. - - . . . - . - .
= EGFNDer Huffman-Code bildet solch einen präfixfreien Code, der gleichzeitig den häufig vorkommenden Zeichen eine kürzere Codelänge generiert. Der Huffman-Code ist eine sogenannte Entropiekodierung.
Mithilfe der Seite https://cmps-people.ok.ubc.ca/ylucet/DS/Huffman.html lässt sich der Algorithmus schrittweise simulieren und visualisieren.
Lasse mit der Seite die Simulation für den Text „OTTOS MOPS KOTZT“ durchführen und beobachte den Aufbau des Baumes.1)
(A) Erzeuge aus dem Baum, den du oben generiert hast, die Codierung für jedes einzelne Zeichen (inklusive Leerzeichen) Anmerkung: Je nach Anordnung der Buchstaben und Knoten im Baum ist dieser Code nicht eindeutig.
Am besten machst du das in einer Tabelle:
Zeichen | O | M | T | … |
Häufigkeit | 4 | 1 | 4 | … |
Code | 01 | … | … | … |
(B) Codiere den Text mit dem gefundenen Code. Wieviel Bit/Byte hat die ASCII Codierung des Textes in Anspruch genommen, wieviele Bit benötigt der Satz, wenn er mit dem Huffman-Code codiert wird?
(C) Welche Information benötigt ein Mitschüler, um deinen Code decodieren und den ursprünglichen Text wiederherstellen zu können?
Für den Text "ABRACADABRA": Erzeuge von Hand den Huffman-Baum, erstelle daraus einen Huffman-Code und codiere damit den Text.
Gegeben ist der folgende Baum:
Mit Hilfe einer "Zwischencodierung" kann man mit dem Huffman Code auch Bilder komprimieren. Betrachte das folgende Bild:
Untersucht man das Bild jetzt zeilenweise und betrachtet die folgenden 4 möglichen "Pixelpaare", kann man das Bild mit der Huffman-Codierung komprimieren:
Pixelpaar | Weiß-Weiß | Weiß-Schwarz | Schwarz-Weiß | Schwarz-Schwarz |
---|---|---|---|---|
Wie oft? | ||||
Code |
Filename | Filesize | Last modified |
---|---|---|
05-kompression_huffman.odp | 871.7 KiB | 29.11.2023 18:23 |
05-kompression_huffman.pdf | 770.5 KiB | 29.11.2023 18:23 |
huff2.png | 10.9 KiB | 28.09.2022 16:00 |
huff2lsg.png | 12.3 KiB | 28.09.2022 16:04 |
huffb01.png | 79.7 KiB | 14.10.2021 16:14 |
mobile.svg | 3.4 KiB | 29.11.2023 18:25 |
pfeil.png | 5.5 KiB | 29.11.2023 18:51 |
streifen.png | 5.1 KiB | 29.11.2023 19:01 |