compressed suffix trie

[Joseph]

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

[Victor Bazarov]

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

[Joseph]

Victor Bazarov <v.********@comAcast.net> 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

[Victor Bazarov]

Joseph wrote:

Victor Bazarov <v.********@comAcast.net> 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