We also give new solutions to the Dynamic Sequence problem. Given a sequence of n symbols in the range [1,s] with binary zero-order entropy H_0, we present a dynamic data structure that requires nH_0 + o(n log s) bits of space, which is able of performing rank and select, as well as inserting and deleting symbols at arbitrary positions, in O(log n * log s) time. Our result is the first entropy-bound dynamic data structure for rank and select over general sequences.
In the case s=2, where both previous problems coincide, we improve the dynamic solution of Hon et al. in that we compress the sequence. The only previous result with entropy-bound space for dynamic binary sequences is by Blandford and Blelloch [SODA 2004], which has the same complexities as our structure, but does not achieve constant 1 multiplying the entropy term in the space complexity.
Finally, we present a new dynamic compressed full-text self-index, for a collection of texts over an alphabet of size s, of overall length n and h-th order empirical entropy H_h. The index requires nH_h + o(n log s) bits of space, for any h <= a * log_s n and constant 0<a<1. It can count the number of occurrences of a pattern of length m in time O(m * log n * log s). Each such occurrence can be reported in O(log^2 n * log log n) time, and displaying a context of length l from a text takes time O(log n * (l log s + log n log log n)). Insertion/deletion of a text to/from the collection takes O(log n * log s) time per symbol. This significantly improves the space of a previous result by Chan et al. [CPM 2004] in exchange for a slight time complexity penalty. We achieve at the same time the first dynamic index requiring essentially nH_h bits of space, and the first construction of a compressed full-text self-index within that working space. Previous results achieve at best O(nH_h) space with constants larger than 1 (Ferragina and Manzini [FOCS 2000], Arroyuelo and Navarro [ISAAC 2005]) and higher time complexities.
An important result we prove in this paper is that the wavelet tree of the Burrows-Wheeler transform of a text, if compressed with a technique that achieves zero-order compression locally (e.g., Raman et al. [SODA 2002]), automatically achieves h-th order entropy space for any h. This unforeseen relation is essential for the results of the previous paragraph, but it also derives into significant simplifications on many existing static compressed full-text self-indexes that build on wavelet trees.