Suffix Trie implementation, please review

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Suffix Trie implementation, please review

leledumbo
Administrator
I've written a unit containing suffix trie implementation. It could be used for: fast string existence search (could be extended with other information if required), though takes quite a lot of spaces (O(n^2) for a string where n is the string length, but grow slower as more strings get added), the existence search have O(m) complexity where m is the string to search for. This string to search for could be exact or a substring of previously added strings.

Please have a look and try it (a test program is included), open for suggestions or whatever you want to say.
Reply | Threaded
Open this post in threaded view
|

Re: Suffix Trie implementation, please review

etrusco
I guess you forgot the attachment? ;-)
BTW, do you know the hashtrie component?
http://www.softcomplete.com/hashtrie.asp

Best regards,
Flávio

On Tue, May 24, 2011 at 1:48 PM, leledumbo <[hidden email]> wrote:

> I've written a unit containing suffix trie implementation. It could be used
> for: fast string existence search (could be extended with other information
> if required), though takes quite a lot of spaces (O(n^2) for a string where
> n is the string length, but grow slower as more strings get added), the
> existence search have O(m) complexity where m is the string to search for.
> This string to search for could be exact or a substring of previously added
> strings.
>
> Please have a look and try it (a test program is included), open for
> suggestions or whatever you want to say.
>
>
> --
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Suffix Trie implementation, please review

leledumbo
Administrator
> I guess you forgot the attachment?

My bad... well it was midnight here ;)
There you go: suffixtrie.zip

> BTW, do you know the hashtrie component?

Only ever heard of, never know the details. Thanks, this could be a lesson to learn.
The improvement over hashtable seems to be in the lookup, so it still uses hashing to generate initial index which in simple case, like in the page you point, operates on the whole string (i.e. O(n)). The lookup would take additional processing. Anyway, it's not really comparable to suffix tries. Instead, it's comparable to (prefix) tries. For lookup and update, tries should perform better. But the disadvantage is that no item may get out once it gets in (at least not so easy).