Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Elias–Fano: split sorted IDs into low parts and high bits

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

Elias–Fano separates each strictly increasing integer into a fixed-width low part and a high part. The high parts are monotone; placing a one at high value plus element rank creates a bit sequence from which the high value can be recovered by select-one minus rank. The low parts retain the omitted bits. This lesson fixes a nonnegative universe bound and validates sorted, unique input before building the representation. It stores the high sequence as a Python list and also stores every one position for direct rank access. Those auxiliary positions make select constant time in this program but are extra machine-word storage, so its conceptual encoded-bit count is not a measurement of Python memory use. The structure is static. There is no insertion or deletion path.

Operational case

A maintenance feed has alert IDs 13, 19, 47, 61, 83, and 129 in a universe below 256. Value at rank three is 61 using zero-based rank; the first value at least 50 is also 61. The lower-bound operation binary-searches reconstructed values and returns no result above the final ID. Duplicate alert IDs are rejected because the lesson indexes a strictly increasing set rather than a multiset. A large universe with few IDs changes the chosen lower-bit width, so copying one hard-coded width into another feed would decode incorrect values. The conceptual bit count covers only low parts and the high bit sequence, not list objects or the select-position helper.

Working Python program

python
class EliasFanoAlertIds:
    def __init__(self, alert_ids, universe):
        if universe < 1 or any(not 0 <= alert_id < universe for alert_id in alert_ids):
            raise ValueError("alert ID outside universe")
        if any(left >= right for left, right in zip(alert_ids, alert_ids[1:])):
            raise ValueError("alert IDs must be strictly increasing")
        self.count = len(alert_ids)
        self.universe = universe
        ratio = max(1, universe // max(1, self.count))
        self.lower_width = ratio.bit_length() - 1
        mask = (1 << self.lower_width) - 1
        self.low_parts = [alert_id & mask for alert_id in alert_ids]
        high_capacity = ((universe - 1) >> self.lower_width) + self.count + 1
        self.high_bits = [0] * high_capacity
        self.one_positions = []
        for rank, alert_id in enumerate(alert_ids):
            position = (alert_id >> self.lower_width) + rank
            self.high_bits[position] = 1
            self.one_positions.append(position)

    def at(self, rank):
        if not 0 <= rank < self.count:
            raise IndexError("rank outside alert IDs")
        upper = self.one_positions[rank] - rank
        return (upper << self.lower_width) | self.low_parts[rank]

    def lower_bound(self, target):
        left, right = 0, self.count
        while left < right:
            middle = (left + right) // 2
            if self.at(middle) < target:
                left = middle + 1
            else:
                right = middle
        return self.at(left) if left < self.count else None

    def encoded_bit_count(self):
        return len(self.high_bits) + self.count * self.lower_width


alerts = EliasFanoAlertIds([13, 19, 47, 61, 83, 129], universe=256)
print("rank-3=", alerts.at(3), " next-50=", alerts.lower_bound(50),
      " conceptual-bits=", alerts.encoded_bit_count(), sep="")

Output

Output
rank-3=61 next-50=61 conceptual-bits=44

Time, space, and tradeoff

For N values in universe U, construction writes O(N + U / 2^L) conceptual high bits plus N low parts, where L is the selected lower width. At(rank) costs O(1) here because one positions are explicitly indexed. Lower bound costs O(log N) such accesses. The encoded representation has N times L low bits and about N + U / 2^L high bits; this Python model also stores O(N) integer references for select positions and unpacked bit/list elements. If a packed rank/select implementation replaces those helpers, its cost depends on that implementation. This structure is useful for immutable ordered IDs, not for a mutable incident queue.

Common Mistakes

  • Do not treat a conceptual bit count as measured Python heap use.
  • Do not accept unsorted or repeated values in a strict-ID index.
  • Do not forget to subtract rank from the selected high-bit position.
  • Do not claim insertions are supported by an immutable encoding.

Connected lessons

Compare its storage and lookup contract with Chunked integer sets: switch sparse arrays to dense bitmaps, Gap-encoded postings: add checkpoints to bytewise seeks, Level-order unary degree tries: encode child runs as bits, then run the index audit and contract quiz.

data structures
range-query-structures
Storage details