The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

SuDS project / Compressed suffix tree

This implementation of compressed suffix tree follows closely a recent article by Sadakane (Compressed Suffix Trees with Full Functionality, Theory of Computing Systems, in press). The implementation supports all typical suffix tree operations, including suffix links. In addition, it supports lowest common ancestor (lca) queries. Some operations work in constant time (traversing in the tree, lca), others are slower than normal suffix tree operations by about a logarithm factor. The space-savings are significant: on a 10MB DNA sequence, the compressed suffix tree was taking about 33MB. A normal suffix tree takes easily 160MB (and this does not yet support lca-queries). Even a plain suffix array takes more space than the compressed suffix tree.
  • Download Files (local site)
  • Offical Site

    Problem Links
    Suffix Trees and Arrays (7)


    This page last modified on 2008-07-10 .
    www.algorist.com