Compressed Representations of Sequences and Full-Text Indexes.

Given a sequence S = s₁s₂ … s_n of integers smaller than r = O(polylog(n)), we show how S can be represented using nH₀(S) + o(n) bits, so that we can know any s_q, as well as answer rank and select queries on S, in constant time. H0(S) is the zero-order empirical entropy of S and nH₀(S) provides an information-theoretic lower bound to the bit storage of any sequence S via a fixed encoding of its symbols. This extends previous results on binary sequences, and improves previous results on general sequences where those queries are answered in O(log r ) time. For larger r, we can still represent S in nH₀(S) + o(n log r ) bits and answer queries in O(log r/ log log n) time. Another contribution of this article is to show how to combine our compressed representation of integer sequences with a compression boosting technique to design compressed full-text indexes that scale well with the size of the input alphabet ∑. Specifically, we design a variant of the FM-index that indexes a string T [1, n] within nH_k (T )+o(n) bits of storage, where H_k (T ) is the kth-order empirical entropy of T . This space bound holds simultaneously for all k ≤ α log_∣∑∣n, constant 0 < α < 1, and _∣∑∣ = O(polylog(n)). This index counts the occurrences of an arbitrary pattern P[1, p] as a substring of T in O(p) time; it locates each pattern occurrence in O(log^1+ε n) time for any constant 0 < ε < 1; and reports a text substring of length ℓ in O(ℓ + log^1+ε n) time. Compared to all previous works, our index is the first that removes the alphabet-size dependance from all query times, in particular, counting time is linear in the pattern length. Still, our index uses essentially the same space of the kth-order entropy of the text T , which is the best space obtained in previous work. We can also handle larger alphabets of size ∣∑∣ = O(n^β), for any 0 < β < 1, by paying o(n log ∣∑∣) extra space and multiplying all query times by O(log ∣∑∣/ log log n). [ABSTRACT FROM AUTHOR]