| |||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||

Description | |||||||||||||||||||||||||||||||||||||||

A lazy, efficient suffix tree implementation. Since many function names (but not the type name) clash with
Prelude names, this module is usually imported import Data.SuffixTree (STree) import qualified Data.SuffixTree as T The implementation is based on the first of those described in the following paper: - Robert Giegerich and Stefan Kurtz, "
*A comparison of imperative and purely functional suffix tree constructions*", Science of Computer Programming 25(2-3):187-218, 1995, http://citeseer.ist.psu.edu/giegerich95comparison.html
This implementation constructs the suffix tree lazily, so subtrees
are not created until they are traversed. Two construction
functions are provided, Estimates are given for performance. The value | |||||||||||||||||||||||||||||||||||||||

Synopsis | |||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||

Types | |||||||||||||||||||||||||||||||||||||||

type Alphabet a = [a] | |||||||||||||||||||||||||||||||||||||||

The list of symbols that constructWith can possibly see in its
input.
| |||||||||||||||||||||||||||||||||||||||

type Edge a = (Prefix a, STree a) | |||||||||||||||||||||||||||||||||||||||

An edge in the suffix tree. | |||||||||||||||||||||||||||||||||||||||

data Prefix a | |||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||

data STree a | |||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||

Construction | |||||||||||||||||||||||||||||||||||||||

constructWith :: Eq a => Alphabet a -> [a] -> STree a | |||||||||||||||||||||||||||||||||||||||

O(k n log n). Constructs a suffix tree using the given
alphabet. The performance of this function is linear in the size
k of the alphabet. That makes this function suitable for small
alphabets, such as DNA nucleotides. For an alphabet containing
more than a few symbols, construct is usually several orders of
magnitude faster.
| |||||||||||||||||||||||||||||||||||||||

construct :: Ord a => [a] -> STree a | |||||||||||||||||||||||||||||||||||||||

O(n log n). Constructs a suffix tree.
| |||||||||||||||||||||||||||||||||||||||

Querying | |||||||||||||||||||||||||||||||||||||||

elem :: Eq a => [a] -> STree a -> Bool | |||||||||||||||||||||||||||||||||||||||

O(n). Indicates whether the suffix tree contains the given
sublist. Performance is linear in the length n of the
sublist.
| |||||||||||||||||||||||||||||||||||||||

findEdge :: Eq a => [a] -> STree a -> Maybe (Edge a, Int) | |||||||||||||||||||||||||||||||||||||||

Here is an example: > find "ssip" (construct "mississippi") Just ((mkPrefix "ppi",Leaf),1) This indicates that the edge "ppi" to get
the remaining prefix string "pi".
Performance is linear in the length | |||||||||||||||||||||||||||||||||||||||

findTree :: Eq a => [a] -> STree a -> Maybe (STree a) | |||||||||||||||||||||||||||||||||||||||

Performance is linear in the length | |||||||||||||||||||||||||||||||||||||||

findPath :: Eq a => [a] -> STree a -> [Edge a] | |||||||||||||||||||||||||||||||||||||||

Performance is linear in the length of the query list. | |||||||||||||||||||||||||||||||||||||||

countLeaves :: STree a -> Int | |||||||||||||||||||||||||||||||||||||||

Performance is linear in the number | |||||||||||||||||||||||||||||||||||||||

countRepeats :: Eq a => [a] -> STree a -> Int | |||||||||||||||||||||||||||||||||||||||

Performance is linear in the length | |||||||||||||||||||||||||||||||||||||||

Traversal | |||||||||||||||||||||||||||||||||||||||

foldr :: (Prefix a -> b -> b) -> b -> STree a -> b | |||||||||||||||||||||||||||||||||||||||

O(t). Folds the edges in a tree, using post-order traversal.
Suitable for lazy use.
| |||||||||||||||||||||||||||||||||||||||

foldl | |||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||

fold | |||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||

Other useful functions | |||||||||||||||||||||||||||||||||||||||

mkPrefix :: [a] -> Prefix a | |||||||||||||||||||||||||||||||||||||||

O(1). Construct a Prefix value.
| |||||||||||||||||||||||||||||||||||||||

prefix :: Prefix a -> [a] | |||||||||||||||||||||||||||||||||||||||

O(n). Obtain the list stored in a Prefix.
| |||||||||||||||||||||||||||||||||||||||

suffixes :: [a] -> [[a]] | |||||||||||||||||||||||||||||||||||||||

suffixes xs == init (tails xs) | |||||||||||||||||||||||||||||||||||||||

Produced by Haddock version 0.8 |