How long is an Elias delta code?

For binary length L, it uses L + 2 floor(log2(L)) bits under this definition.

Does it require knowing the largest integer in advance?

No, although a practical implementation still has resource and integer-size limits.

Can it encode negative numbers?

Only after an explicitly defined mapping to positive integers; the basic code itself is for positive values.

AI Glossary / MLOps and deployment / Intermediate

Elias delta coding

Definition

Elias delta coding is a self-delimiting binary code for positive integers. It represents an integer by first encoding the length of its binary representation with an Elias gamma code, then appending the remaining binary digits. The decoder can determine where each integer ends without a separate fixed-width field for its size.

What it means

The code is useful when integer sizes vary and the maximum value is not fixed in advance. Small values receive shorter representations than very large values, although delta coding is not best for every probability distribution. Its name refers to a particular code introduced by Peter Elias. It is different from delta encoding, which represents differences between values. A system can first calculate differences and then apply Elias delta coding to suitable positive results.

How it works

Let n be a positive integer and let L = floor(log2(n)) + 1 be its binary length. Encode L using gamma coding, then append n's binary representation without its leading one. Under the leading-zero gamma convention used here, gamma coding a number of binary length k adds k−1 zeros before its full binary digits. The decoder first reads the gamma-coded length L, then reads L−1 further bits and restores the omitted leading one. Encoder and decoder must agree on this convention and any mapping for zero or signed values.

Three practical examples

A search-index experiment stores positive gaps between sorted document identifiers with a self-delimiting integer code.
A researcher compares gamma and delta codes on integer sequences with a wide range of magnitudes.
A teaching tool concatenates codes for several positive counts and demonstrates that a decoder can recover their boundaries without inserting a separator between each pair.

Think of it this way

Think of a parcel whose label first tells you how long its contents description is. Delta coding makes even that length label compact by encoding it with another code. The analogy explains the two-stage structure but not the exact bits: the real method uses binary lengths and an omitted leading one, and the bit convention must be specified precisely.

Worked example

Encode n = 13. Its binary representation is 1101, so L = 4. Gamma coding 4 under the stated convention produces 00100: two leading zeros followed by 100. Remove the leading one from 1101 to obtain 101. The delta code is therefore 00100 followed by 101, or 00100101, eight bits in total. Decoding 00100 recovers the length 4; reading three further bits, 101, and restoring the leading one recovers 1101 = 13. For n = 1, L = 1 and the code is simply 1. These examples are bit strings, not text files containing printed zeros and ones.

Illustrative case study

Fictional case: Spruce Search compares integer coders for a small experimental index. Most posting gaps are tiny, while a few are large. The team calculates code lengths on the actual gap histogram and finds that a method's advantage for large values does not establish its total advantage on this dataset. It also measures decoding speed and records how empty lists are represented. The fictional case illustrates evaluation criteria, without claiming a compression ratio or recommending delta coding for every production index.

Common misconceptions and mistakes

Do not confuse the name with subtracting successive values. Do not pass zero directly to the positive-integer definition; a format might map nonnegative x to x + 1, but it must document that choice. Delta coding is not always shorter than gamma coding for small integers. A prefix-free code also does not guarantee recovery after arbitrary bit corruption: an error can change the inferred length and misalign subsequent parsing. Framing and integrity checks remain separate design decisions.

Business use

For businesses, the concept is most relevant inside storage engines, indexes and specialist binary formats. Choosing an integer code affects storage, decoding speed and random-access design. Compare actual encoded bytes, including padding and indexing, rather than only asymptotic formulas. If the integer distribution is known and stable, a different code or block-packing approach may be more appropriate. Compatibility requires a written specification of conventions, mappings and termination rules.

Check your understanding

Why does the code for 13 append only 101 after its encoded length?

Answer: Knowing the binary length tells the decoder that the full representation begins with one. That leading one is therefore implicit and need not be transmitted again.

Related terms

Elias gamma coding
Elias omega coding
Delta encoding
universal integer code
prefix-free code
gap encoding
bit packing

Learn next

Encode 1, 2, 4, 13 and 32 using the stated delta convention, then concatenate and decode them. Compare their lengths with gamma and fixed-width alternatives. Weight those lengths by a realistic integer-frequency table to decide whether the method fits a particular workload.

Sources

Primary author-hosted teaching reference: Manning, Raghavan and Schütze, Introduction to Information Retrieval, gamma and delta code discussion, https://nlp.stanford.edu/IR-book/html/htmledition/gamma-codes-1.html ; 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. Examples explicitly use the leading-zero gamma convention.

Previous: Elementary matrix Next: Elias gamma coding