2

Yes I have read this: Ukkonen's suffix tree algorithm in plain English?

It is a great explanation of the algorithm but it is not so much the algorithm itself that is killing me but rather the data structure used to implement it.

I need the data structure to be as minimal and as fast as possible and I have seen many implementations using only Nodes, some with only edges, some with edges and nodes, etc. Then there are variations, a website I was reading claimed that a node need not have a pointer to its parent, and other places don't account for how children of a node are managed.

My idea is to have a Node structure with int start, and int * end (points to the current end or phase i). Each node will have a suffix_link pointer, a pointer to its parent, and a pointer to a vector containing its child nodes.

My question is, are these things sufficient and necessary to implement a suffix tree? Can I minimize it in any way? I haven't seen an implementation with children in vectors yet so I am skeptical as to my own thinking. Could someone explain what one would need to implement a suffix tree in this manner using only nodes?

Community
  • 1
  • 1
E.Cross
  • 2,087
  • 5
  • 31
  • 39
  • Just a side note, have a look at suffix arrays also. They are said to be much easier to implement. – Jo So Sep 26 '14 at 17:48

2 Answers2

0

Following may be helpful:

Ukkonen’s Suffix Tree Construction

Here we have
1. start, end to represent edge label
2. suffix link
3. an array for children

Anurag Singh
  • 11
  • 1
-1

When i have to implement that algorithm the better explained document was the original Ukkonen paper and there's one newer with images.

Yes in this documents are all the inside to implement Ukkonen's Suffix Tree algorithm.

NetVipeC
  • 4,402
  • 1
  • 17
  • 19