Efficient Fully-Compressed Sequence Representations
We present a data structure that stores a sequence s[1..n] over alphabet [1..?] in \(n\mathcal{H}_{0}(s) + o(n)(\mathcal {H}_{0}(s){+}1)\) bits, where \(\mathcal{H}_{0}(s)\) is the zero-order entropy ofs. This structure supports the queries access, rank and select, which are fundamental building blocks for many other compressed data structures, in worst-case time \({\mathcal{O} ( {\lg\lg\sigma} )}\) and average time \({\mathcal{O} ( {\lg\mathcal{H}_{0}(s)} )}\). The worst-case complexity matches the best previous results, yet these had been achieved with data structures using \(n\mathcal{H}_{0}(s)+o(n\lg \sigma)\) bits. On highly compressible sequences the o(nlg?) bits of the redundancy may be significant compared to the \(n\mathcal{H}_{0}(s)\) bits that encode the data. Our representation, instead, compresses the redundancy as well. Moreover, our average-case complexity is unprecedented.
compressed sequence representations rank and select on sequences compact data structures entropy-bounded structures compressed text indexing