Suffix tree implementation library

This library is an implementation of the suffix tree algorithm applied to indexing. A search on "suffix trees Ukkonen" on a search engine should give you an idea of what I'm talking about. The interesting points are a linear indexing time, very little memory consumption (except for a small custom cache used to save some disk access) and a very fast lookup.

I don't want to spend much time to detail the algorithm behind the library, in fact once you've read a few papers about the Ukkonen implementation it's pretty straight forward.

Note that this implementation has NOT been done in the meaning of finding substring patterns but just to have a fast key/data pair lookup.

An example can be found in the archive. It will introduce you to all the functions of the library for storing key/data pairs and retrieving them. See the README file for a few explanations (very few I admit)

The new version 1.2 finally includes a dumping and loading tool and the library has now a STdelete() function.

Download the library version 1.2
Download the library version 1.1

2001-10-22: Get the 1.3a version, many code changes and improvements in the API, deleted blocks are now reused. It's still alpha quality as no extensive tests have been made yet, but this version is at last getting close to a true DB library. Also note the license change, this is now LGPL code.

Fabien Menemenlis any feedback appreciated