More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries

Roberto Grossi, Alessio Orlandi, Rajeev Raman +1

We consider the problem of representing, in a compressed format, a bit-vector $S$ of $m$ bits with $n$ 1s, supporting the following operations, where $b\in \{0,1\}$: $rank_b(S,i…