The Wonders of the Suffix Tree Through the Lens of Ukkonen’s Algorithm
humanreadablemag.com
The Wonders of the Suffix Tree Through the Lens of Ukkonen’s Algorithm
1–10 of 42 posts
Re: The Wonders of the Suffix Tree Through the Lens of Ukkonen’s Algorithm
#2This might be a stupid question: why is the fact it’s a _suffix_ tree important? (as opposed to building a similar structure with prefixes)
Re: The Wonders of the Suffix Tree Through the Lens of Ukkonen’s Algorithm
#3This might be a stupid question: why is the fact it’s a _suffix_ tree important? (as opposed to building a similar structure with prefixes)
A suffix tree contains a compact trie like graph representation of all the suffixes of a long string. So if you want to know if it contains a substring, you can start at the root and just search like in a prefix tree. Since for the queried word to be an infix it must be a prefix of a suffix, you will find the word in O(|query|) time.
So yeah its a prefix tree, but a prefix tree of all the suffixes.
And now to answer your question. If you naively put every suffix into a regular prefix tree, you would get the same lookup performance. BUT, since the suffixes will share a lot of suffixes, which the prefix tree can't compress you have a lot more memory consumption.
The suffix tree avoids this by essentially performing compression on the suffix as well, so that you simply have pointers to shared suffixes of suffixes, which point to the root.
In the end it's like a diamond shape I guess, trie in the front, compression in the back.
Re: The Wonders of the Suffix Tree Through the Lens of Ukkonen’s Algorithm
#4Also interesting to get into are suffix arrays which you could construct from a tree.
Then there is a notion of generalized suffix arrays, where you mix multiple suffix arrays into a big suffix array. Then you can give fast answers like: what is the longest common prefix between the several tokens, whereas the tokens of your individual suffix arrays could be letters from an alphabet (so you construct a suffix array from words) or maybe words (you construct a suffix array from a sentence)
Re: The Wonders of the Suffix Tree Through the Lens of Ukkonen’s Algorithm
#5This might be a stupid question: why is the fact it’s a _suffix_ tree important? (as opposed to building a similar structure with prefixes)
The key property is that each substring is the begining of a suffix, so if you have your suffixes ordered in lexicographical order, is easy to answer pattern matching queries. Now, you could do the same with prefixes, but then you would need to reverse the query pattern, and things become less straightforward.
Re: The Wonders of the Suffix Tree Through the Lens of Ukkonen’s Algorithm
#6This might be a stupid question: why is the fact it’s a _suffix_ tree important? (as opposed to building a similar structure with prefixes)
The underlying data structure (a trie[0]) is used to create both suffix trees and prefix trees. The 'default' trie is a prefix tree actually.
The reason you would want a suffix tree (over a prefix trie) is that suffix trees are quite useful for computing the longest common substring of two strings (they can do it in linear time).
Re: The Wonders of the Suffix Tree Through the Lens of Ukkonen’s Algorithm
#7This might be a stupid question: why is the fact it’s a _suffix_ tree important? (as opposed to building a similar structure with prefixes)
For most problems, a prefix tree will be just as useful.
But suppose you want to look for the best match of string in a data stream with no predetermined length e.g. a TCP pipe. Then a suffix tree will allow you to process each incoming character in constant time. A prefix tree will not.
Re: The Wonders of the Suffix Tree Through the Lens of Ukkonen’s Algorithm
#8This might be a stupid question: why is the fact it’s a _suffix_ tree important? (as opposed to building a similar structure with prefixes)
The prefix tree of a string is just a linked list, though—it's the string itself. It doesn't help you do anything for a single string, unlike a suffix tree, which is used for finding substrings of a single string.
Moreover, how would you even start searching for a substring using a prefix tree? You can't start at the root, because the substring wouldn't be a prefix. It doesn't help you there at all.
Re: The Wonders of the Suffix Tree Through the Lens of Ukkonen’s Algorithm
#9Also interesting to get into are suffix arrays which you could construct from a tree. Then there is a notion of generalized suffix arrays, where you mix multiple suffix arrays into a big suffix array. Then you can give fast answers like: what is the longest common prefix between the several tokens, whereas the tokens of your individual suffix arrays could be letters from an alphabet (so you construct a suffix array f…
And then you could get into compressed indexes such as the FM-index, which represent a text in a form that is both (typically) smaller than the original, and also supports fast substring queries.
Suffix trees are cool, but they’re just the entry point to a world of wonderful data structures and algorithms.
Re: The Wonders of the Suffix Tree Through the Lens of Ukkonen’s Algorithm
#10Are there some hidden constants/considerations that prevent suffix trees from being used in the real world?
Every time I expect it to show up (e.g., for pattern matching in databases), I almost always see something else used instead (e.g., trigrams)