Skip to content
A C implementation of Ukkonen's suffix tree-building algorithm, with test suite and tree print.
C Shell Gnuplot
Find file
Latest commit 6d2ac4f desmond Updated gnuplots.
Failed to load latest commit information.
nbproject Added hashtable for nodes greater than 6 in size. Added precise memor…
tests Added tests.
LICENSE.txt Added Apache 2.0 license.
Makefile Added files for incomplete version.
README.md corrected a few minor errors.
benchmark.c Added hashtable for nodes greater than 6 in size. Added precise memor…
benchmark.h Added a simple test and also a gnuplot file.
debug Fixed bug in path.c.
error.c Added hashtable for nodes greater than 6 in size. Added precise memor…
error.h Fixed bug in path.c.
hashcpu.gnu Updated gnuplots.
hashcpu.png Updated gnuplots.
hashcpu.ps Updated comparison.txt and hashmem.txt - source files for gnuplot pro…
hashmem.gnu Updated gnuplots.
hashmem.png Updated gnuplots.
hashmem.ps Updated comparison.txt and hashmem.txt - source files for gnuplot pro…
hashmem.txt Updated comparison.txt and hashmem.txt - source files for gnuplot pro…
hashtable.c Added hashtable for nodes greater than 6 in size. Added precise memor…
hashtable.h Added hashtable for nodes greater than 6 in size. Added precise memor…
main.c Added hashtable for nodes greater than 6 in size. Added precise memor…
main.h Added a simple test and also a gnuplot file.
memwatch.c Added hashtable for nodes greater than 6 in size. Added precise memor…
memwatch.h Added hashtable for nodes greater than 6 in size. Added precise memor…
path.c Added hashtable for nodes greater than 6 in size. Added precise memor…
path.h Fixed bug in path.c.
print_tree.c Added hashtable for nodes greater than 6 in size. Added precise memor…
print_tree.h Fixed bug in path.c.
results.png Added a simple test and also a gnuplot file.
results.txt Added tests.
test.c Added hashtable for nodes greater than 6 in size. Added precise memor…
tree.c Added hashtable for nodes greater than 6 in size. Added precise memor…
tree.h Added hashtable for nodes greater than 6 in size. Added precise memor…

README.md

This is a basic implementation in C of Esko Ukkonen's online suffix tree building algorithm. It is intended as a teaching tool, since I have found that there are plenty of mathematical explanations of how the algorithm is truly linear and also plenty of implementations that are poorly written and hard to follow. From either source it is hard to work out exactly how to implement the algorithm. There is a full description of the code and the algorithm (minus the math) on http://programmerspatch.blogspot.com.au/2013/02/ukkonens-suffix-tree-algorithm.html. As explained there the tree.c file can be replaced by a faster implementation, e.g. one that uses small hash tables for large nodes. The supplied implementation uses linked lists which is adequate for testing and demonstration purposes.

Something went wrong with that request. Please try again.