1. Compressed Suffix Trees with Full Functionality.
- Author
-
Sadakane, Kunihiko
- Subjects
DATA structures ,ELECTRONIC data processing ,FUNCTIONAL analysis ,ALGORITHMS ,MATHEMATICAL optimization ,MATHEMATICAL analysis ,MATHEMATICS - 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). [ABSTRACT FROM AUTHOR]
- Published
- 2007
- Full Text
- View/download PDF