Counting prices the representation

If a universe contains $N$ possible values, any uniquely decodable binary representation needs at least $\lceil\log_2 N\rceil$ bits in the worst case. Otherwise fewer than $N$ bit strings would have to name $N$ values, and Chapter 7's pigeonholes would force a collision.

For a subset of $m$ positions chosen from $n$, there are $\binom{n}{m}$ possibilities, so the information lower bound is

$$\log_2 \binom{n}{m}.$$

That many bits are necessary in the worst case.

A representation using the lower bound plus $o(n)$ extra bits while supporting useful operations is succinct. Merely compressing bytes is not enough: the structure must remain queryable without first expanding to a pointer-rich form.

Rank and select are inverse coordinates

For a bit vector $B$:

• $rank_1(i)$ counts 1-bits up to position $i$;
• $select_1(k)$ returns the position of 1-bit number $k$.

For 01011010, $rank_1(6)=4$ and $select_1(3)=5$ under one-based positions. Rank maps position to ordinal; select maps ordinal back to position.

A naive rank query scans the prefix. Store a cumulative count at coarse superblocks, a smaller offset at blocks, and answer the few remaining bits by a table or word-level population count. Carefully chosen block sizes keep the auxiliary directory $o(n)$ while giving constant-time queries in the standard word-RAM model.

This is the recurrence chapter's memoization idea under an information budget: cache just enough strategically placed partial answers that the uncached tail is always small.

A tree becomes parentheses

Walk an ordered rooted tree depth-first. Write 1 when entering a node and 0 when leaving it. A root with two leaf children becomes 110100. Every prefix has at least as many opens as closes, and totals agree at the end: balanced parentheses.

The encoding uses exactly $2n$ bits for $n$ nodes, near the lower bound for ordered rooted trees. Navigation becomes arithmetic on the bit sequence. Matching an open with its close finds a subtree boundary; excess $rank_1(i)-rank_0(i)$ gives depth; rank/select translate between node order and positions.

Bit vectors with rank and select also power wavelet trees, compressed text indexes, and graph encodings. The two operations are less a data structure than an instruction set from which larger succinct interfaces are compiled.

Where succinctness runs out

• Every space claim must name the lower bound, redundancy term, query set, and computation model.
• Static succinct structures often make updates expensive. Dynamic variants pay more space or time.
• A theoretically constant query may lose on real caches to a slightly larger, simpler layout. Measure the relevant workload.
• Encoding is not information security; compact bits may still expose sensitive structure.

Lessons

• Counting possible values yields a lower bound on representation bits.
• Succinct means near that bound while supporting named queries in place.
• Rank and select translate between positions and ordinals using small sampled directories.
• Balanced parentheses turn tree navigation into queries over bits.

Practice

1. Compute rank and select queries for 101001101 under clearly stated indexing conventions.
2. Encode a root with one child, which has two leaf children, as balanced parentheses.
3. Explain why gzip plus full decompression is not automatically a succinct tree.
4. One month later, derive the $\log_2 N$ lower bound from pigeonholes.

The final question is equality under motion

Succinct structures answer questions over a fixed encoded value. The book's closing structure maintains a changing partition: elements become equivalent as connections arrive, and queries ask whether two elements now share a class. The astonishing result is that repeated equality can run almost at pointer speed—provided the representation reshapes itself without changing the partition.

References

1. Jacobson. “Succinct Static Data Structures.” Carnegie Mellon University PhD thesis, 1989. — foundational thesis for succinct bitvectors, trees, and graphs
2. Navarro. “Compact Data Structures.” Cambridge University Press, 2016. — modern treatment of rank/select and compressed indexes
3. Raman, Raman, Rao. “Succinct Indexable Dictionaries with Applications.” SODA, 2002. — near-optimal set representation with rank/select-style operations