online advertising

Thursday, June 25, 2015

Road to suffix tree (07)

In the last post I described the algorithm for inserting a node. I intentionally left vague what do I mean by a location in the tree. A location could be a node or in the middle of an edge. It is always simpler to have only a single concept, so I merged the node class and the edge class together.

To do that, note that there is always exactly one node associated with an edge, so we can just lump the two together. The only exception is the root node, where we can simply associate it with an edge of 0 length.

With this change, we save a lot of pointers too :)

With that, we split the Add code to do a two phase search. In the first phase, we search the key for all but the last character. We assert that the string is already in the tree. In the second phase, we add the last character to the string, according to the three cases.

That result in SuffixTree3, this time around the code is building a real compressed trie now.

No comments :

Post a Comment