Theory Meets Practice for Bit Vectors Supporting Rank and Select

Florian Kurpicz, Niccolò Rigi-Luperti, Peter Sanders

Bit vectors with support for fast rank and select are a fundamental building block for compressed data structures. We close a gap between theory and practice by analyzing an import…