Suffix Compression
Results 1 to 20 of 20
  1. #1
    sCHmIkOla's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    532
    Thanks
    0
    Thanked 0 Times in 0 Posts

    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
    Last edited by sCHmIkOla; 10-10-2002 at 22:08.
    Der folgende Satz ist falsch,
    Der vorherige Satz ist richtig!

  2. #2
    AntiBit's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    738
    Thanks
    0
    Thanked 6 Times in 3 Posts
    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 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.

  3. #3
    sCHmIkOla's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    532
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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
    Der folgende Satz ist falsch,
    Der vorherige Satz ist richtig!

  4. #4
    AntiBit's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    738
    Thanks
    0
    Thanked 6 Times in 3 Posts
    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
    Last edited by AntiBit; 10-10-2002 at 22:37.
    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.

  5. #5
    sCHmIkOla's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    532
    Thanks
    0
    Thanked 0 Times in 0 Posts
    DDDAAAAAAAAAANNNNNNNNKKKKKKEEEEEE

    ich mach in der zwischenzeit den anderen und schau dann mal ob ich was komprimieren kann!

    lg
    Der folgende Satz ist falsch,
    Der vorherige Satz ist richtig!

  6. #6
    sCHmIkOla's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    532
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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!
    Der folgende Satz ist falsch,
    Der vorherige Satz ist richtig!

  7. #7
    AntiBit's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    738
    Thanks
    0
    Thanked 6 Times in 3 Posts
    Ja also das denk ich doch! Kommt ja eine korrekte Lösung raus

    Ciao,
    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.

  8. #8
    sCHmIkOla's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    532
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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
    Last edited by sCHmIkOla; 10-10-2002 at 23:16.
    Der folgende Satz ist falsch,
    Der vorherige Satz ist richtig!

  9. #9
    AntiBit's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    738
    Thanks
    0
    Thanked 6 Times in 3 Posts
    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.

  10. #10

    Title
    Master
    Join Date
    Feb 2002
    Posts
    141
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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..
    Last edited by MrBurnst; 10-10-2002 at 23:50.

  11. #11
    sCHmIkOla's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    532
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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???????
    Last edited by sCHmIkOla; 10-10-2002 at 23:51.
    Der folgende Satz ist falsch,
    Der vorherige Satz ist richtig!

  12. #12
    AntiBit's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    738
    Thanks
    0
    Thanked 6 Times in 3 Posts
    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.

  13. #13

    Title
    Master
    Join Date
    Feb 2002
    Posts
    141
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @*]sCHmIkOla[* : hab genau das gleiche wie du, sollte passen...

  14. #14
    sCHmIkOla's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    532
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @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 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!?
    Der folgende Satz ist falsch,
    Der vorherige Satz ist richtig!

  15. #15

    Title
    Master
    Join Date
    Feb 2002
    Posts
    141
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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...
    Last edited by MrBurnst; 10-10-2002 at 23:57.

  16. #16
    sCHmIkOla's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    532
    Thanks
    0
    Thanked 0 Times in 0 Posts
    blöde frage aber wie sieht so eine lücke dann aus in der tabelle vom packed trie!? einfach eine leere spalte!?
    Der folgende Satz ist falsch,
    Der vorherige Satz ist richtig!

  17. #17
    AntiBit's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    738
    Thanks
    0
    Thanked 6 Times in 3 Posts
    Jo die Länge ist auch 11... Aber die Lücke ist schlecht, das stimmt. Ich werd ihn nochmal machen 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.
    Last edited by AntiBit; 11-10-2002 at 00:17.
    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.

  18. #18
    Jokeman's Avatar
    Title
    Hero
    Join Date
    Feb 2002
    Location
    near Vienna
    Posts
    210
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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?
    Command & Conquer
    =Return of the Dawn=

    TS to TD total conversion

  19. #19
    AntiBit's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    738
    Thanks
    0
    Thanked 6 Times in 3 Posts
    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

    Wolltest du eh das wissen, oder?
    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.

  20. #20
    Jokeman's Avatar
    Title
    Hero
    Join Date
    Feb 2002
    Location
    near Vienna
    Posts
    210
    Thanks
    0
    Thanked 0 Times in 0 Posts
    genau das wollt ich wissen...
    das heißt... nur, wenn an der (Wurzel + Ordnung(Buchstabe im Alphabet)-1)ten stelle der richtige buchstebe fuer diese stelle steht, geht das wort mit diesem buchsteben weiter...
    logisch... haett ich mir selbst auch ueberlegen koennen... THX
    Command & Conquer
    =Return of the Dawn=

    TS to TD total conversion

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
  •