libstree"> ]> This is documentation for release &lst-latest-rel; of &libstree;. &libstree; is free software under terms of the BSD license as given in the License section. This documentation is always available on the web for download and online browsing at http://www.cl.cam.ac.uk/~cpk25/libstree/manual/index.html. Feedback, patches, binary packages and bugreports are all welcome, please send feedback directly to the author at christian.kreibich -AT- cl.cam.ac.uk. Yet Another SRG Production — http://www.cl.cam.ac.uk/Research/SRG/ Welcome! You're looking at the manual for &libstree;, a generic suffix tree implementation. Thanks for reading this. Suffix trees are a building block needed for efficient implementations of many string algorithms. If you've found this library, you probably already know why you want to use them. If not, have a look at the comprehensive textbook by Dan Gusfield. &libstree; is a generic suffix tree implementation, written in C. It can handle arbitrary data structures as elements of a string. It is therefore not limited to simple ASCII character strings, like most demo implementations of suffix algorithms are. Suffix tree generation in &libstree; is highly efficient and implemented using the algorithm by Ukkonen, which means that &libstree; builds suffix trees in time linear to the length of the strings (assuming that string element comparisons can be done in O(1)). &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. Because I needed a library available from within another C program, and because there didn't seem to be a good, reusable C implementation around. Using &libstree; is hopefully really quite simple. As an example, let's walk through one of the test programs found in the test directory of the source distribution: lcshex.c, which calculates the longest common byte sequence of the programs you pass it as command line arguments What do you mean, "What is this good for!?" :)". Since &libstree; operates on arbitrary strings, it needs a string model that leaves the implementation of the common string operations up to the user. String families that use a given set of such operations is called a string class (called LST_StringClass). Strings are instances of the LST_String type, and suffix trees are instances of LST_STree type. Each string belongs to a string class. Since it will often be the case that an application uses only a single class of strings (e.g., byte strings), there is a default string class, whose properties you can specify once and then forget about it. &libstree; currently uses three string-class-specific operations: A function to compare string items (LST_StringItemCmpFunc) A function to copy string items (LST_StringItemCopyFunc) A function to convert a single string into an ASCII string (LST_StringPrintFunc) The default operations assume byte strings, so compare function uses memcmp() on the memory area that the string item occupies, uses simple character assignment to copy an item. Our little test program works on binary files, so we can use the compare and copy function, but for output, we prefer hexadecimal strings. &libstree; already provides a function that does this, and we use it to override the default. Let's look at some code. We will need a suffix tree and a few strings; also, we override the output method as describes above. LST_STree *tree; LST_StringSet *set, *result; LST_String *string; /* Create a string class with a special print method, otherwise * we can use the defaults: */ lst_stringclass_set_defaults(NULL, NULL, lst_string_print_hex); Since most applications will have to handle multiple strings at a time, a container for a number of strings is convenient. &libstree; provides the type LST_StringSet that can hold a set of strings. Let's allocate such a set: /* Create a string set to conveniently hold all our strings: */ set = lst_stringset_new(); Now, we check for each of the program names that the user passed in, whether the file exists and if we can read it. We then allocate a chunk of memory and read the entire program code into it: FILE *f; u_char *data; struct stat st; /* stat() the file, open file handle etc, now read content: */ if (fread(data, 1, st.st_size, f) != (size_t) st.st_size) { printf("Error reading %s -- skipping.\n", argv[i]); free(data); continue; } We're ready to create a string object from this bytesequence and add it to our string set. string = lst_string_new(data, 1, st.st_size); lst_stringset_add(set, string); Now, let's build a suffix tree for all the strings we just put into our string set: /* Create a suffix tree for all strings in the set: */ tree = lst_stree_new(set); Now find the longest common substring of all those strings. /* Find longest common substring(s) */ result = lst_alg_longest_common_substring(tree, 0, 0); Note that the result is also a string set -- there may be multiple longest strings, of the same length. You can limit the results by requesting only substrings of a given minimum and maximum length, see lst_alg_longest_common_substring(). Finally, let's print each of the strings out to the console. The string set contents can be iterated using lst_stringset_foreach(): /* Print them out: */ lst_stringset_foreach(result, string_cb, NULL); That's it. Please browse the other test programs to get a better feeling for the API. &lst-algorithms; &lst-stree; &lst-structs; &lst-string; &lst-debug; Copyright (C) 2003, Christian Kreibich and various contributors. Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies of the Software and its documentation and acknowledgment shall be given in the documentation and software packages that this Software was used. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. This documentation is maintained in DocBook SGML, API documentation is extracted from the code using the gtk-doc tools. Dan Gusfield Cambridge University Press 1997 Esko Ukkonen Algorithmica 14 1995 249-260