compressed suffix trie

Discussion in 'C++' 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

    insert char array 10
    insert char array 9,10
    insert char array 8,9,10
    ....
    insert char array 1,2,3,4,5,6,7,8,9,10


    is there any efficient way to build a trie?
    the above method is toooo slow and consum much memory!




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

  2. Joseph wrote:
    > I want to build a compressed suffix trie from a string for string
    > matching.instead of doing like:
    >
    > input:a string with 10 chars
    >
    > insert char array 10
    > insert char array 9,10
    > insert char array 8,9,10
    > ...
    > insert char array 1,2,3,4,5,6,7,8,9,10
    >
    >
    > is there any efficient way to build a trie?
    > the above method is toooo slow and consum much memory!


    char array[11] = {0};
    const char * const trie[] = { array + 9, array + 8, ... , array };

    Now input your 10 chars in 'array' and use 'trie[5]' to get to
    the fifth (sixth) "string".

    You can use the same method for dynamically sized string and trie.

    Victor
    Victor Bazarov, Sep 22, 2004
    #2
    1. Advertising

  3. Joseph

    Joseph Guest

    Victor Bazarov <> wrote in news:ZAi4d.2801$Ae.2102
    @newsread1.dllstx09.us.to.verio.net:

    > Joseph wrote:
    >> I want to build a compressed suffix trie from a string for string
    >> matching.instead of doing like:
    >>
    >> input:a string with 10 chars
    >>
    >> insert char array 10
    >> insert char array 9,10
    >> insert char array 8,9,10
    >> ...
    >> insert char array 1,2,3,4,5,6,7,8,9,10
    >>
    >>
    >> is there any efficient way to build a trie?
    >> the above method is toooo slow and consum much memory!

    >
    > char array[11] = {0};
    > const char * const trie[] = { array + 9, array + 8, ... , array };
    >
    > Now input your 10 chars in 'array' and use 'trie[5]' to get to
    > the fifth (sixth) "string".
    >
    > You can use the same method for dynamically sized string and trie.
    >
    > Victor


    Oh ,sorry ,I mean,is there any faster way to do the compression?


    OR a dynamic way ?to do the insertion and compression at same time
    Joseph, Sep 22, 2004
    #3
  4. Joseph wrote:
    > Victor Bazarov <> wrote in news:ZAi4d.2801$Ae.2102
    > @newsread1.dllstx09.us.to.verio.net:
    >
    >
    >>Joseph wrote:
    >>
    >>>I want to build a compressed suffix trie from a string for string
    >>>matching.instead of doing like:
    >>>
    >>>input:a string with 10 chars
    >>>
    >>>insert char array 10
    >>>insert char array 9,10
    >>>insert char array 8,9,10
    >>>...
    >>>insert char array 1,2,3,4,5,6,7,8,9,10
    >>>
    >>>
    >>>is there any efficient way to build a trie?
    >>>the above method is toooo slow and consum much memory!

    >>
    >>char array[11] = {0};
    >>const char * const trie[] = { array + 9, array + 8, ... , array };
    >>
    >>Now input your 10 chars in 'array' and use 'trie[5]' to get to
    >>the fifth (sixth) "string".
    >>
    >>You can use the same method for dynamically sized string and trie.
    >>
    >>Victor

    >
    >
    > Oh ,sorry ,I mean,is there any faster way to do the compression?
    >
    >
    > OR a dynamic way ?to do the insertion and compression at same time


    Oh, sorry, I thought you're asking a C++ language question. You should
    find a better place to ask general programming questions, like forum
    'comp.programming' or anything related to compression...

    V
    Victor Bazarov, Sep 22, 2004
    #4
    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: Java
    Replies:
    1
    Views:
    506
    =?ISO-8859-1?Q?Daniel_Sj=F6blom?=
    Sep 22, 2004
  2. Miki Tebeka

    [ANN] Trie for Python

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

    Trie

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

Share This Page