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

Outdated egg!

This is an egg for CHICKEN 4, the unsupported old release. You're almost certainly looking for the CHICKEN 5 version of this egg, if it exists.

If it does not exist, there may be equivalent functionality provided by another egg; have a look at the egg index. Otherwise, please consider porting this egg to the current version of CHICKEN.

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:

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

Ivan Raikov

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/>.