Aufgabe 6.3

[Kubik-Rubik]

Hier kommen Fragen und Antworten zur Aufgabe 6.3 rein!

[|silent]

Kann mir mal jmd. zeigen wie man einen Huffmann-Baum aufstellt? Hab' da gestern nix gescheites gefunden.

Danke schonmal!

[markusj]

Hi,

sieh mal hier nacht, das ist die Seite unseres Tutoriums: http://gbitut14.blogspot.com/
Das oberste Tutorium (4) behandelte unter anderem auch das Huffman-Encoding, ist eigentlich relativ simpel:
Du untersuchst dein Wort zuerst einmal auf die Häufigkeit, in der die einzelnen Zeichen vorkommen.
Jedes Zeichen ist ein Knoten mit eben diesem Häufigkeitswert.
Dann suchst du immer die zwei niederwertigsten Knoten und verbindest diese zu einem neuen, dessen Wert dann die Summe der beiden Unterknoten ist.
Das wiederholst du solange, bis alle Knoten miteinander verbunden sind.
Wenn du nun immer einen Abzweig mit "1" und einen mit "0" bezeichnest, bekommst du für jeden Endknoten einen Pfad, der den neuen "Namen" für den Knoten darstellt.

Ein weiterer guter Link (mit Java-Applet zum Selbst-Probieren): http://www.inf.fh-flensburg.de/lang/alg ... uffman.htm

mfG
Markus

[ryo]

warst du net in gdi?^^

also: zuerst einmal ermittelst du die häufigkeit der zu codierenden zeichen (auf dem blatt die häufigkeit der einzelnen blöcke)

dann schreibst du die einzelnen blöcke als "basis" des baumes nebeneinander auf, darüber die häufigkeiten
ich denke, es ist hier am geschicktesten, z.b. von links nach rechts in ansteigender häufikgeit zu arbeiten

dann verbindest du im ersten schritt die beiden geringsten häufigkeiten, führst sie also mit linien in der nächst höheren ebene des baumes zusammen.
hier schreibst du den wert der summe der beiden häufigkeiten ein.

in schritt 2 nimmst du dir die nächsten zwei kleinsten häufigkeiten (von denen eine durchaus auch die gerade im letzten schritt errechnete sein kann) und verbindest sie wieder zu einem neuen, jenachdem noch höher gelegenen knoten. hier schreibst du wieder die summe rein.

wenn du damit fertig bist, solltest du oben einen einzigen knoten stehen haben, der die gesamsumme der häufigkeiten darstellt, die ja gleich der anzahl an symbolen (bzw. in übungsblatt der gesamtanzahl der 4er blöcke, also 10) enthalten sollte

als letzten schritt beschriftest du immer die linien, die nach rechts von einem knoten (nach unten) abzweigen mit 0, die nach links mit 1 (oder umgekehrt, du solltest nur das gleiche schema beibehalten)

zur codierung muss man nun nur von oben nach unten den baum entlanggehen und die einzelnen werte hintereinander aufschreiben. fertig

hoffe mal, man konnte das einigermaßen verstehen, ist ohne zeichnung halt en bissl blöd...

ah ja, ich seh gerade, dass da jmd schneller war. guck dir das auf jeden fall nochmal an

[Tankwart]

Hab den Baum so:

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

Code: Alles auswählen

             
             10
          0/   \
          6     \
       0/   \    \1
      3      \ 1  \
   0/  \1     \    \
   1    2      3    4
1110  0011   0001   0000

Damit wäre w = 1.01.001.01.001.1.1.000.01.1 (Punkte nur zum besseren Lesen).

[salami]

Hab den Baum so:

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

Code: Alles auswählen

             
             10
          0/   \
          6     \
       0/   \    \1
      3      \ 1  \
   0/  \1     \    \
   1    2      3    4
1110  0011   0001   0000

Damit wäre w = 1.01.001.01.001.1.1.000.01.1 (Punkte nur zum besseren Lesen).

Ich habs genau so, nur dass ich in meinem Baum links "0000" stehen habe und rechts "1110".
Damit ist bei mir w gleich wie bei dir, nur sind die 1er und 0er vertauscht. Ist aber beides richtig.

[Dre]

Der Baum kann theoretisch bei jedem anders aussehen... Folglich auch der komprimierte Code.