Datenkompression: Verlustfreie Verfahren: Statistische Verfahren: Huffman Codierung

zurück

5 Verlustfreie Verfahren

5.1 Statistische Verfahren

5.1.1 Der Morse Code

5.1.2 Shannon-Fano Codierung

5.1.3 Huffman Codierung

5.1.4 Präfixfreie Codes

5.1.5 MNP - MicroCom Network Protokoll

5.1.6 Arithmetische Codierung

5.1.7 Adaptive Arithmetische Codierung

5.1.8 Quasiarithmetische Codierung

5.1.9 CABAC

5.1.10 Dynamische Markov Codierung

5.1.11 PPM

5.1.12 BWT - Burrows-Wheeler-Transformation

5.1.13 BWCA - Burrows-Wheeler Kompressions Algorithmus

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.

Huffman Algorithmus

1. Begonnen wird mit einer Sortierung der Elemente nach ihrer Gewichtung in absteigender Reihenfolge. Das Gewicht ist bspw. die Anzahl der Vorkommen eines Symbols im Text oder auch die Wahrscheinlichkeit ihres Auftretens in einer stationären Quelle.
2. Es werden die beiden Symbole mit dem geringsten Gewicht zu einem neuen Knoten zusammengefasst und aus der Liste entfernt. Der neue Knoten erhält das Gewicht beider Unterknoten und dieser wird mit seinem Gewicht in der Datenmenge für den Code abgelegt und korrekt einsortiert. Damit wurde das Problem m Symbole zu einem Code zusammenzufassen reduziert auf ein Problem m-1 Symbole zu einem Code zusammenzufassen.
3. Der Algorithmus bricht ab, wenn der Baum für ein Symbol berechnet werden muss. Ansonsten wird Schritt 2 ausgeführt.

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\lor 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\lor 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\lor C\lor D\lor E)=P(B\lor C)+P(D\lor 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\rightarrow 0,B\rightarrow 100,C\rightarrow 101,D\rightarrow 110,E\rightarrow 111$

Aufgabe(n) - Huffman-Beispiel 1

1.) [M02] Berechnen Sie die Summe, der im Beispiel 1 grün markierten Felder und vergleichen Sie ihn mit der mittleren Codewortlänge, dieses Codes.

2.) [M03] Bestimmen sie die Anzahl Vereinigungsoperationen (Konstruktion eines neuen Teilbaumes) in Abhängigkeit von der Anzahl der Symbole des Quellenalphabetes.

3.) [M05] Beweisen Sie die Aufwandsklasse O(n) für die Konstruktion dieses Baumes, wenn die Symbole vorsortiert sind.

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...

Aufgabe(n) - Huffman

1.) [M05] Berechnen Sie die Entropie und Redundanz für einen Zwei-Symbolcode mit den Wahrscheinlichkeiten (statistisch unabhängig) $p_{0}=0.71$ und $p_{1}=0.29$, wenn dieser mit einem Huffmancode der Länge 1 codiert wird. Welche Schlussfolgerungen können Sie aus diesem Ergebnis ableiten ?

2.) [M15] Wie kann man den Zwei-Symbolcode mit den Wahrscheinlichkeiten (statistisch unabhängig) $p_{0}=0.71$ und $p_{1}=0.29$ so verändern, dass die Redundanz bzgl. eines Huffman-Code mit der Länge 1 reduziert werden kann. Erläutern Sie ihren Vorschlag. Erläutern Sie unter welchen Nebenbedingungen dieser Code einsetzbar ist. Prüfen Sie welche Redundanz sich ergibt.

3.) [M17] Transformieren sie den Zwei-Symbolcode aus Aufgabe 1 in einen Vier-Symbolcode und Berechnen Sie die Wahrscheinlichkeiten neu. Entwerfen sie einen optimalen Huffman Code und berechnen die Redundanz neu. Vergleichen Sie die berechnete Redundanz mit der Redundanz aus Aufgabe 1 und interpretieren Sie das Ergebnis. Berechnen Sie die Symbolwahrscheinlichkeiten des Ausgabecodes für verschiedene Huffman-Bäume. Zu welchen Ergebnissen kommen Sie? Warum ist die Redundanz der Ausgabesymbole größer, kleiner oder gleich der Redundanz des Zwei-Symbolcodes? Welches Ergebnis ist für einen optimalen Code zu erwarten?

4.) [M12] Zeigen oder widerlegen Sie mit Hilfe eines binären Kommacodes, dass dieser bei statistisch unabhängigen EingabeSymbolen>2 in einen Ausgabecode überführt wird, der statistisch abhängige Ausgabesymbole besitzt.