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
