Skip to content
Tutorials Center
My learning

Topics

Lesson 58 of 63 ยท Projects

Project: Document Search with Ranking

Build a document search engine in Python: an inverted index, TF-IDF and BM25 ranking written by hand, and an honest evaluation with precision and MRR.

In Building a Small Search Engine you made a toy engine that ranked with TF-IDF. This project takes the next step toward how real engines work. You will build a reusable index class, add BM25, the ranking function behind Lucene, Elasticsearch and many other engines, and, most importantly, measure whether the results are any good. Search quality that is only "looks right to me" cannot be improved reliably.

Everything is plain Python with no search library, so each number in the ranking is something you can trace. The collection is 12 short documents about everyday topics, with five test queries whose relevant documents we decided in advance.

The plan

Build, rank, measure

Index Map each term to its documents.
Rank Score with TF-IDF and BM25.
Judge Compare with known relevant results.
Improve Change one thing, measure again.
1 / 2

Step 1: index the collection

Our index stores, for every term, a postings dictionary from document id to term frequency, plus the length of each document and the average length. Those numbers are all that TF-IDF and BM25 need. The analyzer lowercases, splits on letters, drops a handful of stop words and optionally applies a tiny stemmer; the same function processes documents and queries.

The first example builds the index and ranks with TF-IDF, using the same smoothed IDF as scikit-learn's TfidfVectorizer.

Python An index class with TF-IDF ranking

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The collection has 12 documents, 99 distinct terms and an average length of 10.1 terms after stop-word removal. The postings for coffee show the structure: documents 1, 5, 8 and 9 contain it, and document 1 contains it twice.

Look at the three queries critically. For coffee brewing, document 1 wins clearly (0.522) because it has coffee twice and also brewing; documents 8 and 5 follow. Both are relevant, but document 8 ("cold brew") only matches coffee, since brew and brewing are different terms. For mountain hiking the engine returns only documents 7 and 4, and misses document 10, the camping trip, whose text says mountains while the query says mountain. That is exactly the kind of failure that evaluation will quantify, and stemming will fix.

Step 2: BM25 by hand

BM25 (short for "Best Match 25") is TF-IDF's more careful relative. It has the same two ingredients, a term-frequency part and an IDF part, with two refinements:

  1. Saturation. In TF-IDF, ten mentions of a word count ten times as much as one. In BM25, extra mentions help less and less: the first mention matters most, and the score approaches a ceiling. A parameter k1 controls how fast (typical values are 1.2 to 2).
  2. Length normalization. A long document naturally contains more words, so its raw counts are inflated. A parameter b between 0 (ignore length) and 1 (fully normalize) controls how much to correct for length (typical value 0.75).

For one query term in one document the score is

idf ร— tf ร— (k1 + 1) / (tf + k1 ร— (1 โˆ’ b + b ร— doc_length / avg_length))

and the document's score is the sum over the query terms. The IDF used by BM25 is slightly different from the one in TF-IDF: log(1 + (N โˆ’ df + 0.5) / (df + 0.5)), which is never negative.

To see saturation without any collection at all, compute the term-frequency part for growing counts. This example is self-contained.

Python Saturation and length normalization

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the first table: one mention gives a weight of 1.00, ten mentions only 2.17 and twenty 2.33. Raw counting would give 10 and 20. No number of repetitions can pass the ceiling of k1 + 1 = 2.5. That is the defense against keyword stuffing and against long documents that repeat a word. The second table shows a short document earning more credit than a long one for the same count, and the third shows b turning length correction off (b=0) or fully on (b=1).

Step 3: evaluate against judged queries

Now the important part. For five queries we decided in advance which documents a human would call relevant:

Query Relevant documents
coffee brewing 1, 5, 8
tea 2, 12
baking bread 3, 11
mountain hiking 4, 7, 10
caffeine free drinks 12

We compare four engines on the same queries: TF-IDF and BM25, each with the plain analyzer and with a simple stemmer that maps baking, baked and bake to the same term. For every query we compute precision at 3, recall at 3 and the reciprocal rank of the first relevant result, then average over queries (mean reciprocal rank, MRR).

Python TF-IDF versus BM25, with and without stemming

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All four engines find nearly everything, which is normal for a 12-document collection, so look at the differences:

  • Stemming matters more than the ranking formula. With the plain analyzer both engines reach MRR 0.900 and recall at 3 of 0.933. Two things go wrong: mountains does not match mountain, so the camping trip (document 10) is never found for mountain hiking, and for baking bread the cookie recipe, the only document with the exact word baking, ranks first while the two bread documents (bake, baked) follow. With stemming, recall at 3 and MRR both reach 1.000.
  • TF-IDF and BM25 tie here. On a tiny collection of short, similar-length documents, saturation and length normalization have almost nothing to work on. BM25's advantages show up on large collections with documents of very different lengths, where TF-IDF lets long, repetitive documents dominate.
  • Precision at 3 is capped by the data. Two queries (tea, baking bread) have only two relevant documents, and caffeine free drinks returns a single result, so P@3 stays at 0.733 even though the rankings are as good as they can be. Compare engines on the same metric, rather than reading any single value as "73 percent good".

