Generalized Suffix Tree Java Implementation

Question

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.

Hi, i Was wondering is you could tell me which soulution did you use in the end, i have the same issue!!! — Julia, Jul 17 '10 at 06:00
look here: http://stackoverflow.com/questions/9452701/ukkonens-suffix-tree-algorithm-in-plain-english/9513423#9513423 — YAMM, May 31 '13 at 18:34

Garret Wilson · Answer 1 · 2023-04-01T17:38:58.203

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

The library containing the suffix tree implementation described above is now available on GitHub in the globalmentor-base repository in the globalmentor-core subproject in the com.globalmentor.collections package.
The latest version of the library is available from Maven Central using the artifact coordinates com.globalmentor:globalmentor-core .

edited Apr 01 '23 at 17:38

answered Jan 26 '12 at 18:40

Garret Wilson

18,219
30
144
272

The blog post is informative but the source is not currently available (Aug'2015) as it points to https://svn.globalmentor.com/java/trunk/globalmentor-core/ which password protected. – codeDr Aug 19 '15 at 15:24
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. – Garret Wilson Aug 20 '15 at 05:26
The source code is now available via Git and on Maven Central. I've updated the answer above with the new location. – Garret Wilson Jun 18 '16 at 21:17
1

Thanks for pointing that out, @trincot. I've updated the links here and in the blog entry as well. – Garret Wilson Apr 01 '23 at 17:54

score 4 · Answer 2 · answered Jun 09 '09 at 11:33

4

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

answered Jun 09 '09 at 11:33

HMM

2,987
1
20
30

Er, do you know of any implementations (or even tutorials!) for Token Suffix Trees? – Susheel Javadi Nov 18 '09 at 08:57

Dr. Max Völkel · Answer 3 · 2012-07-26T16:46:35.277

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

edited Jul 26 '12 at 16:46

answered Jan 25 '10 at 14:44

Dr. Max Völkel

1,780
2
17
24

1

If it's a direct port of Mark Nelson's, then it isn't a generalized suffix tree. It's just a suffix tree. – HorseloverFat Jul 26 '12 at 11:26
Right, I reworded my answer. Thanks. – Dr. Max Völkel Jul 26 '12 at 16:47

score 2 · Answer 4 · answered Aug 14 '13 at 09:51

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.

answered Aug 14 '13 at 09:51

abahgat

13,360
9
35
42

score 0 · Answer 5 · answered Nov 24 '14 at 05:31

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.

answered Nov 24 '14 at 05:31

eold

5,972
11
56
75

Generalized Suffix Tree Java Implementation

5 Answers5

Linked