Time-space trade-offs for compressed suffix arrays

✍ Scribed by S.Srinivasa Rao

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 70 KB
• Volume: 82
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(01)00298-8

✦ Synopsis

Given a binary string of length n, we give a representation of its suffix array that takes O(nt (lg n) 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 lg lg n. For t = lg lg n, 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(n lg n) bits of space which can be used to find all the k occurrences of a given pattern of length m in O(m/ lg n + k) time. No such structure was known earlier.