Succinct Data Structures, in depth: the information-theoretic bound, rank and select, Elias-Fano and trees in two bits per node

The bound: how few bits are enough

Suppose a class of objects has N members. Any encoding that can distinguish all of them needs at least Z = log₂ N bits for some member. That is the information-theoretic lower bound. Structures are then classed by how close they come to it:

• implicit: Z + O(1) bits. A sorted array used for binary search is implicit for a set.
• succinct: Z + o(Z) bits. The redundancy grows more slowly than Z itself, so its share tends to zero.
• compact: O(Z) bits, a constant factor above the bound.

Three counts recur. A bitvector of length n with m ones is one of C(n, m) possibilities, so Z = log₂ C(n, m), which is far below n when m is small. A sorted set of n distinct values from [0, u) is also one of C(u, n) subsets, about n log₂(u/n) + 1.44n bits when n is much smaller than u. An ordinal tree with n nodes, meaning a rooted tree whose children are ordered, is one of the Catalan number C_n-1 shapes, which is about 2n bits. A pointer-based tree spends 64 bits or more per child pointer, so a tree in about 2 bits per node is a 30x to 100x saving before any labels are stored. The hard part is navigating those bits in constant time, which is what rank and select provide.

Rank and select, the engine

Over a bitvector B, rank1(i) counts the ones in positions [0, i), and select1(j) returns the position of the j-th one. rank0 and select0 are the same for zeros. Jacobson showed in 1989 that rank can be answered in constant time with o(n) extra bits, and later work by Clark and by Munro did the same for select. The practical version stores cumulative counts at two granularities and finishes with a popcount.

