Time-space trade-offs for compressed suffix arrays |
| |
Authors: | SSrinivasa Rao |
| |
Affiliation: | The Institute of Mathematical Sciences, Chennai, India 600 113 |
| |
Abstract: | Given a binary string of length n, we give a representation of its suffix array that takes O(nt(lgn)1/t) bits of space such that given i,1?i?n, the ith entry in the suffix array of the string can be retrieved in O(t) time, for any parameter 1?t?lglgn. For t=lglgn, this gives a compressed suffix array representation of Grossi and Vitter Proc. Symp. on Theory Comput., 2000, pp. 397-406]. For t=O(1/ε), this gives the best known (in terms of space) compressed suffix array representation with constant query time. From this representation one can construct a suffix tree structure for a text of length n, that uses o(nlgn) bits of space which can be used to find all the k occurrences of a given pattern of length m in O(m/lgn+k) time. No such structure was known earlier. |
| |
Keywords: | Data structures Suffix array Suffix tree |
本文献已被 ScienceDirect 等数据库收录! |
|