The Inverted Index

Description

The previous lesson left you with a visible problem: naive_scan works, but every search re-reads the entire corpus, and there's no structure to hang a better weighting criterion on than "count matches." This lesson builds the piece that solves the first problem — no longer re-reading everything — and that's also the input that makes TF and IDF possible in the next lesson: the inverted index.

An inverted index is, at bottom, a single dictionary: every term in the vocabulary points to the list of chunks where it appears, along with how many times it appears in each one. You're going to build it with collections.Counter and a dict, run it over Reservo's corpus's 57 chunks, and inspect its postings (the per-term chunk lists) for a handful of key words. By the end of the lesson you'll have the exact structure TF, IDF, and BM25 get computed on for the rest of the module.

Connection to the module

This is the module's "data structure" lesson: lesson 02 showed you the problem, this one builds the solution to the "stop re-reading everything" part, and lessons 04-05 build the weighting criterion on top of this same structure. The inverted index you assemble here doesn't change shape for the rest of the module — what changes is which calculation you apply on top of it.

Analogy: the topic index, from the inside

In lesson 01 we compared a retrieval index to the topic index at the back of a book. Now look at how that index is built on the inside: it isn't a list of pages with the words they contain (that would be, again, scanning); it's exactly the reverse — a list of words, and for each one, the pages where it shows up. That's why it's called inverted: it inverts the "page → words it contains" relationship into "word → pages that contain it."

NORMAL index (what you already had):
  chunk_1 → {the, focus, room, equipment, includes, ...}
  chunk_2 → {the, studio, room, seats, four, ...}
  ...

INVERTED index (what this lesson builds):
  "focus"     → [chunk_1, ...]
  "equipment" → [chunk_1, chunk_15, chunk_37, ...]
  "room"      → [chunk_1, chunk_2, chunk_4, ...]
  ...

With the inverted index, answering "which chunks does 'equipment' show up in?" is a single dictionary lookup — inverted["equipment"] — instead of going through all 57 chunks asking one by one. That's the structural gain; the weighting criterion (TF/IDF/BM25) comes afterward, computed on this same structure.

Worked example: building and inspecting the inverted index

The tokenizer is the same one from the previous lesson — lowercase, split into sequences of letters/digits, with no common-word removal (the reason for not filtering them out is explained in lesson 04):

import re
from collections import Counter, defaultdict

_TOKEN_RE = re.compile(r"[a-z0-9]+")


def tokenize(text):
    return _TOKEN_RE.findall(text.lower())


def build_inverted_index(chunks):
    """term -> sorted list of (chunk_id, term_freq_in_that_chunk).
    Also returns, per chunk: its counted terms (Counter) and its
    length in tokens -- both needed for TF/IDF/BM25 later on."""
    inverted = defaultdict(list)
    chunk_tokens = {}
    doc_len = {}
    for chunk in chunks:
        tokens = tokenize(chunk.text)
        counts = Counter(tokens)
        chunk_tokens[chunk.chunk_id] = counts
        doc_len[chunk.chunk_id] = len(tokens)
        for term, freq in counts.items():
            inverted[term].append((chunk.chunk_id, freq))
    for postings in inverted.values():
        postings.sort()  # deterministic order, by chunk_id
    return dict(inverted), chunk_tokens, doc_len

Three structures come out of a single pass over the corpus: the inverted index itself (inverted), how many times each term shows up inside each chunk (chunk_tokens, a Counter per chunk), and how many tokens each chunk has in total (doc_len). All three are necessary — the inverted index so you don't re-read everything, and the other two for the relevance calculation coming in lessons 04 and 05.

Let's run it over the complete corpus:

chunks = build_corpus()
inverted, chunk_tokens, doc_len = build_inverted_index(chunks)

print("chunks indexed:", len(chunks))
print("vocabulary size:", len(inverted))
print()

for term in ["wifi", "refund", "boardroom", "discount"]:
    postings = inverted.get(term, [])
    print(f"'{term}' -> {len(postings)} chunks: {postings}")

What to expect:

chunks indexed: 57
vocabulary size: 509

