Statistical encoding of succinct data structures

Abstract

In recent work, Sadakane and Grossi [SODA 2006] introduced a scheme to represent any sequence S = s(1)s(2)...s(n), over an alphabet of size sigma, using nH(k)(S) + O(log(sigma)n/n (k log sigma + log log n)) bits of space, log, n where H-k(S) is the k-th order empirical entropy of S. The representation permits extracting any substring of size Theta(log(sigma) n) in constant time, and thus it completely replaces S under the RAM model. This is extremely important because it permits converting any succinct data structure requiring o(vertical bar S vertical bar) = o(n log sigma) bits in addition to S, into another requiring nH(k)(S) + o(n log sigma) (overall) for any k = o(log(sigma) n). They achieve this result by using Ziv-Lempel compression, and. conjecture that the result can in particular be useful to implement compressed full-text indexes. In this paper we extend their result, by obtaining the same space and time complexities using a simpler scheme based on statistical encoding. We show that the scheme supports appending symbols in constant amortized time. In addition, we prove some results on the applicability of the scheme for full-text self-indexing.