Enhanced Suffix Tree

An enhanced suffix tree than can operate as a sliding window.

The classic Ukkonen's algorithm is implemented, which is maintained in the classic_suffixtree branch. The implementation is primarily based on this Stack Overflow post. http://stackoverflow.com/questions/9452701/ukkonens-suffix-tree-algorithm-in-plain-english In the implementation and comment, I tried to abide to the same notation and names with this post. This implementation has O(1) insert time, so the build time is O(n). It took O(n) space too.

In addition, an enhanced suffix tree is proposed and implemented. Here is a comparison between the classic suffix tree and the enhanced suffix tree.

Classic suffix tree	Enhanced suffix tree
singly linked	doubly linked
keeps the sequence of input	keeps the sequence of input and reference to leaf nodes
O(n) time to build, can build incrementally	O(n) time to build, can build incrementally
Need a special ending character to do pattern match correctly	Use recursive tree structure to eliminate the restriction of ending character
Cannot remove inserted input	Can remove from the head of the input. Current implementation need O(n) time to remove from head, but in theory it can be O(log(n))

Also, a simple regular expression engine that support "+", "*", "?", ".", "|", "()", "" operators. The regular expression can do pattern match on suffix tree in about O(s) time, where s is number of matches found in the target corpus.

Currently, the data structure has been tested and works correctly. But the code still need heavy refactoring and better documentation. Be prepared to face a lot of dirty code and scattered comment if you decided to use this.

qdx/EnhancedSuffixTree

ErrorLooks like something went wrong!

About

Resources

Uh oh!

Stars

Watchers

Forks

Releases

Packages 0

Uh oh!

Languages

Error
Looks like something went wrong!

Packages