2
$\begingroup$

I will soon have to be able to draw a suffix tree of a word on an exam. I tried to understand the different algorithms available, but they seem rather complicated to do "by hand".

I do not see a simple way how to draw such a tree. Is there a simple step by step method for people not knowing the algorithms?

$\endgroup$
  • $\begingroup$ Here are slides for McCreight & Ukkonen. There are sketches of intermediate representations of the first few steps on slide 4 and 48, respectively. $\endgroup$ – greybeard Jan 5 '15 at 10:22
4
$\begingroup$

Here is how to draw the suffix tree for the example $abaab\$$ mentioned in the lecture notes appearing in greybeard's comment.

Root. There are two characters appearing in the word, $a,b$, so the root has two outgoing edges, labeled $a$ and $b$.

Root->a. Following $a$, we have both characters $a,b$ appearing in the word. So this note has two outgoing edges, labeled $a$ and $b$.

Root->a->a. There is only one suffix $aab\$$ starting with $aa$, so we replace this node with a leaf, and modify the edge label to $ab\$$.

Root->a->b. There are two suffixes $abaab\$$ and $ab\$$ starting with $ab$. Correspondingly, we add two children with edges labeled $aab\$$ and $\$$.

Root->b. Following $b$ we have the two suffixes $baab\$$ and $b\$$. Correspondingly, we add two children with edges labeled $aab\$$ and $\$$.

The general method is similar. At each node $w$, we add children corresponding to all possible continuations of $w$ in the word. If there is only one continuation possible, we modify instead the edge label. This algorithm is easy to implement by hand, but could be hard to implement in linear time on a computer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.