Huffman-Kodierung

Shortlinks

Allgemein

Die Huffman-Kodierung ist eine Entropiekodierung, die von David Huffman im Jahr 1952 entwickelt wurde. Durch diese Kodierung werden einer festen Anzahl Zeichen unterschiedlich lange Codes zugeordnet, Zeichen die häufig vorkommen erhalten kurze Codes und Zeichen, die selten vorkommen erhalten lange Codes. Da aus der komprimierten Datei über eine Dekodierung wieder die Originaldatei erstellt werden kann handelt es sich um eine verlustfreie Datenkompression.
Die Huffman-Kodierung wird aufgrund ihrer Schnelligkeit und da sie nicht durch ein Patent geschützt wurde sehr viel verwendet, obwohl es Entropiekodierungen gibt, die bessere Resultate erbringen, wie beispielsweise die Arithmetische Kodierung. Die Huffman-Kodierung wird bei JPG und bei MP3 eingesetzt.

Huffman Baum

Die Huffman-Kodierung basiert auf einem Baum. Dieser Baum besteht aus Ästen und Blättern. Die Blätter sind dabei die Zeichen, die Codiert werden und die Äste sind der Weg (also der Code), der zu den Blättern führt. In diesem Teil schauen wir uns an, wie ein solcher Baum aufgebaut wird und wie er schlussendlich für die Kodierung benutzt wird.

Aufbau des Baumes

Um den Baum aufzubauen muss zuerst die Wahrscheinlichkeit der einzelnen Zeichen bestimmt werden. Dies kann sehr einfach gemacht werden, indem die Anzahl der Vorkommnisse durch die Gesamtanzahl an Zeichen geteilt wird. Wenn also ein Satz, der aus den Zeichen Z = {z1, z2, z3, ..., zm} besteht können die jeweiligen Wahrscheinlichkeiten durch folgende Formel berechnet werden, wobei m die gesamte Anzahl an Zeichen ist und zi 1 beträgt, wenn das betrachtete Zeichen zi ist und 0, wenn nicht.

pzi =
1m
*
m∑i = 1
zi

Nun müssen die Zeichen mit absteigender Wahrscheinlichkeit von links nach rechts in eine Tabelle eingetragen werden. In diesem Beispiel werden alle Häufigkeiten als verschieden betrachtet, wenn aber nun mehrere Zeichen gleich viel vorkommen würden, könnten sie willkürlich angeordnet werden.

Ebene Blätter / Baum
0
z1
pz1
z2
pz2
z3
pz3
z4
pz4
z5
pz5
z6
pz6
z7
pz7
z8
pz8
z9
pz9

Nachdem die Zeichen eingeordnet wurden werden die niedrigsten Wahrscheinlichkeiten in einem Ast zusammengefasst und haben somit eine grössere Wahrscheinlichkeit.

Ebene Blätter / Baum
1 pz2 + pz1
0
z1
pz1
z2
pz2
z3
pz3
z4
pz4
z5
pz5
z6
pz6
z7
pz7
z8
pz8
z9
pz9

Danach wird die Tabelle wieder neu angeordnet, sodass die Elemente mit absteigender Wahrscheinlichkeit von links nach rechts geordnet werden. Das Bedeutet, dass jetzt die folgenden Vergleiche durchgeführt werden müssen.

pz1 + pz2 > pz3
pz1 + pz2 > pz4
pz1 + pz2 > pz5
pz1 + pz2 > pz6
pz1 + pz2 > pz7
pz1 + pz2 > pz8
pz1 + pz2 > pz9

Wenn einer der Vergleiche nicht stimmt, dann kann über alle nachfolgenden Elemente ausgesagt werden, dass sie nicht stimmen. Deswegen müssen diese Vergleiche nicht mehr durchgeführt werden. Falls der Baum grösser wir, macht es Sinn einen effizienten Sortierungsalgorithmus anzuwenden. Nachdem die Zeichen wieder neu angeordnet sind können wir wieder von vorne anfangen, ausser dass alle Zeichen, die nicht mit einem Ast zusammengefasst wurden eine Ebene aufsteigen und die zusammengefassten Zeichen als ein Zeichen auf der höheren Ebene betrachtet werden. Der Baum ist fertig, wenn alle Zeichen in einem Ast zusammengefasst wurden, dessen Wahrscheinlichkeit 1 beträgt. Keine Angst, wenn du es bis jetzt noch nicht richtig verstanden hat, es folgt ein konkretes Beispiel, in dem der Algorithmus vollständig ausgeführt wird.

