Succinct Bitvectors, in depth: RRR classes and offsets, Elias-Fano as a sparse bitvector, measured space and choosing by density

The interface and the space bound

Fix the interface first: access(i) returns bit i, rank1(i) counts 1s in positions [0, i), and select1(j) returns the position of the j-th 1. Mixing an inclusive and an exclusive rank convention is the most common bug in this area, so write the convention in the type's doc comment.

How small can a bitvector with m ones in n positions be? There are C(n, m) such vectors, so any representation that can tell them apart needs log2 C(n, m) bits in the worst case. That is at most n H0(m / n), where H0(p) = -p log2 p - (1 - p) log2 (1 - p) is the zero-order entropy. At density 0.5, H0 is 1 bit per bit and a plain bitvector is optimal. At density 0.05 it is 0.286 bits per bit, and at 0.001 it is 0.011, so a plain bitvector wastes 3.5 times and 90 times the necessary space. Succinct means the total is the bound plus a lower-order term; compressed means the bound is the entropy rather than n. The succinct data structures article derives the bound in general.

RRR: classes and offsets

The RRR structure (Raman, Raman and Rao, 2002) cuts the bitvector into blocks of B bits and describes each block by two numbers. Its class is its popcount, a value from 0 to B that takes ceil(log2(B + 1)) bits. Its offset says which of the C(B, class) blocks with that popcount it is, which takes ceil(log2 C(B, class)) bits. Blocks that are all zeros or all ones have exactly one member in their class and need no offset at all; a block with one 1 needs 4 bits at B = 15; a block with six to nine 1s needs 13.

The offset is computed with the combinatorial number system. Scan the block from its high bit down, keeping the number of 1s still to place. Whenever bit pos is 1, add C(pos, remaining), the number of blocks that agree so far but have a 0 here, and decrement remaining. Decoding reverses it: at each position, if the offset is at least C(pos, remaining), the bit is 1 and you subtract. For the block with positions 0 and 2 set (the integer 0b101), the class is 2 and the offset is 1, stored in 7 bits.

To answer rank without scanning, keep a sample every s blocks holding the rank so far and the bit position of the next offset in the variable-length offset stream. A rank query loads the nearest sample, adds the classes of the blocks in between (cheap, they are fixed width), and decodes only the block containing position i. The original paper chose B around (log2 n) / 2 so that offset decoding is a table lookup; practical libraries use larger blocks and decode arithmetically, trading speed for space.

A tested RRR implementation

The reference implementation below keeps the classes and offsets as Python lists for clarity, but counts the bits a packed layout would use. A production version stores classes in a packed array and offsets in one bit stream.

import math

B = 15
C = [[math.comb(n, k) for k in range(B + 1)] for n in range(B + 1)]
OFFSET_BITS = [math.ceil(math.log2(C[B][k])) for k in range(B + 1)]   # 0 for k = 0, B

def encode_block(bits):
    k, offset, remaining = bits.bit_count(), 0, bits.bit_count()
    for pos in range(B - 1, -1, -1):
        if remaining == 0:
            break
        if bits >> pos & 1:
            offset += C[pos][remaining]       # blocks with a 0 here come first
            remaining -= 1
    return k, offset

def decode_block(k, offset):
    bits, remaining = 0, k
    for pos in range(B - 1, -1, -1):
        if remaining == 0:
            break
        if offset >= C[pos][remaining]:
            offset -= C[pos][remaining]
            bits |= 1 << pos
            remaining -= 1
    return bits

