_suffixtree_ : suffix trees in linear time Danny Yoo (dyoo@hkn.eecs.berkeley.edu) This is an implementation of suffix trees and their linear-time construction with the Ukkonen algorithm. This implementation is based on notes from Gusfield, "Algorithms on Strings, Trees, and Sequences". Availability ============ To grab this package from PLaneT, (require (planet "suffixtree.ss" ("dyoo" "suffixtree.plt" 1))) The source will also be available here: http://hkn.eecs.berkeley.edu/~dyoo/plt/suffixtree/ Example ======= Let's rush into a minimal example: > (require (planet "suffixtree.ss" ("dyoo" "suffixtree.plt" 1))) > > (define tree (make-tree)) > (tree-add! tree (string->label "00010010$")) > > (define root (tree-root tree)) > > (node-children root) (# # #) > (string->label (node-up-label (car (node-children root)))) "$" Introduction ============ Suffix trees encode all the nonempty suffixes of a string. For example, the string "0100101$" corresponds to the following suffix tree. root | V +--- $ | +--- 1 --- $ | | | +---- 0 --- 0101$ | | | +---- 1$ | +--- 0 --- 0101$ | +---- 1 ---- $ | +----- 0 --- 1$ | +---- 0101$ Every path from the root to any leaf spells out a suffix of the string "0100101$", and every suffix is accounted for. This in itself might not sound too sexy, but by preprocessing a string as a suffix tree, we can then do some amazing things. For example, we can see if a substring is present in a suffix tree in time bounded by the length of the substring by following characters starting from the root. Suffix trees also allow us to find the longest common substring between strings in linear time. Dan Gusfield's book "Algorithms on Strings, Trees, and Sequences" sings praises about suffix trees, and deservedly so. Constructing a suffix tree can be done in linear-time; the algorithm used here is Ukkonen's algorithm, since it's one of the simplest to code. That being said, the algorithm is not quite simple; for more information on the construction algorithm, see the References section below. Suffix Tree API =============== _suffixtree.ss_ The main structures are trees, nodes, and labels. Trees ----- A suffix tree consists of a root. This implementation allows multiple labels to be added to the tree. > (make-tree) Constructs an empty suffix tree with a single root node. > (tree? datum) Returns #t if datum is a suffix tree. > (tree-root tree) Selects the root node from a tree. > (tree-add! tree label) Adds a label and all of its nonempty suffixes to the tree. > (tree-walk tree label succeed-f fail-f) Starting from the tree-root, walks along a path whose path label exactly matches the input label. If the label matched completely, calls succeed-f with the position where the matching had succeeded. succeed-f node up-label-offset -> A If the label mismatched, calls fail-f with the tree position where the matching had failed. fail-f: node up-label-offset input-label-offset -> B The return value from tree-walk will either be A or B. > (tree-contains? tree label) Returns #t if a path exists starting from the tree-root of the tree whose path-label exactly matches label. tree-contains? is an application of tree-walk: (define (tree-contains? tree label) (tree-walk tree label (lambda (node up-label-offset) #t) (lambda (node up-label-offset input-label-offset) #f))) Nodes ----- Nodes form the structure of the suffix tree, and link up children nodes as well. Every internal node I of a suffix tree will also have a suffix-node whose path-label is the immediate suffix of node I. > (node-up-label node) Selects the label of the edge that connects this node to its parent. The up-label of the root node is empty. > (node-parent node) Selects the parent of this node. The root of a suffix tree has no parent, so (node-parent (tree-root tree)) returns #f. > (node-suffix-link node) Selects the suffix node of this node. If the suffix-link is not set, returns #f. > (node-find-child node label-element) Selects the child whose up-label starts with the label-element. If no such child can be found, returns #f. > (node-children node) Selects the list of children nodes to this node. If the node is a leaf, returns (). Labels ------ Labels represent an immutable sequence of label-elements. Label-elements can be anything that compare with equal?, but the most common label-elements will be characters. Labels can be sublabeled with efficiency. > (string->label string) Constructs a label from a string. Each of the label-elements of this label will be a character. > (string->label/with-sentinel string) Constructs a label from a string with a trailing sentinel character to guarantee that all suffixes can be explicitely represented in a suffix tree. (See the Caveats section below for details.) Note that label->string can't be directly used on a label with a sentinel. > (label->string label) Constructs a string from a label, assuming that all label-elements of the string are characters. > (vector->label vector) Constructs a label from a vector. > (vector->label/with-sentinel vector) Constructs a label from a vector with a trailing sentinel character. > (label->vector label) Selects a vector of the label-elements that represent the label. This vector is immutable. > (sublabel label left-offset [right-offset]) Derives a new sliced label from the parent label, along the half-open interval [left-offset, right-offset). If right-offset is omitted, it defaults to (label-length label). (<= left-offset right-offset) should be true. > (label-ref label offset) Returns the label's label-element at that offset. > (label-length label) Returns the length of a label. > (label-equal? label-1 label-2) Warning: two labels may have equal content, but come from different sources. > (label-source-eq? label-1 label-2) Returns #t if both labels share a common derivation from sublabeling. > (label-source-id label) Returns an numeric identifier for this label. (label-source-eq? label-1 label-2) logically implies: (= (label-source-id label-1) (label-source-id label-2)) Caveats ======= The code in tree-add! assumes that the construction of the full suffix tree on its input string is possible. Certain strings don't have an full explicit suffix tree, such as "foo". +-- "foo" | +-- "oo" In this case, when we try to construct a suffix tree out of "foo", we have an implicit suffix tree, where not every leaf corresponds to a suffix of the input string. The suffix "o" is implicit in this tree. In order to guarantee that all suffixes will have a place in the suffix tree, we'll often add a sentinel character at the end the string to make sure all suffixes have a unique path in the suffix tree. For example, assuming that we use "$" as our sentinel: +-- "foo$" | +-- "o" -- "o$" | | | +---- "$" | +-- "$" The API has the function string->label/with-sentinel to automatically add a unique sentinel character at the end of a string. (let ((tree (make-tree)) (label (string->label/with-sentinel "foo"))) (tree-add! label)) so be sure to use this if you need to ensure the representation of all suffixes in the suffix tree. References ========== Dan Gusfield. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, New York, NY, 1997. Lloyd Allison. Suffix Trees. http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/Suffix/ Mark Nelson. Fast String Searching With Suffix Trees. Dr. Dobb's Journal, August, 1996. http://www.dogma.net/markn/articles/suffixt/suffixt.htm Mummer: Ultra-fast alignment of large-scale DNA and protein sequences. http://mummer.sourceforge.net/