Wenn wir einen "reinen" Text als ASCII-Datei speichern, so belegt jedes gespeicherte Zeichen 8 Bit. Wir könnten auch sagen, es wird mit 8 Bit codiert. Ob dieses Zeichen nun 1000 Mal oder nur ein einziges Mal im Text vorkommt, spielt dabei keine Rolle. Das ist im Hinblick auf den Speicherbedarf einer Datei sicherlich keine effektive Codierungsmethode! Effizienter wäre eine Codierung, welche die Häufigkeiten der Zeichen im Text berücksichtigt. Wenn ein Zeichen häufig im Text auftritt, wählen wir einen möglichst kurzen Code dafür. Wenn ein Zeichen hingegen nur ganz selten vorkommt, macht es nichts, wenn sein Code etwas länger ist. Das Ziel ist also ein Code mit folgender Eigenschaft: je grösser die Wahrscheinlichkeit, dass ein Zeichen im Text auftritt, desto kürzer soll sein Code sein (im Vergleich zu den Codes der anderen Zeichen). Wir könnten auch sagen: je häufiger ein Zeichen im Text vorkommt, desto kürzer soll sein Code sein. Die Wahrscheinlichkeiten bzw. die Häufigkeiten der Zeichen spielen also eine zentrale Rolle.
Im Themenkomplex Huffman-Code hast du ein Verfahren zur verlustlosen Textkompression, die Huffman- Codierung, 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: Es werden immer die zwei Knoten mit der geringsten Häufigkeit zu einem Vaterknoten zusammengefasst und die Häufigkeiten der Kinder addiert. Die Summe der Häufigkeiten der Kinder ist der Wert im Vaterknoten. Sobald der Baum nur noch einen vaterlosen Knoten hat (die Wurzel), ist der Huffman-Baum fertig aufgebaut. Die Kanten, die links aus einem Knoten abgehen, werden mit „0“ beschriftet, die Kanten, die rechts aus dem Knoten abgehen, werden mit „1“ gekennzeichnet. Das Codewort für einen Buchstaben liest man aus dem Huffman-Baum ab, indem man von der Wurzel ausgehend im Baum bis zum gesuchten Buchstaben am Ende des Baumes (im Blatt) wandert und die dabei gefundenen 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 in der Bitfolge eine „0“ steht und 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. Dies wiederholt man so lange, bis man am Ende der Bitfolge angelangt ist. Die Codewörter der Huffman-Codierung sind präfixfrei, d.h. kein Codewort ist Anfang eines anderen Codewortes. Das Huffman-Verfahren erstellt immer die kürzest mögliche Codierung, d.h. man kann einen Text mit Hilfe der Häufigkeiten nicht besser codieren. Die Codierung ist optimal, d.h. sie minimiert die mittlere Codewortlänge. Diese gibt an, wie viele Binärzeichen im Durchschnitt für die Codierung eines Buchstabens benötigt werden.