Warum ASCII nicht reicht, wie die Huffman-Codierung funktioniert und warum sie optimal ist – kompakt auf einer Seite.
Wenn wir einen „reinen" Text als ASCII-Datei speichern, belegt jedes Zeichen 8 Bit – unabhängig davon, ob es 1000 Mal oder nur ein einziges Mal im Text vorkommt. Für den Speicherbedarf einer Datei ist das keine effektive Codierung!
Effizienter wäre eine Codierung, welche die Häufigkeiten der Zeichen im Text berücksichtigt:
Das Ziel ist ein Code mit folgender Eigenschaft: Je größer die Wahrscheinlichkeit, dass ein Zeichen im Text auftritt, desto kürzer soll sein Code sein (im Vergleich zu den Codes der anderen Zeichen). Oder einfacher: Je häufiger ein Zeichen vorkommt, desto kürzer sein Code. Die Häufigkeiten der Zeichen spielen also eine zentrale Rolle.
Im Themenkomplex Huffman-Code hast du ein Verfahren zur verlustlosen Textkompression kennengelernt. Bei der Textkompression wird der Text so verdichtet, dass der benötigte Speicherplatz sinkt und die Übertragungszeit verkürzt wird. Verlustlos bedeutet, dass der Ursprungstext nach der Kompression originalgetreu wiederhergestellt werden kann.
Die Idee des Verfahrens von Huffman beruht auf einem einfachen Prinzip: Statt jedem Buchstaben im Text ein gleich langes Codewort zuzuordnen, bekommen Buchstaben, die häufig im Text vorkommen, ein kürzeres Codewort als selten vorkommende Buchstaben. Als Hilfsmittel verwendet die Huffman-Codierung einen binären Baum – den Huffman-Baum.
Die Buchstaben und die Werte ihrer Häufigkeiten im Text bilden die Blätter des Baumes. Der Baum wird aus diesen Blättern bottom-up wie folgt aufgebaut:
Die Kanten, die links aus einem Knoten abgehen, werden mit 0 beschriftet,
die Kanten, die rechts abgehen, mit 1.
Das Codewort für einen Buchstaben liest man ab, indem man von der Wurzel ausgehend
im Baum bis zum gesuchten Buchstaben (im Blatt) wandert und die Beschriftungen an den Kanten
(0 bzw. 1) notiert.
Bei der Decodierung einer Huffman-codierten Bitfolge geht man ebenso vor: Von der
Wurzel ausgehend geht man nach links, wenn eine 0 in der Bitfolge steht, und nach rechts,
wenn eine 1 vorkommt. Sobald man in einem Blatt angekommen ist, hat man einen Buchstaben
decodiert und fängt wieder bei der Wurzel an. Das wiederholt man so lange, bis man am Ende der
Bitfolge angelangt ist.