Pfeile bei Huffman, welche Richtung?

Question

Hallo,

heute wurde im Tut erwähnt, wie wichtig es ist, die Pfeile bei dem Huffman Baum einzuzeichnen und dass es dort schnell zu Punktabzug kommen kann.

Nun bin ich mir aber nicht sicher in welche Richtung die Pfeile hier gezeichnet werden müssen. In der Lösung zu der entsprechenden Aufgabe zeigen die Pfeile quasi von der Wurzel zu den Blättern (so wie man auch den Code ablesen würde), im Skript bei der Beispielaufgabe zeigen die Pfeile jedoch gerade in die entgegengesetzte Richtung (Siehe Bild). Welche Art der Zeichnung wird in der Klausur als korrekt gewertet?

Vielen Dank

Comments

Was die Richtung der Pfeile angeht, haben Sie recht, dass wir dabei nicht konsistent waren. Herr Schmeck zeichnet die Pfeile so, wie sie in der Originalarbeit von Huffman gezeichnet wurden, nämlich von den Blättern zur Wurzel (entsprechend dem Aufbau des Baums). Bei der Implementierung des XWizards habe ich allerdings nicht so tief recherchiert, sondern fand es einfach intuitiver, wie Sie sagen, die Pfeile in der Richtung zu zeichnen, wie die Wörter abgelesen werden. Vielleicht werde ich das noch ändern, ich weiß aber nicht, ob es eher Verwirrung oder Einsicht stiften würde.

In der Klausur dürfen Sie die Pfeile jedenfalls beliebig setzen (natürlich aber alle in derselben Richtung bitte).

Answer 1

In welche Richtung die Pfeile zeigen, ist uns egal - was der Tutor oder die Tutorin vermutlich meinte, ist, dass es sehr wichtig ist, in welche Richtung die Code-Wörter abgelesen werden. Das ist eigentlich das einzige, was relativ oft beim Huffman falsch gemacht wird. 

Man liest die Codewörter immer von der Wurzel zu den Blättern hin ab. In Ihrem Beispiel wäre das Wort anders herum abgelesen dasselbe, aber das ist im Allgemeinen nicht der Fall! Wenn Sie die Wörter von den Blättern zur Wurzel ablesen, ist die Fano-Bedingung nicht erfüllt, und dafür bekommen Sie sehr empfindliche Punktabzüge.

Das ist also ein sehr unnötiger Fehler, den man leicht vermeiden kann.

Answer 2

Hallo updrr,

waehrend in den Tutorien und im Uebungsbuch die Pfeilrichtung wie richtig angegeben von der Wurzel in Richtung Blatt geht, so dass wirklich ein binaerer Baum entsteht ist hier der entgegengesetzte weg gewaehlt worden, um die Richtung der Konstruktion und Addition von Wahrscheinlichkeiten anzuzeigen. Der gestrichelte rote Pfeil zeigt ja die Ableserichtung.

Wenn Du bei der Huffmann-Kodierung die Pfeile von der Wurzel zum Blatt anbringst (sodass ein binaerer Baum entsteht), dann ist das sicherlich richtig (und wird auch so gewertet) und auch meine Empfehlung um Missverstaendnissen vorzubeugen. Ggf. gibt es noch genauere Infos.

Marvin (Tutor)