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

Gap-encoded postings: add checkpoints to bytewise seeks

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

A posting list contains strictly increasing document IDs. Subtracting the previous ID turns them into nonnegative gaps, and a seven-payload-bit byte code writes small gaps in fewer bytes than large ones. This program sets the high byte bit when another byte follows; a byte with that bit clear ends the integer. Every few postings it records the absolute document ID and byte offset immediately after its code. Seek-at-least binary-searches checkpoint IDs, starts after the greatest checkpoint no larger than the target, and decodes subsequent gaps until it finds a qualifying ID. The previous absolute ID is necessary because gaps cannot be interpreted independently. A checkpoint equal to the target answers directly. The list is immutable and stored as one bytearray plus Python checkpoint records.

Operational case

A term appears in documents 47, 61, 83, 129, and 515. Seeking at least 80 returns 83; seeking at least 200 returns 515. With a checkpoint every two postings, a seek may skip a prefix of the byte stream before decoding the short local tail. The encoded gaps occupy six bytes in this particular trace, excluding checkpoint tuples and the Python bytearray header. That number should not be generalized into a compression guarantee: widely spaced IDs take more bytes, and dense checkpoints can cost more than they save for small lists. The parser rejects a truncated integer rather than silently accepting a partial document ID.

Working Python program

python
from bisect import bisect_right


def encode_unsigned(value):
    if value < 0:
        raise ValueError("negative gap")
    encoded = bytearray()
    while value >= 128:
        encoded.append((value & 127) | 128)
        value >>= 7
    encoded.append(value)
    return encoded


def decode_unsigned(data, offset):
    value = 0
    shift = 0
    while offset < len(data):
        part = data[offset]
        offset += 1
        value |= (part & 127) << shift
        if not part & 128:
            return value, offset
        shift += 7
    raise ValueError("truncated integer code")


class GapPostingIndex:
    def __init__(self, document_ids, checkpoint_stride=3):
        if checkpoint_stride < 1 or any(document_id < 0 for document_id in document_ids):
            raise ValueError("invalid document ID or stride")
        if any(left >= right for left, right in zip(document_ids, document_ids[1:])):
            raise ValueError("document IDs must increase strictly")
        self.data = bytearray()
        self.checkpoints = []
        self.checkpoint_ids = []
        self.count = len(document_ids)
        previous = 0
        for position, document_id in enumerate(document_ids):
            self.data.extend(encode_unsigned(document_id - previous))
            previous = document_id
            if position % checkpoint_stride == 0:
                self.checkpoints.append((document_id, len(self.data)))
                self.checkpoint_ids.append(document_id)

    def values(self):
        result = []
        previous = 0
        offset = 0
        while offset < len(self.data):
            gap, offset = decode_unsigned(self.data, offset)
            previous += gap
            result.append(previous)
        return result

    def seek_at_least(self, target):
        checkpoint = bisect_right(self.checkpoint_ids, target) - 1
        if checkpoint >= 0:
            previous, offset = self.checkpoints[checkpoint]
            if previous == target:
                return previous
        else:
            previous, offset = 0, 0
        while offset < len(self.data):
            gap, offset = decode_unsigned(self.data, offset)
            previous += gap
            if previous >= target:
                return previous
        return None


postings = GapPostingIndex([47, 61, 83, 129, 515], checkpoint_stride=2)
print("seek-80=", postings.seek_at_least(80), " seek-200=", postings.seek_at_least(200),
      " bytes=", len(postings.data), sep="")

Output

Output
seek-80=83 seek-200=515 bytes=6

Time, space, and tradeoff

Encoding N document IDs costs O(T) time and T bytes for the emitted byte stream, plus O(N / S) checkpoints at stride S. Full iteration costs O(T + N). Seek-at-least costs O(log(N / S) + S * B) time in the worst local block, where B is the maximum encoded bytes in one scanned gap; for arbitrary-size Python integers B is not a fixed constant. Memory includes T bytes and checkpoint records, not just the byte count printed by the example. This implementation does not support in-place updates, phrase positions, term frequencies, or direct random access to posting rank without scanning from a checkpoint.

Common Mistakes

  • Do not decode a gap without the preceding absolute ID.
  • Do not forget that a checkpoint offset points after its encoded posting.
  • Do not count stream bytes as total index memory.
  • Do not accept a truncated variable-length integer as a complete posting.

Connected lessons

Compare its storage and lookup contract with Elias–Fano: split sorted IDs into low parts and high bits, Chunked integer sets: switch sparse arrays to dense bitmaps, Level-order unary degree tries: encode child runs as bits, then run the index audit and contract quiz.

Block-max postings: skip safe document-score regions adds a distinct structure contract to compare.

data structures
hash-tables
Storage details