Data Structure - Suffix Tree

Introduction

Suffix Tree is a compressed trie containing all the suffixes of the given text T as their keys and positions in the text as their values. ^[4]

Suffix tree of the text T can be built in the time linear to the length of T. See algorithms of Ukkonen^[1] or Weiner^[5].

Example of the Suffix Tree built using Ukkonen's algorithm from a word "BANANA".

Suffix tree can be used to efficiently perform the following operations:

• Find all occurrences of a string P (pattern) in a text T
• Finding the longest common substring

Suffix tree is closely related to the following data structures:

• Suffix array
• LCP array
• FM index
• Wavelet Tree
• Z Function (Pattern Searching)^[2]

Implementation

C# implementation:

• Suffix Tree construction - Naive O(n²) algorithm
• Suffix Tree construction - Naive O(n³) algorithm
• Suffix Tree construction - Ukkonen's on-line linear O(n) algorithm
• Linear time pattern matching using Z Function

The code can be tested on Ideone platform. The input text is transformed to the DOT notation and can be rendered using Webgraphviz

Problems

• String Similarity

Links

• [1] Ukkonen (1995), On-line construction of suffix trees
• [2] Dan Gusfield, Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, Cambridge University Press, 1997
• [3] Ukkonen's Suffix Tree Construction
• [4] Suffix Tree (Wikipedia)
• [5] Weiner (1973), Linear pattern matching algorithms