Back
+30 XP
Concept

In-Memory Inverted Index with BM25 Scoring

Naive string containment (`term in text`) cannot rank search relevance. The Okapi BM25 ranking function improves on TF-IDF by adding term frequency saturation ($k_1$) so repeated spam keywords don't inflate scores, combined with length normalization ($b$) to penalize bloated documents 📚🔎⚡.

python
import math
from collections import Counter

def calc_bm25_tf(tf, doc_len, avg_len, k1=1.5, b=0.75):
    # Diminishing returns on term frequency
    return (tf * (k1 + 1)) / (tf + k1 * (1 - b + b * (doc_len / avg_len)))

print("BM25 TF Factor (tf=1):", calc_bm25_tf(1, 10, 10))
print("BM25 TF Factor (tf=20):", calc_bm25_tf(20, 10, 10))

# 25. In-Memory Inverted Index with BM25 Scoring Search engines like Lucene, Elasticsearch, and Vespa don't just ask *"Does this word appear in the document?"*. They answer: *"Which document is the most relevant match for this user's query?"* 🛑. ```python # The BM25 Scoring Formula Components: # 1. IDF (Inverse Document Frequency): # Rare words across the corpus (e.g. "asynchronous") yield high points. # Common words (e.g. "the", "and") yield near-zero points. # # 2. Term Frequency Saturation (k1 parameter): # Mentioning a word 2 times is much better than 1 time. # Mentioning a word 200 times is barely better than 20 times (curbs keyword spam). # # 3. Document Length Normalization (b parameter): # A 10-word document mentioning "Python" is much more focused than # a 10,000-word encyclopedic dump that happens to mention "Python" once. ``` ### The Inverted Index Advantage By pre-tokenizing and mapping terms to document frequencies (`df[term]`), query resolution skips unmatching documents, computing BM25 relevancy scores in sub-millisecond in-memory sweeps 📚🔎⚡. --- ### Interactive Pop-Quiz 🧠 #### Why does Okapi BM25 outperform classic TF-IDF when ranking long documents? - [ ] BM25 applies term frequency saturation ($k_1$) and penalizes excessively long documents ($b$), preventing keyword-stuffed articles from dominating results 🔎 - [ ] Because BM25 uses GPU neural networks - [ ] Because TF-IDF is restricted to numeric search only - [ ] Because BM25 encrypts all document tokens with SHA-256 --- ### Practical Challenge 🎯 Implement `BM25Index(k1: float = 1.5, b: float = 0.75)` with `add_document(doc_id: str, text: str)` and `score(doc_id: str, query: list[str]) -> float`. Index 3 documents: `'python high performance asynchronous sockets'`, `'python basics for complete beginners'`, and `'high performance computing'`. Compute score for `['python', 'performance']`, assert `doc1` score is strictly higher than `doc2` and `doc3`, and print the scores. <details> <summary>Solution</summary> ```python import math from collections import Counter class BM25Index: def __init__(self, k1: float = 1.5, b: float = 0.75): self.k1 = k1 self.b = b self.docs = {} self.doc_lens = {} self.avg_doc_len = 0.0 self.df = Counter() def add_document(self, doc_id: str, text: str): tokens = text.lower().split() self.docs[doc_id] = tokens self.doc_lens[doc_id] = len(tokens) for t in set(tokens): self.df[t] += 1 self.avg_doc_len = sum(self.doc_lens.values()) / len(self.doc_lens) def score(self, doc_id: str, query: list[str]) -> float: total_score = 0.0 doc_tokens = self.docs[doc_id] tf = Counter(doc_tokens) n_docs = len(self.docs) doc_len = self.doc_lens[doc_id] for term in query: if term not in self.df: continue df_val = self.df[term] idf = math.log((n_docs - df_val + 0.5) / (df_val + 0.5) + 1.0) term_freq = tf[term] numerator = term_freq * (self.k1 + 1.0) denominator = term_freq + self.k1 * (1.0 - self.b + self.b * (doc_len / self.avg_doc_len)) total_score += idf * (numerator / denominator) return round(total_score, 4) index = BM25Index() index.add_document("doc1", "python high performance asynchronous sockets") index.add_document("doc2", "python basics for complete beginners") index.add_document("doc3", "high performance computing and systems") s1 = index.score("doc1", ["python", "performance"]) s2 = index.score("doc2", ["python", "performance"]) s3 = index.score("doc3", ["python", "performance"]) assert s1 > s2 assert s1 > s3 print(f"BM25 Ranking verified: doc1={s1} > doc2={s2}, doc3={s3}") ``` </details>

Checkpoint

Why does Okapi BM25 outperform classic TF-IDF when ranking long documents? 🧠

Practice

Implement `BM25Index(k1: float = 1.5, b: float = 0.75)` with `add_document(doc_id: str, text: str)` and `score(doc_id: str, query: list[str]) -> float`. Index 3 documents: `'python high performance asynchronous sockets'`, `'python basics for complete beginners'`, and `'high performance computing'`. Compute score for `['python', 'performance']`, assert `doc1` score is strictly higher than `doc2` and `doc3`, and print the scores. 🎯

Terminal
01
Tap code blocks below to assemble
Available Blocks