Abstract. Given a sequence S = s 1 s 2 . . . s n of integers smaller than r = O(polylog(n)), we show how S can be represented using n H 0 (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. H 0 (S) is the zero-order empirical entropy of S and n H 0 (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 Author's addresses: P. Ferragina, Dipartimento di Informatica, Università di Pisa, Largo Bruno Pontecorvo 3, I-56127 Pisa, Italy, e-mail: ferragina@di.unipi.it; G. Manzini, Dipartimento di Informatica, Università del Piemonte Orientale, Via Bellini, 25g, I-15100 Alessandria, Italy, e-mail: manzini@mfn.unipmn.it; V. Mäkinen, Department of Computer Science, P.O. Box 68 (Gustaf Hällströmin katu 2b), FI-00014 University of Helsinki, Finland, e-mail: vmakinen@cs.helsinki.fi; G. Navarro (contact author), Departamento de Ciencias de la Computación, Universidad de Chile, Blanco Encalada 2120, Santiago, Chile, e-mail: gnavarro@dcc.uchile.cl. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or direct commercial advantage and that copies show this notice on the first page or initial screen of a display along with the full citation. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work in other works requires prior specific permission and/or a fee. Permissions may be requested from Publications Dept., ACM, Inc., 2 Penn Plaza, Suite 701, New York, NY 10121-0701 USA, fax +1 (212) 869-0481, or permissions@acm.org. results on general sequences where those queries are answered in O(log r ) time. For larger r , we can still represent S in n H 0 (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 n H 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).
For example, a CSA achieving the small space given above REF achieves search(m) = O(m(1 + log σ log log n )) and lookup(n) = O(log 1+ n) for any constant > 0.
Compressed representations of sequences and full-text indexes
TALG
Mathematics Computer Science