· 2 min read
Building a BM25 search engine from scratch
What I learned by implementing indexing, BM25 ranking, and retrieval evaluation in plain Python.
Loading post…
· 2 min read
What I learned by implementing indexing, BM25 ranking, and retrieval evaluation in plain Python.
Loading post…
BM25 is a good reminder that useful search does not have to begin with a large model. For a university information-retrieval project, I built a small search engine in plain Python: it reads a document collection, creates an index, ranks queries, and evaluates the results against relevance judgments.
The code is available in the project repository.
BM25 scores a document by combining three useful ideas:
A common form is:
Here, is the frequency of query term in document , is the document length, and is the collection's average document length. The project uses and .
The implementation uses the Robertson–Spärck Jones form of inverse document frequency:
When a term appears in more than half of the collection, that expression can be negative. My query path clamps those contributions to zero. Today I would probably use the always-positive BM25 IDF variant instead, but the choice is explicit in the code and worth understanding.
flowchart TD A[Documents] --> B[Tokenize] B --> C[Remove stop words] C --> D[Porter stemming] D --> E[Term frequencies and document lengths] E --> F[Precomputed BM25 postings] F --> G[index.json] G --> H[Rank queries]
The indexer lowercases and tokenizes each document, removes stop words, and applies a Porter stemmer. It records term frequencies, document frequencies, and document lengths before calculating a BM25 contribution for every term-document pair.
Those contributions are written to index.json. At query time, the engine performs
the same text normalization, finds each term's postings, adds their stored scores,
and sorts the documents. Manual searches return the top 15 results.
Precomputing the scores made queries quick, but it moved work and storage into the index. The large index was 211 MB as JSON. A simple ID mapping reduced it to 155 MB, although encoding and decoding made startup slower. A production version would use a compact binary postings format and store the statistics needed to change ranking parameters without rebuilding everything.
The project implements Precision, Recall, Precision@10, R-Precision, mean average precision, bpref, and NDCG. On the supplied large corpus, the recorded run produced:
| Metric | Score |
|---|---|
| Precision@10 | 0.583 |
| R-Precision | 0.530 |
| MAP | 0.555 |
| NDCG | 0.556 |
| Recall | 0.896 |
These numbers are tied to that corpus, its relevance judgments, and the project's result cutoff. They are useful for comparing changes inside the same experiment, not as a general BM25 benchmark.
The formula is the small part. Most of the work sits around it: consistent text processing, an index that can be loaded efficiently, sensible result cutoffs, and an evaluation loop that catches regressions. That is still true in modern search stacks, even when BM25 becomes the lexical half of a hybrid retrieval system.
For the theory behind the ranking function, Stephen Robertson and Hugo Zaragoza's BM25 review is the reference I would start with.
Comments
View on GitHub