Answer multi-word queries with an inverted index
Continues from the last build: An engine that can only answer one term at a time, hash lookup for an exact term or trie prefix for autocomplete, with no way to combine multiple words in a single query.
Every query so far has been one word. Type 'python' and the hash index answers instantly, type 'pyth' and the trie autocompletes it.
What you'll build
A working inverted index (term to sorted postings) plus O(n+m) intersect/union/difference over postings lists, wired to a boolean query parser that answers multi-term AND/OR/NOT queries and short-circuits on empty postings, backed by a benchmark proving it beats a naive per-document scan as the corpus grows.
See how we teach, before you sign up
You don't just get code dumped on you. Every starter file and every solution is explained line-by-line, in plain English. Here's one real file from this project:
from __future__ import annotations
from collections import defaultdict
from dataclasses import dataclass, field
@dataclass
class Document:
doc_id: int
title: str
text: str
def tokenize(text: str) -> list[str]:
"""Lowercase, strip punctuation, split on whitespace. No stemming yet."""
cleaned = []
for ch in text.lower():
cleaned.append(ch if ch.isalnum() else " ")
return "".join(cleaned).split()
class InvertedIndex:
"""term -> sorted list of doc_ids that contain it (the postings list)."""
def __init__(self) -> None:
self.postings: dict[str, list[int]] = defaultdict(list)
self.documents: dict[int, Document] = {}
def add(self, doc: Document) -> None:
self.documents[doc.doc_id] = doc
seen_terms = set(tokenize(doc.text))
for term in seen_terms:
self.postings[term].append(doc.doc_id)
def build(self, docs: list[Document]) -> None:
for doc in docs:
self.add(doc)
# Keep every postings list sorted so two-pointer merges work.
for term in self.postings:
self.postings[term].sort()
def get(self, term: str) -> list[int]:
return self.postings.get(term.lower(), [])
Reading this file
self.postings: dict[str, list[int]] = defaultdict(list)The inverted index itself: term maps to a sorted list of doc ids, not the other way around.seen_terms = set(tokenize(doc.text))Dedupe terms per document first so one doc cannot append its own id twice to a postings list.self.postings[term].sort()Sorting once at build time is what makes the two-pointer merges in the next file O(n+m) instead of O(n*m).def get(self, term: str) -> list[int]:A single lookup is O(1) average, hash the term, hand back its postings. This is the rung-2 hash index, kept as the foundation.
Tokenizes documents and builds term -> sorted postings.
That's 1 of 7 explained code blocks in this single project.
The build, milestone by milestone
- 1
Build the inverted index: term to sorted postings
4 guided stepsRung 2's hash index answered 'does this exact title exist'. It cannot answer 'which documents contain the word python', because it never recorded WHICH documents contain WHICH words. The inverted index is that missing map: invert from doc-to-words into word-to-docs.
- 2
Implement postings-list set operations with two pointers
4 guided stepsA query like 'python AND fast' needs the doc ids that appear in BOTH postings lists. The naive way, checking every id in list a against every id in list b, is O(n*m). Because both lists are already sorted from milestone 1, two pointers can walk them once each and merge in O(n+m).
- 3
Parse and evaluate boolean multi-term queries
4 guided stepsThe set operations exist in isolation so far. A real search box takes one string. This milestone wires tokenized query text to the right sequence of intersect/union/difference calls, which is the actual feature: boolean multi-term search.
- 4
Keep ranking alive through set operations
4 guided stepsA bare list of doc ids answers 'which documents match' but throws away 'how well do they match'. Converting to Python sets for speed is the classic trap here: set operations are unordered and carry no payload, so the moment you cast postings to set() to intersect them, every score attached to a doc id is gone and the result order becomes arbitrary.
- 5
Benchmark it against a naive multi-term scan on growing input
4 guided stepsBig-O reasoning about O(n+m) merges only counts if a stopwatch backs it up. The naive baseline, for a two-term AND, scanning every document and checking whether both words appear in its text, is O(D * L) per query where D is the number of documents and L is average document length. That has to visibly fall behind as the corpus grows for this rung to have been worth building.
What's inside when you start
You'll walk away with
This is portfolio-grade. Build it free.
Sign up to unlock every milestone step-by-step, the code skeletons, full reference solutions, and checkable tasks, with your progress saved as you build.
Start building