Datenkompression: Verlustfreie Verfahren: Statistische Verfahren: Huffman Codierung

zurück

5 Verlustfreie Verfahren Datenkompression: Verlustfreie Verfahren: Statistische Verfahren: TOC

Huffman Codierung

5.1.3 Huffman Codierung

Der von David Albert Huffman vorgestellte Artikel "A method for the construction of minimum redundancy codes" (Proceedings of the Institute of Radio Engineers, September 1952, Volume 40, Nummer 9, Pages 1098-1101) ist insofern ein Klassiker, als das der vorgestellte Algorithmus für die Datenkompression eine sehr weite Verbreitung gefunden hat. Der Algorithmus wird sehr vielseitig eingesetzt. Man stelle sich Suchalgorithmen vor, die häufiger vorkommende Worte schneller finden sollen, als weniger häufigere, somit kann die Laufzeit dieser Algorithmen optimiert werden. Denn die sog. Pfad-Länge spiegelt sich direkt in der Ausführungsgeschwindigkeit wieder.

Mit der Zeit wurde der von Huffman entwickelte Algorithmus immer vielseitiger angewendet. Manchmal wurde dieser Algorithmus allein verwendet, manchmal wurde dieser in Verbindung mit anderen Kompressionstechniken als ein Schritt unter vielen benutzt. Er ähnelt dem von Claude Shannon und Robert Fano entwickelten Verfahren, produziert Codes mit minimaler Redundanz, die entweder besser oder gleichwertig zum Shannon-Fano Code sind. Der entscheidende Unterschied zwischen beiden Verfahren ist, dass der Shannon-Fano-Code von oben nach unten (Top-Down) und der Huffman-Code von unten nach oben (Bottom-Up) konstruiert wird. Noch immer ist dieser Algorithmus Gegenstand intensiver Forschung, wird aber im Bereich der Datenkompression meiner Ansicht nach, zugunsten der arithmetischen Codierung verdrängt werden.

Am besten kann dieser Algorithmus an den beiden Beispielen aus dem Abschnitt zur Shannon-Fano-Codierung nachvollzogen und erläutert werden.

Beispiel 1 - Huffman Code (Quelle:
ThePacker)

Symbol	'A'	'B'	'C'	'D'	'E'
p(Symbol)	0.4	0.15	0.15	0.15	0.15
1.Schritt
				0	1
				0.3
2.Schritt
		0	1
		0.3
3.Schritt
		0		1
		0.6
4.Schritt
	0	1
	1.0
Resultierender Codebaum
	0	1
		0		1
		0	1	0	1
	A	B	C	D	E

Erläuterungen zum Beispiel 1

Im ersten Schritt werden die beiden Elemente D und E zusammengefasst, da sie die kleinste Wahrscheinlichkeit aufweisen und am Ende der sortierten Datenmenge stehen. Sie werden zu einem Meta-Symbol (Teil-Baum) zusammengefasst, welches/der eine linke und rechte Untermenge besitzt, die sich mit Hilfe des Symbols '0' für 'D' und '1' für 'E' unterscheiden lässt. Diesem Meta-Symbol wird die Summenwahrscheinlichkeit der beiden Symbole 'D' und 'E' zugeordnet.

$P(D\vee E)=P(D)+P(E)=0.3=0.15+0.15$

Im zweiten Schritt wird analog zum ersten Schritt Verfahren. Die beiden Symbole mit der geringsten Wahrscheinlichkeit, in diesem Fall sind es 'B' und 'C' werden zu einem Meta-Symbol (Teil-Baum) zusammengefasst. Die beiden Wahrscheinlichkeiten werden addiert und das entstehende Meta-Symbol besitzt die Summenwahrschenlichkeit der beiden Symbole.

$P(B\vee C)=P(B)+P(C)=0.3=0.15+0.15$

Im dritten Schritt werden wieder zwei Symbole zu einem neuen Symbol zusammengefasst. Es existiert das Symbol 'A', sowie die beiden Metasymbole 'BC' und 'DE'. Das Symbol 'A' hat eine Wahrscheinlichkeit von P(A)=0.4, und die beiden Metasymbole je eine Wahrscheinlichkeit von P('BC')=0.3 und P('DE')=0.3. Die beiden Symbole, die in diesem Schritt zusammengefasst werden sind die beiden Meta-Symbole die zu einem größeren Teilbaum zusammengefasst werden. Beide Teilbäume besitzen eine Wahrscheinlichkeit von 0.3 und somit eine Summenwahrscheinlichkeit von 0.6. Beide Teilbäume werden erneut durch die beiden Symbole '0' und '1' repräsentiert.

$P(B\vee C\vee D\vee E)=P(B\vee C)+P(D\vee E)=0.6=0.3+0.3$

Anschließend (im vierten Schritt) werden die letzten beiden Symbole zum gesamten Teilbaum vereint. Das Symbol 'A' und der Teil-Baum für die Symbole 'B', 'C', 'D' und 'E'. In diesem Fall soll das Symbol 'A' mit der Wahrscheinlichkeit P(A)=0.4 durch die '0' repräsentiert werden und der bereits konstruierte Teilbaum durch den Wert '1'.

Liest man den 'Resultierenden Baum' von oben nach unten, so ergeben sich die folgenden Symbolzuordnungen $A\to 0,B\to 100,C\to 101,D\to 110,E\to 111$

Beispiel 2 - Huffman Code (Quelle:
ThePacker)

Symbol	'A'	'B'	'C'	'D'	'E'	'F'	'G'
p(Symbol)	0.4	0.1	0.1	0.1	0.1	0.1	0.1
1.Schritt
						0	1
						0.2
2.Schritt
				0	1
				0.2
3.Schritt
		0	1
		0.2
4.Schritt
				0		1
				0.4
5.Schritt
		0		1
		0.6
6.Schritt
	0	1
	1.0
Resultierender Codebaum
	0	1
		0		1
		0	1	0		1
				0	1	0	1
	A	B	C	D	E	F	G

Erläuterungen zum Beispiel 2 hier... Vorlage:Clear