15

I am looking for a Java implementation of the Generalized Suffix Tree (GST) with the following features:

After the creation of the GST from say 1000 strings I would like find out how many of these 1000 strings contains some other string 's'.

The search must be quiet fast, as I need to apply the search on about 100'000 candidate strings of average length 10.

Improve this question
2
  • Hi, i Was wondering is you could tell me which soulution did you use in the end, i have the same issue!!! Commented Jul 17, 2010 at 6:00
  • look here: stackoverflow.com/questions/9452701/… Commented May 31, 2013 at 18:34

5 Answers 5

Reset to default
4

Try The Semantic Discovery Toolkit. It has an implementation on text/src/java/org/sd/text/radixtree

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Er, do you know of any implementations (or even tutorials!) for Token Suffix Trees?
4

I created a suffix tree in Java that allows you easily add your own search functionality and other matching algorithms. My blog post, Suffix Trees in Java, has an overview as well as instructions for downloaded the latest version. My Java implementation is based on Mark Nelson's Fast String Searching With Suffix Trees article.

Update 2023-04-01

Improve this answer

4 Comments

The blog post is informative but the source is not currently available (Aug'2015) as it points to svn.globalmentor.com/java/trunk/globalmentor-core which password protected.
I'm doing my best to convert our repository from Subversion to Git and make it public again. That should happen within a week or two. Feel free to ping me if it's not available by then. Cheers.
The source code is now available via Git and on Maven Central. I've updated the answer above with the new location.
Thanks for pointing that out, @trincot. I've updated the links here and in the blog entry as well.
3

There is a Java implementation of a Non-General Suffix Tree is available at: http://illya-keeplearning.blogspot.com/2009/04/suffix-trees-java-ukkonens-algorithm.html

Improve this answer

2 Comments

If it's a direct port of Mark Nelson's, then it isn't a generalized suffix tree. It's just a suffix tree.
Right, I reworded my answer. Thanks.
2

You can find an implementation of a Generalized Suffix Tree in Java here. I tried to document it as much as I could, so you might find it useful.

Improve this answer

Comments

0

Here is my implementation of SuffixTree: https://github.com/losvald/sglj/blob/master/src/main/java/org/sglj/util/PATTrie.java

Among other things, it supports storing arbitrary data in nodes, and finding the set of values associated with the prefix.

Improve this answer

Comments