· 

Die Huffman-Codierung

1. Einführung

Um ein ASCII-Zeichen im Computer darzustellen, werden 8 Bits (also ein Byte) verwendet, d. h. wenn du ein Wort mit 10 Buchstaben hast, dann werden 80 Bits (bzw. 10 Bytes) benötigt, um dieses im Computer zu speichern. Das muss doch auch einfacher gehen! Ja, man könnte z. B. die einzelnen Zeichen in einem Wort von links nach rechts durchgehen und für jeden "neuen" (d. h. bislang noch nicht aufgetauchten Buchstaben) einen Binärcode fixer Länge vergeben. Dabei zählst du einfach binär hoch und weist so den Buchstaben einen Binärcode (ggf. mit führenden Nullen) zu.

Es geht aber noch effizienter, nämlich durch den Huffman-Code. Der Buchstabe e kommt nämlich z. B. häufiger in Wörtern der deutschen oder englischen Sprache vor als z. B. das x. Es liegt also der Schluss nahe, häufig vorkommende Buchstaben mit so wenigen Zeichen wie möglich zu codieren. Statt also eine fixe Länge für Binärcodes vorzugeben, werden mit dem Huffman-Code die Zeichen in einem Wort mit Binärcodes variabler Länge codiert. 

Der Huffman-Code erfüllt übrigens die Fano-Bedingung, d. h. dass kein Codewort Anfangswort eines anderen Codewortes ist und somit jede codierte Zeichenreihe eindeutig decodierbar ist. Das wirst du später noch sehen.


2. Der Algorithmus

Wie läuft der Algorithmus ab?

Algorithmus: Huffman-Codierung

Eingabe: Wort
Ausgabe: Huffman-Code des Worts
  1. Zähle, wie oft die einzelnen Zeichen im zu codierenden Wort vorkommen.
  2. Verknüpfe die beiden Zeichen, die am seltensten im Wort vorkommen und schreibe an ihre Wurzel, wie oft diese beiden Zeichen zusammen im Wort auftauchen. Der Knoten mit dem Zeichen, das häufiger vorkommt, steht rechts. Was ist, wenn es mehrere Zeichen mit denselben Vorkommen gibt? Dann wählst du einfach eine von ihnen aus. Bei der Übertragung von Huffman-codierten Nachrichten muss nämlich im Allgemeinen die Code-Tabelle mit übertragen werden, d. h. je nach Aufbau des Huffman-Baums ergeben sich später unterschiedliche Binärcodes für die einzelnen Zeichen.
  3. Wiederhole Schritt 2 so lange, bis alle Zeichen als Knoten im Huffman-Baum vorhanden sind. Achte darauf, dass nun auch die neu enstandenen (Wurzel-)Knoten in die Betrachtung mit einfließen.
  4. Lies nun die die Binärcodes der einzelnen Zeichen ab. Schreibe dafür an jede linke Kante eine 0 und an jede rechte Kante eine 1. Gehe vom Wurzelknoten bis zu dem jeweiligen Blatt und sammle auf dem Weg alle Nullen und Einsen ein. An den Blättern stehen jetzt die Binärcodes der jeweiligen Zeichen.
  5. Ersetze die Zeichen in dem Wort durch die binären Darstellungen an den Blättern des Huffman-Baums.

3. Beispiel

Als Beispiel betrachten wir das Wort MISSISSIPPI. Dieses Wort hat 11 Zeichen, d. h. man würde 88 Bits benötigen, um dieses Wort im Computer zu speichern. 

In dem Wort tauchen (von links nach rechts) nur die Buchstaben M, I, S und P auf. Du könntest also die einzelnen Zeichen mit Binärcodes der Länge zwei codieren (weil es 4 verschiedene Buchstaben gibt):

  • M = 00
  • I = 01
  • S = 10
  • P = 11

Wenn du jedes Zeichen in dem Wort MISSISSIPPI durch die soeben erstellten Binärcodes ersetzt, erhältst du als Ergebnis das Wort 0001101001101001111101. Statt 88 Zeichen werden nun nur noch 22 Zeichen benötigt, was einer Speicherplatzersparnis von 75% entspricht!

Kann man mit dem Huffman-Code noch mehr Speicherplatz einsparen? Ja, kann man. Die einzelnen Buchstaben kommen nämlich sehr häufig in dem Wort vor und wenn man für die häufig vorkommenden Buchstaben nur kurze Binärcodes verwendet, ist das Wort mit noch weniger Zeichen speicherbar.

Der Algorithmus zur Ermittlung des Huffman-Codes sieht zunächst einmal vor, dass die Anzahl der Vorkommen der einzelnen Zeichen gezählt werden. Dann machen wir das doch mal: #FÜR YOUTUBE BESCHREIBEN#:

  • M: 1
  • I: 4
  • S: 4
  • P: 2

Es bietet sich also an, für die Buchstaben I und S möglichst kurze Binärcodes zu verwenden, weil sie ziemlich häufig im Wort vorkommen. Nun schreibt der Algorithmus vor, dass man einen Huffman-Baum erzeugt.

  • Wir suchen uns zunächst die beiden Zeichen aus, die am seltensten im Wort vorkommen und verknüpfen diese. Das wären in diesem Fall die Zeichen M und P. Den dazugehörigen Wurzelknoten nennen wir z. B. MP. An diesen schreiben wir, wie oft die beiden Zeichen M und P insgesamt im Wort vorkommen. Das wären 1+2=3 mal.
  • Nun schaust du, welche Zeichen jetzt am seltensten vorkommen und verknüpfst diese. An dem Knoten MP steht der Wert 3. Dieser besitzt aktuell den geringsten Wert und wird nun entweder mit I oder S verknüpft, da diese beiden Zeichen gleich oft im Wort vorkommen. Wir wählen an dieser Stelle S aus. Addiert ergibt sich an dem Wurzelknoten, den wir z. B. MPS nennen, dann der Wert 3+4=7.
  • Jetzt ist nur noch ein Zeichen übrig, nämlich das I. Der Wurzelknoten besitzt also den Wert 4+7=11.

Der Huffman-Baum sieht wie folgt aus:

An jede linke Kante kommt nun eine 0 und an jede rechte Kante eine 1.

Die Binärcodes der einzelnen Zeichen an den Blättern können wir ablesen, indem wir von der Wurzel bis zu dem jeweiligen Blatt navigieren, die entsprechenden Zahlen an den Kanten einsammeln und hintereinander schreiben.

  • Für das I also 0.
  • Für das M nacheinander 1-0-0.
  • Für das P nacheinander 1-0-1.
  • Für das S nacheinander 1-1.

Nun ersetzt du nacheinander die einzelnen Zeichen im Wort durch die gebildeten Binärcodes an den Blättern und erhältst als Ergebnis das Wort

100011110111101011010

Wie du siehst, besitzt das neue Wort sogar noch ein Zeichen weniger als die Variante mit der festen Binärcodelänge. Daraus ergibt sich eine Gesamtersparnis von ca. 76% zu nicht codierten Variante mit ASCII-Codes. Bei anderen Wörtern ist der Unterschied zwischen dem Huffman-Code und der Codierung mit fester Bytecodelänge noch größer.