Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Wonders of the Suffix Tree Through the Lens of Ukkonen’s Algorithm

humanreadablemag.com

Post reply on HN
Print view View original

11–20 of 42 posts

Re: The Wonders of the Suffix Tree Through the Lens of Ukkonen’s Algorithm

#11

Post by msclrhd »

alexchamberlain wrote: post #2

This might be a stupid question: why is the fact it’s a _suffix_ tree important? (as opposed to building a similar structure with prefixes)

If you have keys that tend to have common prefices (e.g. URLs in RDF) then checking them in reverse (e.g. with a suffix tree) is generally faster, as you will hit differences quicker.

Re: The Wonders of the Suffix Tree Through the Lens of Ukkonen’s Algorithm

#12

Post by del_operator »

robinhouston wrote: post #9
weitzj wrote: post #4

Also 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.

The Burrows-Wheeler transform was an interesting thing to see! When I used to teach at an immersive 3 month program for web dev we had a few weeks of playing with such arrays, trees, tries, dynamic programming, and text from Wikipedia.

Re: The Wonders of the Suffix Tree Through the Lens of Ukkonen’s Algorithm

#13

Post by mehrdadn »

th-th-throwaway wrote: post #10

Are 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)

A couple of considerations that come to mind for a database: (a) efficiency, and (b) dynamicity. The tree structure isn't particularly efficient (it has a lot of space overhead, and I think it's also not as fast), so you'd prefer something else if possible. So people often use suffix arrays + LCA preprocessing instead. However, those are hard to make dynamic (your database is constantly changing), so I'd expect that still makes it tough to use them in databases. Though I suspect this isn't the whole story.

Re: The Wonders of the Suffix Tree Through the Lens of Ukkonen’s Algorithm

#14

Post by herostratus101 »

I remember learning about this in a data structures class, and it is a remarkable data structure. But the author of this article needs to pick up a copy of Strunk and White. This reads like it was written by a high school junior. Awful, awful writing.

Re: The Wonders of the Suffix Tree Through the Lens of Ukkonen’s Algorithm

#15

Post by joppy »

mehrdadn wrote: post #8
alexchamberlain wrote: post #2

This 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.

This is such a clear and illuminating explanation as to why _suffix_, rather than prefix trees, are so useful.

Re: The Wonders of the Suffix Tree Through the Lens of Ukkonen’s Algorithm

#16

Post by StefanKarpinski »

A suffix array is of similar utility to a suffix tree, more compact to store, and pretty simple to compute: all you need to do is start with an array of each index into the data from start to end, then sort the indices by memcmp'ing the suffix string starting at each index. There are more optimized algorithms, but they're within 2-3x for moderately sized data (megabytes). You need the fancier sorting algorithms if you're constructing a prefix array of something huge like a genome.

Re: The Wonders of the Suffix Tree Through the Lens of Ukkonen’s Algorithm

#18

Post by srpablo »

th-th-throwaway wrote: post #10

Are 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)

Not _quite_ a suffix tree, but a similar structure called a GADDAG is sometimes used in word-generating board games (Scrabble, Words With Friends).

GADDAGs are different because they're more like "reversed prefix" trees, but they help with the issues of placing a new word from a dictionary onto the board using the existing letters of another word.

   [1]: https://en.wikipedia.org/wiki/GADDAG

Re: The Wonders of the Suffix Tree Through the Lens of Ukkonen’s Algorithm

#20

Post by saagarjha »

> Introduced to the world in 1973 by Peter Weiner, suffix trees are a relatively new concept in computer science, with this newness likely fueling its obscurity.

That isn't really all that new; it's just about when red-black trees and B-trees were invented as well and I wouldn't call those "obscure".

Post reply on HN