3 ms·
Ukkonen's suffix tree algorithm explained in plain English
- caustic 15y agoFor those who want to learn more about this kind of algorithms on strings, there is a great book named, unsurprisingly, "Algorithms on Strings" (http://www.amazon.com/Algorithms-Strings-Maxime-Crochemore/dp/0521848997 http://www.amazon.com/Algorithms-Strings-Maxime-Crochemore/d...). Although I must admint, jogojapan has written a really clear and thoughtful explanation of Ukkonen's algorithm on stackoverflow, the best one I've ever read.
- ahelwer 15y agoI've not read that textbook, but another excellent text is "Algorithms on Strings, Trees, and Sequences" by Dan Gusfield (http://www.amazon.ca/Algorithms-Strings-Trees-Sequences-Computational/dp/0521585198 http://www.amazon.ca/Algorithms-Strings-Trees-Sequences-Comp...). It has a strong bioinformatics leaning, so you learn all sorts of interesting near-real-world applications for the algorithms. Starts off talking about all the standard exact pattern matching algorithms, then moves on to suffix trees, then inexact matching, then finishes off with some advanced topics (that I have not read yet). Anyway, I'm really enjoying reading it and definitely recommend it.
- jemka 15y agoFor anyone (like me) that isn't familiar with what this would be used for should have a look at the first link the Stack Overflow OP references: http://marknelson.us/1996/08/01/suffix-trees/ http://marknelson.us/1996/08/01/suffix-trees/