On Compressing Compact Suffix Arrays
Veli Mäkinen and Gonzalo Navarro
The compact suffix array (CSA) is a space-efficient full-text index,
which is fast in practice to search for patterns in a static text. Compared to
other compressed suffix arrays (Grossi and Vitter, Sadakane, Ferragina
and Manzini), the CSA is significantly larger (1.6 times the text size, as
opposed to 0.3-0.8 of compressed suffix arrays). Worse than that, the CSA
needs the text separately available, while compressed suffix arrays include
the text, that is, they are self-indexes. However, although
compressed suffix arrays are very fast to determine the number of
occurrences of a pattern, they are in practice very slow to report even a
few occurrence positions or text contexts. In this aspect the CSA is much
faster. In this paper we contribute to this space-time tradeoff by introducing
the Compressed CSA (CCSA), a self-index that improves the space usage of
the CSA in exchange for search speed. The main idea is to add small
extra data structures that permit searching and displaying the text without
actually accessing it, so the text can be deleted. We show that the occ
occurrence positions of a pattern of length m in a text of length
n can be reported in O((m+occ)*log n) time using the CCSA, whose
representation needs O(n(1+H_k*log n)) bits for any k, H_k
being the k-th order empirical entropy of the text. In practice the CCSA
takes 1.23 times the text size (and includes the
text). This is still larger than current compressed suffix arrays, and similar
in size to the LZ-index of Navarro. Search times, however, are by far better
than any existing self-index, except for reporting text contexts of occurrences,
where the LZ-index is still superior.