Huffman-Codierung

Aus KGS-Wiki

Die Huffman-Codierung ist ein Codierungsverfahren, um Texte zu komprimieren. Dieses Verfahren wird unter anderem bei der Zip-Komprimierung eingesetzt, mit der Dateien und Verzeichnisse komprimiert werden können. 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⋅3=33 Bit Speicherplatz:

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

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⋅1=5 Bit für die fünf As, 2⋅2=4 Bit für die zwei Ns und 4⋅4=16 Bit für die einzelnen P, M, K und L:

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

Diese zweite Codierung wurde nach dem Huffman-Algorithmus erstellt, um den Text platzsparender darzustellen. Allein bei diesem kurzen Wort hat sich schon eine Verbesserung gezeigt: unkomprimiert wurden 3 Bit für ein Zeichen benötigt, komprimiert nur noch 2511≈2,27 Bit pro Zeichen.

Aber! Aber bei einem Huffman-codierten Text muss natürlich immer die Codierungstabelle mitgeliefert werden, was natürlich auch zusätzlichen Speicherplatz kostet. Insofern lohnt sich dieses Verfahren vor allem bei langen Texten mit kleinen Alphabeten.

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

k
l
a
u
s
-
g
r
o
t
h
c
e
Leerz.
n
m
ü

Schritt 3

k (1)
l (2)
a (1)
u (3)
s (3)
- (2)
g (1)
r (2)
o (1)
t (2)
h (2)
c (1)
e (3)
Leerz. (1)
n (2)
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.

k (1)
l (2)
a (1)
u (3)
s (3)
- (2)
g (1)
r (2)
o (1)
t (2)
h (2)
c (1)
e (3)
Leerz. (1)
n (2)
m (1)
ü (1)
2

g und o kommen ebenfalls nur einmal vor.

k (1)
l (2)
a (1)
u (3)
s (3)
- (2)
g (1)
r (2)
o (1)
t (2)
h (2)
c (1)
e (3)
Leerz. (1)
n (2)
m (1)
ü (1)
2
2

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

k (1)
l (2)
a (1)
u (3)
s (3)
- (2)
g (1)
r (2)
o (1)
t (2)
h (2)
c (1)
e (3)
Leerz. (1)
n (2)
m (1)
ü (1)
2
2
2
2

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, Bindestrich, r, t, h, n und die neuen Knoten k+a, g+o, c+Leerzeichen und m+ü. Sie werden ebenfalls paarweise verbunden.

k (1)
l (2)
a (1)
u (3)
s (3)
- (2)
g (1)
r (2)
o (1)
t (2)
h (2)
c (1)
e (3)
Leerz. (1)
n (2)
m (1)
ü (1)
2
2
2
2
4
4
4
4
4

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

k (1)
l (2)
a (1)
u (3)
s (3)
- (2)
g (1)
r (2)
o (1)
t (2)
h (2)
c (1)
e (3)
Leerz. (1)
n (2)
m (1)
ü (1)
2
2
2
2
4
4
4
4
4
6

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

k (1)
l (2)
a (1)
u (3)
s (3)
- (2)
g (1)
r (2)
o (1)
t (2)
h (2)
c (1)
e (3)
Leerz. (1)
n (2)
m (1)
ü (1)
2
2
2
2
4
4
4
4
4
6
7

Die vier Knoten mit einer 4 werden ebenfalls paarweise verbunden

k (1)
l (2)
a (1)
u (3)
s (3)
- (2)
g (1)
r (2)
o (1)
t (2)
h (2)
c (1)
e (3)
Leerz. (1)
n (2)
m (1)
ü (1)
2
2
2
2
4
4
4
4
4
6
7
8
8

Langsam vervollständigt sich der Baum

k (1)
l (2)
a (1)
u (3)
s (3)
- (2)
g (1)
r (2)
o (1)
t (2)
h (2)
c (1)
e (3)
Leerz. (1)
n (2)
m (1)
ü (1)
2
2
2
2
4
4
4
4
4
6
7
8
8
13
16

Und so sieht der vollständige Baum aus

k (1)
l (2)
a (1)
u (3)
s (3)
- (2)
g (1)
r (2)
o (1)
t (2)
h (2)
c (1)
e (3)
Leerz. (1)
n (2)
m (1)
ü (1)
2
2
2
2
4
4
4
4
4
6
7
8
8
13
16
29

Schritt 6

0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
k (1)
l (2)
a (1)
u (3)
s (3)
- (2)
g (1)
r (2)
o (1)
t (2)
h (2)
c (1)
e (3)
Leerz. (1)
n (2)
m (1)
ü (1)
2
2
2
2
4
4
4
4
4
6
7
8
8
13
16
29

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.

Die vollständige Code-Tabelle sieht folgendermaßen aus:

a c e g h k l m n o r s t u ü - Leer
11001 11100 010 11010 1010 11000 0110 11110 1011 11011 1000 001 1001 000 11111 0111 11101
Diese Seite wurde von einer Lehrkraft überprüft.
Abgerufen von „https://wiki.kah.gs/index.php?title=Huffman-Codierung&oldid=7608“