🔒 Locked

Creating suffix trees in java

Started by ug02070 Oct 12, 2005 at 8:52 AM 2 replies 1.2k views

Original Post

ug02070

Oct 12, 2005 at 8:52 AM

hi, i have managed to create a sorted suffix array in java. i now want to create a suffix tree from this suffix array. has anyone had any experience at doing this, i cannot seem to find the best way to represent a node and an edge. is there a java class that allows you to create nodes and edges which would be suitable for this problem. thanks Danny ps as example, i first need to add an edge to '$', i then need to create a new edge for 'a', with an edge to '$', 'bra' and cadabra etc etc from a list that looks like this $ a$ abra$ acadabra$ thanks

ug02070

Author

ug02070

Oct 12, 2005 at 9:14 AM

this is all i have managed to do so far:

[source = "java"]public class SuffixTree{	static String string;	static Integer[] suffixArray;	static String[] route1 = new String[5];		public static void makeTree(String astring, Integer[] asuffixArray)	{		string = astring;		suffixArray = asuffixArray;					for(int p = 1; p < 5; p++)			{				route1 = string.substring(suffixArray.intValue(), string.length());			}	}		public static void printTree()	{		for(int p = 1; p < 5; p++)		{			System.out.println(route1);		}			}}

and it prints out the following:

a$
abra$
abracadabra$
acadabra$
Press any key to continue...

which shows that it is capable of storing the nodes by use of just an array, but obviously checks need to be made that i.e
because a is already stored, a is not needed within abra, and a or bra is not needed within abracadabra.
is this the right route to be taking or is there a simpler and tidier method?
thanks

TDragon

Oct 12, 2005 at 9:34 AM

It's not always a good thing to ask others for help. Especially in cases such as this, where you couldn't figure out how to parse and store a suffix array (GDers wrote it for you), and now you can't figure out how to store a suffix tree, you might want to think about either setting your sights a bit lower or going back to the basics and making sure you fully comprehend them. Wanting to complete this project is an admirable goal, but in my estimation you don't have the knowledge or the practice yet to do it.

If you must complete it, I strongly suggest you read through a Data Structures coursebook (there's an excellent one using Java 5.0 that I used last semester) to gain an understanding of the mechanisms behind everything you're trying to do.

Having us write your code for you will not help you understand why and how these algorithms and structures work. That's why I normally tend not to give people code for a specific scenario. (Instead, I often provide general rules or abstracted pseudo-code.)

Learning to program is a worthwhile goal. You have to dig up, chew, and swallow the information yourself, though; being spoonfed doesn't build your mental muscles.

ug02070

Author

ug02070

Oct 13, 2005 at 5:07 AM

thanks for your view but "GDers wrote it for you" isnt correct as my version i actually wrote myself to create the suffix array is different, i did it on my own. I dont expect code off people, i learned that trying to translate c into java wasnt working and that i was much better just understanding what needed to be done and coding my own version, it was then very easy.
all i am asking for here is some ideas of how to create a tree, whether a node class has to be created to store parents and children or if an array will simply do, all i'm asking is the best way to approach it and then i will do the rest myself.
thanks
Danny =)

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.