class BitVector:
    """Plain bits plus a sampled rank directory: one cumulative count per 512-bit
    superblock and one relative count per 64-bit word."""
    def __init__(self, bits):
        self.n = len(bits)
        self.words = []
        for i in range(0, self.n, 64):
            w = 0
            for j, b in enumerate(bits[i:i + 64]):
                w |= b << j
            self.words.append(w)
        self.super, self.rel = [], []
        total = 0
        for k, w in enumerate(self.words):
            if k % 8 == 0:
                self.super.append(total)
            self.rel.append(total - self.super[-1])
            total += bin(w).count("1")
        self.ones = total

    def rank1(self, i):
        """Number of 1s in positions [0, i)."""
        k, r = divmod(i, 64)
        if k == len(self.words):
            return self.ones
        mask = (1 << r) - 1
        return self.super[k // 8] + self.rel[k] + bin(self.words[k] & mask).count("1")

    def rank0(self, i):
        return i - self.rank1(i)

    def select1(self, j):
        """Position of the j-th 1 (j counts from 1): binary search over rank."""
        lo, hi = 0, self.n
        while lo < hi:
            mid = (lo + hi) // 2
            if self.rank1(mid + 1) < j:
                lo = mid + 1
            else:
                hi = mid
        return lo

    def select0(self, j):
        lo, hi = 0, self.n
        while lo < hi:
            mid = (lo + hi) // 2
            if self.rank0(mid + 1) < j:
                lo = mid + 1
            else:
                hi = mid
        return lo

    def __getitem__(self, i):
        return (self.words[i // 64] >> (i % 64)) & 1

rank1 is three memory reads and one popcount. select here is a binary search over rank, O(log n), which is enough to make the later code correct. Production libraries store a sampled position for every k-th one, jump to the right block, and scan a few words, which gives near-constant time. Overhead is a design choice. Vigna's rank9 layout spends about 25% extra space and answers rank with essentially one cache miss. Poppy (Zhou, Andersen and Kaminsky, 2013) gets overhead down to roughly 3% by using larger blocks and interleaving the counts. The wavelet tree article uses these same primitives to answer range queries over sequences.

Elias-Fano: sorted integers near the bound

Elias-Fano stores a sorted sequence of n integers from [0, u). Choose l = floor(log₂(u/n)). Split each value into its low l bits and its remaining high bits. Store the low parts verbatim in an array of n l-bit fields. Store the high parts in unary: for the i-th value (0-based) with high part h, set bit h + i of a bitvector H. Because the sequence is sorted, the high parts never decrease. Each bucket's ones therefore land after the previous bucket's, and the zeros between them count bucket boundaries. H has n ones and at most u / 2^l + 1 zeros, so the total is about n(2 + log₂(u/n)) bits, close to the C(u, n) bound above.

import math

class EliasFano:
    def __init__(self, values, universe):
        n = len(values)
        self.n = n
        self.l = max(0, int(math.floor(math.log2(universe / n)))) if n else 0
        low_mask = (1 << self.l) - 1
        self.low = [v & low_mask for v in values]       # packed l-bit fields in production
        high = [0] * (n + (universe >> self.l) + 1)
        for i, v in enumerate(values):
            high[(v >> self.l) + i] = 1                  # unary bucket, shifted by i
        self.high = BitVector(high)

    def access(self, i):
        """i-th value, 0-based: select finds the bucket, low bits fill in the rest."""
        hi = self.high.select1(i + 1) - i
        return (hi << self.l) | self.low[i]

    def next_geq(self, x):
        """Smallest stored value >= x, or None."""
        b = x >> self.l
        pos = self.high.select0(b) + 1 if b > 0 else 0  # first slot of bucket b
        i = pos - b                                      # number of values before bucket b
        while i < self.n:
            v = self.access(i)
            if v >= x:
                return v
            i += 1
        return None

Worked trace. For the eight values in the figure, u = 44, so u/n = 5.5 and l = 2. The low parts are 3, 0, 3, 1, 2, 3, 1, 3. The high parts 0, 1, 1, 3, 3, 3, 5, 10 set bits 0, 2, 3, 6, 7, 8, 11 and 17 of a 20-bit H. To read access(3): select1(4) = 6, the high part is 6 - 3 = 3, and the value is 3 x 4 + 1 = 13. For next_geq(16): bucket b = 4. The fourth zero of H is at position 9, so bucket 4 begins at position 10, after 10 - 4 = 6 values. access(6) = 21, which is the answer. Posting-list intersection in a search engine is a loop of next_geq calls, which is why Vigna's quasi-succinct indices build on Elias-Fano.

Trees in about two bits per node

LOUDS, the level-order unary degree sequence, encodes an ordinal tree by visiting nodes in breadth-first order. Each node writes a one for each child, followed by a zero. A '10' prefix for an imaginary super-root gives every real node a parent one. The tree then takes 2n + 1 bits, and node x in BFS numbering (1-based) is identified with the x-th one.

def louds_bits(children, root=0):
    bits, order, q = [1, 0], [], [root]
    while q:
        v = q.pop(0)
        order.append(v)
        kids = children.get(v, [])
        bits += [1] * len(kids) + [0]
        q += kids
    return bits, order

class Louds:
    def __init__(self, bits):
        self.b = BitVector(bits)
    def first_child(self, x):
        p = self.b.select0(x) + 1            # start of node x's child run
        return self.b.rank1(p) + 1 if self.b[p] == 1 else None
    def degree(self, x):
        return self.b.select0(x + 1) - self.b.select0(x) - 1
    def parent(self, x):
        return self.b.rank0(self.b.select1(x))   # owner of the run holding x's 1

For the tree 0 → {1, 2, 3}, 1 → {4, 5}, 3 → {6}, the encoding is 10 1110 110 0 10 0 0 0, which is 15 bits for 7 nodes. Node 2 in BFS order is original node 1. Its run starts after the second zero, at position 6, which holds a one, so first_child(2) = rank1(6) + 1 = 5, original node 4. parent(7) finds the seventh one at position 10. Four zeros precede it, the super-root's included, so the parent is BFS node 4, original node 3. Every navigation step is a constant number of rank and select calls.

LOUDS does not give subtree size or lowest common ancestor. The balanced parentheses (BP) encoding writes '(' entering and ')' leaving each node in a depth-first walk, also in 2n bits. With a range min-max tree over the excess, as in Sadakane and Navarro's work, it adds subtree size, depth and LCA. Use LOUDS for downward-walking tries, as marisa-trie does, and BP for DFS-order queries.

Engineering for real hardware

• Popcount is the hot instruction. On x86-64 it is POPCNT, and on Arm NEON it is CNT plus a horizontal add. Python 3.10+ exposes it as int.bit_count(). Compilers emit it only when the target allows it, so build with -mpopcnt or an appropriate -march, or rank silently falls back to a slower software popcount.
• Cache misses dominate. A rank query costs a superblock read, a block read and a data word read. If those are in three cache lines, that is three misses on a large vector. Interleaved layouts that put counts and bits in one 64-byte line are the main reason modern designs beat older ones.
• Build once, query many. These structures are static. Inserting one value into Elias-Fano means rebuilding it. For updates, batch changes into a small mutable delta and merge periodically, as LSM trees do.
• Memory-map the result. Flat word arrays map from disk with no deserialisation.
• Partition for skew. Elias-Fano spends bits according to the average gap u/n. Dense runs inside a sparse list waste space, so partitioned Elias-Fano splits the list into chunks with their own parameters.

Failure modes

• Off-by-one conventions. Libraries disagree on whether rank is inclusive and on whether select is 0- or 1-based. Mixing conventions shifts every navigation result by one node. Wrap the library in your own functions with documented semantics, and test them against a brute-force oracle, as this page's harness does.
• Unsorted or duplicate input to Elias-Fano. Unsorted input corrupts H silently. The structure tolerates duplicates if it is built for non-decreasing values, but next_geq semantics must then be defined. Assert sortedness at build time.
• Wrong universe. A value equal to or above u writes past the end of H. Set u = max + 1 from the data, not from a guess.
• Tiny inputs. The fixed overheads of directories and headers dominate below a few thousand elements. A plain sorted array is smaller and faster there.
• Measuring the wrong thing. Benchmarks on a vector that fits in L2 cache hide the cache-miss behaviour that decides production performance. Benchmark at the real size.

Trade-offs

What to do next

1. Copy the BitVector, EliasFano and Louds classes, and run them against a brute-force oracle on random inputs before changing anything.
2. Find one large, static, sorted integer array in your system, such as document IDs, file offsets or timestamps. Measure its size as Elias-Fano and the latency of next_geq at full size.
3. For production, use a maintained library such as SDSL-lite or Vigna's Sux in C++, or folly's Elias-Fano coding, rather than porting this Python.
4. Wrap whichever library you use in functions with explicit rank and select conventions, and keep the oracle tests.
5. Keep learning: wavelet trees over rank and select, Roaring bitmaps, suffix arrays, tries in depth and Cartesian trees and range minimum.