Improved Dynamic Rank-Select Entropy-Bound Structures
Rodrigo González and Gonzalo Navarro
Operations rank and select over a sequence of symbols have many
applications to the design of succinct and compressed data structures to
manage text collections, structured text, binary relations, trees, graphs, and
so on. We are interested in the case where the collections can be updated via
insertions and deletions of symbols. Two current solutions stand out as the
best in the tradeoff of space versus time (considering all the operations).
One solution, by Mäkinen and Navarro, achieves compressed space (i.e.,
nH_0 + o(n log s) bits) and O(log n * log s) worst-case time for
all the operations, where n is the sequence length, s is the
alphabet size, and H_0 is the zero-order entropy of the sequence. The
other solution, by Lee and Park, achieves O(log n *
(1+(log s)/(log log n))) amortized time and uncompressed space, i.e.
n log s + O(n) + o(n log s)
bits. In this paper we show that the best of both worlds can be achieved. We
combine the solutions to obtain nH_0 + o(n log s) bits of space and
O(log n * (1+(log s)/(log log n))) worst-case time for all the
operations. Apart from the best current solution to the problem, we obtain
several byproducts of independent interest applicable to partial sums, text
indexes, suffix arrays, the Burrows-Wheeler transform, and others.