Succinct Representation of Sequences
Paolo Ferragina, Giovanni Manzini, Veli Mäkinen, Gonzalo Navarro · 2008
Abstract. Given a sequence S = s1s2... sn such that 1 ≤ sq ≤ r for all q, where r = O(polylog(n)), we show how S can be represented using nH0(S)+o(n) bits (where H0(S) is the zero-order entropy of S), so that we can know any sq, as well as answer rank and select queries on S, in constant time. This extends previous results on binary sequences, and improves previous results on general sequences where those queries are answered in O(log r) time. Furthermore, we show how our technique can be applied to improve a succinct full-text index. 1