Huffman-Codierung

Die Huffman-Codierung ist ein Codierungsverfahren, um Texte zu komprimieren. Ziel ist es, dieselbe Information mit weniger Speicherplatz darzustellen. Die Idee dahinter ist es, für häufiger verwendete Zeichen kürzere Codierungen zu verwenden als für seltener verwendete.

💬

Beispiel

Nehmen wir das Wort PANAMAKANAL.

Eine normale Codierung würde für alle Zeichen gleich viele Bits benötigen. Für die sechs verwendeten Buchstaben A, K, L, M, N, P bräuchte man je drei Bit und könnte sie zum Beispiel so codieren:

A	K	L	M	N	P
000	001	010	011	100	101

Damit bräuchte man für das Wort PANAMAKANAL $11\cdot 3=33$ Bit Speicherplatz.

Man könnte die Zeichen aber auch so codieren:

A	K	L	M	N	P
0	1100	1101	1110	10	1111

Damit bräuchte man für das Wort PANAMAKANAL nur noch 25 Bit Speicher, nämlich $5\cdot 1=5$ Bit für die fünf As, $2\cdot 2=4$ Bit für die zwei Ns und $4\cdot 4=16$ Bit für die einzelnen P, M, K und L.

Diese Codierung ist jetzt schnell hinimprovisiert, es gibt aber auch einen exakten Algorithmus, um aus einem gegebenen Textstück die optimale Huffman-Codierung zu berechnen.

Algorithmus

Der Algorithmus zur Codierung arbeitet folgendermaßen:

1. Such dir ein Textstück zum Codieren.
2. Schreibe alle Zeichen, die du für deine Codierung brauchst, nebeneinander am unteren Rand einer Seite auf.
3. Schreibe zu jedem Zeichen, wie oft es vorkommt. Kreise das Zeichen und die Zahl ein. Diese Kreise nennen wir "Knoten"
4. Such dir die beiden Knoten mit den kleinsten Zahlen, die noch keine Verbindung nach oben haben.
   1. Zeichne einen neuen Knoten darüber.
   2. Verbinde den neuen Knoten mit den beiden anderen Knoten.
   3. Zähle die Zahlen in den beiden anderen Knoten zusammen.
   4. Schreibe die Summe in den neuen Knoten.
5. Wiederhole Schritt 4 so lange, bis nur noch ein Knoten übrig ist, der keine Verbindung nach oben hat.
6. Beschrifte alle Verbindungen, die nach links zeigen, mit 0. Beschrifte alle Verbindungen, die nach rechts zeigen, mit 1.

Beispiel

Schritt 1

klaus-groth-schule neumünster soll mein Text sein.

Schritt 2

flowchart TD k(["k"]) l(["l"]) a(["a"]) u(["u"]) s(["s"]) -(["-"]) g(["g"]) r(["r"]) o(["o"]) t(["t"]) h(["h"]) c(["c"]) e(["e"]) space(["Leerz."]) n(["n"]) m(["m"]) ü(["ü"])

Schritt 3

flowchart TD k(["k (1)"]) l(["l (2)"]) a(["a (1)"]) u(["u (3)"]) s(["s (3)"]) -(["- (2)"]) g(["g (1)"]) r(["r (2)"]) o(["o (1)"]) t(["t (2)"]) h(["h (2)"]) c(["c (1)"]) e(["e (3)"]) space(["Leerz. (1)"]) n(["n (2)"]) m(["m (1)"]) ü(["ü (1)"])

Schritt 4 und 5

k und a kommen je einmal vor – sie werden zu einem neuen Knoten verbunden, in den wir eine 2 schreiben.

flowchart TD k(["k (1)"]) l(["l (2)"]) a(["a (1)"]) u(["u (3)"]) s(["s (3)"]) -(["- (2)"]) g(["g (1)"]) r(["r (2)"]) o(["o (1)"]) t(["t (2)"]) h(["h (2)"]) c(["c (1)"]) e(["e (3)"]) space(["Leerz. (1)"]) n(["n (2)"]) m(["m (1)"]) ü(["ü (1)"]) ka([2]) --- k ka --- a

g und o kommen ebenfalls nur einmal vor.

flowchart TD k(["k (1)"]) l(["l (2)"]) a(["a (1)"]) u(["u (3)"]) s(["s (3)"]) -(["- (2)"]) g(["g (1)"]) r(["r (2)"]) o(["o (1)"]) t(["t (2)"]) h(["h (2)"]) c(["c (1)"]) e(["e (3)"]) space(["Leerz. (1)"]) n(["n (2)"]) m(["m (1)"]) ü(["ü (1)"]) ka([2]) --- k ka --- a go([2]) --- g go --- o