Konkretes Beispiel

In diesem Beispiel wollen wir den Satz: "ein-kleines-beispiel" kodieren. Zuerst müssen wir die Wahrscheinlichkeiten der einzelnen Buchstaben berechnen.

pe =
520
=
14
,
pi =
420
=
15
,
pn =
220
=
110
,
p- =
220
=
110
,
pk =
120
,
pl =
220
=
110
,
ps =
220
=
110
,
pb =
120
,
pp =
120

Aus diesen Wahrscheinlichkeiten erstellen wir nun unseren Baum. Dabei müssen die Zeichen nach ihrer Wahrscheinlichkeit von links nach rechts geordnet werden.

Ebene Blätter / Baum
0
e
14
i
15
n
110
l
110
s
110
-
110
k
120
b
120
p
120

Nun werden die Zeichen mit den niedrigsten Wahrscheinlichkeiten zusammengefasst.

Ebene Blätter / Baum
1
110
+
120
=
320
120
+
120
=
110
0
e
14
i
15
n
110
l
110
s
110
-
110
k
120
b
120
p
120

Jetzt werden die Zeichen, die nicht zusammengefasst wurden in die Ebene 1 angehoben. In der Ebene 1 werden die Zeichen wieder nach ihren Wahrscheinlichkeiten geordnet. Danach werden wieder die Zeichen mit den tiefsten Wahrscheinlichkeitswerten zusammengefasst.

Ebene Blätter / Baum
2
110
+
110
=
15
110
+
110
=
15
1
e
14
i
15
110
+
120
=
320
n
110
l
110
s
110
120
+
120
=
110
0
-
110
k
120
b
120
p
120

Wieder werden die Wahrscheinlichkeiten verglichen und die Zeichen werden neu angeordnet und auf die gleiche Ebene angehoben. Danach werden wieder die Zeichen mit den niedrigsten Wahrscheinlichkeiten zusammengefasst.

Ebene Blätter / Baum
3
15
+
320
=
720
2
e
14
i
15
110
+
110
=
15
110
+
110
=
15
110
+
120
=
320
1
n
110
l
110
s
110
120
+
120
=
110
-
110
k
120
0
b
120
p
120

Jetzt werden die Zeichen wieder ihrer Wahrscheinlichkeit entsprechend neu angeordnet und auf eine Ebene angehoben. Danach werden wieder diejenigen mit den kleinsten Wahrscheinlichkeiten zusammengefasst.

Ebene Blätter / Baum
4
15
+
15
=
25
3
15
+
320
=
720
e
14
i
15
110
+
110
=
15
2
110
+
110
=
15
110
+
120
=
320
n
110
l
110
1
s
110
120
+
120
=
110
-
110
k
120
0
b
120
p
120

Wieder erhalten die Zeichen eine neue Anordnung und es werden alle auf die gleiche Ebene gebracht. Danach werden wieder die Zeichen mit der kleinsten Wahrscheinlichkeit zusammengefasst.

Ebene Blätter / Baum
4
720
+
14
=
35
3
15
+
15
=
25
15
+
320
=
720
e
14
2
i
15
110
+
110
=
15
110
+
110
=
15
110
+
120
=
320
1
n
110
l
110
s
110
120
+
120
=
110
-
110
k
120
0
b
120
p
120

Nun sind wir fast am Ende angelangt. Es gibt nur noch zwei Äste, die zusammengefasst werden können. Die Zeichen werden also wieder neu angeordnet und die letzten Äste werden zusammengefasst.

Ebene Blätter / Baum
5
35
+
25
= 1
4
15
+
320
=
720
15
+
15
=
25
3
15
+
320
=
720
e
14
i
15
110
+
110
=
15
2
110
+
110
=
15
110
+
120
=
220
n
110
l
110
1
s
110
120
+
120
=
110
-
110
k
120
0
b
120
p
120

In Python geschriebener Beispielcode

