Der Huffman Code wurde im Jahre 1952 von David A. Huffman entwickelt. Er dient z.B. in JPG-Daten zur Speicherplatz-Einsparung. Die Motivation hinter diesem Code ist die unbefriedigende Tatsache, das eine Variable immer einen gewissen Speicherplatz verbraucht, ob sie nun voll ausgenutzt wird, oder nicht! Die effizienteste und offensichtlichste Anwendung ist bei der Speicherung von Texten.

Ein Zeichen (char) verbraucht 8 Bit. Nun treten längst nicht alle Zeichen in der gleichen Häufigkeit auf, sondern haben verschiedene Häufigkeiten. So ist in der deutschen Sprache das „E“ der mit Abstand häufigste Buchstabe. Wenn man nun möglichst speichersparend Texte speichern möchte, könnte man häufigen Buchstaben einen kürzeren Bitcode geben. Auch Stopbits, die das Ende eines Zeichens markieren kosten Speicherplatz. Was man braucht ist eine Möglichkeit, um den Text in eine Bitfolge mit variablen Bitlängen ohne Stopbits zu transferieren, die aber trotzdem alle nötigen Informationen enthalten, um den Text hinterher wieder zum Ausgangszustand zu encoden.

Die Huffman-Codierung setzt auf Binäre Bäume, um den Code zu speichern und schnell zu benutzen.

Man benötigt für die Umsetzung von Text in Huffman Code 3 Schritte:

• Die Häufigkeitsverteilung des Textes
• Erstellung des Codes
• Eigentliches Codieren

Für die Häufigkeitsverteilung zählt man entweder die Buchstaben, oder man kennt die Sprache des Textes und benutzt die für diese Sprache ermittelten Häufigkeiten. Letzeres hat den Nachteil, das man nicht den für diesen Text optimalen Code erhält, aber man normalerweise trotzdem eine große Einsparung hat. Dafür spart man sich die Zählarbeit und hat bei allen zu speichernden Texten einen relativ guten und gleichen Code.

Egal auf welche Weise man es macht: Hinterher sollte man die Häufigkeit aller vorkommenden Buchstaben in z.B. einem Array gespeichert haben.

Benötigte Hilfsmittel: Funktionierende Binärbaum-Struktur

Für jeden Buchstaben erstellt man einen Baum, bzw. Wurzel. Es entsteht dadurch ein sogenannter Wald: Viele nicht verbundene Bäume. Umgangssprachlich macht man nun folgendes: Man verbindet nun so lange die Bäume mit der geringsten Häufigkeit, bis man nur noch einen Baum hat. Programmiertechnisch heißt das: Erstelle solange neue Bäume und weise ihnen die beiden seltensten Bäume als Blätter hinzu, bis nur noch ein Baum vorhanden ist.

Dieser Code leistet dies: [code] [/code]

Jetzt haben wir einen Baum, der die Codierung enthält: Linke Kanten stellen die 0 dar, Rechte die 1.

Um nun den Code für ein bestimmtes Zeichen zu erhalten könnten wir grundsätzlich 2 Methoden anwenden.

1. Wir sprechen das Blatt mit dem Zeichen an und hangeln uns den Baum nach oben, was voraussetzt das die benutzte Baumstruktur dies unterstützt. Außerdem müssen sämtliche Blätter in irgendeiner Weise direkt zugänglich sein.
2. Wir durchsuchen den Baum nach unserem benötigten Zeichen und merken uns welchen Weg wir gegangen sind. → Hier bietet sich eine rekursive Lösung an.

Da Rekursionen viel Schreibarbeit einsparen können und elegant sind (? und Programmierer grundsätzlich schreibfaul sind ?), werde ich den 2. Weg erklären.

In Hinsicht auf die Geschwindigkeit des Codes sollte man den Baum nur einmal bemühen, um die Codes für jedes Zeichen zu erhalten. Je nach Größe des Baumes „kostet“ ein Durchlauf weit mehr Aufrufe, als ein Array-Zugriff.

Autorendiskussion