The per-query listing marks relevant results with + and irrelevant ones with -. The two minus signs are the composting guide (9) for tea and the cookie recipe (6) for baking bread: both contain the query words, but a human did not judge them relevant. Those false positives are the ones a better ranker (or synonyms and context) would have to demote.

Step 4: what the metrics hide

Metrics are a compass, not a map. Some honest remarks about this setup:

  • Five queries is a tiny test set. One query changing rank moves MRR a lot. Real evaluations use hundreds of queries, often collected from logs, and report averages with confidence intervals.
  • Judgments are opinions. We called document 9 (composting with tea leaves) not relevant to tea. Another judge might disagree, and different judgments change the scores. Real projects measure how much annotators agree (see Evaluation, Bias and Responsible NLP).
  • Precision at 3 punishes short answer lists. caffeine free drinks has one relevant document, so even a perfect engine can score at most 1/3 precision at 3 for that query. Choose k to match what users see.
  • Graded relevance is better. Mark documents as perfect, good or marginal and use a metric such as nDCG that rewards putting the best documents first. Binary labels are the simplest start.
  • Failure cases deserve a closer look. Print the ranking for a query that scored badly and read it. The cause is usually something fixable: a missing synonym, a stop word that mattered, or a stem that merged two meanings.

Step 5: a search function you can reuse

To finish the project, wrap the best engine in a function that a website or command-line tool could call. It should handle the awkward cases explicitly: empty queries, queries made only of stop words, and no matches. It should also return a short snippet around the first matching word so users can see why a result matched. The last example does that and checks its own behavior with a few assertions.

Python A reusable search function with snippets and tests

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The function handles the awkward inputs explicitly. An empty query and a query made only of stop words (the and of) return an empty list instead of crashing, and an unknown word (xylophone) returns no results. Case does not matter (COFFEE equals coffee), and brewing and brew find the same top document, which proves the same analyzer runs on both sides. Snippets show the context of the first match, so a user can see why a result appeared.

The assertions are a small regression suite. When you change the analyzer, the scoring or the stop-word list, run them again; for retrieval quality, rerun the judged queries from the previous step as well. This is the same discipline as in NLP in Production: never ship a ranking change you have not measured.

What real engines add

You now have the same architecture as Lucene and Elasticsearch in miniature. Production systems add:

  • Compressed, sorted postings and skip pointers so intersection and scoring touch as little memory as possible.
  • Fields and boosts (title matches count more than body matches, the idea behind BM25F).
  • Typo tolerance and prefix search, built from edit distance and character n-grams.
  • Better text analysis: real stemming or lemmatization, synonyms and language-specific rules.
  • Learned ranking that combines BM25 with other signals such as freshness and clicks.
  • Semantic retrieval with embeddings, often combined with BM25 in a hybrid system; see Retrieval and RAG.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does BM25's saturation parameter k1 control?

    With a small k1 extra mentions of a word quickly stop helping, and the weight approaches a ceiling of k1 + 1. Length correction is controlled by b.
  2. 2. What happens with b = 0 in BM25?

    b scales the length correction. At 0 the document length is ignored; at 1 the correction is full.
  3. 3. What does MRR (mean reciprocal rank) reward?

    Each query scores 1 divided by the rank of its first relevant result, so rank 1 gives 1.0, rank 2 gives 0.5, and so on; the scores are averaged over queries.
  4. 4. Why can precision at 3 never reach 1.0 for a query with a single relevant document?

    Precision at k divides the number of relevant results in the top k by k. With one relevant document the best possible value is 1/3.
  5. 5. Why must the same analyzer be applied to documents and queries?

    If documents are stemmed but queries are not, "baking" in a query would never match the stored stem. Both sides must produce the same terms.

Summary

  • An inverted index with term frequencies, document lengths and the average length is everything TF-IDF and BM25 need.
  • BM25 improves on TF-IDF with saturating term frequency (k1) and tunable length normalization (b).
  • Evaluate with judged queries and metrics such as precision at k, recall at k and MRR; change one thing at a time and measure.
  • Small test sets and subjective judgments limit what the numbers prove.
  • A reusable search function must handle empty queries, stop-word-only queries and no matches, and should explain results with snippets.

Next, summarize a document instead of searching a collection: Project: Extractive Text Summarizer.