Project 13

Compress and Rebuild an Inverted Index

Encode a small positional inverted index as a bounded binary artifact, rebuild it exactly, and prove that its search behaviour has not changed.

  • 11 milestones
  • Optional
  • Browser workspace

Project question: Can you encode a complete positional inverted index in a versioned binary file, rebuild every posting exactly, and prove that its search behavior has not changed?

What makes this a project

An index format is a contract among identities, bytes, and decoded records. In this project you will assign stable document ordinals, encode reversible gaps, write one canonical integer stream, store strict UTF-8 dictionary records, and wrap the payload in a bounded container. You will then parse it defensively, rebuild the source index, compare its structure and search behavior, and measure the representations with their denominators visible.

This is one inspectable lossless representation. It does not claim to define an optimal or production-ready search-index format. A measured byte ratio on the supplied fixture is evidence about that fixture, not a promise about all data or hardware.

You will produce:

  • checked corpus, tokenizer, index, query, and configuration identities;
  • document ordinals, reversible document and position gaps, and trace rows;
  • a canonical variable-byte integer stream and strict UTF-8 payload records;
  • a bounded index.bin container with defensive decoding and a rebuilt index;
  • separate structural and search-behavior equivalence evidence;
  • controlled numerical size accounting and exact plot data;
  • malformed-stream results, serialized artifacts, read-back, and a separate replay; and
  • an evidence-limited compressed-index card.

What you should know first

The project follows the Python path through Chapter 13. You should be able to preserve ordered records and stable IDs, calculate reversible differences, distinguish text from bytes, apply a supplied integer-byte rule, read and write binary files, validate bounded records, serialize artifacts, and replay a deterministic workflow. TEXT-04 is useful but optional. The project restates its complete rules, so do not invent a different codec or file format.

Supplied inputs

Use the accepted TEXT-04 corpus, tokenizer identity, document manifest, complete positional inverted index, queries, and expected search artifacts, or a version-matched fallback. Also use plans/compression_config.json, tiny hand-check tables and byte groups, complete containers, decoded indexes, expected search results, and deliberately malformed byte fixtures.

Every source artifact retains corpus, tokenizer, index, query, and configuration identity. Encoding must not change token selection, term spelling, document order, positions, scoring, ranking, result limits, or excerpt rules.

The project workspace

project/
  README.md
  data/                              # supplied, read only
  plans/compression_config.json      # supplied starting config
  src/config.py                      # reader implementation
  src/gaps.py                        # reader implementation
  src/varint.py                      # reader implementation
  src/payload.py                      # reader implementation
  src/container.py                   # reader implementation
  src/rebuild.py                     # reader implementation
  src/equivalence.py                 # reader implementation
  src/measure.py                     # reader implementation
  src/report.py                      # reader implementation
  src/main.py                        # reader implementation
  output/                            # generated artifacts
  tests/public_cases.py              # supplied, read only

Keep one continuous workspace through every milestone. Gap conversion, integer-stream coding, payload writing, bounded parsing, container validation, reconstruction, structural comparison, search replay, and size accounting should remain independently inspectable.

Project milestones

Work through these in order. Each milestone produces evidence used by the next one, while project completion remains separate from lesson progress.

  1. 1Verify source-index identities, configuration, and bounds

    Check exact source identities, positional-index structure, query compatibility, format versions, and positive non-boolean parser bounds.

  2. 2Assign 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.

  3. 3Build the canonical integer stream

    Implement the published shortest variable-byte representation and an offset decoder that rejects truncation, overflow, and non-canonical forms.

  4. 4Encode document and term records

    Write bounded length-prefixed UTF-8 document IDs and lexical term records while retaining byte offsets and exact text identity.

  5. 5Encode complete positional postings

    Encode every posting count, document-ordinal gap, position count, and full-token position gap with traceable offsets and groups.

  6. 6Parse defensively and rebuild the index

    Check bounds before iteration or slicing, consume the payload exactly, reject malformed streams, and recover all positional records.

  7. 7Wrap and validate the binary container

    Add the LMP magic, accepted version, and big-endian payload length, then reject malformed outer containers in a defined order.

  8. 8Prove structural index equivalence

    Rebuild exact document and posting structures and compare deterministic serializations with first-mismatch evidence.

  9. 9Prove search-behaviour equivalence

    Replay the same exact-term searches against both indexes and compare query analysis, scores, ranks, truncation, and excerpts field by field.

  10. 10Measure, save, reload, and replay the evidence

    Separate controlled posting-value measurements from representation sizes, save every artifact, read it back, and reproduce it in a fresh replay tree.

  11. 11Write and audit the compressed-index card

    State the byte rules, bounds, equivalence tests, measurement denominators, malformed evidence, replay result, and limits of the claim.

Required evidence

Save versioned compression configuration and corpus/tokenizer/index/query identity; document_ordinals.csv, gap_trace.csv, and varint_trace.csv; canonical index.bin and its SHA-256 digest; payload_layout.jsonl with ordered fields, offsets, lengths, and source identities; rebuilt_inverted_index.json and an exact structural comparison record; source-versus-rebuilt query analysis, contribution, ranking, and excerpt comparison records; size_accounting.csv and figures from exact saved plot data; malformed-stream results; compressed_index_manifest.json; read-back checks; a separate replay agreement or first-mismatch record; and project-root report.md.

Limits

This project does not teach dictionary compression, front coding, blocked dictionaries, Huffman, gamma, or delta codes, bit-level packing, skip pointers, compressed in-place query execution, query optimization, memory mapping, streaming or incremental updates, concurrency, encryption, checksums beyond artifact identity, recovery from corrupt input, production index formats, performance benchmarking, operating-system cache claims, web crawling, or retrieval-augmented generation. It does not claim that this format is optimal, universally smaller, or faster.

Review

The final review asks whether identities and ordering survive, every gap and integer is canonical, UTF-8 and bounds are checked before allocation, the payload and container are consumed exactly, structural and search equivalence are tested separately, size denominators are fair, malformed inputs are covered, replay is separate, and the card stays within measured evidence.