How Elias Delta Coding Compresses Large Integers

Elias delta coding is a universal compression algorithm designed to encode positive integers into variable-length bitstreams without requiring predefined boundaries. By applying Elias gamma coding directly to the bit-length of a target number rather than encoding that length in raw unary, Elias delta drastically reduces prefix overhead. This double-logarithmic approach provides significantly higher compression density for very large integers compared to standard binary or Elias gamma coding.

The Limitation of Elias Gamma on Large Integers

To store arbitrary-sized integers in standard binary without predefined byte boundaries, a decoder needs to know where each number ends. Elias gamma coding solves this by representing a positive integer \(x\) in two parts: 1. A prefix representing the number of bits in binary, encoded in unary (zeros followed by a single one). 2. A suffix containing the binary digits of \(x\) (omitting the leading most-significant bit, which is always 1).

The total bit length for Elias gamma is: \[\text{Bits}_{\gamma} = 2\lfloor\log_2 x\rfloor + 1\]

While Elias gamma is efficient for small numbers, its unary prefix grows linearly with the number of bits required by \(x\). For massive integers, dedicating \(\lfloor\log_2 x\rfloor\) bits purely to indicate length wastes considerable storage space.

The Elias Delta Mechanism

Elias delta coding improves efficiency by compressing the length descriptor itself. Instead of encoding the length of the binary string in unary, it recursively encodes the length using Elias gamma coding.

The encoding process follows three steps for an integer \(x\):

1. Calculate the Binary Length: Determine \(L = \lfloor\log_2 x\rfloor + 1\), which is the number of bits needed to represent \(x\) in standard binary.
2. Gamma-Encode the Length: Encode \(L\) using standard Elias gamma coding. This takes \(2\lfloor\log_2 L\rfloor + 1\) bits.
3. Append the Value Payload: Append the remaining \(\lfloor\log_2 x\rfloor\) bits of \(x\) (the standard binary representation of \(x\) excluding its leading 1).

Mathematical Efficiency and Density Gains

The total number of bits required to store an integer \(x\) under Elias delta coding is:

\[\text{Bits}_{\delta} = \lfloor\log_2 x\rfloor + 2\lfloor\log_2(\lfloor\log_2 x\rfloor + 1)\rfloor + 1\]

This introduces an asymptotic overhead of \(O(\log_2 \log_2 x)\), compared to the \(O(\log_2 x)\) overhead of Elias gamma coding.

• For \(x = 17\) (binary 10001): \(L = 5\). Gamma uses 9 bits; Delta uses 9 bits (no gain at small scales).
• For \(x = 1{,}000{,}000\) (approx. \(2^{20}\)): Gamma requires 39 bits (\(19 \text{ prefix} + 1 + 19 \text{ payload}\)), whereas Delta requires only 28 bits (\(8 \text{ gamma-length} + 19 \text{ payload} + 1\)).
• For \(x \approx 2^{1024}\): Gamma requires 2,047 bits, while Delta requires only 1,045 bits—nearly cutting the bit representation in half.

Summary of Compression Advantages

Elias delta coding achieves superior compression density for large integers by replacing the linear growth of the length prefix with a logarithmic growth rate. As integer values scale into millions and beyond, the overhead of the structural metadata becomes negligible relative to the actual payload, approaching the theoretical information-entropy limit of raw binary while remaining fully self-delimiting.