Ukkonen's suffix tree algorithm, what is necessary?
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?
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.
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
下一篇: Ukkonen的后缀树算法，有什么必要？