Huffman-Kodierung


Die Lauflängenkodierung eignet sich dann, wenn wenige Zeichen sehr oft vorkommen. Ein Schwarz-Weiß-Bild kann mit gerade mal 2 Informationen (Schwarz / Weiß) aufgebaut werden, daher ist diese Situation perfekt für die Lauflängenkodierung geeignet. Dagegen ist die Lauflängenkodierung für einen Text ungeeignet, da in der Sprache praktisch keine mehrfachen Informationen hintereinander auftreten.

In einem Text folgen meist höchstens zwei gleiche Buchstaben aufeinander. Wir suchen ein Verfahren, mit welcher ein Text symmetrisch komprimiert abgespeichert werden kann.

Sie erinnern sich:

  • komprimieren = Information wird mit einem bestimmten Algorithmus mit weniger Speicherplatz gespeichert
  • symmetrisch = Information kann komprimiert werden und später verlustfrei wieder entkomprimiert (extrahiert) werden

Zuerst muss klar sein, wie ein Text gespeichert wird. Je nach verwendeter Code-Tabelle (ASCII, UTF,...) wird einem Textzeichen eine Bitfolge zugeordnet. Je nachdem, wie viele Zeichen in einer Kodierung kodiert werden, ist die notwendige Bitfolge unterschiedlich lang.

  • Beim ASCII-Code wird ein Zeichen mit 1 Byte = 8 Bit kodiert, so dass damit 256 Zeichen kodiert werden können.
  • Beim UTF-Code wird ein Zeichen meist mit 4 Byte = 4 x 8 = 32 Bit kodiert, so dass damit \(2^{32} = 4.294.967.296\) Zeichen kodiert werden können.

Wenn ein Text im UTF-Code gespeichert ist und jedes Zeichen 4 Byte Speicherplatz benötigt, kann bei langen Texten viel Speicherplatz notwendig werden. Im Folgenden sollen Sie ein Verfahren kennenlernen, mit welchem ein Text platzsparend komprimiert und wieder extrahiert werden kann: Kodierung mit variabler Länge. Exemplarisch werden wir das Huffman-Verfahren genauer ansehen.


Häufigkeit von Buchstaben

Bei einem deutschen Text variiert die Häufigkeit von Buchstaben: Häufigkeit von Buchstaben in Wörtern . In einem Roman ist also zu erwarten, dass es sehr oft den Buchstaben "e" und sehr selten den Buchstaben "y" gibt.

Diese Einsicht führt zur Grundidee der Huffman-Kodierung. Jedem Zeichen werden nicht die 4 Byte aus dem UTF-Code zugeordnet, sondern man sucht eine eigene Kodierung, die nur speziell für das Dokument gilt, das man komprimieren möchte. Die Idee der Kodierung ist folgende:

  • man erstellt eine Liste von Zeichen, die in einem Text vorkommen.
  • man zählt jedes Zeichen und stellt fest, wie oft es im Text vorkommt.
  • Jedem Zeichen wird ein neue Bitfolge aus 1 und 0 zugeordnet. Dabei soll die Bitfolge um so kürzer sein, je häufiger ein Zeichen im Text vorkommt.

Ein Beispiel: Das Wort "erdbeere" soll komprimiert werden. Im ASCII-Code bräuchte man 8 x 8 = 64 Bit, um dieses Wort zu speichern, wir versuchen es mit einer deutlich kürzeren Bitfolge.

Versuch 1:

"e" kommt 4 Mal vor: also bekommt "e" den Code 1
"r" kommt 2 Mal vor: also bekommt "r" den Code 0
"d" und "b" kommen nur ein einziges Mal vor: Also "d" = 10; "b" = 11.

"erdbeere" würde kodiert werden mit: 1010111101. Das ist im Vergleich zu den 64 Bit im ASCII-Code ein ziemlich kurzer Code. Aber die Extrahierung des Originaltextes funktioniert nicht! Das Problem ist, wenn man die kodierte Bitfolge durchläuft, dann weiß der Algorithmus nicht, ob die Bitfolge "10" ein "d" oder "er" sein soll. So kurz geht es also doch nicht.


Eineindeutige Bitfolgen

Wie kann ein Text komprimiert werden, so dass der Text wieder eindeutig extrahiert werden kann? Woher soll der Algorithmus wissen, wann ein Zeichen zu Ende ist und das neue Zeichen beginnt. Man könnte die Idee haben ein Trennzeichen einzufügen, das zwei kodierte Bitfolgen voneinander abtrennt. Aber wie soll das Trennzeichen aussehen? Woher weiß der Algorithmus, wann ein Trennzeichen beginnt und eine Zeichen-Bitfolge endet?

Die Informatiker fanden eine recht einfache Lösung für das Problem: man verwendet kein Trennzeichen, sondern sorgt dafür, dass jedem Zeichen im Text eine Bitfolge zugeordnet wird, die folgenden Regeln genügt:

  • Jede Bitfolge ist einmalig.
  • Keine Bitfolge stimmt mit dem Anfang einer anderen Bitfolge überein.