'wifi' -> 8 chunks: [('boardroom-room-manual-002', 2), ('focus-room-manual-002', 2), ('lounge-room-manual-002', 2), ('operations-manual-raw-003', 1), ('phonebooth-room-manual-002', 2), ('studio-room-manual-002', 2), ('wifi-and-equipment-faq-000', 1), ('wifi-and-equipment-faq-003', 1)]
'refund' -> 4 chunks: [('cancellation-policy-003', 1), ('no-show-policy-001', 1), ('refund-policy-000', 1), ('refund-policy-003', 1)]
'boardroom' -> 8 chunks: [('boardroom-room-manual-000', 1), ('boardroom-room-manual-004', 1), ('lounge-room-manual-004', 1), ('operations-manual-raw-001', 1), ('operations-manual-raw-002', 1), ('phonebooth-room-manual-004', 1), ('studio-room-manual-000', 1), ('wifi-and-equipment-faq-000', 1)]
'discount' -> 9 chunks: [('boardroom-room-manual-003', 1), ('cancellation-policy-001', 1), ('focus-room-manual-003', 1), ('lounge-room-manual-003', 1), ('membership-tiers-faq-000', 1), ('membership-tiers-faq-001', 2), ('membership-tiers-faq-002', 1), ('phonebooth-room-manual-003', 1), ('studio-room-manual-003', 1)]

509 distinct terms, from 57 chunks — that's Reservo's corpus's complete vocabulary. Look at "discount"'s postings: it shows up in 9 different chunks, and in membership-tiers-faq-001 it appears twice (that's the membership FAQ's "How Much Discount Does the Pro Tier Get?" section) while everywhere else it appears once each. That frequency difference — 2 against 1 — is exactly what the next lesson turns into a relevance signal (term frequency). Also look at "boardroom": it shows up in 8 chunks, but none of them is cancellation-policy — the real cancellation policy document (Module 1) never mentions the Boardroom room by name; the ones that do are lounge-room-manual-004, in its House Rules ("...unlike Focus, Phonebooth, and Boardroom"), along with studio-room-manual-000 ("It sits between Focus and Boardroom...") and the operations manual, which names it twice for its access code and its cleaning. This is the first, executed hint of something lesson 07 is going to confirm with a full query: the corpus's real vocabulary doesn't always match what you'd assume from the document table.

A useful edge case: the word "a"

Compare the postings of a content word against a function word:

print("postings for 'a':", len(inverted.get("a", [])), "chunks out of", len(chunks))
print("postings for 'reimbursement':", inverted.get("reimbursement", []))

What to expect:

postings for 'a': 37 chunks out of 57
postings for 'reimbursement': []

"a" shows up in 37 of the 57 chunks — almost two-thirds of the corpus. As a search term, it barely discriminates anything: knowing a chunk contains "a" tells you almost nothing about its topic. At the opposite end, "reimbursement" shows up in zero chunks — the inverted index doesn't even have that key. Keep this second fact in mind: it's exactly the term lesson 06 uses to demonstrate, executed, BM25's lexical limit.

Why this is faster than naive_scan

naive_scan (lesson 02) walks all 57 complete chunks for every search, no matter how many terms the query has. With the inverted index, finding candidate chunks for an N-term query costs N dictionary lookups — one per term — plus walking only those terms' postings lists, which are typically much smaller than the whole corpus:

naive_scan:          checks all 57 chunks, for ANY query
with inverted index:  checks only len(postings["wifi"]) + len(postings["lounge"]) + ...
                       = 9 + a few more, instead of 57

With 57 chunks the difference is cosmetic — but in a real corpus of thousands or millions of chunks, the difference between "checking everything" and "checking only the query terms' postings lists" is the difference between a system that responds in milliseconds and one that doesn't respond in a reasonable time at all. The structure doesn't change with the corpus's size; what changes is how much it matters.

Common mistakes

1. Forgetting the inverted index stores frequency, not just presence. inverted["boardroom"] isn't just the list of chunks where it appears — it's a list of (chunk_id, frequency) pairs. If you only store presence/absence, you lose exactly the signal that tells "a word mentioned in passing" apart from "a chunk mainly about that topic."

2. Building an inverted index per document instead of per chunk. This guide indexes at the chunk level (57 entries), not the document level (13 entries) — because what search is going to return is chunks, not whole documents. If you aggregate by document, you lose the granularity that makes citing the exact source useful later.

3. Not initializing doc_len and chunk_tokens in the same pass as inverted. All three structures get computed from the same tokenization of each chunk — computing them separately means tokenizing each chunk more than once, and risking a tokenizer change ending up applied to one structure but not the other.

4. Assuming a 509-term vocabulary is "small" and optimizing doesn't matter. With this toy corpus, any approach runs fast. This lesson's point isn't speed over 57 chunks — it's the correct structure, the same one a system with millions of chunks needs, unchanged in shape.

