Huffman-Kodierung

Die Huffman-Kodierung wird dazu verwendet, Text wie auch Binärdaten zu komprimieren.

Der Algorithmus liefert beweisbar immer einen optimalen Baum für die gegebenen Wahrscheinlichkeiten.

Er wird folgendermassen verwendet:

Zu kodierender Text ist: Huffman

1. Zuerst zählt man die gleichen Ziffern zusammen und schreibt ihre Häufigkeit auf.

2. Danach fängt man bei der kleinsten Häufigkeit an und verbindet Sie mit den zweitkleinsten (kann auch eine gleiche sein).

3. Die Anzahl der beiden Häufigkeiten schreibt man darüber.

4. Jetzt fängt man wieder von vorne an, also nimmt wieder die kleinste Häufigkeit und verbindet sie mit der nächst kleinsten...

5. Das wiederholt man, bis nichts mehr übrigbleibt.

6. Zum Schluss wird die linke Kante mit 0 beschriftet und die rechte mit 1 (kann auch umgekehrt sein, je nach Definition).

Jetzt hat man einen fertigen Binär-Baum.

Den Code kann jetzt ganz einfach hergestellt werden, indem man von oben nach unten bis zur Ziffer vorgeht und den entsprechenden Kanten-Wert als Code verwendet.

Geht man auch wieder von oben nach unten mit dem Codewert, erhält man wieder den ursprünglichen Text.