suffixtree-0.1ContentsIndex
Data.SuffixTree
Portabilityportable
Stabilityexperimental
Maintainerbos@serpentine.com
Contents
Types
Construction
Querying
Traversal
Other useful functions
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 qualified, e.g. 

  import Data.SuffixTree (STree)
  import qualified Data.SuffixTree as T

The implementation is based on the first of those described in the following paper:

This implementation constructs the suffix tree lazily, so subtrees are not created until they are traversed. Two construction functions are provided, constructWith for sequences composed of small alphabets, and construct for larger alphabets.

Synopsis
type Alphabet a = [a]
data Prefix a
data STree a
= Node [(Prefix a, STree a)]
| Leaf
constructWith :: Eq a => Alphabet a -> [a] -> STree a
construct :: Ord a => [a] -> STree a
elem :: Eq a => [a] -> STree a -> Bool
find :: Eq a => [a] -> STree a -> Maybe (Prefix a, STree a)
fold :: (Prefix a -> b -> b) -> b -> STree a -> b
fold' :: (a -> Prefix b -> a) -> a -> STree b -> a
prefix :: Prefix a -> [a]
suffixes :: [a] -> [[a]]
Types
type Alphabet a = [a]
The list of symbols that constructWith can possibly see in its input.
data Prefix a
The prefix string associated with an Edge.
show/hide Instances
Eq a => Eq (Prefix a)
??? a => Show (Prefix a)
data STree a
A suffix tree. The implementation is exposed to ease the development of custom traversal functions. Note that (Prefix a, STree a) pairs are not stored in any order.
Constructors
Node [(Prefix a, STree a)]
Leaf
show/hide Instances
??? a => Show (STree a)
Construction
constructWith :: Eq a => Alphabet a -> [a] -> STree a
O(k n log n). Construct 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). Construct a suffix tree.
Querying
elem :: Eq a => [a] -> STree a -> Bool
O(n). Indicate the suffix tree contains the given subsequence. Performance is linear in the length of the subsequence.
find :: Eq a => [a] -> STree a -> Maybe (Prefix a, STree a)
O(n). Return the portion of the suffix tree at which the given subsequence is located. If the subsequence is not found, return Nothing.
Traversal
fold :: (Prefix a -> b -> b) -> b -> STree a -> b
O(n). Fold the edges in a tree, from bottom to top. Suitable for lazy use.
fold' :: (a -> Prefix b -> a) -> a -> STree b -> a
O(n). Fold the edges in a tree, from bottom to top. Suitable for strict use.
Other useful functions
prefix :: Prefix a -> [a]
Obtain the list stored in a Prefix.
suffixes :: [a] -> [[a]]

Return all non-empty suffixes of the argument, longest first. Behaves as follows: 

suffixes xs == init (tails xs)
Produced by Haddock version 0.8