High-order entropy compressed bit vectors with rank/select (Q1736624)

Summary: We design practical implementations of data structures for compressing bit-vectors to support efficient rank-queries (counting the number of ones up to a given point). Unlike previous approaches, which either store the bit vectors plainly, or focus on compressing bit-vectors with low densities of ones or zeros, we aim at low entropies of higher order, for example \(101010 \dots 10\). Our implementations achieve very good compression ratios, while showing only a modest increase in query time.