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
//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

 

[=?ISO-8859-1?Q?Daniel_Sj=F6blom?=]

Hi all,

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

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.