Friday, June 26, 2015

Road to suffix tree (12)

Reaching our final trick, which is yet another time saver.

This time we rely on a rule named "Once a leaf, always a leaf". The book used the same name.

At the face of it, it is a simple rule. There is no rule that turn a leaf into something else, so this rule is obvious.

Not so obvious is that all strings with a leaf as a prefix will also be a leaf in future extensions.

Let's say, the string "Happy" lead to a leaf, we can be sure that "Happy Birthday" will also end up in a leaf, because in every extension, we reach a leaf, and just extended it.

Now the interesting part comes. Extending a leaf is simply increasing its end index. What if we never explicitly store the end index and simply rely on the current iterations end number?

In that case the leaf extension rule is simply a no-op, and we can skip it. Once the last iteration ends with either leaf extension or split rule can be skipped, because the next iteration will definitely be a leaf extension rule.

That result in our last iteration. Since this is the final product, I just name it the final name, SuffixTree!

No comments :

Post a Comment