Elias-Fano Encoding for Integer Sequences

Elias-Fano encoding is a quasi-succinct data structure that compresses monotonically non-decreasing sequences of non-negative integers into a space close to the information-theoretic lower bound. By splitting each integer into its most significant (high) and least significant (low) binary bits, the technique achieves near-optimal compression while supporting constant-time random access and fast predecessor searches without full decompression.

The Mathematical Foundation

Consider a strictly increasing or non-decreasing sequence of \(n\) integers:

\[S = (x_0, x_1, x_2, \dots, x_{n-1})\]

where the maximum value is bounded by \(x_{n-1} \le U\).

The information-theoretic lower bound required to represent any subset of \(n\) elements from a universe of size \(U\) is:

\[\left\lceil \log_2 \binom{U}{n} \right\rceil \approx n \log_2\left(\frac{U}{n}\right) + n \log_2(e) \text{ bits}\]

Elias-Fano achieves a total size bounded by \(n \lceil \log_2(U / n) \rceil + 2n\) bits, which is less than half a byte per element away from the theoretical minimum.

Bit Splitting: Low Bits and High Bits

The encoding determines a split point \(l\) for the binary representation of each integer:

\[l = \max\left(0, \left\lfloor \log_2\left(\frac{U}{n}\right) \right\rfloor\right)\]

Every integer \(x_i\) in the sequence is partitioned into two components: 1. Low Bits (\(L_i\)): The lowest \(l\) bits, computed as \(x_i \bmod 2^l\). 2. High Bits (\(H_i\)): The remaining upper bits, computed as \(\lfloor x_i / 2^l \rfloor\).

Storing the Low Bits

The low bits of all \(n\) integers are concatenated directly into a uniform bit array. Because every low-bit representation has a fixed width of \(l\) bits, the sequence \(L = (L_0, L_1, \dots, L_{n-1})\) occupies exactly \(n \times l\) bits. Retrieving the low bits for the \(i\)-th element simply requires reading \(l\) consecutive bits starting at bit offset \(i \times l\).

Storing the High Bits

Since \(S\) is non-decreasing, the sequence of high bits \(H = (H_0, H_1, \dots, H_{n-1})\) is also non-decreasing and bounded by \(U / 2^l \approx n\). The high bits are encoded using a unary-like bitvector:

  1. Initialize an empty bitvector.
  2. For each unique bucket value \(k \in [0, \lfloor U / 2^l \rfloor]\), append a number of 1s equal to the frequency of \(k\) in \(H\).
  3. Append a 0 to signal the transition to \(k+1\).

This bitvector contains exactly \(n\) ones (one for each integer) and at most \(n\) zeros (one for each possible high-bit value), resulting in a length of at most \(2n\) bits.

Decoding and Fast Operations

To reconstruct any integer \(x_i\):

  1. Find the position of the \((i+1)\)-th 1 in the high-bit bitvector using a fast hardware-accelerated select_1(i) operation.
  2. The high-bit value \(H_i\) equals the number of 0s preceding this 1, calculated as \(\text{select}_1(i) - i\).
  3. Extract the \(l\) low bits starting at index \(i \times l\) from the low-bit array.
  4. Recombine the parts using binary arithmetic: \(x_i = (H_i \ll l) \ | \ L_i\).

Using auxiliary rank/select index structures that require negligible additional space (typically \(o(n)\) bits), both element lookups and predecessor queries operate in \(O(1)\) time.