packed trie

  • folgendes: ganz am ende, wenn ich den packed trie ausfülle:


    index is klar, buchstaben auch


    nur, nach welcher motivation trag ich die werte in NEXT und END ein ?


    was ist, wenn zb das A aus knoten 1 im knoten 3 bei einem kastl, zb C END=TRUE hat und bei einem andern kastl, zb bei B weitergeht zu AB und dann wieder in einen andern knoten usw...


    naja, is schwer das so in worten zu formulieren was ich mein... hoffentlich hats irgendwer verstanden:


    also ich möcht eigentlich wissen, woher ich weiß was ich in die zeilen END und NEXT eintragen muß im packed trie...


    ich mein wenns mehrere möglichkeiten gibt wie ein wort weitergeht, sonst is nämlich eh nur trivial :)

  • würd mich auch interessieren.
    Und wie such ich in so nem packed trie?
    Im Skriptum is zwar ein pseudocode, nur da steht: k += ord(Wi) - 1


    was soll ord() sein?
    und wie komm ich auf den 1.index?
    wenn die wurzel index = 2 hat ist es ja noch möglich aber was passiert wenn der index > 2 ist? dann komm ich ja nicht mehr an die 1.stelle wenn ord() > 0 ist.

  • also das hab ich inzwischen gechekt bin ur stolz ;)


    aaaaaaaaalso


    du schaust immer im ursprünglichen indexed trie nach, für jeden knoten jeden buchstaben, und was dort bei end steht (true/false) trägst du in den packed trie ein


    zum NEXT:


    dort gehört immer die indexzahl hin, wo der nachfolgeknoten aus dem indexed-trie beginnt



    alles klar?



    das suchen im packed trie hab ich auch nicht ganz nachvollziehen können, aber primär müss ma ja ihn ja nur mal erstellen können :)

  • ord(Wi) ist einfach der ascii-code (=eine zahl, nicht ein character) des i-ten elements vom Wort W


    ord braucht man um mit einem Zeichen in einem array zu indizieren, ord macht aus char -> int


    beim suchen: wenn man über die indizes zu einem feld kommt wo der character den ich grad suche übereinstimmt, suche ich von dort aus weiter mit dem nächsten "offset"-index
    wenn der character wo ich 'gelandet' bin nicht übereinstimmt ist das wort nicht drin im trie


    zusätzlich: ist mein wort aus und das feld wo ich grad hingekommen bin ist nicht als ende markiert, ist das wort auch nicht im trie


    peter

  • ja das ist alles sehr kompliziert...


    Next im packed trie (ich gehs von unten nach oben durch):


    Du hast im packed trie irgendwelche Buchstaben und darunter das end und darunter das next. Da schaust mal auf Deine Schraffierung, zu welchem Knoten das Feld gehört. Dann schaust nach im (suffix komprimierten) indexed trie oben, wo der Zeiger von dem Feld mit dem Buchstaben (im richtigen Knoten) hinzeigt (falls dort einer rauszeigt, wenn nicht, kannst gleich 0 ins next-Feld schreiben).


    Jetzt gehts wieder runter - Du weißt die Knoten-Nummer, auf die gezeigt wird, jetzt schaust in der Zwischen-Zeichnung nach, wo dieser Knoten beginnt im packed trie und das tragst dann unter next ein.