Compression keeps discovering numbers inside other compression problems.
How long is this run? How far back is that match? How many symbols belong to this block? How large is this dictionary entry? Which index should the decoder follow?
These are not letters, pixels or words. They are integers.
And integers create their own compression problem.
If we reserve 32 bits for every count, then the number 3 costs as much as the number 3,000,000,000. That is convenient, but often wasteful. If small values occur much more often than large ones, the code should reflect that.
Universal integer codes are one family of answers. They provide self-delimiting representations for positive integers without requiring a fixed maximum value in advance. Small numbers get short names. Large numbers remain representable, but they pay more.
Quick Read
- Compression formats constantly need to encode counts, lengths, offsets and indexes.
- Fixed-width integers are simple but can waste bits when small values dominate.
- Variable-length integer codes give short representations to small values and longer representations to large ones.
- Self-delimiting codes tell the decoder where one integer ends without a separate length field.
- Elias gamma and delta codes are classic universal codes for positive integers.
- Golomb codes are efficient when values roughly follow geometric-type distributions.
- Rice codes are a Golomb special case that makes decoding especially simple when the divisor is a power of two.
- No one integer code is best for every distribution; the source statistics determine what is efficient.
The One-Sentence Answer
Universal integer codes compress non-negative or positive integers by giving common small values short self-delimiting codewords while allowing arbitrarily large values to remain representable without fixing a maximum width in advance.
Why Integers Need Compression Too
Suppose a compressor finds a repeated phrase 12 bytes behind the current position. It may need to encode an offset of 12 and a match length of 7.
Now imagine another match sits 50,000 bytes back and has length 300.
The same fields must support both tiny and large values.
A fixed-width representation solves this mechanically. Reserve enough bits for the largest allowed value and use that width every time.
But if small offsets and short run lengths are common, that scheme repeatedly spends space describing leading zeros.
Variable-length coding asks a better question:
Why should a small number pay the rent of a large number it is not?
Fixed Width Is Predictable, Not Always Efficient
An 8-bit unsigned integer can represent 256 values. A 16-bit field can represent 65,536 values. A 32-bit field can represent billions.
The benefit is simplicity:
- the decoder always knows exactly how many bits to read;
- random access is straightforward;
- hardware handles fixed widths efficiently;
- there is no codeword-boundary ambiguity.
The cost appears when the distribution is skewed.
If 90% of your values are below 16, using 32 bits for each one spends far more space than the uncertainty requires.
Variable Length Turns Magnitude Into Cost
A variable-length integer representation lets code length grow with magnitude.
Small numbers use fewer bits. Large numbers use more.
This is the same economic principle seen throughout the Compression series:
common / expected / small → short description rare / surprising / large → longer description
But a new problem appears immediately.
If integers have different lengths, how does the decoder know where one ends and the next begins?
Self-Delimiting Codes
A self-delimiting code contains enough structure that the decoder can determine the codeword boundary from the code itself.
This avoids storing a separate length before every integer, which would partly defeat the point.
Prefix-free codes solve the same family of boundary problems we saw with Huffman coding: no valid codeword is the prefix of another, so one code can be decoded and then the next can begin immediately.
Universal integer codes use carefully designed prefix structures so infinitely many positive integers can each receive a finite codeword.
Elias Gamma Coding: Describe the Length, Then the Number
Elias gamma coding is one of the cleanest examples.
To encode a positive integer n:
- Write n in binary.
- Count how many bits the binary form uses.
- Write that many bits in a self-delimiting pattern by placing a run of zeros before the binary representation.
For example:
1 → 1 2 → 010 3 → 011 4 → 00100 5 → 00101 6 → 00110 7 → 00111 8 → 0001000
The number of leading zeros tells the decoder how many additional bits belong to the codeword.
The representation is self-delimiting and needs no predetermined maximum integer.
Why Gamma Coding Likes Small Numbers
For n with binary length L, gamma coding uses roughly 2L−1 bits.
That makes very small values compact and large values progressively more expensive.
If your source produces many small integers with a long tail of occasional large values, this can be useful.
If the distribution is concentrated around one huge value instead, gamma coding may be a poor fit.
As always, the code must match the source.
Elias Delta Coding: Compress the Length More Carefully
Gamma coding spends unary-like overhead describing the bit-length of n. Elias delta coding goes one level further.
It encodes the length itself using a gamma code, then appends the remaining binary digits of n.
This makes delta coding more efficient than gamma coding for sufficiently large integers, because the description of the length grows more slowly.
The idea is recursive in spirit:
number → binary length → compressed description of the length + remaining bits
Compression has compressed part of its own metadata.
How Far Can This Recursion Go?
Elias omega coding continues the idea of recursively describing lengths. The deeper lesson is not that everyone should memorise a family of Elias codes.
The lesson is architectural:
If the metadata has structure, the metadata can be compressed too.
Lengths, indexes and counts are not outside the information problem. They are part of it.
Golomb Coding: What if Small Values Follow a Geometric Pattern?
Suppose a non-negative integer source produces 0 very often, 1 slightly less often, 2 less often again, and so on, with probability decaying approximately geometrically.
This distribution appears naturally in waiting times, prediction errors and run lengths under some models.
Golomb coding is designed for this kind of source.
Choose a positive parameter m. For value n, divide n into:
quotient q = floor(n / m) remainder r = n mod m
Encode the quotient in unary, then encode the remainder in a compact binary form.
The quotient handles how many groups of m we passed. The remainder identifies the position inside the final group.
Unary Coding: Expensive but Useful in the Right Place
Unary coding represents an integer using a run of one symbol followed by a terminator, such as:
0 → 0 1 → 10 2 → 110 3 → 1110 4 → 11110
By itself, unary coding is terrible for large numbers because length grows linearly with n.
But inside Golomb coding, the quotient is deliberately scaled by m. If m is chosen well, q stays small often enough that unary becomes efficient.
This is another recurring compression principle: a primitive method can become powerful when a transform first puts the data into a distribution the method likes.
Rice Coding: Golomb With Powers of Two
Rice coding is a special case of Golomb coding where m is a power of two:
m = 2^k
Now the remainder is simply the lowest k binary bits of n, and the quotient is what remains after shifting right by k bits.
This makes implementation extremely simple:
- shift to obtain the quotient;
- mask to obtain the remainder;
- encode quotient in unary;
- append k remainder bits.
Rice coding is therefore a beautiful example of trading a little modelling flexibility for very efficient machine operations.
Why Rice Codes Appear Around Prediction Residuals
Predictive compression often produces small residual magnitudes. If predictions are good, errors cluster around zero and large deviations become less common.
Map signed residuals into non-negative integers and a Golomb or Rice code can be a natural fit.
The pipeline becomes:
predict → compute residual → map sign → integer code
The better the predictor, the more often the integer coder sees small values.
Signed Integers Need a Mapping
Many universal codes are naturally defined for positive or non-negative integers.
Prediction errors can be negative.
A common trick is to interleave signs:
0 → 0 -1 → 1 +1 → 2 -2 → 3 +2 → 4 ...
Now small magnitudes map to small non-negative integers, preserving the distribution that makes variable-length coding useful.
Variable-Length Integers in Real Software
Many practical systems use byte-oriented variable-length integers rather than bit-oriented Elias or Golomb codes.
A common design stores seven payload bits in each byte and reserves one continuation bit indicating whether another byte follows.
Small integers fit in one byte. Larger values spill into two, three or more.
This may be less bit-efficient than a specialised universal code, but it aligns beautifully with byte-addressed computers and simple decoders.
Engineering often chooses the code that is cheapest for the whole machine, not the one that wins by a fraction of a bit in isolation.
The Continuation-Bit Pattern
Imagine each byte carries seven bits of integer payload and one flag:
0xxxxxxx → last byte 1xxxxxxx → more bytes follow
The decoder keeps reading until it encounters the terminating byte.
This is self-delimiting at byte granularity.
Why Not Huffman-Code Every Integer?
You can Huffman-code a finite set of integer symbols if their probabilities are known.
But what if integers have no practical fixed maximum, or the support is enormous?
A universal integer code provides a direct codeword for any positive integer without building a gigantic alphabet-specific tree.
The price is that it cannot be perfectly tailored to every possible source distribution.
Why Not Arithmetic-Code the Integer Distribution?
You can do that too.
If you have a good probability model over integer values, arithmetic coding or ANS can convert those probabilities into efficient code lengths.
Universal integer codes are attractive when you want a simple self-contained representation without maintaining a large explicit probability table.
Again, the right answer depends on system architecture.
Every Compression Format Has Hidden Integers
Once you start looking, integer coding appears everywhere:
- run lengths;
- dictionary match lengths;
- dictionary distances;
- block sizes;
- table sizes;
- symbol counts;
- number of records;
- restart intervals;
- indexes;
- timestamps and deltas;
- metadata lengths;
- model parameters.
A compressor can have an excellent core model and still waste space if these structural integers are encoded carelessly.
Counts Are Often More Predictable Than Raw Data
A run of repeated pixels may have unpredictable colour but a highly predictable run length. A document’s literal bytes may be complex while its paragraph lengths follow a narrow distribution. Match distances in a dictionary compressor may cluster strongly near zero.
Integer side channels can therefore have their own statistical structure.
Compressing the payload while leaving the structural numbers raw can leave substantial savings unused.
The Parameter Is a Bet About the Tail
Golomb and Rice codes include a parameter that controls the balance between unary quotient length and binary remainder length.
Choose the parameter too small and medium values create long unary quotients. Choose it too large and the fixed remainder wastes bits on tiny values.
Parameter selection is therefore a model of the integer distribution.
Adaptive codecs can change the parameter by block or over time as the distribution shifts.
Universal Does Not Mean Optimal for Every Integer
The word “universal” again needs discipline.
A universal integer code is designed to represent every positive integer with a self-delimiting code and to behave well over broad families or under particular asymptotic criteria.
It does not mean the code is shortest for every individual integer or every source distribution.
If you know the source is uniform over 0 to 255, eight fixed bits may be exactly right. If the source is geometric, Golomb may be better. If the source distribution is known precisely, entropy coding may win.
Compression remains model-relative.
Integer Coding and Boundaries
Self-delimiting codes solve one boundary problem while creating another trade-off.
Variable lengths improve average size but can make random access harder. To find the thousandth integer, a decoder may need to scan earlier variable-length fields unless an index provides offsets.
Fixed-width arrays are wasteful but directly addressable. Variable-length streams are compact but sequential.
Locality and compression pull against each other again.
Integer Coding and Error Propagation
If one bit is corrupted in a self-delimiting stream, the decoder may misread a boundary and interpret later bits incorrectly.
Some formats therefore place variable-length integers inside framed blocks with checksums or restart points.
Useful redundancy returns to protect compact metadata.
Database Compression Uses Integer Codes Everywhere
Sorted integer columns often have small differences between adjacent values.
Instead of storing absolute values, databases may store deltas. Those deltas are usually small and can be packed into narrower widths or variable-length representations.
Sometimes groups of deltas share one bit width. Sometimes exceptions are handled separately. Sometimes FOR—frame of reference—subtracts a base so every value becomes smaller.
Again the sequence is familiar:
transform large integers into small residual integers → encode small integers cheaply
Posting Lists and Search Engines
A search engine stores lists of document identifiers containing a term. The IDs may be large, but sorted IDs have positive gaps.
If documents containing the same term are relatively close in ID space, those gaps can be much smaller than the absolute identifiers.
Gap encoding plus variable-length integer codes can therefore reduce index size significantly.
The search engine is not really compressing document IDs. It is compressing distances between them.
Human Language Does This Too
We rarely say, “Repeat this sentence one hundred and twenty-three times” by writing the sentence 123 times.
We compress repetition into a count.
Then language compresses the count further because “three” is shorter and more common than “three hundred and seventy-four thousand, nine hundred and twelve”.
Magnitude influences verbal length.
Education: Small Numbers Deserve Small Representations
A student often writes 1, 2, 3, 4, 5 far more often than 3,847,291 in ordinary school work.
Our numeral system already reflects a variable-length principle: larger magnitudes require more digits.
Binary works similarly. Small integers need fewer significant bits.
Universal integer codes simply add self-delimitation so a sequence of variable-length binary numbers can be decoded unambiguously.
Primary School: Why Does 7 Need Fewer Digits Than 7,000,000?
Ask pupils why ordinary decimal notation gives small numbers short written forms and larger numbers longer ones.
Then show that a fixed seven-digit field would write 7 as 0000007.
Which is easier to read? Which wastes space?
The intuition behind variable-length integer coding is already familiar.
Secondary School: Build a Self-Delimiting Number Code
Ask students to invent a binary code for all positive integers where the decoder can tell when one integer ends without separators.
They will quickly discover the hard part: a variable-length code needs boundary information.
Then introduce Elias gamma coding as one elegant solution.
JC and Beyond: Integer Distributions Become Source Models
At higher levels, universal integer coding connects source coding, heavy-tailed distributions, geometric models, prefix-free codes and asymptotic redundancy.
Golomb codes are especially important because they are optimal for certain geometric distributions under suitable conditions. Rice codes trade some model granularity for bit-level implementation simplicity.
The deeper lesson is that integers are not merely metadata around compression. Their probability distribution is itself a source-coding problem.
A Universal-Integer-Code Checklist
- Are the integers bounded or effectively unbounded?
- How often are small values produced?
- What does the tail of the distribution look like?
- Must the code be self-delimiting?
- Would byte-oriented varints simplify implementation?
- Would Elias gamma or delta fit the distribution better?
- Would Golomb or Rice match geometric-like values?
- Can signed values be mapped to small non-negative magnitudes?
- How does variable length affect random access?
- What framing protects against boundary loss after corruption?
The Deeper Point
Compression is full of hidden numbers.
Runs become counts. Matches become lengths and distances. Blocks become sizes. Tables become frequencies. Indexes become offsets.
If those numbers are usually small, writing every one with a giant fixed-width field is like printing every house number on a billboard.
A small number deserves a small name—provided the decoder can still tell exactly where that name ends.