Christian Kreibich
ICIR ICSI
ICSI » ICIR » Christian Kreibich » libstree
libstree
A generic suffix tree library

News

  • Many of you have pointed out bugs in the prerelease. Thank you all for the reports. I am doing my best to fix them, but it is increasingly hard for me to find time to work on libstree. Therefore, more than ever, patches are welcome. Should you be interested in improving and possibly maintaining libstree, I'd especially like to hear from you. Get in touch! 24.09.07

  • I have received a lot of requests and comments on libstree lately — thanks! I have bundled up a pre-release of 0.4.3 in response to your feedback. 06.03.07

Introduction

libstree is a generic suffix tree implementation, written in C. It can handle arbitrary data structures as elements of a string. Unlike most demo implementations, it is not limited to simple ASCII character strings. Suffix tree generation in libstree is highly efficient and implemented using the algorithm by Ukkonen. This means that libstree builds suffix trees in time linear to the length of the strings, assuming that string element comparisons can be done in constant time.

libstree can handle multiple strings per suffix tree, including dynamic insertion and removal of strings. It provides various means of obtaining information about nodes in the tree, such as depth-first and breadth-first iteration, leaves iteration, and bottom-up iteration. libstree provides implementations of longest-common-substring and longest-repeated-substring algorithms, as examples of how to build complex algorithms using the suffix tree primitives.

libstree is using the BSD license, builds on Linux, FreeBSD and OpenBSD, and probably others as well. It has no further requirements. For the latest version and documentation, see links below..

FAQs

  • Q: I've computed an LCS. I'd like to know the indices of each substring for one of the input strings in my suffix tree. Can I get those?

    A: Currently, no. Sorry. Patches welcome!

  • Q: Can I use libstree for strings other than byte sequences?

    A: Yes, absolutely. You can provide your own implementations of string item constructors, compare functions, etc.

Manual

The current manual is always available online here. It is also included in the distribution, and available for download as a tarball.

Links

updated on 27 November 09 | yummy spam, yesss... built with TT | (cc) Christian Kreibich