Compressed Compact Suffix Arrays
Veli Mäkinen and Gonzalo Navarro
Abstract.
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 (2.7 times the text size, as
opposed to 0.6-0.8 of compressed suffix arrays). The space of the CSA includes
that of the text, which the CSA needs separately available. Compressed suffix
arrays, on the other hand, include the text, that is, they are
self-indexes. 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 trade off
by introducing the Compressed CSA (CCSA), a self-index that improves the
space usage of the CSA in exchange for search speed. 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.6 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 are by far better
than for self-indexes that take less space than the text, and competitive
against the LZ-index and versions of compressed suffix arrays tailored to take
1.6 times the text size.