Rechnernetze
Home ] Nach oben ] [ Huffmann ] Adaptive Huffmann ] Arithmetische Kodierung ] LZ77 ] LZ78 ] LZW ]

 

Huffmann-Kodierung


Die einfache Huffmann-Kodierung stellt eine algorithmische Umsetzung der informationstheoretischen Regel dar, möglichst gleichwahrscheinliche Teilmengen der zu kodierenden Werte zu verwenden, um eine (sub-) optimale Kodierung zu erhalten. Sie erzeugt einen binären Baum, dessen Blätter den Zeichen entsprechen, und der zu jedem Knoten zwei Nachfolger (0, 1) besitzt. Eine Kodierung verwendet jeweils ein entsprechendes Anfangsstück.

1. Initialisierung: Alle Zeichen werden Knoten zugeordnet und nach ihrer Häufigkeit in einer Liste sortiert.

2. Solange die Liste der Knoten noch mehr als ein Element enthält:

  1. Entnehme die Elemente mit der geringsten Häufigkeit der Liste und erzeuge einen Elternknoten hierfür.
  2. Weise die Summe der Häufigkeiten der Kinder dem Elternknoten zu und füge diesen Knoten der Liste zu.
  3. Den Zeigern des Elternknoten wird der Code 0, 1 zugeordnet (Reihenfolge im Prinzip beliebig).

Zeichen

Häufigkeit

log2(1/pi)

Code

Anzahl der Bits für Kodierung

A

15

1.38

0

15

B

7

2.48

100

21

C

6

2.70

101

18

D

6

2.70

110

18

E

5

2.96

111

15

Summe =

37

   

87

 

Im obigen Beispiel werden 87 Bits zu Kodierung benutzt, während eine Kodierung mit jeweils 3 Bits 121 Bits benötigen würde. Die idelle Entropie ist 2.19, währen die wahre Entropie in diesem Beispiel 87/39 = 2,23 ist, also nahe an der wahren Entropie liegt.