Aufgabe 1:

Überlegen Sie sich mit Hilfe dieser beiden Regeln eine Kodierung für die Zeichen in "erdbeere", so dass nach einer Kodierung die Extrahierung eindeutig funktionieren kann.

Mögliche Lösung: hier klicken...
Eine mögliche Kodierung ist: "b" = 111; "d" = 110; "r" = 10; "e" = 0

Damit wird aus "erdbeere" die Bitfolge: 01011011100100

Bei einer Extrahierung geht der Algorithmus durch die Bitfolge und vergleicht die Bits mit der "Legende".

0 gibt es: 0 = e. Der erste Buchstabe ist "e".
1 gibt es nicht, also nächstes Bit dazu. 10 gibt es: 10 = r. Der zweite Buchstabe ist "r".
1 gibt es nicht, also nächstes Bit dazu. 11 gibt es nicht, also nächstes Bit dazu. 110 gibt es: 110 = d. Der dritte Buchstabe ist "d".
1 gibt es nicht, also nächstes Bit dazu. 11 gibt es nicht, also nächstes Bit dazu. 111 gibt es: 111 = b. Der vierte Buchstabe ist "b".
0 gibt es: 0 = e. Der fünfte Buchstabe ist "e".
0 gibt es: 0 = e. Der sechste Buchstabe ist "e".
1 gibt es nicht, also nächstes Bit dazu. 10 gibt es: 10 = r. Der siebte Buchstabe ist "r".
0 gibt es: 0 = e. Der achte Buchstabe ist "e".

Damit wurde "erdbeere" eindeutig wieder extrahiert.

Wie findet man eineindeutige Bitfolgen?

Der typische Ablauf für die Komprimierung eines Textes ist folgender:

  • ermittle alle Zeichen, die in einem Text vorkommen
  • ermittle die Häufigkeit für jedes Zeichen (zählen)
  • Finde Bitfolgen für jedes Zeichen, die einmalig sind und bei der keine Bitfolge mit dem Anfang einer anderen Bitfolge übereinstimmt.
  • Wandle den Text mit Hilfe der neuen Bitfolgen in eine komprimierte Bitfolge um und speichere die "Legende" (Zuordnung von Zeichen zu kurzer Bitfolge) mit ab.

Das Auffinden von geeigneten Bitfolgen durch einen Algorithmus ist schwierig. Huffman hatte 1952 einen Algorithmus dafür vorgeschlagen. Diesen Algorithmus können Sie auf folgender Internetseite in Aktion sehen.

Aufgabe 2:

Öffnen Sie folgende Internetseite in einem neuen Fenster: Huffman-Kodierung

Geben Sie das Wort "erdbeere" ein, klicken Sie auf "Build tree" und beobachten Sie die Entstehung des binären Baums (eine Struktur, bei der von einem Knoten immer genau zwei weitere Knoten ausgehen). Wenn der Algorithmus hängen bleibt, laden Sie die Seite bitte neu. Wenn der Algorithmus erfolgreich war steht unten die Meldung "Animation Completed".

Wie kommt man von diesem binären Baum zu der Code-Zuordnung: "b" = 111; "d" = 110; "r" = 10; "e" = 0, die in der Lösung zur letzten Aufgabe angegeben wurde?

Mögliche Lösung: hier klicken...
Man wählt "links = 1" und "rechts = 0". Dann geht man entlang des Baums bis zu einem Zeichen und notiert die Bitfolge.

Also: "b" = links, links, links = 111; "d" = links, links, rechts = 110; "r" = links, rechts = 10; "e" = rechts = 0.

Wie funktioniert der Huffman-Algorithmus?

Nachdem klar ist, wie aus einem Huffman-Baum die Kodierung für einen Text erzeugt wird, fehlt nur noch die Kenntnis darüber, wie der Huffman-Baum erzeugt wird. Das sollen Sie sich mit Hilfe der Animation selbst klar machen.

Aufgabe 3:

Öffnen Sie folgende Internetseite in einem neuen Fenster: Huffman-Kodierung

Geben Sie unterschiedliche Worte ein und lassen Sie sich jeweils einen binären Baum erzeugen.

Erstellen Sie in Ihrer Arbeitsgruppe eine Dokumentation in einem Programm Ihrer Wahl zum Thema: Wie wird zu einem gegebenen Text ein Huffman-Baum erzeugt? Legen Sie dazu einen zu komprimierenden Text fest. Der Text sollte mindestens 10 verschiedene Zeichen beinhalten.

Geben Sie die Dokumentation im Aufgabenmodul ab.

Zur Erstellung der Dokumentation können Sie die Pause-Funktion der Animation nutzen und den entstehenden Baum mit Hilfe eines geeigneten Tools in Ihre Dokumentation einfügen. Jeder Schritt sollte zusätzlich zur Bildschirmkopie mit einem kurzen Text erklärt werden.