Are There Any Good C++ Suffix Trie Libraries? [closed]

Question

Does anyone know of a really rock solid C++ library for suffix tries? Other than the one in Mummer?
Ideally, I'd like:
Some concept of concurrency.
Good caching behavior.
Permissive license.
Support for arbitrary alphabets.

Alcohol

Looks like someone proposed a boost GSoC project for one - lists.boost.org/Archives/boost/2009/04/150393.php can't find any results from it yet though. – Russian

Seems there is at least one promising library already actually from the follow up to that: code.google.com/p/patl – Russian

@awoodland: great link, I especially like the Levenshtein iterator with support for optional operations. – Edwyna

Patl is really solid, I forgot it had suffix tries. Would you like to make that an answer? – Alcohol

Answer 1

Being a bioinformatician, my pick would be SeqAn (check out the sequence index section). It implements a lazy suffix tree and an enhanced suffix array (an equivalent data structure), both of which have good cache behaviour.

Kobe

Ooh! One I hadn't heard of, and with a suffix array too! That's fantastic. – Alcohol

Upvote. I like the gloabal functionality of this library. I have just started exploring it. Something that should be mentioned IMO is that, for some tasks, it may be not fast enough. Personal preliminary comparisons show that, e.g. by using a seqan::Alphabet, things can get slowed down significantly, even when using e.g. Array-Alloc for Strings. (compared to using a std::vector of std::string as alphabet). Probably the traditional comfort vs. speed situation. – Luxemburg

Answer 2

Having actually used and then forgotten PATL, I'd like to tuck in a link in an answer.
http://code.google.com/p/patl/
It's got a couple really distinct features, and is generally pleasant reading as well.

Alcohol

Answer 3

Most likely this is a tutorial but IMO worth reading and with source code: http://marknelson.us/1996/08/01/suffix-trees.

Chenab