Correspondence To Suffix Trees
Suffix arrays are closely related to suffix trees:
- Suffix arrays can be constructed by performing a depth-first traversal of a suffix tree. The suffix array corresponds to the leaf-labels given in the order in which these are visited during the traversal, if edges are visited in the lexicographical order of their first character.
- A suffix tree can be constructed in linear time by using a combination of suffix and LCP array. For a description of the algorithm, see the corresponding section in the LCP array article.
It has been shown that every suffix tree algorithm can be systematically replaced with an algorithm that uses a suffix array enhanced with additional information (such as the LCP array) and solves the same problem in the same time complexity. Advantages of suffix arrays over suffix trees include improved space requirements, simpler linear time construction algorithms (e.g., compared to Ukkonen's algorithm) and improved cache locality.
Read more about this topic: Suffix Array
Famous quotes containing the word trees:
“The nectar and ambrosia, are withheld;
And in the midst of spoils and slaves, we thieves
And pirates of the universe, shut out
Daily to a more thin and outward rind,
Turn pale and starve. Therefore, to our sick eyes,
The stunted trees look sick, the summer short,
Clouds shade the sun, which will not tan our hay,
And nothing thrives to reach its natural term;”
—Ralph Waldo Emerson (1803–1882)