1. Huffman-Codierung
David Huffman hat 1952 ein Verfahren entwickelt, mit welchem Zeichen platzsparender codiert werden können. Seine Idee ist, dass Zeichen, welche häufig im Text vorkommen, einen kürzeren Code erhalten, als Zeichen, welche selten im Text vorkommen.
Die Huffman-Codierung und ähnliche Verfahren werden für das Komprimieren von Dateiformaten wie DOCX, JPG oder MP3 eingesetzt. 1
Codebaum
Ein Codebaum ist eine Struktur mit einem Startknoten. Von diesem aus geht es entweder nach links oder rechts unten weiter. Eine 0 im Code bedeutet nach links gehen, eine 1 nach rechts gehen. Wenn ein Knoten mit einem Buchstaben erreicht wird, hat man ein Zeichen decodiert, man beginnt wieder von vorne.
Erstellen eines Huffman-Baumes
Am Beispiel der Codierung des Texts «EINTRITT FREI» soll der Huffman-Algorithmus erläutert werden.
Zuerst zählt man, wie oft jedes Zeichen im Text vorkommt und erstellt eine Häufigkeitstabelle.
| Zeichen | Häufigkeit |
|---|---|
| ␣ | 1 |
| F | 1 |
| N | 1 |
| R | 2 |
| E | 2 |
| I | 3 |
| T | 3 |
Nun geht es darum, einen Codierungsbaum zu erstellen. Die Häufigkeiten der Buchstaben bilden je einen Knoten. Die Häufigkeit steht im Knoten, der Buchstaben darunter. Die Knoten werden nach Häufigkeit sortiert:
Nun werden die zwei Knoten mit den kleinsten Häufigkeiten an einen neuen Knoten angehängt und an letzter Stelle derselben Häufigkeit eingefügt. Der neue Knoten enthält die Summe der Häufigkeiten der ursprünglichen Knoten:
Dies wird wiederholt bis alle Knoten miteinander verbunden sind.
Treten mehrfach dieselben Häufigkeiten auf, spielt es für die Kompressionsrate keine Rolle, welche zwei Knoten/Blätter gewählt werden. Hier wurden «N» mit «R» zusammengefasst - man könnte aber auch «N» mit «E» oder mit dem neuen Knoten «2» zusammenfassen.
Wichtig ist, dass immer die kleinsten Knoten zusammengefasst werden. Hier wurden die zwei Knoten mit Häufigkeit «2» zusammengefasst.
Ist der Baum fertig, werden alle Äste, welche nach links zeigen, mit einer «0» markiert, alle die nach rechts zeigen mit einer «1».
Nun kann eine Codierungstabelle erstellt werden, indem der Code für jedes Zeichen vom Baum abgelesen wird:
| Zeichen | Code |
|---|---|
| I | 00 |
| T | 01 |
| N | 100 |
| R | 101 |
| E | 111 |
| ⎵ | 1100 |
| F | 1101 |
Alles nochmals Schritt für Schritt im Video
Übungen
Decodieren Sie diese Bitfolge mit dem obenstehenden Codebaum. Das Symbol ⎵ steht für das Leerzeichen.
0111101011000110110101
- Erstellen Sie zum Wort «MISSISSIPPI» eine Häufigkeitstabelle.Schritt 1
-
Angenommen, der Text würde mit UTF-8 codiert. Wie viele Bits können eingespart werden?
Laden... -
Der Vergleich mit UTF-8 ist nicht wirklich fair! Überlegen Sie sich, weshalb er nicht fair ist und wie dies "fairer" verglichen werden könnte.
Laden...
Minimale Codierung mit fester Bitlänge
Die minimale Codierung ist eine Codierung mit fester Bitlänge, wobei die Bitlänge minimal ist, d.h. es werden so wenige Bits wie möglich pro Zeichen verwendet. Bei 4 verschiedenen Zeichen braucht es mindestens 2 Bits, da mit 1 Bit nur 2 verschiedene Zeichen codiert werden können (0 und 1). Mit 2 Bits können 4 verschiedene Zeichen codiert werden (00, 01, 10, 11).
Das Wort «MISSISSIPPI IST EIN FLUSS» besteht aus 11 verschiedenen Zeichen: M, I, S, P, ⎵, T, E, N, F, L, U. Eine minimale Codierung mit fester Bitlänge ordnet jedem Zeichen so wenige Bits wie möglich zu. Da es 11 verschiedene Zeichen gibt, braucht es mindestens 4 Bits pro Zeichen, da mit 3 Bits nur 8 verschiedene Zeichen codiert werden können (; 000, 001, 010, 011, 100, 101, 110, 111), mit 4 Bits können verschiedene Zeichen codiert werden (0000, 0001, ..., 1111).
Wir können also jedem Zeichen 4 Bits zuordnen, z.B.:
| Zeichen | M | I | S | P | ⎵ | T | E | N | F | L | U |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Code | 0000 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 |
Die 25 Zeichen von «MISSISSIPPI IST EIN FLUSS» würden damit mit Bits codiert werden.
Der Vergleich der Huffman-Codierung mit UTF-8 ist nicht wirklich fair, da UTF-8 eine Codierung mit fester Bitlänge ist, bei der jedes Zeichen mit 8 Bits codiert wird, unabhängig von seiner Häufigkeit im Text. Die Huffman-Codierung hingegen ist eine Codierung mit variabler Bitlänge, bei der häufige Zeichen mit weniger Bits codiert werden als seltene Zeichen. Ein fairerer Vergleich wäre daher die Huffman-Codierung mit einer minimalen Codierung mit fester Bitlänge, bei der jedes Zeichen mit so wenigen Bits wie möglich codiert wird.
Weitere Übungen
- Schritt 1
Erstellen Sie zum Wort «EXTERNER EFFEKT» eine Häufigkeitstabelle.