Bitvector Rank–Select Directory
Navigate packed bits by translating between prefix counts and positions of ones.
By Riano · Published · Updated · Report a correction
Bitvector Rank–Select Directory
Rank and select operations allow querying the number of ones in a prefix of a bit vector and finding the position of the k-th one. A block directory structure precomputes these values for blocks of bits, enabling fast lookups without scanning the entire vector.
Worked Example
Consider a bit vector and prefix length. We can manually calculate the rank and select operations.
- Take the bit vector 00110101 and prefix length 4.
- The exclusive prefix rank is the count of ones in the first 4 bits (0011), which is 2.
- The select position for the 2nd one is the zero-based index 3.
Experiment
Use the Interactive Bitvector Rank–Select Directory to explore rank and select calculations.
- Select Bits to be "Mixed".
- Select Prefix length to be 4. Observe that the exclusive prefix rank updates.
- Change One ordinal to 4. Notice the new select position calculated.
Limitations
This directory explicitly demonstrates full-block lookup and residual scanning but does not claim to attain the theoretically optimal asymptotic succinct space bounds.
References
For further reading, see the Stanford CS166 lecture notes on Rank and Select which describes these succinct data structures in more detail.
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive Bitvector Rank–Select Directory module.
Try Bitvector Rank–Select Directory on Riano →