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

31–40 of 42 posts

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

#31

Post by pzh »

herostratus101 wrote: post #14

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.

It seems like the style of the article is deliberately long-winded and poetic to match the type of content that the “human readable magazine” is going for (similar to New Yorker articles). It’s likely seeking to cater to a specific niche of reader preferences.

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

#32

Post by ridiculous_fish »

In practice one should typically prefer a suffix array to a suffix tree. A suffix array is conceptually so easy!

1. Given a set of strings, put all the suffixes into a set. For example "derp" -> "derp", "erp", "rp", "p".

2. Sort it

It's cheap! The number of suffixes equals the string length, and suffixes can be mere references into the string input. So in practice you use maybe ~2x memory compared to the input - and in big cache friendly chunks (not tries).

Now you're flying. If you want to perform a substring search:

1. Binary search on the first character. You get a range of suffixes which begin with that character.

2. Within that range, perform a binary search on the second character. Now you have a range of suffixes which begin with the first two characters.

3. etc.

Powerful and easy.

By the way this technique of going character by character can and should be extended to the sort itself; look up "three-way radix quicksort" for what you never learned in school.

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

#33

Post by SamReidHughes »

ridiculous_fish wrote: post #32

In practice one should typically prefer a suffix array to a suffix tree. A suffix array is conceptually so easy! 1. Given a set of strings, put all the suffixes into a set. For example "derp" -> "derp", "erp", "rp", "p". 2. Sort it It's cheap! The number of suffixes equals the string length, and suffixes can be mere references into the string input. So in practice you use maybe ~2x memory compared to the input - and…

More like 4x or 8x the memory (of an ASCII string) if you just use pointers or size_t’s. Abstractly, you need at minimum (n log n) memory to represent a permutation, which is what you’re doing.

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

#34

Post by mumblemumble »

joe_the_user wrote: post #30
mumblemumble wrote: post #29

Earlier quoted context omitted.

The only thing suffix trees have in common with B-tries that I can see is that they're both non-binary trees. A B-tree stores whole keys in the nodes, not fragments of values. And a B-tree tries to self-balance, so there's a lot of leeway for what keys get pushed up to the root node. B-trees split and merge nodes based on the number of items in them, trying to achieve a certain fill factor. A suffix tree, on the othe…

I should phrase it differently; what does a suffix tree get you that a standard sorting tree doesn't get you. A standard sorting tree would get you all the neighbors in lexical order. What more do you need?

The B-tree just lets you quickly find out if a given string is in a set. The suffix tree lets you do things like finding the longest common substring very quickly, or looking for repeating motifs.

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

#35

Post by mehrdadn »

joppy wrote: post #15
mehrdadn wrote: post #8

Earlier quoted context omitted.

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.

Thanks!

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

#36

Post by joe_the_user »

mumblemumble wrote: post #34
joe_the_user wrote: post #30

Earlier quoted context omitted.

I should phrase it differently; what does a suffix tree get you that a standard sorting tree doesn't get you. A standard sorting tree would get you all the neighbors in lexical order. What more do you need?

The B-tree just lets you quickly find out if a given string is in a set. The suffix tree lets you do things like finding the longest common substring very quickly, or looking for repeating motifs.

A B-tree (or any sorting/index tree) allows one to find nearby elements in where sorting order one choose. If one takes a B-tree of strings sorted in lexical order, one find the neighbors of a given string X. If you start with a string X=YZ, where Y is smallest substring in our base string-to-search and Z is the part that doesn't occur, then the (left and right) neighbors of X will be other strings containing Y, if such strings exist. Search of this sort may take O(log(l)) time admitted where a suffix tree might take O(1) time (for all I know) but still, a lot of specialized search trees are not that different from B-tree+special-sort-order, as far as I can tell. For example, B-tree + Z-ordering gives you a spatial sorting tree.

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

#37

Post by raincom »

j-pb wrote: post #3
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)

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…

Why can't one construct a prefix tree of all prefixes, then start process from the right to left (assume that it is an offline algorithm)?

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

#38

Post by j-pb »

raincom wrote: post #37
j-pb wrote: post #3

Earlier quoted context omitted.

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…

Why can't one construct a prefix tree of all prefixes, then start process from the right to left (assume that it is an offline algorithm)?

Because you can walk search trees from their root but not from their leafs.

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

#39

Post by raincom »

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)

Peter Weiner, who first invented suffix trees gave an answer to this question on p.3 of "Linear Pattern Matching Algorithms"[1]: "If P does match a substring of S, then reverse(P) also matches a substring of reverse(S). This observation implies that every technique which solves a pattern matching problem working from left to right has a dual procedure which works from right to left. In what follows, we adopt a left to right view point, referring only briefly to dual concepts as appropriate."

[1]https://pdfs.semanticscholar.org/d339/0f13eed511cde1116446e7...

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

#40

Post by herostratus101 »

pzh wrote: post #31
herostratus101 wrote: post #14

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.

It seems like the style of the article is deliberately long-winded and poetic to match the type of content that the “human readable magazine” is going for (similar to New Yorker articles). It’s likely seeking to cater to a specific niche of reader preferences.

You've got to be kidding me. The sentences are excruciating to read. New Yorker prose is in a different universe. The writing is spare and lucid. You can't evaluate the quality of prose with "wc -w".
Post reply on HN