Indexed Trie --> Packed Trie ?
Results 1 to 5 of 5
  1. #1
    PsychoTheRapist's Avatar
    Title
    Elite
    Join Date
    Feb 2002
    Posts
    366
    Thanks
    3
    Thanked 2 Times in 1 Post

    Indexed Trie --> Packed Trie ?

    Wie wandle ich einen Indexed Trie nach der Suffix Compression in einen Packed Trie um? Ich muss ehrlich zugeben, dass ich aus dem Skriptum nicht ganz schlau werde... Vielen Dank schon im Voraus

  2. #2

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts
    Kurz:
    Man verschiebt die Anfaenge der Knoten so, dass sich
    keine Informationen ueberschreiben, wenn man alles
    in ein Array Schreibt. Dann schreibt man alles in
    ein Array. Jeder Link auf einen Knoten zeigt
    einfach an die Stelle im neuen Array, wo der Knoten in
    diesem Array beginnt (huh, viermal das Wort Array in nur
    vier Zeilen ;-))

    Lang:
    In einem Indexed Trie sind nur die Eintraege eines
    Knotens wichtig, bei denen entweder ein Wort aufhoeren
    kann (end == true) oder die einen Link auf einen
    anderen Knoten haben.

    Alle anderen Felder enthalten eigentlich keine wichtige
    Information. Darin koennte man also Information
    von anderen Knoten speichern.

    Wenn man das Beispiel aus dem Skriptum ansieht (Seite 92),
    sieht man, dass man die Knoten (1) und (3) ineinander
    "verzahnen" kann, wenn man den Start vom Array (1)
    um eins nach rechts verschiebt.

    In dem fertigen Array[0..4] waren dann an den Stellen
    0, 2 und drei Informationen des dritten Knotens und an
    den Stellen 1 und 4 welche vom ersten Knoten.

    Wenn nun ein Knoten einen Link zum Knoten (3) hat,
    zeigt dieser Link ganz normal auf den Anfang des Arrays,
    denn dort beginnt der Knoten (3).

    Will man auf den Knoten (1) zeigen muss man auf den
    Index 1 verweisen, weil man ja den Knoten (1) um eins
    nach rechts verschoben hat.

    Diese Links zeigen nur auf die Stelle an denen ein
    bestimmter Knoten beginnt, bei diesem Index muss nicht
    zwingend ein Information dieses Knotens stehen, denn
    es kann ja sein, dass das erste Feld eines Knotens
    keine wichtige Information enthaelt (z.B.: beim
    Knoten 2).

    Wenn man einem Link folgt erwartet man ja einen
    gewissen Buchstaben in diesem Knoten zu finden, dabei
    ist jeder Buchstabe b an folgender Stelle:
    wurzel + Ordnung(b) - 1, wobei die Ordnung eines Buchstaben
    seine Stelle im Alphabet ist (Bsp. Ord(c) = 3).

    Ein Beispiel:
    Der Trie ist der Packed Trie aus dem Skriptum (Seite
    92). Unser Wort ist "ab". Der Index des ersten
    Knotens ist 2.

    wurzel + Ord(a) - 1 = 2 + 1 - 1 = 2

    Und wenn wir an der Stelle 2 im Trie nachsehen, ist da
    tatsaechlich ein a. Next zeigt auf 7 (dort beginnt der
    Knoten 2). Wir erwarten in diesem Knoten ein 'b' zu
    finden.

    7 + Ord(b) - 1 = 7 + 2 - 1 = 8

    An dieser Stelle steht auch ein 'b' und da die Variable
    end auf True ist, darf hier das Wort auch aufhoeren. Wenn
    wir das Wort "ac" gesucht haetten waeren wir im zweiten
    Schritt zu Stelle 9 gekommen und dort ist kein 'c', also
    ist das wort "ac" nicht im Trie enthalten.

    Tut mir leid, dass die Erklaerung so umstaendlich geworden ist,
    aber das ist irgendwie schwer in Worte zu fassen. Ich hoffe es
    hat trotzdem ein wenig geholfen.

  3. The Following 10 Users Say Thank You to yrucrem For This Useful Post:


  4. #3
    PsychoTheRapist's Avatar
    Title
    Elite
    Join Date
    Feb 2002
    Posts
    366
    Thanks
    3
    Thanked 2 Times in 1 Post
    Vielen Dank vor allem für die lange Version deiner Erklärung. War sehr hilfreich. Ich hätte aber noch 2 Fragen. 1, Beim Indexed Trie hab ich noch irgendeine Wurzel die auf meinen ersten Knoten zeigt. Ist es nun so dass der erste Knoten des Indexed Tries nach der Umwandlung in den Packed Trie zu meiner "neuen" Wurzel wird? bzw. wie komme ich sonst auf den Index der Wurzel? Die 2te Frage: Warum beginne ich gerade Knoten 1 und 3 miteinander zu "verzahnen". Könnte ich auch bsp mit 1 und 2 beginnen? Im Skriptum steht was davon die Knoten nach ihrer Anzahl belegter Elemente absteigend zu sortieren und so weiterzumachen. Offensichtlich bleibt es mir überlassen wie ich "verzahne", oder?

  5. #4

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts
    Auch beim Packed Trie hast du eine Wurzel die Zeigt dann eben auf die Stelle im Array an der der erste Knoten beginnt (im Beispiel ist das glaube ich 2).

    Wie man die Knoten arrangiert ist voellig gleich, das stimmt. Es duerfen sich nur keine Felder mit Information ueberschneiden und keine zwei Knoten duerfen an der selben stelle im Array beginnen (sonnst kann man sie ja nicht mehr auseinanderhalten).

  6. #5
    PsychoTheRapist's Avatar
    Title
    Elite
    Join Date
    Feb 2002
    Posts
    366
    Thanks
    3
    Thanked 2 Times in 1 Post
    Vielen Dank

Tags for this Thread

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
  •