Squeezing succinct data structures into entropy bounds

Consider a sequence S of n symbols drawn from an al- phabet A = {1,2,...,σ}, stored as a binary string of n log σ bits. A succinct data structure on S supports a given set of primitive operations on S using just f(n) = o(n log σ) extra bits. We present a technique for trans- forming succinct data structures (which do not change the binary content of S) into compressed data structures usingnHk+f(n)+O(n(logσ+loglogσn+k)/logσn) bits of space, where Hk ≤ log σ is the kth-order empiri- cal entropy of S. When k+logσ = o(logn), we improve the space complexity of the succinct data structure from nlogσ+o(nlogσ) to nHk +o(nlogσ) bits by keeping S in compressed format, so that any substring of O(logσ n) symbols in S (i.e. O(log n) bits) can be decoded on the fly in constant time. Thus, the time complexity of the supported operations does not change asymptotically. Namely, if an operation takes t(n) time in the succinct data structure, it requires O(t(n)) time in the resulting compressed data structure. Using this simple approach we improve the space complexity of some of the best known results on succinct data structures We extend our results to handle another definition of entropy.