| dc.description.abstract | Given a sequence of n bits with binary zero-order entropy
H0, we present a dynamic data structure that requires nH0 + o(n) bits
of space, which is able of performing rank and select, as well as inserting
and deleting bits at arbitrary positions, in O(log n) worst-case
time. This extends previous results by Hon et al. [ISAAC 2003] achieving
O(log n= log log n) time for rank and select but #2;(polylog(n)) amortized
time for inserting and deleting bits, and requiring n+o(n) bits of space;
and by Raman et al. [SODA 2002] which have constant query time but a
static structure. In particular, our result becomes the #12;rst entropy-bound
dynamic data structure for rank and select over bit sequences.
We then show how the above result can be used to build a dynamic fulltext
self-index for a collection of texts over an alphabet of size #27;, of overall
length n and zero-order entropy H0. The index requires nH0 +o(n log #27;)
bits of space, and can count the number of occurrences of a pattern of
length m in time O(mlog n log #27;). Reporting the occ occurrences can
be supported in O(occ log2 n log #27;) time, paying O(n) extra space. Insertion
of text to the collection takes O(log n log #27;) time per symbol,
which becomes O(log2 n log #27;) for deletions. This improves a previous
result by Chan et al. [CPM 2004]. As a consequence, we obtain an
O(n log n log #27;) time construction algorithm for a compressed self-index
requiring nH0 + o(n log #27;) bits working space during construction. | |
