This site is currently running a Kickstarter to launch a new programming magazine. If you'd like to see more content like this out there, consider taking a look:
https://www.kickstarter.com/projects/pekalicious/human-reada...
The Wonders of the Suffix Tree Through the Lens of Ukkonen’s Algorithm
21–30 of 42 posts
Re: The Wonders of the Suffix Tree Through the Lens of Ukkonen’s Algorithm
#22[deleted]
Re: The Wonders of the Suffix Tree Through the Lens of Ukkonen’s Algorithm
#23A 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 yo…
Just as a side note, that algorithm for suffix array construction has really bad worst cases (consider a string of all "a"s).
It won't matter for experimenting or most likely for using it on smallish realistic texts, but anything where you're taking user data for instance you'd want to step up to a slightly more clever algorithm (there's an O(n lg n) worst case one that's still very simple, called rank doubling I believe).
Re: The Wonders of the Suffix Tree Through the Lens of Ukkonen’s Algorithm
#24> 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".
You're right, it is not new. It is slightly obscure though. Definitely comes up if you study algorithms enough, but I don't think intro courses usually even mention them, and most working programmers won't have any idea they exist.
Re: The Wonders of the Suffix Tree Through the Lens of Ukkonen’s Algorithm
#25I 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.
English may not be their first language.
Re: The Wonders of the Suffix Tree Through the Lens of Ukkonen’s Algorithm
#26(Ironically, for a site called "Human Readable Magazine" I found that really hard to read.)
Re: The Wonders of the Suffix Tree Through the Lens of Ukkonen’s Algorithm
#27(Edit: I been curious/confused by this for years)
Can someone explain how this is fundamentally different from a b-tree of the substrings of a string? You'd store each substring by start index and each leaf is where the substring becomes unique.
Re: The Wonders of the Suffix Tree Through the Lens of Ukkonen’s Algorithm
#28I 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.
This was one of the most insightful articles I’ve read on HN in a while, and I’d love to see more of this content or even pay a premium to some publisher who has this category of technical deep dives.
My unsolicited feedback to you - it doesn’t hurt to practice empathy. The fact that you assumed the authors primary language is English (and even if it really is - it doesn’t matter) and hold them to that bar - and you point out the data structure is something you already knew - is this the same way you provide feedback in a work environment? Don’t take this as an attack, but I guarantee you would be a short timer in my org.
Re: The Wonders of the Suffix Tree Through the Lens of Ukkonen’s Algorithm
#29(Edit: I been curious/confused by this for years) Can someone explain how this is fundamentally different from a b-tree of the substrings of a string? You'd store each substring by start index and each leaf is where the substring becomes unique.
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 other hand, is storing fragments of the values, and I believe (but have not bothered to prove) that there is one and only one minimal and valid way to organize the tree for a given set of data. Suffix trees add children when the data mandate that they do in order to remain correct, not just in order to make room.
Re: The Wonders of the Suffix Tree Through the Lens of Ukkonen’s Algorithm
#30(Edit: I been curious/confused by this for years) Can someone explain how this is fundamentally different from a b-tree of the substrings of a string? You'd store each substring by start index and each leaf is where the substring becomes unique.
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?