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.

Alltagsbezug

Die Huffman-Codierung und ähnliche Verfahren werden für das Komprimieren von Dateiformaten wie DOCX, JPG oder MP3 eingesetzt. ¹

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. Der neue Knoten enthält die Summe der Häufigkeiten der ursprünglichen Knoten:

Dies wird wiederholt bis alle Knoten miteinander verbunden sind. Wenn zwei Knoten die gleiche Häufigkeit haben, spielt es keine Rolle, welcher gewählt wird. Im nächsten Schritt wird der kleinste Knoten «N» mit «R» zusammengefasst. Man könnte aber «N» auch mit «E» oder dem neuen Knoten «2» zusammenfassen.

Wichtig ist, dass immer die kleinsten Knoten zusammengefasst werden. Hier werden die zwei Knoten mit Häufigkeit 2 zusammengefasst:

Wenn der Baum fertig ist, 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

Zusammenfassung

Übungen

1. Decodieren

Decodieren Sie diese Bitfolge mit dem obenstehenden Codebaum. Das Symbol ⎵ steht für das Leerzeichen.

0111101011000110110101

2. Huffman-Codierung 1

1. Erstellen Sie zum Wort «MISSISSIPPI» eine Häufigkeitstabelle.

2. Erstellen Sie einen Huffman-Baum

3. Codieren Sie das Wort.

4. Angenommen, der Text würde mit UTF-8 codiert. Wie viele Bits können eingespart werden?

5. Angenommen die 4 Buchstaben würden ohne Huffman-Baum mit einer eigenen, minimalen Codierung codiert (daher so wenige Bits pro Buchstaben wie irgend möglich). Wie viele Bits wären dann nötig? Wie viele Bits werden im Vergleich dazu eingespart?

SSR

3. Huffman-Codierung 2

1. Erstellen Sie zum Wort «EXTERNER EFFEKT» eine Häufigkeitstabelle.

2. Erstellen Sie einen Huffman-Baum

3. Codieren Sie das Wort.

4. Lohnt sich die Huffman-Codierung? Wo würden Sie diese allenfalls einsetzen?

SSR

Take-Home Message

Footnotes

1. Quelle: Wikipedia: Huffman coding
   ↩