Milestone 2 of 8

Build and hand-check a tiny inverted index

Map each exact text term to manifest-ordered document postings and strictly increasing full-token positions, then compare every count with a hand calculation.

Start with a corpus small enough to check with a pencil. The index is a set of records, not a magic lookup table.

Goal

Build postings for a few tiny documents, preserve every matching token position, and prove the posting and count invariants by hand.

Inputs

Use documents such as "red blue red", "blue green", and an empty document. Use the canonical tokenizer records, so positions include every scanned token even though only text tokens become terms. Preserve spelling and case. For each term, collect one posting per document that contains it.

Each posting contains:

document_id
term_count
positions

Positions are full token positions in strictly increasing order. The term count is the length of that position list.

Deliverables

Implement the small construction in src/index.py. Store terms in lexicographically increasing token-text order and postings in corpus-manifest document order. Produce a hand-check fixture and document statistics that also include the empty document.

Checks

For every posting, check term_count == len(positions). For every term, check that its posting count equals the number of documents containing it and that the sum of its posting term counts equals its corpus count. Check that the sum of all posting term counts equals the sum of document indexed lengths.

Use a repeated term, a shared term, a term present in one document, and a zero-term document. Check exact case, an underscore, a non-ASCII term, and punctuation around a term. Do not treat spaces, newlines, or punctuation as terms. Do not infer document identity from a row or array position.

Workspace

Keep the posting builder and invariant checks in src/index.py. Do not add query processing or ranking yet. Keep source token records unchanged.

Hints

HintCollect positions before sorting

Append a position to the posting where it occurs. Sort only the final term and document keys, not the positions you already recorded.

HintCount at two levels

A term's corpus count counts occurrences. Its posting count counts documents. They answer different questions.

Review

Choose one term and explain its complete posting list. Which invariant would fail first if one repeated occurrence were skipped? Which invariant would fail if the empty document were dropped from document statistics?

How to check your work

Checks compare term order, document order, positions, and totals with the tiny fixture. The index stores exact occurrences; it does not claim that a term's presence proves a document is relevant.