Order is free information

Consider document identities

12, 19, 20, 37, 41

Five ordinary 32-bit integers occupy 160 bits. But the list is strictly increasing. Store the first identity and the positive gaps:

12, 7, 1, 17, 4

The values are smaller because each predecessor predicts a lower bound for its successor. The transformation is lossless:

$$d_i=\sum_{j=1}^{i}g_j, \qquad g_1=d_1,\quad g_i=d_i-d_{i-1}.$$

The floor beneath every lossless representation

How many increasing lists of $n$ distinct identities can be chosen from a universe of $u$ identities? Exactly

$$\binom{u}{n}.$$

Any uniquely decodable fixed-length representation of all such sets therefore needs at least

$$L(u,n)=\left\lceil\log_2\binom{u}{n}\right\rceil$$

bits in the worst case. This is a counting argument: fewer bit strings cannot name every possible set.

For sparse sets, Stirling's approximation gives the useful scale

$$\log_2\binom{u}{n}\approx n\log_2(u/n)+n\log_2 e.$$

The first term resembles storing an average gap of $u/n$; the second records that gaps vary. A measured codec can be reported as bits per posting and as excess over this corpus-independent combinatorial floor.

The floor does not predict decode speed, random access, update cost, or block metadata. It tells us only how far a representation is from the minimum number of distinguishable states.

Elias gamma: write the magnitude twice

For a positive integer $x$, let

$$b=\lfloor\log_2x\rfloor.$$

Its ordinary binary representation has $b+1$ bits. Elias gamma writes $b$ zeroes followed by that binary representation. Examples:

Hence

$$|\gamma(x)|=2\lfloor\log_2x\rfloor+1.$$

The unary prefix tells the decoder how many remaining binary bits to read. The code is simple and universal—it needs no fitted source parameter—but it performs bit-level control work for every integer.

Elias delta: compress the magnitude

Gamma writes the magnitude $b$ in unary. Delta instead gamma-codes the binary length $b+1$, then appends the low $b$ bits of $x$:

$$|\delta(x)|=\lfloor\log_2x\rfloor +2\left\lfloor\log_2(\lfloor\log_2x\rfloor+1)\right\rfloor+1.$$

Delta eventually improves on gamma for large integers, while adding another dependent decode step. “Universal” means the expected length remains within a bounded-factor relationship for broad source families; it does not mean the code wins every finite workload.

Golomb–Rice: fit the gaps you actually have

Assume positive gaps follow a geometric distribution

$$\Pr[g=k]=p(1-p)^{k-1}.$$

Choose modulus $m$. Write $g-1=qm+r$, encode quotient $q$ in unary, and encode remainder $r$ in a truncated binary code. Rice coding restricts $m=2^b$, so the remainder always uses exactly $b$ bits.

Let $a=1-p$. For Rice modulus $m=2^b$,

$$\mathbb E[q] =\sum_{j\ge1}\Pr[g-1\ge jm] =\sum_{j\ge1}a^{jm} =\frac{a^m}{1-a^m}.$$

Therefore the expected code length is

$$\mathbb E[L_m]=b+1+\frac{a^m}{1-a^m}.$$

Balancing unary quotient and remainder suggests an unrestricted Golomb modulus near

$$m^*\approx\frac{-\ln2}{\ln(1-p)},$$

with Rice choosing a nearby power of two. Estimate from the actual gap distribution and include the parameter in the format. A fitted code can beat a universal one, but the fit can age as the corpus changes.

Variable byte: spend bits to simplify control

Variable-byte coding groups payload into seven-bit chunks and uses one control bit per byte to mark continuation or termination. A nonnegative integer uses

$$\max(1,\lceil \operatorname{bitlength}(x)/7\rceil)$$

bytes.

It wastes up to seven payload positions at a byte boundary and repeats control bits. In return it is simple, byte-aligned, and easy to integrate. Its scalar decoder branches on each control bit; predictable length distributions help the branch predictor, irregular ones do not.

Stream VByte separates control bytes from payload bytes. Four two-bit length codes describe four integers, letting a decoder load and shuffle payload with SIMD instructions instead of discovering each length through a dependent branch. The paper's reported throughput is tied to its Haswell machine, compiler, data movement boundary, and corpus. It is evidence for a design, not a timeless speed constant.

Bit packing: one width per block

For a block of $B$ gaps, compute

$$w=\max_i\operatorname{bitlength}(g_i)$$

and store all gaps in exactly $w$ bits plus the block header. The payload costs $Bw$ bits. Vectorized unpackers process fixed groups with shifts, masks, and SIMD lanes.

One outlier can set $w$ for the whole block. Patched schemes store most values at a smaller base width and record exceptions separately. This improves size when exceptions are rare but adds streams, branches, and reconstruction work.

The block size joins two tradeoffs already seen in Chapter 11:

• small blocks adapt widths closely and add more headers;
• large blocks amortize headers and expose more outliers;
• fixed-size SIMD blocks simplify loops but may not align with skip blocks or cache lines.

