###
Practical Dynamic Entropy-Compressed Bitvectors with Applications

####
Joshimar Córdova and Gonzalo Navarro

Compressed data structures provide the same functionality as their
classical counterparts while using entropy-bounded space. While they have
succeeded in a wide range of static structures, which do not undergo updates,
they are less mature in the dynamic case, where the theory-versus-practice gap
is wider. We implement compressed dynamic bitvectors *B* using
*|B|H0(B)+o(|B|)* or *|B|H0(B)(1+o(1))* bits of space, where
*H0* is the
zero-order empirical entropy, and supporting queries and updates in
*O(w)*
time on a *w*-bit word machine. This is the first implementation that provably
achieves compressed space and is also practical, operating within
microseconds.
Bitvectors are the basis of most compressed data structures; we explore
applications to sequences and graphs.