Huffman Code

Mit dem Huffman Code kann man effizient Daten kodieren um in vielen Fällen Speicher zu sparen.

Beispiel eines Huffman Codes

Ausgangswort: PANAMAKANAL

Buchstabe	A	N	P	M	K	L
Wahrscheinlichkeit	$\frac{5}{11}$	$\frac{2}{11}$	$\frac{1}{11}$	$\frac{1}{11}$	$\frac{1}{11}$	$\frac{1}{11}$

Wie erstellt man einen Huffman Baum?

Erstelle Blattknoten aus jedem Zeichen der zu kodierenden Nachricht, wobei jedes Zeichen nur einmal mit den verschiedenen Häufigkeiten des Auftretens der Zeichen berücksichtigt wird, die nach Priorität geordnet werden sollen, wobei die Zeichen mit den niedrigsten Häufigkeiten Vorrang haben.
Extrahiere die beiden Knoten mit der niedrigsten Gewichtung in aufsteigender Reihenfolge der Häufigkeit, d. h. der Knoten mit der niedrigsten Häufigkeit muss zuerst extrahiert werden.
Erstelle einen neuen internen Knoten mit einer Häufigkeit, die der Summe der Häufigkeiten dieser beiden Knoten entspricht. Definiere den ersten extrahierten Knoten als den linken Sohn dieses Knotens und den zweiten Knoten als den rechten Sohn. Füge den neu erstellten Knoten zur Liste der verbleibenden Knoten hinzu.
Wiederhole die Schritte 2 und 3, bis du durch alle Knoten gegangen bist, die du in Schritt 1 erhalten hast. Der verbleibende Knoten ist die Wurzel des Baumes und die Konstruktion ist abgeschlossen.

Beispiel 2

Kodierte Daten mit dem Huffman Baum 1100 0 10 0 1101 0 1110 0 10 0 1111

Beispiel: Vergleich: Unkomprimiert zu Komprimiert

	Größe	Relative Größe
Komprimiert	33 Bit	100%
Unkomprimiert	25 Bit	75%

Beispiel Fischers Fritz fischt frische Fische

Kodiert werden soll: ”FISCHERSFRITZFISCHTFRISCHEFISCHE”

Buchstabe	F	I	S	C	H	E	R	T	Z
Wahrscheinlichkeit	$\frac{5}{32}$	$\frac{5}{32}$	$\frac{5}{32}$	$\frac{4}{32}$	$\frac{4}{32}$	$\frac{3}{32}$	$\frac{3}{32}$	$\frac{2}{32}$	$\frac{1}{32}$

Beispiel: Digitalisierung eines Tonsignals

Wert	244	201	175	50	42	70	121
m	$\frac{6}{17}$	$\frac{2}{17}$	$\frac{3}{17}$	$\frac{2}{17}$	$\frac{2}{17}$	$\frac{1}{17}$	$\frac{1}{17}$