Elias Delta Encoding

The Elias Delta encoding is an entropy compression algorithm for encoding strictly positive integers ($ n \ge 1 $) in compact binary form.

It is a universal prefix code: no codeword is a prefix of another, allowing for unambiguous decoding without a separator.

It is designed to represent integers without knowing their probability distribution beforehand, using codewords whose length increases approximately as $ \log_2 n + 2\log_2\log_2 n $

The method involves two steps. First, the user calculates $ L = \lfloor \log_2 n \rfloor $, that is, the position of the most significant bit of $ n $.

The high part is defined as $ H = L + 1 $ (the binary length of $ n $), which is then encoded using Elias Gamma.

The low part corresponds to the $ L $ bits of $ n $ after removing the most significant bit.

The Delta code is the concatenation of Gamma($ H $) followed by these $ L $ bits.

Elias Gamma directly encodes $ n $, whereas Elias Delta first encodes the binary length of $ n $, which reduces overhead for large integers.

The length of the Gamma code is $ 2\lfloor \log_2 n \rfloor + 1 $

The length of the Delta code is $ \lfloor \log_2 n \rfloor + 2\lfloor \log_2(\lfloor \log_2 n \rfloor + 1) \rfloor + 1 $

Thus, when $ n $ becomes very large, the dominant term of Delta grows more slowly than that of Gamma, making it more efficient for wide-ranging and highly variable values.

Gamma remains simpler and is often preferable for small integers.

To decode, the user begins by decoding the Elias prefix Gamma, which yields $ H $ (the binary length of $ n $).

The user then sets $ L = H - 1 $. They then read the following $ L $ bits, which constitute the lower part. The integer is reconstructed by $ n = 2^L + \text{lower part} $.

The user may prefer Elias Delta for:

— index or gap compression in algorithms like LZ77;

— compact storage of identifiers or offsets in databases;

— transmission of packets containing large integers.

For very small integers (typically $ n \le 4 $), Elias Gamma or unary encoding may be more efficient.

If the distribution of integers is known and highly skewed, an adaptive encoding (e.g., Huffman or Golomb-Rice) will generally be superior.

If $ n = 2^k $, then $ L = k $ and the low part is $ 0 $. The Delta code is then simply Gamma($ k+1 $) followed by $ k $ zeros.

Elias Delta is defined only for strictly positive integers ($ n \ge 1 $), because calculating $ \lfloor \log_2 n \rfloor $ is impossible for $ n = 0 $

To include $ 0 $, the user can apply a systematic offset before encoding.

The simplest method is to encode $ n' = n + 1 $ with Elias Delta. Thus: $ n = 0 $ becomes $ n' = 1 $ and is encoded normally; $ n = 1 $ becomes $ n' = 2 $, and so on.

When decoding, the user applies the opposite operation: if Delta returns $ n' $, then the original integer is $ n = n' - 1 $

This transformation is bijective and does not alter the prefix properties of the code.

Elias Delta can only encode positive integers. To encode signed integers, the user first applies zigzag encoding, which transforms each relative integer $ x $ into a non-negative integer $ z(x) $ by alternating positives and negatives around zero.

The standard transformation is: $ z(x) = 2|x| $ if $ x < 0 $, $ z(x) = 2x + 1 $ if $ x \ge 0 $

This gives the correspondence: $ 0 \mapsto 1 $, $ -1 \mapsto 2 $, $ 1 \mapsto 3 $, $ -2 \mapsto 4 $, $ 2 \mapsto 5 $, etc.

The user then encodes $ z(x) $ with Elias Delta (possibly offset to include $ 0 $ if necessary). On decoding, the inverse operation reconstructs $ x $:

$ x = \lfloor z/2 \rfloor $ if $ z $ is even (original negative)

$ x = (z - 1)/2 $ if $ z $ is odd (original positive)

Zigzag is particularly suitable for Elias codes because it prevents small negative numbers from producing very large codes, by keeping values close to zero represented by small integers.