Vorlesung: Codierung und Kryptographie
  Huffman-Codierung interaktiv
 

Vorbemerkungen | Codierung | Eigenschaften | Experimentiersystem | Anwendungsbeispiel | VortragMathematica-Programm | Literatur

   
   
 

Präfixfreie Codierung

Die vom Huffman-Algorithmus generierten Codewörter sind unterschiedlich lang, je nach dem wie häufig das entsprechende Zeichen im Text vorkommt. Woher weiß man dann bei der Decodierung, wann ein neues Zeichen beginnt? Dies liegt an der Präfixfreiheit des Huffman-Codes. Ein bekanntes Beispiel für einen Präfixcode ist das deutsche Telefonnummernsystem. Wählt man beispielsweise die Nummer „110“, dann „weiß“ das System, es folgen keine weiteren Ziffern und man wird mit der Polizei verbunden. Das Senden eines Endzeichens entfällt. Dies liegt daran, dass die Ziffern „110“ nie Anfangsteil (=Präfix) einer anderen Telefonnummer sind, d.h. in unserem Telefonnetz gibt es beispielsweise keinen Telefonanschluss mit der Nummer „1101“. Genauso ist jede Telefonnummer nie vollständig im Anfang einer anderen Telefonnummer enthalten. Dies bezeichnet man als präfixfreie Codierung. Der Huffman-Code ist ebenfalls ein solcher präfixfreier Code, d.h. kein Codewort ist Anfang eines anderen Codewortes. Am Codebaum erkennt man einen präfixfreien Code an der Eigenschaft, dass die Zeichen nur an den Endpunkten des Baumes (den so genannten Blättern) zu finden sind und dies ist beim Huffman-Baum konstruktionsbedingt immer der Fall.

Optimalität

Das Huffman-Verfahren erstellt immer den möglichsten kürzesten Code, d.h. man kann einen Text mit Hilfe der Häufigkeitsverteilung nicht besser codieren. Man sagt, die Codierung ist optimal. Als Kenngröße verwendet man dafür die mittlere Codewortlänge. Sie gibt an, wieviele Binärzeichen im Durchschnitt pro Textzeichen benötigt werden. Werden wie in dem besprochenen Beispiel 21 Bit für 11 Zeichen benötigt, ist die mittlere Codewortlänge 21/11= 1,91 Bit. Das Huffman-Verfahren minimiert die mittlere Codewortlänge.
Dabei besteht ein interessanter Zusammenhang zu dem Begriff der Entropie. Die Entropie einer Nachricht gibt an, wie stark die Häufigkeiten der Textzeichen in einer Nachricht schwanken. Ist die Entropie klein, sind die Häufigkeiten der vorkommenden Zeichen sehr unterschiedlich. Umgekehrt ist die Entropie groß, wenn die Häufigkeiten sich nicht sehr stark unterscheiden. Maximal wird die Entropie, wenn alle Zeichen mit der gleichen Häufigkeit auftreten. Es besteht ein direkter Zusammenhang zwischen der Entropie eines Textes und der mittleren Codewortlänge eines Huffman-Codes. Ist die Entropie klein, die Häufigkeiten der Textzeichen variieren also stark, dann konstruiert das Huffman-Verfahren einen Code mit einer kleinen Codewortlänge. Bei einer Gleichverteilung der Häufigkeiten, also maximaler Entropie, kann das Verfahren keine Redundanz ausnutzen. Die mittlere Codewortlänge eines Huffman-Codes ist also ein Maß für die Entropie des Textes.


--> Interaktive Simulation des Verfahrens