Für c, m, ü und das Leerzeichen gilt dasselbe.

flowchart TD k(["k (1)"]) l(["l (2)"]) a(["a (1)"]) u(["u (3)"]) s(["s (3)"]) -(["- (2)"]) g(["g (1)"]) r(["r (2)"]) o(["o (1)"]) t(["t (2)"]) h(["h (2)"]) c(["c (1)"]) e(["e (3)"]) space(["Leerz. (1)"]) n(["n (2)"]) m(["m (1)"]) ü(["ü (1)"]) ka([2]) --- k ka --- a go([2]) --- g go --- o cspace([2]) --- c cspace --- space mü([2]) --- m mü --- ü

Jetzt gibt es keine Knoten mehr, in denen eine 1 steht und die keine Verbindung nach oben haben. Dafür gibt es zehn Knoten, in denen eine 2 steht: l, u, Bindestrich, r, t, h, n und die neuen Knoten k+a, g+o, c+Leerzeichen und m+ü. Sie werden ebenfalls paarweise verbunden.

flowchart TD k(["k (1)"]) l(["l (2)"]) a(["a (1)"]) u(["u (3)"]) s(["s (3)"]) -(["- (2)"]) g(["g (1)"]) r(["r (2)"]) o(["o (1)"]) t(["t (2)"]) h(["h (2)"]) c(["c (1)"]) e(["e (3)"]) space(["Leerz. (1)"]) n(["n (2)"]) m(["m (1)"]) ü(["ü (1)"]) ka([2]) --- k ka --- a go([2]) --- g go --- o cspace([2]) --- c cspace --- space mü([2]) --- m mü --- ü kago([4]) --- ka kago --- go cspacemü([4]) --- cspace cspacemü --- mü l-([4]) --- l l- --- - rt([4]) --- r rt --- t hn([4]) --- h hn --- n

Die kleinste Zahl, die jetzt in einem Knoten steht, ist die 3. u und s werden miteinander verbunden.

flowchart TD k(["k (1)"]) l(["l (2)"]) a(["a (1)"]) u(["u (3)"]) s(["s (3)"]) -(["- (2)"]) g(["g (1)"]) r(["r (2)"]) o(["o (1)"]) t(["t (2)"]) h(["h (2)"]) c(["c (1)"]) e(["e (3)"]) space(["Leerz. (1)"]) n(["n (2)"]) m(["m (1)"]) ü(["ü (1)"]) ka([2]) --- k ka --- a go([2]) --- g go --- o cspace([2]) --- c cspace --- space mü([2]) --- m mü --- ü kago([4]) --- ka kago --- go cspacemü([4]) --- cspace cspacemü --- mü l-([4]) --- l l- --- - rt([4]) --- r rt --- t hn([4]) --- h hn --- n us([6]) --- u us --- s

Jetzt gibt es noch einen Knoten mit einer 3, nämlich e. Dieser wird mit einem beliebigen Knoten mit einer 4 verbunden.

flowchart TD k(["k (1)"]) l(["l (2)"]) a(["a (1)"]) u(["u (3)"]) s(["s (3)"]) -(["- (2)"]) g(["g (1)"]) r(["r (2)"]) o(["o (1)"]) t(["t (2)"]) h(["h (2)"]) c(["c (1)"]) e(["e (3)"]) space(["Leerz. (1)"]) n(["n (2)"]) m(["m (1)"]) ü(["ü (1)"]) ka([2]) --- k ka --- a go([2]) --- g go --- o cspace([2]) --- c cspace --- space mü([2]) --- m mü --- ü kago([4]) --- ka kago --- go cspacemü([4]) --- cspace cspacemü --- mü l-([4]) --- l l- --- - rt([4]) --- r rt --- t hn([4]) --- h hn --- n us([6]) --- u us --- s el-([7]) --- e el- --- l-

Die vier Knoten mit einer 4 werden ebenfalls paarweise verbunden

flowchart TD k(["k (1)"]) l(["l (2)"]) a(["a (1)"]) u(["u (3)"]) s(["s (3)"]) -(["- (2)"]) g(["g (1)"]) r(["r (2)"]) o(["o (1)"]) t(["t (2)"]) h(["h (2)"]) c(["c (1)"]) e(["e (3)"]) space(["Leerz. (1)"]) n(["n (2)"]) m(["m (1)"]) ü(["ü (1)"]) ka([2]) --- k ka --- a go([2]) --- g go --- o cspace([2]) --- c cspace --- space mü([2]) --- m mü --- ü kago([4]) --- ka kago --- go cspacemü([4]) --- cspace cspacemü --- mü l-([4]) --- l l- --- - rt([4]) --- r rt --- t hn([4]) --- h hn --- n us([6]) --- u us --- s el-([7]) --- e el- --- l- rthn([8]) --- rt rthn --- hn kagocspacemü([8]) --- kago kagocspacemü --- cspacemü

