FINDING NEEDLES · CHAPTER 04
Three chapters of parts, one file. The engine is fast for one reason: it only scores the documents that are on a query word's list.
A bird club keeps field logs. Someone asks for “heron at dawn”. The slow way is to open every log, score it, sort all the scores, and show the top two. That works for eight logs. It does not work for eight million.
The index from chapter 1 already knows which logs say heron and which say dawn. Any other log has tf = 0 for both words, so its BM25 score is exactly 0. You do not need to compute a number you already know.
The work of a query grows with the length of its words' postings lists, not with the size of the collection. Everything in this chapter is a way of keeping that true.
The tokenizer lowercases, keeps runs of letters, and drops seven stop words: a, and, at, in, on, over, the. Punctuation disappears with the split. The same function runs on logs and on queries.
birds · stages · postings · top-k
| Log | Text | Terms kept |
|---|---|---|
| 1 | Grey heron fishing at the reed bed, dawn. | 6 |
| 2 | Two kingfishers on the river at dawn. | 4 |
| 3 | Heron and little egret together on the mudflat. | 5 |
| 4 | Robin singing in the garden hedge. | 4 |
| 5 | Barn owl hunting over the meadow at dusk. | 5 |
| 6 | Wren in the hedge, robin nearby. | 4 |
| 7 | Heron standing still. Heron struck, caught a fish. | 7 |
| 8 | Swifts screaming over the old town at dusk. | 5 |
Log 1 becomes grey, heron, fishing, reed, bed, dawn. The query “heron at dawn” becomes heron, dawn. The lengths add up to 40, so avgdl = 5.
Chapter 1 stored a sorted list of ids per word. BM25 also needs the count, so each postings list here is a small dict: log id to tf. Next to it sits one more dict, log id to length. That is the whole index.
| Term | Postings {log: tf} | df | BM25 idf |
|---|---|---|---|
| heron | {1: 1, 3: 1, 7: 2} | 3 | 0.944 |
| dawn | {1: 1, 2: 1} | 2 | 1.281 |
| fish | {7: 1} | 1 | 1.792 |
| fishing | {1: 1} | 1 | 1.792 |
The eight logs give 33 terms in the index. The idf is the +1 form from chapter 3: ln(1 + (N − df + 0.5) / (df + 0.5)) with N = 8. Notice fish and fishing are two different terms. This tokenizer does not stem.
The engine also keeps a running total of all lengths as logs are added. Then avgdl is one division at query time, not a loop over every log.
Start with an empty dict of scores, the accumulators. Take the query terms one at a time. For each, walk its postings list and add that term's BM25 part into the log's accumulator. This is called term-at-a-time scoring.
the engine reads 5 postings entries in total, one per (term, log) pair that exists. A loop over every log would check 8 logs × 2 terms = 16 pairs, and 11 of them would come out zero.
So the engine scores 4 of 8 logs. In a real collection the gap is far bigger. A query word that appears in a thousand documents out of ten million costs a thousand additions, not ten million. Stop words are dropped partly for this reason: their lists are nearly the whole collection.
Term-at-a-time needs one accumulator per touched document, which can be a lot of memory for common words. Document-at-a-time instead walks all the query's postings lists side by side, in id order, like the AND merge in chapter 1. It finishes one document's score before moving to the next, so it only ever holds the current top k.
That opens a second trick. Each term has a maximum possible BM25 part. If the best a document could still reach is below the weakest score in the top k, skip it without scoring. MaxScore and WAND are the two classic versions. They return the same top k as the full computation, with much less work on long lists.
You want the best two, not a sorted list of everything. Keep a min-heap of size k. Its smallest entry, the weakest of the current best, sits on top where you can read it in one step. A new score either beats it and replaces it, or is thrown away.
For “heron at dawn” with k = 2, the accumulators arrive in the order 1, 3, 7, 2:
n scored documents, each costing at most one heap step of size log k. With k = 10 and a million candidates, that is a heap of 10, not a sort of a million.
Log 2 never says heron and still beats log 7, which says it twice. Dawn is the rarer word, and BM25 caps the second heron. That is chapter 3 at work inside the engine.
Interactive · Which logs get scored
Pink logs are on a query word's list and get an accumulator. The rest are never touched.
“owl at dusk” reads 3 postings entries and scores only logs 5 and 8: log 5 at 3.073, log 8 at 1.281. “heron fish” ranks log 7 first at 2.707, and log 1 gets only its heron part: it says fishing, not fish. “robin hedge” is a tie at 2.790. The heap breaks it toward the lower id.
One file, standard library only. The check script also runs a brute-force BM25 that scores every log and sorts them all, and confirms that both return the same top k.
"""A small search engine over eight bird-watching field logs.
Tokenizer, inverted index, BM25 over postings only, and a top-k heap.
Standard library only. Run it: python engine.py
"""
import heapq
import math
import re
LOGS = {
1: "Grey heron fishing at the reed bed, dawn.",
2: "Two kingfishers on the river at dawn.",
3: "Heron and little egret together on the mudflat.",
4: "Robin singing in the garden hedge.",
5: "Barn owl hunting over the meadow at dusk.",
6: "Wren in the hedge, robin nearby.",
7: "Heron standing still. Heron struck, caught a fish.",
8: "Swifts screaming over the old town at dusk.",
}
STOP = {"a", "and", "at", "in", "on", "over", "the"}
def tokenize(text):
"""Lowercase, keep runs of letters, drop stop words. Same for logs and queries."""
return [w for w in re.findall(r"[a-z]+", text.lower()) if w not in STOP]
class Engine:
def __init__(self, k1=1.2, b=0.75):
self.k1, self.b = k1, b
self.postings = {} # term -> {doc_id: tf}
self.lengths = {} # doc_id -> number of stored terms
self.total = 0 # sum of all lengths, kept so avgdl is one division
def add(self, doc_id, text):
terms = tokenize(text)
self.lengths[doc_id] = len(terms)
self.total += len(terms)
for term in terms:
plist = self.postings.setdefault(term, {})
plist[doc_id] = plist.get(doc_id, 0) + 1
def idf(self, term):
n, df = len(self.lengths), len(self.postings[term])
return math.log(1 + (n - df + 0.5) / (df + 0.5))
def accumulate(self, query):
"""Term at a time. Only documents on a query term's postings list get a score."""
avgdl = self.total / len(self.lengths)
scores = {}
for term in tokenize(query):
plist = self.postings.get(term)
if plist is None:
continue # no list, no work
idf = self.idf(term)
for doc_id, tf in plist.items():
norm = 1 - self.b + self.b * self.lengths[doc_id] / avgdl
part = idf * tf * (self.k1 + 1) / (tf + self.k1 * norm)
scores[doc_id] = scores.get(doc_id, 0.0) + part
return scores
def search(self, query, k=3):
return top_k(self.accumulate(query), k)
def top_k(scores, k):
"""Keep a min-heap of the best k. The weakest kept score sits at heap[0]."""
heap = []
for doc_id, score in scores.items():
item = (score, -doc_id) # on a tie, the lower id is the stronger one
if len(heap) < k:
heapq.heappush(heap, item)
elif item > heap[0]:
heapq.heapreplace(heap, item) # drop the weakest, keep this one
return [(-neg_id, score) for score, neg_id in sorted(heap, reverse=True)]
def build(logs=LOGS):
engine = Engine()
for doc_id, text in logs.items():
engine.add(doc_id, text)
return engine
if __name__ == "__main__":
engine = build()
for doc_id, score in engine.search("heron at dawn", k=2):
print(doc_id, round(score, 3), LOGS[doc_id])
Looping over every document “to be safe”. A document on no query word's list scores 0 in BM25. Scoring it gives the same answer at the cost of the whole collection. Walk the postings.
Tokenizing the query differently. If the query keeps “at” or keeps capitals, it looks up terms the index never stored. One tokenize function, used in both places.
Expecting “fish” to find “fishing”. Without stemming they are different terms with different lists. Decide at index time; you cannot fix it at query time.
Recomputing collection stats per query. avgdl and N must be cheap to read. Summing every length on each query is a hidden loop over the whole collection.
Unclear ties in the heap. Python compares tuples item by item. Decide what breaks a tie, here the lower id, and put it in the tuple, or two runs can disagree on equal scores.
Log 4 is on neither list, so tf is 0 for both words and its BM25 score is exactly 0.
It has tf 1 and length 5, which is avgdl. The tf part is 2.2 / 2.2 = 1.
Only log 1. Log 3 at 0.944 and log 7 at 1.167 are both below its 2.057, so neither gets in.
The question at each step is “does this beat the weakest one I am keeping?”. A min-heap puts that weakest score on top.