Inverted Indexes and Lexical Retrieval
An inverted index maps each indexed term to the documents that contain it. It avoids scanning every document at query time and preserves the statistics needed by lexical scoring models.
Prerequisites
Understand relevance judgments, dictionaries, sets, and term counts.
Learning goals
- Make text analysis an explicit, versioned contract.
- Construct postings and document frequency without counting repeated terms twice.
- Explain the difference between candidate matching and scoring.
- Identify vocabulary mismatch and index-freshness failure modes.
Index contract
The fixture tokenizer lowercases text and extracts ASCII alphanumeric tokens with [a-z0-9]+. It performs no stemming, stop-word removal, synonym expansion, or language detection. That simple policy is reproducible, not universally correct. Changing it changes indexed terms, document frequency, matches, and therefore scores; reindexing and evaluation must travel together.
For term , document frequency is
Term frequency counts occurrences within a document. Document frequency counts a document at most once. A posting normally stores a document identifier plus frequency and, when phrase or highlighting behavior needs it, positions and offsets.
Worked example
This example indexes title and description together only to expose the basic structure. The next lesson keeps fields separate.
import csv
import re
from collections import defaultdict
with open("tests/fixtures/recommender-systems/search-catalog.csv", encoding="utf-8", newline="") as handle:
catalog = list(csv.DictReader(handle))
postings = defaultdict(dict)
for item in catalog:
tokens = re.findall(r"[a-z0-9]+", f"{item['title']} {item['description']}".lower())
for token in sorted(set(tokens)):
postings[token][item["item_id"]] = tokens.count(token)
print(f"documents={len(catalog)} vocabulary={len(postings)}")
print(f"search_df={len(postings['search'])} postings={sorted(postings['search'].items())}")
Expected output:
documents=8 vocabulary=64
search_df=4 postings=[('s3', 1), ('s4', 1), ('s6', 2), ('s8', 1)]
At query time, an OR retrieval can union postings; an AND retrieval can intersect them. That matching decision is separate from how candidates are scored. Always define empty-query behavior, tie-breaking, maximum candidate count, and whether filters run before or after lexical matching.
Limitations
- Exact tokens miss morphology, spelling variants, synonyms, and meaning expressed with different words.
- Aggressive normalization can merge distinct concepts or damage identifiers.
- A stale index can return deleted, unavailable, or policy-ineligible items.
- Posting-list size affects latency; the toy example is not a benchmark or production storage design.
Practice
Add the query “ranked searches.” Decide whether stemming, lemmatization, or a synonym rule should connect it to the catalog, then document a counterexample where that rule would hurt precision.
Next steps
BM25 and field-aware scoring uses term frequency, document frequency, and length normalization to order matches.
Primary sources
Checked 2026-10-17: Apache Lucene, search and scoring package documentation; Robertson and Zaragoza, The Probabilistic Relevance Framework: BM25 and Beyond.