Compressed suffix trees with full functionality

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 vertical bar A vertical bar) 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).