packed trie
Results 1 to 8 of 8

Thread: packed trie

  1. #1
    Kenny's Avatar
    Title
    Special User
    Join Date
    Jan 2002
    Location
    wien 23
    Posts
    507
    Thanks
    0
    Thanked 0 Times in 0 Posts

    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
    ciao.Markus

    http://www.mworx.at - Markus Jerko Photography

  2. #2
    bla's Avatar
    Title
    Master
    Join Date
    Jun 2002
    Posts
    174
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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.

  3. #3
    Kenny's Avatar
    Title
    Special User
    Join Date
    Jan 2002
    Location
    wien 23
    Posts
    507
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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
    ciao.Markus

    http://www.mworx.at - Markus Jerko Photography

  4. #4
    LordOfTheBite's Avatar
    Title
    Hero
    Join Date
    Feb 2002
    Location
    Vienna
    Posts
    191
    Thanks
    2
    Thanked 0 Times in 0 Posts
    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

  5. #5

    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    534
    Thanks
    3
    Thanked 124 Times in 78 Posts
    ich würd sagen:
    im Skriptum ist ord(W) einfach die Nummer des Buchstaben im Alphabet, also ord('a') ist 1 und ord('z') ist 26.
    Der Algorithmus ist dann eh leicht nachvollziehbar.

  6. #6

    Title
    Veteran
    Join Date
    Feb 2002
    Location
    Villach
    Posts
    17
    Thanks
    0
    Thanked 0 Times in 0 Posts
    also ich check das mit den packed trie immer noch nicht ganz. wie komme ich drauf was ich da bei next eintragen muss????????

  7. #7
    VTEC's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    674
    Thanks
    0
    Thanked 1 Time in 1 Post
    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.
    HaRdCoRe HaS JuSt BeGuN!

  8. The Following User Says Thank You to VTEC For This Useful Post:


  9. #8

    Title
    Veteran
    Join Date
    Feb 2002
    Location
    Villach
    Posts
    17
    Thanks
    0
    Thanked 0 Times in 0 Posts
    *plötzlichallesklarwird* danke, sehr gut erklärt cya

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •