[Haskell-cafe] Suffix tree

[Ketil Malde]

On Sun, 2007-08-12 at 23:09 +0100, Jon Harrop wrote:
> Suffix trees are a data structure used to search for a substring of length "m" 
> in a string of length "n" in O(m) time. Suffix trees can also be used for 
> efficient approximate searches. This data structure is of particular 
> importance in bioinformatics.

Suffix trees (and their sibling, suffix arrays) are cool.  Basically a
suffix tree is a trie, but where any nodes with only one child are
collapsed.  Easy to construct through sorting, linear time is trickier,
and perhaps the biggest problem is keeping memory use reasonable.

Suffix arrays is a sorted array of indices, so it's more compact, but
takes O(m log n) to search.  There's also the enhanced suffix array,
which provides the same functionality as the suffix tree, but uses
approximately the same space as well (something like 12n bytes vs 5n
bytes, IIRC).

> Does anyone have any Haskell code implementing suffix trees? I'm particularly 
> interested in high-performance construction.

I was using a suffix tree to index some data, but I discovered I only
needed the tree to constant depth, so - shame on me - I ended up simply
sorting the suffixes in one case, and storing hashed words in a Map in
another.

I've also toyed with FFI'ing to comressed suffix arrays, but in the end,
this wasn't as successful as I'd hoped.  For straightforward suffix
array construction, this is probably the fastest way to go about it,
though.

Linear time suffix trees are a bit complicated to implement in a
functional language, as they depend on additional links in the tree
during construction.  I'm sure this can be done using IO/STrefs, but it
would of course be cooler if it could be done tying-the-knot style. 

Anyway, I have a handful of shaky FFI bindings, a reasonable bibtex
file, and lots of good will and encouragement.  Let me know if you have
use for any of them!

-k