# a ist der String, auf dem eine Basis für einen Huffman-Baum aufgebaut wird def base(a): p = [] lenght = len(a) x = 0 i = 0 # Eine While-Schleife wird benötigt, da unbekannt ist, wie viel mal sie durchlaufen wird while x < lenght: # Zählt wie oft ein Zeichen im String vorkommt counter = float(a.count(a[0])) # Entfernt das Zeichen, damit es nur einmal gezählt wird a = a.replace(a[0], '') # Definiert die Wahrscheinlichkeit des Zeichens p.append(counter / lenght) i += 1 x += counter # Sortiert die Liste mit den Wahrscheinlichkeiten in absteigender Reihenfolge p.sort(reverse = True) return p # Die Liste base ist die Basis, auf der ein Huffman-Baum aufgebaut wird def Tree(base): # Gibt in jedem Durchlauf eine Ebene der Basis aus print(base) # Abbruchbedingung, wenn der Baum fertig ist, dann ist die Wahrscheinlichkeit 1 if base[0] == 1: return # Addiert die zwei niedrigsten Wahrscheinlichkeiten base[-2] = base[-1] + base[-2] base.remove(base[-1]) # Die Liste wird wieder sortiert base.sort(reverse = True) # Die Funktion wird rekursiv aufgerufen Tree(base) a = 'ein-kleines-beispiel' # Ruft die Funktionen auf, die einen Huffman-Baum als Matrix ausgeben Tree(base(a))

Beispielaufgaben

Nun kannst du Aufgaben zu Huffman-Bäumen lösen. Dabei wird dir entweder ein Huffman-Baum als Input gegeben und du musst den zugehörigen String herausfinden, oder es wird ein String gegeben und du musst den zugehörigen Huffman-Baum herausfinden. Der String wird zufällig generiert, es werden also höchstwahrscheinlich keine sinnvollen Wörter erscheinen.
Fülle das Feld mit dem Baum so aus, dass du immer zuerst das Zeichen und danach die zugehörige Wahrscheinlichkeit, durch Komma abgetrennt hinschreibst. Für die höheren Ebenen füge jeweils, analog zu den Wahrscheinlichkeiten die Zeichen zusammen. Schreibe den Baum so, dass du für jedes Zusammenfassen eines Elementes eine neue Ebene anfängst. Falls das Format nicht genau stimmt kann deine Lösung nicht erkannt werden. Falls dir die Vorgaben nicht klar sind kannst du die erste Aufgabe als gelöstes Beispiel benutzen, indem du auf "Lösung anzeigen" drückst. Wenn der Baum nicht ganz in das Textfeld hineinpasst kannst es mit der Maus verändern, indem du an der Ecke unten links ziehst.


Am besten zeichnest du dir den Huffman-Baum auf Papier aus und füllst ihn danach in das vorgegebene Textfeld ein, da es nicht so einfach ist, ihn direkt hineinzuschreiben.

Baum String




Kodierung der Zeichen

Allgemein

Bis jetzt haben wir gelernt, wie man einen Huffman-Baum aufgebaut. Nun geht es noch darum, wie man diesen einsetzen kann um Zeichen zu kodieren.
Um die Zeichen zu kodieren müssen wir sie in binärer Form darstellen. Dafür kann sehr einfach der vorher aufgebaute Huffman-Baum gebraucht werden. Dabei wird immer beim Stamm (ganz oben, dort wo die Wahrscheinlichkeit 1 beträgt) angefangen und wenn eine Abzweigung nach links genommen wird eine 0 geschrieben, ansonsten eine 1. So bekommen die Zeichen also genau so lange Codes, wie Ebenen durchquert werden müssen, bis die Zeichen erreicht werden.
Die Dekodierung eines Code kann erst schwierig erscheinen, da die Codes jeweils unterschiedliche Längen haben, abhängig vom Informationsgehalt des Zeichens. Es ist aber schnell erkennbar, wenn man ein Code dekodiert, denn wenn man das erste Zeichen hat, dann wäre es sinnlos, dass der Code dort noch weiter geht, da der Baum nicht mehr weiter geht.

Konkretes Beispiel

Nun wollen wir uns die Huffman-Kodierung an einem konkreten Beispiel anschauen. Dafür nehmen wir dasselbe Beispiel, das auch schon für den Aufbau des Huffman-Baumes benutzt wurde, da wir so den Baum bereits erstellt haben. Wir haben also den String: "ein-kleines-beispiel" mit dem Huffman-Baum.

