Einleitung

Der Huffman-Algorithmus basiert auf der Idee, häufig auftretenden Zeichen kurze Codes zuzuordnen. Selten auftretende Zeichen erhalten lange Codes. Dabei wird ein binärer Codebaum aufgebaut, mit dessen Hilfe die jeweiligen Codes zu den Zeichen ausgelesen werden können. Der Algorithmus ist unter anderem Bestandteil folgender Formate:

  • JPEG
  • ZIP
  • GZIP

Das Verfahren ist optimiert für Fax-, Schreibmaschinen- oder handgeschriebene Dokumente, eignet sich also weniger für Bilddaten, die sich wesentlich von diesem Typus unterscheiden. Es kann unter Umständen sogar sein, dass diese Daten nach der Kodierung größer sind als vorher.

Dieses Modul beschreibt vor allem das Grundprinzip des Huffman-Algorithmus, jedoch auch kurz die verschiedenen Varianten davon.

Entwicklungsgeschichte

Der Algorithmus wurde von David A. Huffman, der damals am MIT (Massachusetts Institute of Technology) studierte, etwa um 1952 entwickelt. David A. Huffman wurde später Mitbegründer des Computer Science Department an der University of Califoria at Santa Cruz (UCSC). Das Verfahren zur Datenkompression wurde später weiterentwickelt und wird in bestimmten Bereichen nach wie vor eingesetzt.
Die Huffman- Kodierung unterliegt keiner patentrechtlichen Einschränkung.

Kodierung

Das Grundprinzip der Huffman-Kodierung sieht folgendermaßen aus:
Ausgegangen wird von einer Häufigkeitszuordnung aller vorkommenden Zeichen, beispielsweise eine Tabelle wie diese:

String: Walter_war_alt (_ steht für Leerzeichen)
Zeichen: W a l t e r w _
Häufigkeit: 1 3 2 2 1 2 1 2
In %: 7,15 21,43 14,29 14,29 7,15 14,29 7,15 14,29


Dann werden im Baum jeweils die Endknoten mit der geringsten Auftrittswahrscheinlichkeit einem neuen Überknoten zugeordnet, dem die Summe der beiden Wahrscheinlichkeiten zugewiesen wird (hier gibt es oft mehrere Möglichkeiten den Baum aufzubauen, innerhalb eines fertigen Kodierbaumes sind die Codes aber natürlich eindeutig).
Das wiederholt sich so lange bis es einen Wurzelknoten gibt, in dem alle Knoten zusammengeführt werden. Um den Code für jedes Zeichen zu bekommen, beginnt man bei der Wurzel, also hier dem Knoten mit der Beschriftung 14 (= die Länge des Strings), den Weg bis zu dem benötigten Zeichen zurückzuverfolgen und notiert dabei immer die 0 oder 1 an der Verbindung zwischen den Knoten.

Den Vorgang für das Stringbeispiel "Walter war alt" sehen Sie in folgender Animation:

Dekodierung

Für die Dekodierung benötigt man neben dem zurück zu kodierenden String auch den zur Kodierung verwendeten Binärbaum. Die Abfolge an Binärdaten, wie in diesem Beispiel „00000110011000111110100010111110101100110“ wird dann Zeichen für Zeichen zurückkodiert. Anhand des Binärbaumes geht man von der Wurzel aus und verfolgt den Weg durch den Baum, der durch die 01-Folge der Zeichenkette vorgegeben bis man zu einem Endknoten (Blatt) gelangt Im konkreten Fall kommt man nach 0000 zum Endknoten- an diesem steht das Zeichen „W“.
Anschließend beginnt man mit dem nächsten Zeichen im String wieder bei der Wurzel des Binärbaums. Auf diese Weise wird die gesamte Abfolge von 0 und 1 in den ursprünglichen String zurück verwandelt. Die Codes für die Zeichen sind eindeutig - das heißt wenn 0000 der Code für ein Zeichen ist, kann kein Zeichen durch z.B. 000 dargestellt werden, da sonst bei der Dekodierung mehrere Lösungen möglich wären und die Informationen verloren gehen könnten.

Varianten

Zur Erstellung des Codebaums benötigt man eine bestimmte statistische Zeichenverteilung. Aus der Frage nach der Ermittlung dieser Verteilung ergeben sich die folgenden Varianten:

  • Statische Verteilung
  • Dynamische Verteilung
  • Adaptive Verteilung
Um die Zeichenverteilung korrekt zu ermitteln, benötigt man Einsicht in die gesamten Daten, da die Verteilung zu Beginn des Kodiervorganges noch nicht bekannt ist und im Normalfall auch nicht über den gesamten Datenbestand hinweg gleich bleibt.

Statische Kodierung
Bei dieser Art wird ein fest vorgegebener Baum verwendet, der nicht auf die Besonderheiten der vorliegenden Daten eingeht, sondern völlig unabhängig davon auf einer Standardanalyse beruht (z.B. Häufigkeitsverteilung von Buchstaben in einer bestimmten Sprache). Es gibt also vordefinierte Bäume für verschiedene Einsatzbereiche wie z.B. englischsprachige Texte. (Hier kennt man die Buchstaben als Buchstaben, was beim Fax nicht der Fall ist).
Wenn die Daten der vom Baum angenommenen Häufigkeitsverteilung in etwa entsprechen, wird relativ gute Effizienz erreicht, der Kodierbaum wird im Encoder und Decoder gespeichert und muss nicht mit den Daten mitgeliefert werden. Weiters ist keine Laufzeitgenerierung des Baumes nötig. Allerdings sinkt die Kodiereffizienz stark, wenn die Daten nicht der angenommenen Häufigkeitsverteilung entsprechen.

Dynamische Kodierung
Hier wird nicht, wie bei der statischen Kodierung, ein fest vorgegebener Baum verwendet, sondern vor Beginn der Kodierung eine Häufigkeitsanalyse durchgeführt, aus der sich die Codes ergeben. Der Kodierbaum ist daher wesentlich besser an die vorliegenden Daten angepasst als eine standardisierte Tabelle, allerdings muss die Tabelle mit den Daten mitgeliefert werden, da sonst keine Dekodierung erfolgen kann. Weiters kann es sein, dass, wenn die dynamische Kodierung über die gesamten Quelldaten hinweg angewendet wird, und die Häufigkeiten nicht über alle Daten hinweg annähernd gleich bleibend sind, der Codebaum in späteren Segmenten nicht mehr der realen Häufigkeitsverteilung entspricht. Entgegenwirken kann man diesem Problem mit Hilfe einer Segmentierung der Daten, was aber wiederum mehr Aufwand in der Header-Bildung bedeutet.

Adaptive Kodierung
Diese Form der Kodierung verändert den Codebaum entsprechend der bereits encodierten Daten. Ausgegangen wird entweder von einem Standard- oder einem leeren Baum, wobei immer das letzte Zeichen in die Datengrundlage für die Weiterverarbeitung mit einbezogen wird. So wird die Kodierung kontinuierlich an die gegebenen Daten angepasst. Das Verfahren eignet sich allerdings nicht für kleinere Datenmengen, da hier, wie auch am Beginn der Kodierung die erreichte Effizienz sehr gering ist.

Nähere Informationen zu Grafikdateiformaten findet man unter folgenden Links:

Ergänzende und vertiefende Module