Golomb-Rice Coding for Postings Gaps

A postings list stored as gaps has a skewed distribution: most gaps are small, and a few are large. The ideal code for such a distribution spends few bits on the common small values and more on the rare large ones, and the Golomb family is the canonical construction that does exactly this with a single tunable parameter. Rice coding is the special case where the parameter is a power of two, which turns the division and remainder into a shift and a mask and makes the whole scheme cheap enough to be the default bit-level code for postings.

The family sits one rung below the byte-aligned and bit-packed schemes in this cluster: it is a true variable-length code over bits, with no block structure and no byte alignment, and it is optimal for a specific and realistic model of the gap distribution. Its cost is that every value requires a data-dependent decode, and its correctness depends on a divisor chosen to match the data.

The geometric model and the optimality result

The natural model for gaps is the geometric distribution: the probability of a gap of length g is proportional to p^g for some p between 0 and 1, which says that a gap of one is the most common, a gap of two the next most common, and so on, decaying geometrically. Postings placed uniformly and independently in a document stream produce exactly this distribution for the gaps, and although real collections are burstier than the model, the geometric distribution is the right first approximation.

Golomb’s 1966 result shows that for a geometric source with parameter p, the optimal prefix code has gaps of size m, where m is roughly the value that solves p^m ≈ 1/2, and the code assigns a quotient and a remainder against m. The result is not an approximation: it is the construction that minimises expected code length for the geometric source, and it is the reason the code has a parameter at all. The parameter m is the expected gap, in the sense that it is the divisor against which gaps are split.

The quotient-remainder structure follows from the distribution. Large gaps have large quotients and are rare, so the quotient is encoded with a code that grows with its value — a unary code, a run of zero bits terminated by a one. Small gaps have small quotients and are common, so the unary code’s short form for them is exactly the right cost. The remainder is uniform over 0 to m−1 when the source is geometric, so it is encoded in a fixed number of bits, ⌈log₂ m⌉ for the remainder, with the trailing remainder values folded to avoid wasting a bit.

Rice: when the divisor is a power of two

Rice coding fixes m = 2^k, so the remainder is the low k bits of the value and the quotient is the rest, and both are extracted with a shift and a mask rather than a division. Encoding a gap g:

/* Encode g with Rice parameter k into a bit writer. */
void rice_encode(uint32_t g, int k, struct bitwriter *w) {
    uint32_t q = g >> k;              /* quotient: high bits */
    uint32_t r = g & ((1u << k) - 1); /* remainder: low k bits */
    while (q--) bit_write(w, 0);      /* unary quotient */
    bit_write(w, 1);
    write_bits(w, r, k);              /* fixed-width remainder */
}

/* Decode one value; returns the gap and advances the reader. */
uint32_t rice_decode(int k, struct bitreader *rd) {
    uint32_t q = 0;
    while (bit_read(rd) == 0) q++;
    uint32_t r = read_bits(rd, k);
    return (q << k) | r;
}

The unary quotient is the data-dependent part: a gap of g costs roughly g / 2^k zero bits plus one terminator plus k remainder bits. For a gap of one with k = 3, that is a quotient of zero — one bit — plus three remainder bits, four bits total, against eight for a variable byte. For a gap of a million with k = 3, the quotient is 125,000, which costs 125,001 bits, and the code is catastrophically bad. The parameter k sets the expected gap the code is tuned for, and a mismatch in either direction is expensive.

The asymmetry matters. A k too large wastes bits on the remainder of every value, because the fixed remainder width is ⌈k⌉ and small gaps pay it in full. A k too small explodes the unary quotient of the large gaps, because the quotient length is linear in g / 2^k. The optimum is narrow, and choosing k is the entire difficulty of using the code.

Choosing the divisor

The divisor should be close to the mean gap. For a geometric source the optimal m is approximately the mean gap of the source, and in the Rice form k is ⌈log₂ of the mean⌉. The mean gap is the document frequency divided by the number of postings, which is computable exactly for each term: a term with n postings in a collection of N documents has mean gap N/n, so k ≈ log₂(N/n).

This is a per-term quantity, and it is the reason Rice-coded postings are stored per term with the parameter in the term’s dictionary entry. A frequent term with mean gap of ten uses k = 3 or 4; a rare term with mean gap of a hundred thousand uses k = 17. The dictionary must carry k alongside the postings pointer, and it does, because the decoder cannot start without it.

There are two refinements. The first is that the remainder need not be a full k bits when the mean is not a power of two; the original Golomb construction folds the remainder so that m need not be a power of two, saving a fraction of a bit per value at the cost of a division instead of a shift. Rice accepts the rounding to the next power of two and the wasted bit in exchange for the shift-and-mask decode. The second is that the mean gap is a static property of the term, but the distribution within a term is bursty, so a single k is a compromise across the list; adaptive schemes that change k as the list is decoded, based on the gaps seen so far, tighten this at the cost of decoder state.

Interaction with position streams

Position gaps inside a document are a different source with a much lower mean. A term occurring in a phrase has position gaps of one, so the mean position gap can be near one, and a Rice code with k = 0 or k = 1 — where the remainder is empty or one bit and every gap is a unary quotient — is the natural fit. This is the same observation that motivates the separation of document and position streams in positional indexes, and it is where Rice coding is at its strongest: a stream of mostly-ones encodes at close to one bit per value, which no byte-aligned code approaches.

The same skew that helps here hurts elsewhere. A position stream with an occasional long gap — a term that appears once early and once at the end of a long document — pays a unary quotient proportional to the long gap, and the k chosen for the common case of one is far too small for it. The burstiness that bit packing with frame-of-reference blocks handles by isolating outliers per block is handled here only by the adaptive variants, which is the concrete cost of the geometric model’s optimism.

When to prefer it, and the failure modes

The honest comparison is against the other codes in this cluster on three axes: space, decode speed, and adaptability.

Space: Rice is near-optimal for a geometric source and is the best of the schemes here on exactly that distribution, beating byte-aligned and fixed-width bit packing when the gaps match its parameter. On non-geometric, heavy-tailed data it is not optimal, and a block-structured scheme with per-block parameters can do better on the body while isolating the tail.

Decode speed: the unary quotient is a loop over single bits, and each value has a data-dependent number of steps, so Rice decoding is slower per value than a fixed-width unpack or a branch-free variable-byte decoder. The loop is the same branch-prediction hazard described in the variable-byte discussion, but over individual bits, which is worse. A table-driven decoder that looks up several bits at once mitigates this and is the standard implementation trick.

Adaptability: the code has one parameter, chosen per term, and it cannot adapt within a list without changing the format. Every other scheme in this cluster either needs no parameter or adapts per block. The per-term parameter is also a correctness coupling: a dictionary entry whose k does not match the encoded list produces a decode that reads the wrong number of bits and desynchronises the rest of the list, so the parameter and the payload are one unit and must never be edited separately.

The failure mode worth naming last is the division of labour. A Rice-coded list has no block boundaries and no random access, so a seek into the middle of a list requires decoding from the start, and the only remedy is a skip array layered on top, which reintroduces the block structure the bit-level code was meant to avoid. For sequential reads — term-at-a-time evaluation, position-stream scanning — that is no cost at all, and it is why Rice coding belongs to the sequential, disk-bound end of the design space rather than to the random-access, latency-bound end. The monotone, random-access alternative is Elias-Fano, and the two occupy complementary corners of the same trade.