The `perf-search-layout` discipline adds a machine question: after decoding, are the integers consumed sequentially, searched in place, or materialized into another array? A codec that expands into a cache-cold buffer can lose to a larger representation queried directly.

Front coding the dictionary

Sorted terms share prefixes:

compress
compressed
compression
compressor

Store the first term, then each common-prefix length and remaining suffix. In blocks, keep one full restart term followed by front-coded entries. Restart spacing trades random lookup work against saved bytes.

Front coding removes repeated bytes only because lexicographic order clusters prefixes. It does not replace the dictionary lookup structure from Chapter 2. A term table may keep restart offsets or a separate search layout so lookup does not decode from the beginning.

The round-trip law belongs to the wire form

Suppose an encoder sorts and deduplicates postings before writing them. Then an arbitrary in-memory sequence $x$ need not satisfy

$$\operatorname{decode}(\operatorname{encode}(x))=x.$$

The format never promised to preserve order or duplicates. Its canonical law is

$$\operatorname{encode}(\operatorname{decode}(\operatorname{encode}(x))) =\operatorname{encode}(x).$$

Also pin intermediate bytes for known examples. A round-trip test alone can be satisfied by two mutually inverse but wrong functions. The encoded bytes prove which format was chosen.

ENCODE-POSTINGS(IDENTITIES, CODEC)
Input:  finite document IDENTITIES, declared positive-integer CODEC
Output: canonical encoded bytes

ordered ← SORT-UNIQUE(IDENTITIES)
previous ← 0
output ← empty byte sequence
for each identity d in ordered
    gap ← d - previous
    output ← APPEND(output, ENCODE-POSITIVE(CODEC, gap))
    previous ← d
return output

Bounds precede decoding. A decoder validates block counts, bit widths, payload lengths, checked products, and cumulative document identities before allocating or publishing output. Truncation, overflow, nonpositive gaps, and identities outside the corpus are typed failures, not partial lists.

Measure the whole representation path

For each corpus stratum and codec, record:

• encoded bytes and bits per posting;
• excess over $\log_2\binom{u}{n}$;
• encode and decode throughput;
• single-list latency and batched throughput;
• branches, branch misses, instructions, and cache misses where available;
• peak decoded scratch and retained memory;
• seek or restart cost for partial access;
• scalar and SIMD paths on every supported architecture;
• end-to-end query latency, not decoder microbenchmarks alone.

The static-layout lesson matters here: headline SIMD throughput often assumes several independent blocks in flight and data moving between named cache levels. Single-query latency can improve less. Publish the boundary that was measured.

No codec wins the entire plane. Gamma and delta are compact bit codes with dependent decoding. Golomb–Rice fits geometric gaps. Variable byte favors simplicity. Stream VByte separates controls for SIMD. Fixed-width block packing spends headers to make wide parallel decoding possible. A small flat array can beat all of them when the list is tiny.

Lessons

• Sorted postings imply positive gaps; encode the gaps rather than repeated absolute identities.
• A sorted $n$-subset of a $u$-element universe needs at least $\log_2\binom{u}{n}$ bits to distinguish every possibility.
• Elias codes need no fitted source parameter; Golomb–Rice spends a parameter to match geometric gaps.
• Byte alignment and separated controls may use more bits and decode faster.
• Bit packing trades block headers and outlier sensitivity for fixed-width SIMD work.
• Front coding exploits prefix sharing but needs restart points for bounded access.
• Canonicalizing encoders obey encode–decode–encode, not necessarily decode–encode identity on arbitrary inputs.
• Round trips must pin known encoded bytes.
• Measure transport size, decode work, retained memory, and query consumption as separate boundaries.

Practice

1. Gap-encode $[3,4,9,20,21]$, gamma-code the gaps, and count the bits.
2. Compute $\lceil\log_2\binom{16}{4}\rceil$ and compare it with four fixed four-bit identities.
3. Derive $\mathbb E[q]=a^m/(1-a^m)$ using the tail-sum formula for a nonnegative integer random variable.
4. For gaps $[1,2,3,31]$, compare one four-value bit-packed block with two two-value blocks, including one width header per block.
5. Give a sequence for which decode–encode does not preserve the in-memory value but encode–decode–encode preserves canonical bytes.
6. Design a benchmark whose decoder-only winner loses end-to-end because it materializes more scratch or prevents direct searching.

References

1. Peter Elias. “Universal Codeword Sets and Representations of the Integers.” IEEE Transactions on Information Theory 21, no. 2, 1975.
2. Solomon W. Golomb. “Run-Length Encodings.” IEEE Transactions on Information Theory 12, no. 3, 1966.
3. Daniel Lemire and Leonid Boytsov. “Decoding Billions of Integers per Second through Vectorization.” Software: Practice and Experience 45, no. 1, 2015.
4. Daniel Lemire, Nathan Kurz, and Christoph Rupp. “Stream VByte: Faster Byte-Oriented Integer Compression.” Information Processing Letters 130, 2018.