Huffman

Huffman-Kodierung geht auf das Morsealphabet zurück und nutzt die unterschiedlichen Wahrscheinlichkeiten aus, mit der einzelne Zeichen auftreten. Ein Zeichen, das sehr oft vorkommt, wird mit einer kurzen Kodierungssequenz ausgestattet wie z.B. 1 oder 01, und ein Zeichen, das sehr selten auftritt, mit einer längeren Kodierungsfolge wie z.B. 00001. Die Länge der Kodierung ergibt sich zum einen aus dem Vorrat der Zeichenmenge und zum anderen aus dem daraus resultierenden Ableitungsbaum. Typisches Einsatzgebiet der Huffman-Kodierung sind Texte. Das Huffmanverfahren ist ein verlustfreier Algorithmus. Das folgende Beispiel soll die Einfachheit dieser Art der Komprimierung darstellen.

Beispiel für Huffmankodierung

Gegeben sei eine beliebige Textfolge, wie z.B.

''wadde hadde du de da''

Normalerweise wird nun 1 Zeichen mit 8 Bit kodiert. Dies entspricht hier 20 Zeichen x 8 Bit = 160 Bit.

Nun wird die Häufigkeit der einzelnen Zeichen ermittelt.

d	-	a	e	h	u	w
7	4	3	3	1	1	1

Daraus wird ein Ableitungsbaum erstellt. Die zwei jeweils kleinsten Knoten werden zu einem neuen Knoten addiert. Die Reihenfolge beginnt von unten nach oben, und wird solange fortgesetzt bis nur noch der Wurzelknoten vorhanden ist. Anschließend werden an den Kanten die entsprechenden 0 und 1 angeschrieben. Linke Kanten 1, rechte kanten 0.

So ergibt sich eine Tabelle mit den Werten:

d	-	a	e	h	u	w
1	011	010	001	00011	00010	00000

Kodiert sieht es dann so aus (natürlich ohne Trenner):

00000 | 010 | 1 | 1 | 001 | 011 | 00011 | 010 | 1 | 1 | 001 | 011 | 1 | 00010 | 011 | 1 | 001 | 011 | 1 | 010

Die kodierten Zeichen werden mit der Entschlüsselungstabelle als neue Datei abgespeichert. Die neue Datei hat hier eine Länge von 51 Bit (ohne die Kodierungstabelle). Ein Ersparnis von ca. 69%.

Es können jedoch folgende Gründe für eine Verschlechterung sorgen. Variiert die Wahrscheinlichkeit der einzelnen Zeichen kaum, so kommen sie alle sehr selten vor. Der ``worst-case'' ist eine Gleichverteilung der zu kodierenden Zeichen. Ist der Text sehr kurz ``bläht'' die dazugehörige Kodierungstabelle die Datei unnötig auf.