Suffix Compression

  • Hallo!


    Also ich hab kein Problem mit der Aufstellung des Index-Tries, jedoch kann ich die Suffix Comp. nur bedingt nachvollziehen wie se im Strikp ist!


    Kann man die Suffix Compression nur anwenden wenn die Wörter mit der selben Endung auch gleich lang sind, oder kann man es mit beliebigen Wörtern machen!?!?


    Dazu gleich ein BSP. Bei den Prüfungsangaben vom 21.6.02 ...kann es sein dass man da bei der Suffix Compression NICHTS streichen kann!?!?


    BITTE, Danke


    grüße

  • Grüss dich.
    Nein, man kann schon etwas komprimieren.


    Du meinst vermutlich das Beispiel mit der Wortmenge
    { CBB, CA, EB, A, CD, DB, DA }


    Also beim Indexed Trie, da geht ja bei Kasterl 1 ein Pfeil von E weg zu dem anderen Kasterl (nr.4, bei dem nur B True ist)


    Jetzt kannst du bei der SuffixComp. diesen Pfeil zum letzten Kasterl (Nr. 5) umleiten und Nr. 4 komplett wegstreichen.


    Guter Tipp: Weisst du woran man das sofort erkennt? Kasterl 4 hat bei end: false, true, false, false, false


    und Nr. 5 hat bei end auch ganz genau das selbe: false, true, false, false, false ---> Deswegen kann man da ansetzen mit der SuffixCompression :D :D Geht im Skriptum Beispiel genauso!


    Gruss, AntiBit

    Hätten uns Spiele wie Pac-Man in unserer Jugend beeinflusst, würden wir heute durch dunkle Räume irren, elektronische Musik hören und Pillen fressen.

  • hmmm....du hast glaub ich das andere beispiel....ich mein das von gruppe A mit {BE, DB, BCB, BD, E, AC, AE}


    und wie schauts aus mit wortlängen!? kann man nur gleich lange wörter (zb. adec und bcec aber nicht adba und cba) komprimieren oder?


    danke schon mal
    grüße

  • Ich werd das mal gleich machen zum übern, und dann hier editieren.


    EDIT:


    Also, auch hier kann man komprimieren:


    Kästchen Nr.3 (F,T,F,F,F) kann man wegstreichen, indem man den Pfeil von Kästchen Nr.1 von D zu Kästchen Nr. 4 führt
    (auch F,T,F,F,F).


    Alles klar?


    /EDIT

    Hätten uns Spiele wie Pac-Man in unserer Jugend beeinflusst, würden wir heute durch dunkle Räume irren, elektronische Musik hören und Pillen fressen.

  • das heißt also....es ist unabhängig von der Wortlänge!?ODER!? Und es ist also erlaubt von der ersten "ebene" zur dritten "ebene" einen Pfeil zu machen!? wenn das so ist, ist eh alles klar.....hab mir nur gedacht, man muss immer von der einen zur nächsten ebene, und darf nur in der gleiche ebene komprimieren! steht leider im Skript ja nix drin....


    aber danke vielmals!

  • ich poste mal kurz meinen packed trie....vielleicht könntest du kurz schaun ob der bei dir auch so ausschaut


    (CBB, CA, EB, A, CD, DB, DA)
    [list=1]
    [*]1 2 3 4 5 6 7 8 9 10
    [*]a b a d c d e a b b
    [*]T F T T F F F T T T
    [*]0 10 0 0 1 8 10 0 0 0
    [/list=1]


    grüße

  • Ui... das Ding schaut bei mir komplett anders aus:


    1 2 3 4 5 6 7 8 9 10 11
    A B C D E A B D A B
    T T F F F T F T T T
    0 0 6 10 1 0 1 0 0 0

    Hätten uns Spiele wie Pac-Man in unserer Jugend beeinflusst, würden wir heute durch dunkle Räume irren, elektronische Musik hören und Pillen fressen.

  • is es eigentlich egal welchen von den beiden Pfeilen man "umleitet"? schon, oder? ich mein, ob ich jetzt das eine oder das andere suffix benutze sollt eigentlich wurscht sein...


     


    AntiBit : macht nix, man kann die einzelnen "Kastln" natürlich unterschiedlich anordnen, da kommt schon mal was anderes raus..

  • hmmmm....... was für einen index hat deine wurzel!? meine hat index 3!?


    wie kann das sein!?....shit


    meine aufbau etwa so


    ......12345678910
    1........x_xxx
    2.....xx_x_
    3.................xx___
    5..................._x___



    wenn ich mich nicht irre ist das die einzige möglichkeit ein lückenloses feld zu erzeugen oder???????

  • Zitat

    is es eigentlich egal welchen von den beiden Pfeilen man "umleitet"? schon, oder? ich mein, ob ich jetzt das eine oder das andere suffix benutze sollt eigentlich wurscht sein...


    Das ist nicht unbedingt egal. Ist nur zulässig, wenn du damit kein neues Wort einführst. Also in unserem vorher besprochenen Beispiel geht das nicht.


    @ *]sCHmIkOla[*


    Hmm also der Aufbau ist bei mir so:


    X_XXX
    _____XX_X_
    _________XX___
    _X___


    Wurzel ist 1 bei mir.

    Hätten uns Spiele wie Pac-Man in unserer Jugend beeinflusst, würden wir heute durch dunkle Räume irren, elektronische Musik hören und Pillen fressen.

  • AntiBit
    aber du hast ja bei nummer 8 eine lücke.....das sollte ja wenns geht nicht sein oder?!....ausserdem müsste dein feld ja dann 11 lang sein oder!?!?!


    MrBurnst


    DANKE:D das is eine erleichterung......is ja doch nicht mehr so viel zeit zur prüfung


    P.S: ist das was antibit jetzt gemacht hat FALSCH oder einfach nur eine schlechtere annäherung!?

  • ich denke nicht dass lücken was machen, es is sicher nicht immer möglich alles so aneinanderzureihen dass es keine lücken gibt (naja, in den Ü-Bsps vielleicht schon, aber i.r.l. ...)


     


    AntiBit : wenn die beiden tabellen genau gleich ausschaun (T/F und linkage) dann kann es doch nur egal sein, oder. Neue Wörter können ja nur dazukommen wenn sich die eine Tabelle in irgendeiner Art von der anderen unterscheidet, und dann kann man die beiden sowieso nicht verlinken, egal in welche Richtung, denn dann würde man ja entweder eben neue Wörter schaffen oder welche löschen...

  • Jo die Länge ist auch 11... Aber die Lücke ist schlecht, das stimmt. Ich werd ihn nochmal machen :rolleyes: Edit folgt hehe.


    EDIT:


    Also habs jetzt so angeordnet wie du, es kommt das selbe raus. Fast. Der einzige kleine Fehler den du hast, ist dass die 10er durch 9 ersetzt gehören, weil 5er-Kastl ja bei Index 9 anfängt, und net 10.


    Ansonsten alles roger!
    Danke auch an MrBurnst für den Tipp.

    Hätten uns Spiele wie Pac-Man in unserer Jugend beeinflusst, würden wir heute durch dunkle Räume irren, elektronische Musik hören und Pillen fressen.

  • wie man diese beispiele loest, hab ich schon durchschaut... aber, ich hab noch nicht so ganz durchblickt, wie man dann wieder auf die woerter kommt...
    es wird beim packt tree doch immer auf den index der ersten spalte eines knotens verwiesen...
    aber dort kann doch durch das verschachteln auch etwas eines andren knotens drinnenstehen...
    b.z.w. wie komm ich auf alle einträge des knotens, wenn ich nur auf den anfang verwiesen habe und dazwischen durchs verschachteln werte andrer knoten stehen?

  • Also wenn du deinen Packed Tree hast dann geht das so:


    Nehmen wir das gerade diskutierte Bsp., und versuchen das Wort CBB wiederzufinden:


    Die allg. Formel lautet: Wurzel + Ordnung(Buchstabe im Alphabet)-1;


    Wenden wir das an: Die Wurzel ist am Anfang in unserem Bsp. 3.
    D.h. Für C: 3 + 3 (C ist dritter Buchstabe im Alphabet) - 1 = 5


    An Index 5 steht C;F;1 ... passt. Heisst wir haben Buchst. C, noch kein Ende und die neue Wurzel ist 1.


    B: 1 + 2 - 1 = 2


    Passt auch: In 2 steht B;F;9


    2tes B: 9 + 2 - 1 =10


    An Stelle 10 steht B;T;0 -
    fertig ... Dieses B ist das Ende(true) und verweist nicht mehr weiter :D


    Wolltest du eh das wissen, oder? :D

    Hätten uns Spiele wie Pac-Man in unserer Jugend beeinflusst, würden wir heute durch dunkle Räume irren, elektronische Musik hören und Pillen fressen.