Abstract
We introduce new data structures for compressed suffix trees whose size are linear in the text size. The size is measured in bits; thus they occupy only O(n log|A|) bits for a text of length n on an alphabet A. This is a remarkable improvement on current suffix trees which require O(n log n) bits. Though some components of suffix trees have been compressed, there is no linear-size data structure for suffix trees with full functionality such as computing suffix links, string-depths and lowest common ancestors. The data structure proposed in this paper is the first one that has linear size and supports all operations efficiently. Any algorithm running on a suffix tree can also be executed on our compressed suffix trees with a slight slowdown of a factor of polylog(n).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles and news from researchers in related subjects, suggested using machine learning.Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Sadakane, K. Compressed Suffix Trees with Full Functionality. Theory Comput Syst 41, 589–607 (2007). https://doi.org/10.1007/s00224-006-1198-x
-
Advertisement
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00224-006-1198-x