Milestone 2 of 11

Assign document ordinals and hand-check gaps

Map manifest-ordered document IDs to zero-based ordinals and prove that document and full-token position gaps round-trip exactly.

Gaps save repeated values only when the original order is explicit. Start with the document table and hand-check both kinds of reversible positional gap.

Goal

Assign zero-based document ordinals in corpus-manifest order, retain the full document-ID table, and derive reversible document and full-token position gaps.

Inputs

Use the validated source index and manifest. Document IDs are non-empty, unique strict UTF-8 strings and are never inferred from a later array row. For a term's strictly increasing document ordinals, the first gap is the first absolute ordinal; each later gap is the difference from the preceding ordinal. The first gap may be zero, while every later gap is positive.

For each posting, full-token positions are non-negative and strictly increasing. The first position gap is the first absolute position; later gaps are successive differences. The first gap may be zero, while later gaps are positive.

Deliverables

Implement src/gaps.py. Produce output/document_ordinals.csv with ordinal, document ID, manifest position, and identity. Produce output/gap_trace.csv with source values, prior values, gap kind, gap, and reconstructed value for each document and position sequence.

Checks

Hand-check empty and zero-term documents, zero and large first ordinals and positions, one and several postings, repeated terms across documents, and strictly increasing positions. Decode every gap cumulatively and prove the original ordinal and position sequences return exactly.

Reject duplicate or empty IDs, out-of-order IDs, negative values, non-increasing source ordinals or positions, an invalid later zero gap, and an ordinal outside the stored document table. Check that posting term counts equal decoded position counts and that the source index is unchanged.

Workspace

Keep ordinal assignment and gap conversion in src/gaps.py. Write only the ordinal and gap traces. Do not encode bytes or build the outer payload yet.

Hints

HintThe first gap is different

There is no previous value for the first document or position. Store its absolute value directly; only later gaps are differences.

HintDecode with an accumulator

Start from zero and add each gap. Check the reconstructed sequence against the source after every posting.

HintThe table is the boundary

A decoded ordinal is valid only when it addresses the stored document-ID table. Do not recover an ID from a row that happens to have the same number.

Review

Use a posting with first ordinal zero and another whose first ordinal is large. Which gaps may be zero, and why would making every gap positive lose valid source data?

How to check your work

Checks compare the ordinal table and gap trace with the tiny fixtures. The supplied fixture round-trips absolute values exactly and preserves the manifest's stable IDs.