GolombRice

GolombRice is a data encoding scheme used for compressing sequences of non-negative integers. It is a specialization of Golomb coding where the divisor m is a power of two, typically written as m = 2^k.

In encoding, given x, compute q = floor(x / m) and r = x mod m. The code for x consists of the unary representation of q (a sequence of q ones followed by a zero) followed by the binary representation of r using k bits. Decoding reverses this: read unary q by counting leading ones until a zero, then read k bits to obtain r, and reconstruct x = q m + r.

GolombRice coding is favored for data that exhibit a geometric-like distribution with many small values and a tail of larger values. Its strengths include simplicity, fast arithmetic, and one-pass encoding/decoding suitable for streaming. The choice of k determines efficiency; smaller k favors smaller values, larger k can better accommodate larger values, and many implementations use adaptive schemes that adjust k over blocks of data.

A typical use is as an entropy coder for residuals in lossless compression systems, including image and audio contexts, where the data are near geometric. The standard Rice form (the case m = 2^k) offers a simple, efficient implementation, while the general Golomb code with arbitrary m provides flexibility for different distributions. See also Golomb coding and Rice coding.