Ebene Blätter / Baum
5
35
+
25
= 1
4
15
+
320
=
720
15
+
15
=
25
3
15
+
320
=
720
e
14
i
15
110
+
110
=
15
2
110
+
110
=
15
110
+
120
=
220
n
110
l
110
1
s
110
120
+
120
=
110
-
110
k
120
0
b
120
p
120

Nun ordnen wir den Abzweigungen auf den Ästen den Code 0, wenn nach links abgezweigt wurde und den Code 1, wenn nach rechts abgezweigt wurde. Der Baum sieht dann also folgendermassen aus.

Ebene Blätter / Baum
5
01
35
+
25
= 1
4
01
15
+
320
=
720
01
15
+
15
=
25
3
01
15
+
320
=
720
e
14
i
15
01
110
+
110
=
15
2
01
110
+
110
=
15
01
110
+
120
=
220
n
110
l
110
1
s
110
01
120
+
120
=
110
-
110
k
120
0
b
120
p
120

Das erste Zeichen vom String: "ein-kleines-beispiel", der dekodiert werden soll ist ein 'e'. Wenn wir dieses 'e' nun im Huffman-Baum suchen, können wir erkennen, dass im ersten Ast nach links und im zweiten Ast nach rechts gehen müssen. Das 'e' erhält also den Code 01. Danach kommt ein 'i'. Um zum 'i' zu gelangen müssen wir beim ersten Ast nach rechts und beim zweiten Ast nach links abzweigen. So erhält das 'i' den Code 10. Der gesamte Code bis jetzt ist also 0110. Für die weiteren Zeichen erhalten wir die in der folgenden Tabelle aufgezeichneten Codes.

Zeichen Code Gesamtcode bis jetzt Auftrittswahrscheinlichkeit
e 01 01 0.25
i 10 0110 0.2
n 110 0110110 0.1
- 0010 01101100010 0.1
k 0011 011011000100011 0.05
l 111 011011000100011111 0.1
e 01 01101100010001111101 0.25
i 10 0110110001000111110110 0.2
n 110 0110110001000111110110110 0.1
e 01 011011000100011111011011001 0.25
s 0000 0110110001000111110110110010000 0.1
- 0010 01101100010001111101101100100000010 0.1
b 00010 0110110001000111110110110010000001000010 0.05
e 01 011011000100011111011011001000000100001001 0.25
i 10 01101100010001111101101100100000010000100110 0.2
s 0000 011011000100011111011011001000000100001001100000 0.1
p 00011 01101100010001111101101100100000010000100110000000011 0.05
i 10 0110110001000111110110110010000001000010011000000001110 0.2
e 01 011011000100011111011011001000000100001001100000000111001 0.25
l 111 011011000100011111011011001000000100001001100000000111001111 0.1

Der String: "ein-kleines-beispiel" kann also mit dem 60 Bit langen Code: 011011000100011111011011001000000100001001100000000111001111 kodiert werden. Wenn wir den String aber mit einer Kodierung kodieren würden, die keine Rücksicht auf den Informationsgehalt der Zeichen nimmt, bräuchten wir mindestens 4 Bit pro Zeichen, damit die 9 verschiedenen Zeichen dargestellt werden können. Somit wären mindestens 20 Zeichen * 4 Bit pro Zeichen = 80 Bit nötig, um den String zu kodieren. Somit haben wir 20 Bit redundante Daten eingespart mit der Huffman-Kodierung.

Beispielaufgaben

Jetzt da du gelernt hast, wie man einen Huffman-Baum aufbauen kann und wie dieser danach benutzt wird, um eine Zeichenkette zu kodieren ist es an der Zeit dieses Wissen in Aufgaben anzuwenden. Du hast entweder einen String gegeben, zu dem du einen Huffman-Baum erstellen musst, womit du ihn gleich noch kodieren kannst oder einen Code und den dazugehörenden Huffman-Baum zum dekodieren.


Der Baum muss die gleichen formalen Eigenschaften einhalten wie in der letzten Aufgabe. Der Baum wird immer noch so gelesen, dass eine Abzweigung nach links eine 0 bedeutet und eine Abzweigung nach rechts eine 1 bedeutet. Der Baum ist nun aber auf dem Kopf, er muss also von unten nach oben gelesen werden.

Baum Code String