compressed suffix trie

Discussion in 'Java' started by Joseph, Sep 22, 2004.

  1. Joseph

    Joseph Guest

    Hi all,

    I want to build a compressed suffix trie from a string for string
    matching.instead of doing like:

    input:a string with 10 chars
    //incremental-insertion method
    for loop(10 to 1){
    insert char array index 10
    insert char array index 9,10
    insert char array index 8,9,10
    ....
    insert char array 1,2,3,4,5,6,7,8,9,10
    }
    and then do the bottom-up compression


    problem:
    is there any efficient way to build a compressed suffix trie?
    the above method is toooo slow and consum much memory!
    is there any faster way to do the compression?
    OR a dynamic way ?to do the insertion and compression at same time



    Thanks a lot guys
     
    Joseph, Sep 22, 2004
    #1
    1. Advertising

  2. Joseph wrote:
    > Hi all,
    >
    > I want to build a compressed suffix trie from a string for string
    > matching.instead of doing like:

    <snip>
    > problem:
    > is there any efficient way to build a compressed suffix trie?
    > the above method is toooo slow and consum much memory!
    > is there any faster way to do the compression?
    > OR a dynamic way ?to do the insertion and compression at same time


    From your description I gather that you are using the brute-force
    algorithm. For ideas, look here:

    http://citeseer.ist.psu.edu/giegerich97from.html
    http://citeseer.ist.psu.edu/grossi93suffix.html

    For future reference, this newsgroup is supposed to address java
    questions only. Next time, try comp.programming or comp.theory.

    --
    Daniel Sjöblom
    Remove _NOSPAM to reply by mail
     
    =?ISO-8859-1?Q?Daniel_Sj=F6blom?=, Sep 22, 2004
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Joseph

    compressed suffix trie

    Joseph, Sep 22, 2004, in forum: C++
    Replies:
    3
    Views:
    1,805
    Victor Bazarov
    Sep 22, 2004
  2. Miki Tebeka

    [ANN] Trie for Python

    Miki Tebeka, Oct 1, 2003, in forum: Python
    Replies:
    0
    Views:
    422
    Miki Tebeka
    Oct 1, 2003
  3. Klaus Neuner
    Replies:
    7
    Views:
    505
    Klaus Neuner
    Jul 26, 2004
  4. Polar

    Trie

    Polar, Aug 3, 2004, in forum: C Programming
    Replies:
    0
    Views:
    592
    Polar
    Aug 3, 2004
  5. chuck
    Replies:
    8
    Views:
    1,089
    chuck
    Oct 1, 2007
Loading...

Share This Page