You are looking at historical revision 25760 of this page. It may differ significantly from its current revision.

## suffix-tree

An implementation of the suffix tree data structure.

## Usage

(require-extension suffix-tree)

## Documentation

In this implementation, a suffix tree is a tree where and each branch has a label that represents an element from a list with branches ordered on the basis of their labels. Only one branch per distinct label value is allowed per node. Ends of lists are designated by an EOL marker; a value may be associated with the EOL symbol.

The suffix tree permits partial look ups; that is, if the tree contains the lists `'(a b c)` and `'(a b d)`, then looking up key `'(a b)` will return the subtree that contains `'(c)` and `'(d)` as branches.

### Procedures

The library defines a suffix tree "object" -- a procedure that takes a method name as a symbol, and returns the procedure that implements the respective operation.

The suffix tree object is created by procedure `make-suffix-tree`:

*[procedure]*

`make-suffix-tree:: LEQ? KEY->LIST -> SELECTOR`

where:

`LEQ?`is a less-than-or-equal procedure for comparing elements of the member lists- {{KEY->LIST} is a procedure that takes in a key value and returns a list

The returned selector procedure can take one of the following arguments:

`'insert`- inserts a new element (list); a procedure of the form
`(LAMBDA (K BVAL) ...)`where`K`is a value of the type recognized by`KEY->LIST`and`BVAL`is the end-of-list value `'lookup`- looks up an element (list); a procedure of the form
`(LAMBDA (K) ...)`where`K`is a value of the type recognized by`KEY->LIST`; returns the EOL value or`#F`if the given element is not found `'lookup/partial`- partial lookup; returns the EOL value,
`#f`or the subtree that corresponds to the given partial key `'remove`- removes an element
`'merge`- merges the suffix tree with another; if there is a list that appears in both suffix trees, an exception is raised
`'partition`- splits the tree into three suffix-trees on the basis of the given element a. The first suffix-tree consists of branches with keys less than a (plus any EOL value), the second contains the branch (if any) associated with a, and the third consists of branches for keys greater than a

## Examples

## About this egg

### Author

### Version history

- 1.0
- Initial release

### License

Copyright 2011-2012 Ivan Raikov and the Okinawa Institute of Science and Technology. This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. A full copy of the GPL license can be found at <http://www.gnu.org/licenses/>.