Huffman Allgemein

[fnerdted]

Hallo Leute,
ich habe im Studium die Huffman Codierung kennen gelernt und habe mir eine kleine Implementierung geschrieben. Jetzt ist mir aufgefallen, dass die Codelänge von einem Buchstaben, wenn ich einen Text mit n unterschiedlichen Buchstaben einlese, die Länge von log2(n) + 1 weit überschreitet.

Mein Beispieltext hatte 72 verschiedene Buchstaben, insgesamt ca. 10000.
Einige Buchstaben hatten eine Codierungslänge von 13 Bit.

Zuerst war ich verwirrt, allerdings habe ich dann mal den Beispielcode unseres Professors genommen und der erzielte die selben Codierung.


Ist es normal, dass bei einem schönen ASCII test wo jedes zeichen mit 8 Bit codiert werden kann mit der Huffman Codierung eine längere Bitfolge entsteht (natürlich nur bei manchen buchstaben, die die häufig auftraten hatten bei mir auch nur 3 oder 4 bit) ???:L ???

Grüße ted

 

[rme]

Ja, anders würde es doch gar nicht funktionieren. Wenn du erreichen möchtest, dass du häufige Zeichen mit 3 Bit codierst, kann es doch nicht gleichzeitig funktionieren, dass alle anderen Zeichen trotzdem mit 8 Bit codiert werden. Sonst wäre die Decodierung nicht eindeutig möglich (Präfixfreiheit).

Der Sinn von Huffman ist gerade, die Aufteilung so zu machen, dass sie sich nach der Häufigkeit der Zeichen richtet - die häufigen Zeichen bekommen eine kurze Codierung und die seltenen eine längere, sodass der Text tatsächlich kürzer codiert wird. Damit das klappt, muss man natürlich für jeden Text einen neuen, passenden Baum berechnen - dann kann es nicht sein, dass der Text hinterher länger als vorher ist (von der Übertragung des Baumes einmal abgesehen).