Langsam vervollständigt sich der Baum

flowchart TD k(["k (1)"]) l(["l (2)"]) a(["a (1)"]) u(["u (3)"]) s(["s (3)"]) -(["- (2)"]) g(["g (1)"]) r(["r (2)"]) o(["o (1)"]) t(["t (2)"]) h(["h (2)"]) c(["c (1)"]) e(["e (3)"]) space(["Leerz. (1)"]) n(["n (2)"]) m(["m (1)"]) ü(["ü (1)"]) ka([2]) --- k ka --- a go([2]) --- g go --- o cspace([2]) --- c cspace --- space mü([2]) --- m mü --- ü kago([4]) --- ka kago --- go cspacemü([4]) --- cspace cspacemü --- mü l-([4]) --- l l- --- - rt([4]) --- r rt --- t hn([4]) --- h hn --- n us([6]) --- u us --- s el-([7]) --- e el- --- l- rthn([8]) --- rt rthn --- hn kagocspacemü([8]) --- kago kagocspacemü --- cspacemü usel-([13]) --- us usel- --- el- rthnkagocspacemü([16]) --- rthn rthnkagocspacemü --- kagocspacemü

Und so sieht der vollständige Baum aus

flowchart TD k(["k (1)"]) l(["l (2)"]) a(["a (1)"]) u(["u (3)"]) s(["s (3)"]) -(["- (2)"]) g(["g (1)"]) r(["r (2)"]) o(["o (1)"]) t(["t (2)"]) h(["h (2)"]) c(["c (1)"]) e(["e (3)"]) space(["Leerz. (1)"]) n(["n (2)"]) m(["m (1)"]) ü(["ü (1)"]) ka([2]) --- k ka --- a go([2]) --- g go --- o cspace([2]) --- c cspace --- space mü([2]) --- m mü --- ü kago([4]) --- ka kago --- go cspacemü([4]) --- cspace cspacemü --- mü l-([4]) --- l l- --- - rt([4]) --- r rt --- t hn([4]) --- h hn --- n us([6]) --- u us --- s el-([7]) --- e el- --- l- rthn([8]) --- rt rthn --- hn kagocspacemü([8]) --- kago kagocspacemü --- cspacemü usel-([13]) --- us usel- --- el- rthnkagocspacemü([16]) --- rthn rthnkagocspacemü --- kagocspacemü root([29]) --- usel- root --- rthnkagocspacemü

Schritt 6

flowchart TD k(["k (1)"]) l(["l (2)"]) a(["a (1)"]) u(["u (3)"]) s(["s (3)"]) -(["- (2)"]) g(["g (1)"]) r(["r (2)"]) o(["o (1)"]) t(["t (2)"]) h(["h (2)"]) c(["c (1)"]) e(["e (3)"]) space(["Leerz. (1)"]) n(["n (2)"]) m(["m (1)"]) ü(["ü (1)"]) ka([2]) ---|0| k ka ---|1| a go([2]) ---|0| g go ---|1| o cspace([2]) ---|0| c cspace ---|1| space mü([2]) ---|0| m mü ---|1| ü kago([4]) ---|0| ka kago ---|1| go cspacemü([4]) ---|0| cspace cspacemü ---|1| mü l-([4]) ---|0| l l- ---|1| - rt([4]) ---|0| r rt ---|1| t hn([4]) ---|0| h hn ---|1| n us([6]) ---|0| u us ---|1| s el-([7]) ---|0| e el- ---|1| l- rthn([8]) ---|0| rt rthn ---|1| hn kagocspacemü([8]) ---|0| kago kagocspacemü ---|1| cspacemü usel-([13]) ---|0| us usel- ---|1| el- rthnkagocspacemü([16]) ---|0| rthn rthnkagocspacemü ---|1| kagocspacemü root([29]) ---|0| usel- root ---|1| rthnkagocspacemü

Fertig! Jetzt können wir auf dem Weg vom obersten Knoten zu jedem Buchstaben seine Codierung ablesen.

Das e wird zum Beispiel mit 010 codiert, oder das a mit 11001.