Can gamma coding represent zero directly?

Not under the positive-integer definition; a mapping such as x to x + 1 can support nonnegative values.

Why is it self-delimiting?

The leading prefix determines how many remaining bits belong to the current integer.

Does it need a learned probability model?

No. Its codeword assignment is fixed by the integer value, although that does not make it optimal for every source.

AI Glossary / MLOps and deployment / Intermediate

Elias gamma coding

Definition

Elias gamma coding is a self-delimiting binary representation of positive integers. It combines a simple indication of an integer's binary length with the integer's binary digits. Smaller positive integers receive shorter codewords, and a decoder can recover successive values without an external separator between their codewords.

What it means

Many data structures contain positive counts or gaps of varying sizes. Using the same wide field for every value wastes space when most are small. Gamma coding offers a simple alternative without requiring a separately transmitted probability table. Its suitability still depends on the actual values. The basic code covers positive integers only; zero and negative numbers need a documented mapping. The term is unrelated to gamma correction in imaging or the gamma function in mathematics.

How it works

Under the leading-zero convention used here, write n in binary and count its digits L. Prefix those digits with L−1 zeros. To decode, count zeros until the first one; if there are k zeros, that one begins a binary number with k additional digits. Read them and recover n. The code length is 2 floor(log2(n)) + 1 bits. Another common presentation uses a different unary convention for the length, so implementations must agree on the precise bit representation rather than only saying “gamma code.”

Three practical examples

An introductory search engine stores positive differences between consecutive sorted document identifiers using compact integer codes.
A programmer serializes positive run lengths and compares gamma-coded payload size with fixed-width counters.
A compression class uses gamma codes to demonstrate prefix-free parsing before moving to more sophisticated integer or entropy coders.

Think of it this way

Think of a message that first tells you how many digits to expect, then provides the number. Gamma coding makes the announcement part of the bitstream so the next message can begin immediately afterward. The analogy should not suggest that this announcement is free: its cost grows with the binary length and can be substantial for large integers.

Worked example

Encode the values 1, 3 and 10. Their binary forms are 1, 11 and 1010. Adding zero prefixes of lengths 0, 1 and 3 gives 1, 011 and 0001010. The concatenated stream is 10110001010. A decoder first sees 1 and returns 1. Next it counts one zero, reads the following one plus one additional bit, and returns binary 11 = 3. Finally it counts three zeros and reads 1010, returning 10. The total payload is 1 + 3 + 7 = 11 bits, compared with 12 bits for three fixed four-bit fields. Framing, padding and the number of values can still add overhead.

Illustrative case study

Fictional case: Hazel Index tests gamma coding on posting-list gaps. Its demonstration dataset contains many gaps of one and two, making the code look attractive. A second collection has far larger gaps, so the team compares total size and query decoding time again. It records the zero-handling and list-termination conventions in the format description. This fictional case illustrates the need for representative distributions rather than claiming that gamma coding is the best general-purpose index format.

Common misconceptions and mistakes

Do not encode printed text characters “0” and “1” and expect the theoretical bit count: those characters occupy storage too. A bit-packed implementation is required to realize bit-level savings. Do not confuse prefix-free parsing with error correction or random access. A damaged prefix can misalign later values, and locating the thousandth value may require decoding earlier ones unless an index is present. Gamma coding also becomes relatively expensive for large integers because its unary length component grows linearly with binary length.

Business use

For businesses, gamma coding is usually an internal storage-format choice rather than a visible product feature. Evaluate it by actual encoded size, CPU cost, access patterns and compatibility. A small theoretical saving can be outweighed by padding, restart points or slower decoding. Compare against alternatives using the same input values and include the cost of any transformation that produces those values. Keep test cases for boundaries such as powers of two, where the code length increases.

Check your understanding

How many bits encode 8 under the leading-zero gamma convention?

Answer: Binary 8 is 1000, which has four digits. Three prefix zeros produce 0001000, a seven-bit codeword. The result agrees with 2 floor(log2(8)) + 1 = 7.

Related terms

Elias delta coding
Elias omega coding
Unary code
prefix-free code
gap encoding
universal integer code

Learn next

Build a table of gamma codes for integers 1 through 16 and check the transitions at 2, 4, 8 and 16. Concatenate several codes and decode them manually. Then calculate average length from a real frequency table rather than judging the method from one conveniently small number.

Sources

Primary author-hosted teaching references: Introduction to Information Retrieval, https://nlp.stanford.edu/IR-book/html/htmledition/gamma-codes-1.html ; alternative convention discussion, https://nlp.stanford.edu/IR-book/html/htmledition/references-and-further-reading-5.html . Source search excerpts consulted; full original-paper and editorial review remain pending. All worked bitstrings use the explicitly stated leading-zero convention.

Previous: Elias delta coding Next: Elias omega coding