Scheiss Baum

  • Kann mir bitte jemand sagen wie ich diesen scheiss Baum für den Huffman-Code darstellen kann. Das mit den 1ern und den 0ern hab ich ja kapiert, aber wann mache ich eine Verzweigung und wann nicht, das muss ja irgendein Konzept haben.


    Ich hoffe das kann mir jemand erklären da ja morgen schon der Test ist.


    Vielen Dank im vorraus!


    P.S. Hoffe das noch wer munter ist.

  • Zitat

    Original geschrieben von braveheart
    P.S. Hoffe das noch wer munter ist.


    Aber immer :D


    Zur Frage: den Baum brauchst ja eh nicht wirklich zeichnen.
    Fass die beiden Zeichen mit geringster Auftrittswahrscheinlichkeit zam. Damits konsistent ist sagen wir das/die Zeichen mit kleinerem p bekommen die 0, das/die mit größerem p die 1. Jetzt schreibst dudiese 0 oder 1 von rechts beginnend zu dem/den Zeichen dazu.


    Bsp: Du fasst "a" und "cd" zusammen. a hat p von 0.3, cd von 0.29.
    Code vorher:
    a - [noch nix]
    c - 1
    d - 0


    Code nachher:
    a - <b>1</b>
    c - <b>0</b>1
    d - <b>0</b>0


    Überprüf halt ob ichs richtig erklärt hab in dem du ein paar mal den online Test machst... :)

  • hi,


    Es gibt mehrer Varianten die Baeume zu zeichenen.


    Also wenn du die 2 niedrigsten Werte zusammenfasst.
    Schreib dir immer die Summe der 2 ergebnisse auf den Knoten.
    Wenn du dann das naechste mal Zusammenfasst und dieser Knoten(mit der Summe) dabei ist kannst du Ihn verbinden.


    Nehmen wir mal das Beispiel aus dem Buch.


    Am anfang steht dort.
    a 0.40
    b 0.20
    c 0.18
    d 0.11
    e 0.11


    er fasst zuerst d und e zusammen. Summe ist 0.22
    d+e 0.22


    a 0.40
    d+e 0.22
    b 0.20
    c 0.18


    dann fasst du b+c zusammen.
    das ist wieder ein eigener Knoten.



    a 0.40
    b+c 0.38
    d+e 0.22


    Erst hier werden dann die beiden Knoten zusammengefasst.
    Also du schaust wo auf deinen bis jetzt nebeneinander gezeichneten Knoten diese Werte sind.
    Dann fasst du sie wieder zusammen. Der Rest was unten dran haengt interssiert dich jetzt nicht mehr.
    usw.


    Schreib dir einfach immer alle Werte in den Baum hinein. Dann siehst du genau wie du es zusammenfassen kannst!


    major