5. Thinking the inverted index, on its own, is already a relevance criterion. It isn't — it's the structure that makes computing relevance quickly possible. inverted["boardroom"] tells you which 6 chunks the word shows up in, but it doesn't yet tell you which of those 6 is most relevant to a complete query — or whether those 6 are really about Boardroom, or just mention it in passing. That's TF/IDF/BM25, lessons 04 and 05.

Exercises

Exercise 1: Inspect the postings for "cancel" vs "cancellation" (Easy)

Without running anything first, predict: are "cancel" and "cancellation" going to share the same postings in the inverted index, or are they separate entries? Then run the index and confirm.

chunks = build_corpus()
inverted, chunk_tokens, doc_len = build_inverted_index(chunks)

print("cancel:", inverted.get("cancel", []))
print("cancellation:", inverted.get("cancellation", []))

cancel: [('cancellation-policy-000', 1)]
cancellation: [('cancellation-policy-002', 1), ('cancellation-policy-003', 1), ('membership-tiers-faq-000', 2), ('membership-tiers-faq-002', 1), ('no-show-policy-000', 2), ('no-show-policy-001', 1), ('payment-methods-faq-000', 1), ('refund-policy-000', 1), ('refund-policy-001', 1), ('refund-policy-002', 1), ('refund-policy-003', 1)]

Exercise 2: Build the index over a subset (Medium)

Build the inverted index using only the chunks with doc_id "focus-room-manual", "studio-room-manual", and "boardroom-room-manual" (the three smallest room manuals). Report the resulting vocabulary size and the postings for the word "room".

chunks = build_corpus()
subset = [c for c in chunks if c.doc_id in
          {"focus-room-manual", "studio-room-manual", "boardroom-room-manual"}]
print("chunks in the subset:", len(subset))

inverted, chunk_tokens, doc_len = build_inverted_index(subset)
print("subset vocabulary:", len(inverted))
print("postings for 'room':", inverted.get("room", []))

chunks in the subset: 15
subset vocabulary: 179
postings for 'room': [('boardroom-room-manual-000', 2), ('boardroom-room-manual-001', 1), ('boardroom-room-manual-004', 1), ('focus-room-manual-000', 2), ('focus-room-manual-001', 1), ('focus-room-manual-004', 1), ('studio-room-manual-000', 1), ('studio-room-manual-001', 1)]

Exercise 3: Find the corpus's most frequent term (Hard)

Without using any library outside the stdlib, write code that walks Reservo's corpus's complete inverted index and finds: (a) the term that appears in the most distinct chunks (highest len(postings)), and (b) the (chunk_id, term) pair with the highest frequency within a single chunk. Run it and report both.

chunks = build_corpus()
inverted, chunk_tokens, doc_len = build_inverted_index(chunks)

# (a) term in the most distinct chunks
most_common_term = max(inverted.items(), key=lambda pair: len(pair[1]))
print(f"term in the most chunks: '{most_common_term[0]}' in {len(most_common_term[1])} chunks")

# (b) highest frequency within a single chunk
best = None
for term, postings in inverted.items():
    for chunk_id, freq in postings:
        if best is None or freq > best[2]:
            best = (chunk_id, term, freq)
print(f"highest frequency in a single chunk: {best[1]!r} appears {best[2]} times in {best[0]}")

term in the most chunks: 'the' in 50 chunks
highest frequency in a single chunk: 'a' appears 6 times in refund-policy-000

Summary and next step

• The inverted index is a term → (chunk_id, frequency) list dictionary — the structure that avoids re-reading the entire corpus on every search.
• We built it with collections.Counter and defaultdict, in a single pass over Reservo's corpus's 57 chunks: 509 vocabulary terms, with postings ranging from "reimbursement" (0 chunks) to "the" (50 chunks).
• The index gets computed at the chunk level, not the document level — because search is going to return chunks with their exact citation, not whole documents.
• The inverted index solves the "don't re-read everything" problem; it does not yet solve the weighting problem (which of the chunks containing a term is the most relevant?) — that's exactly what TF and IDF build in the next lesson, computed on this same structure.

Next lesson: 04 — Term frequency and IDF. We turn the postings lists into a real relevance criterion: how much a term repeats inside a chunk, and how rare it is across the whole corpus — by hand, and verified with a numpy matrix.

Additional resources

1. Python — collections.defaultdict — The structure that simplifies building the inverted index without manually checking whether a key already exists.
2. Python — collections.Counter — The per-chunk term count that feeds both the inverted index and TF/BM25.
3. Manning, Raghavan & Schütze — Introduction to Information Retrieval, ch. 1: "Boolean retrieval" — The standard academic reference for the inverted index structure this lesson implements.
4. Python 3.14 — What's New — The version all of this module's code runs on.