Compressed Suffix Trees with Full Functionality |
| |
Authors: | Kunihiko Sadakane |
| |
Affiliation: | (1) Department of Computer Science and Communication Engineering, Kyushu University, Hakozaki 6-10-1, Higashi-ku, Fukuoka 812-8581, Japan |
| |
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). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|