Huffman-Kodierung

Für die Dekodierung benötigt man neben dem zurück zu kodierenden String auch den zur Kodierung verwendeten Binärbaum. Die Abfolge an Binärdaten, wie in diesem Beispiel „00000110011000111110100010111110101100110“ wird dann Zeichen für Zeichen zurückkodiert. Anhand des Binärbaumes geht man von der Wurzel aus und verfolgt den Weg durch den Baum, der durch die 01-Folge der Zeichenkette vorgegeben bis man zu einem Endknoten (Blatt) gelangt Im konkreten Fall kommt man nach 0000 zum Endknoten- an diesem steht das Zeichen „W“.
Anschließend beginnt man mit dem nächsten Zeichen im String wieder bei der Wurzel des Binärbaums. Auf diese Weise wird die gesamte Abfolge von 0 und 1 in den ursprünglichen String zurück verwandelt. Die Codes für die Zeichen sind eindeutig - das heißt wenn 0000 der Code für ein Zeichen ist, kann kein Zeichen durch z.B. 000 dargestellt werden, da sonst bei der Dekodierung mehrere Lösungen möglich wären und die Informationen verloren gehen könnten.