class RRR:
    def __init__(self, bitlist, sample=32):
        self.sample, self.classes, self.offsets = sample, [], []
        self.rank_samples, self.ptr_samples = [], []
        ones = ptr = 0
        for b in range(0, len(bitlist), B):
            if (b // B) % sample == 0:
                self.rank_samples.append(ones)
                self.ptr_samples.append(ptr)   # where this block's offset starts
            word = sum(bit << i for i, bit in enumerate(bitlist[b:b + B]))
            k, off = encode_block(word)
            self.classes.append(k)
            self.offsets.append(off)
            ones, ptr = ones + k, ptr + OFFSET_BITS[k]
        if len(self.classes) % sample == 0:   # so rank1(n) finds a sample
            self.rank_samples.append(ones)
            self.ptr_samples.append(ptr)

    def rank1(self, i):
        # number of 1s in positions [0, i)
        blk, inblk = divmod(i, B)
        s = blk // self.sample
        r = self.rank_samples[s] + sum(self.classes[s * self.sample:blk])
        if inblk:
            word = decode_block(self.classes[blk], self.offsets[blk])
            r += (word & ((1 << inblk) - 1)).bit_count()
        return r

Test it the only way that catches off-by-one errors: build a prefix-sum array of the raw bits and compare rank1(q) with prefix[q] for thousands of random q, including 0, n and multiples of B. int.bit_count needs Python 3.10 or later; in C or Rust it compiles to the hardware popcount instruction.

Measured: where the bits go

Building 2^20-bit vectors and counting the bits of each component shows where the space goes. Samples hold two 64-bit numbers every 32 blocks at B = 63 and every 128 blocks at B = 15, so both spend about 0.065 bits per bit on samples. Elias-Fano, described next, depends only on n and the number of 1s.

Three lessons come out of the table, in bits per input bit. First, the class array sets a floor: log2(B + 1) / B is 0.267 at B = 15 and 0.095 at B = 63, paid even on an all-zero vector. Larger blocks lower the floor but make each decode longer. Second, on independent random bits, Elias-Fano wins once the vector is sparse: at density 0.001 it is within about 5 percent of H0 while RRR is stuck above its class floor. Third, on the clustered vector, where 10 percent of 4,096-bit regions are half full and the rest are empty, RRR's offsets total only 0.082 bits per bit, well below the global H0 of 0.255. RRR is not beating entropy. Global zero-order entropy only sees the overall density, while RRR's per-block classes adapt to local density: empty blocks cost a class and nothing else. Clustered data is where RRR earns its complexity.

These are sizes, not speeds. A plain rank is a sample read plus a popcount; an RRR rank sums up to s classes and decodes a block arithmetically, which is several times slower in practice. Measure on your own queries before committing.

Elias-Fano as a sparse bitvector

A bitvector with m ones is the same thing as the sorted list of the positions of those ones, and Elias-Fano stores a sorted list near optimally. Choose l = floor(log2(n / m)). Each position is split into its low l bits, stored verbatim in an array of m l-bit fields, and its high part, stored in unary: for each bucket of 2^l positions, write one 1 per element in the bucket and then a 0. The high part takes about m + n / 2^l bits, so the total is roughly m (2 + log2(n / m)) bits.

With a select structure on the high bits, select1(j) is one select plus one array read, which makes Elias-Fano very fast for select. rank1(i) finds the start of bucket i >> l with a select0 on the high bits, then scans the low bits of that bucket for values below i; the scan is short because buckets average under two elements. access(i) is a rank in disguise. Elias-Fano is what the sd_vector type in the sdsl-lite library implements, beside its plain bit_vector and its rrr_vector.

At density 0.5 Elias-Fano is the wrong tool, 1.5 bits per bit by the table. It shines below a density of a few percent, which is exactly where posting lists, sparse feature indicators and wavelet tree levels over large alphabets sit.

Choosing a representation

If you need set operations such as AND and OR between bitmaps rather than rank and select, a container format such as Roaring is usually better. If a bitvector is one level of a wavelet tree, choose per level: upper levels on skewed text are often sparse or clustered, so mixing representations inside one tree is common.

Operational guidance

• Measure before choosing. Compute density and a cheap clustering signal, the fraction of all-zero 64-bit words, on real data. Pick by the table, then benchmark rank and select latency at your actual query mix.
• Use 64-bit counters. Samples stored as 32-bit integers overflow beyond 2^32 bits, which is only 512 MiB of raw bitvector. Tests at small sizes never see it.
• Serialise with a header. Store a format version, n, m, B, the sample rate and the endianness. A memory-mapped index that silently loads with a different block size returns wrong ranks, not errors.
• Build in one streaming pass. RRR and Elias-Fano can both be built while scanning bits once, appending classes, offsets and samples. Keep the raw bits only when you need them for a verification pass.
• Compile for popcount. Without a target flag such as -mpopcnt or -march=native, C compilers may emit a slower software popcount; check the generated code.

Failure modes

• Inclusive versus exclusive rank. Off-by-one answers at block boundaries are the classic symptom. Test i = 0, i = n and every multiple of B.
• Choosing RRR for sparse random data. The class array costs 0.095 bits per bit even at B = 63, eight times Elias-Fano's total at density 0.001.
• Choosing Elias-Fano for dense data. Above roughly one quarter density it exceeds a plain bitvector.
• Small vectors. Under a few thousand bits, directories and headers dominate; a plain array scanned with popcount is smaller and faster.
• Large B with a slow decoder. A rank that decodes a 63-bit block bit by bit can cost far more than the memory it saved. Profile the decode loop.

Trade-offs

What to do next

1. Write the rank convention into your bitvector type's documentation and add the prefix-sum oracle test.
2. For each bitvector in your index, record n, m and the fraction of all-zero words.
3. Estimate plain, RRR and Elias-Fano sizes with the formulas above before writing any code; the table usually decides.
4. Prototype with the Python RRR class, then move to a library such as sdsl-lite and benchmark rank and select latency on your real query log.
5. Add a versioned header and 64-bit samples before the first index ships.
6. Read the rank and select structures article to make the plain case as fast as possible.