chickadee » suffix-tree

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:

make-suffix-tree:procedure

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

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

Contents »