J6MediumPart J · RecSys & Search Metrics

BM25 (Okapi BM25) Ranking Algorithm

⚡Flashcard Drill➔

Sparse lexical scoring balancing saturating term frequencies, IDF rarity, and document length normalization.

⏱️ Time: O(|Q| * 命中倒排链长)
💾 Space: O(词表 + 倒排索引索引空间)
🎯 Interactive Self-Practice Loop (Attempt Before Peeking)
Practice in 4 steps: recall mechanism, complete core lines, check edge cases, and log mastery locally.
Step 1 · Mechanism Recall & Stability Self-Check
Step 2 · Complete Key Implementation Lines
import numpy as np
import math
class BM25:
def __init__(self, corpus: list, k1: float = 1.5, b: float = 0.75):
self.k1 = k1
self.b = b
self.corpus_size = len(corpus)
self.doc_lens = [len(doc) for doc in corpus]
self.avgdl =
# 统计词频与文档频率 (DF)
self.doc_freqs = {}
for doc in corpus:
unique_words = set(doc)
for w in unique_words:
self.doc_freqs[w] = self.doc_freqs.get(w, 0) + 1
def get_idf(self, word: str) -> float:
df = self.doc_freqs.get(word, 0)
# 常见平滑形式: ln((N - df + 0.5) / (df + 0.5) + 1.0)
return math.log((self.corpus_size - df + 0.5) / (df + 0.5) + 1.0)
def score(self, query: list, doc_idx: int) -> float:
doc = self.corpus[doc_idx] if hasattr(self, 'corpus') else None
doc_len = self.doc_lens[doc_idx]
score = 0.0
len_norm = 1.0 - self.b + self.b * (doc_len / self.avgdl)
for q in query:
if q not in self.doc_freqs:
continue
# 统计词在当前 doc 的词频
tf = self.count_in_doc(q, doc_idx)
idf = self.get_idf(q)
score += idf * (tf * (self.k1 + 1.0)) / (tf + self.k1 * len_norm)
return float(score)
def count_in_doc(self, word: str, doc_idx: int) -> int:
return self._corpus_tokens[doc_idx].get(word, 0)
def build_bm25(corpus: list, k1: float = 1.5, b: float = 0.75):
bm = BM25(corpus, k1, b)
bm._corpus_tokens = []
for doc in corpus:
counts = {}
for w in doc:
counts[w] =
bm._corpus_tokens.append(counts)
return bm
Step 3 · Verify Boundary Cases & Assertions
Step 4 · Follow-Up Drill & Review Outcome
Q1: How does Reciprocal Rank Fusion (RRF) combine dense vector search and BM25 in hybrid retrieval?
Next: Pre-Filtered Hybrid Search with RRF Fusion →
💡

Core Mental Anchor / Mnemonic

Cap term-frequency growth with k1 and penalize bloated docs with parameter b.

📐 Mathematical Derivation & Core Formula

Score(D,Q)=∑q∈QIDF(q)⋅f(q,D)⋅(k1+1)f(q,D)+k1⋅(1−b+b⋅∣D∣avgdl)\mathrm{Score}(D, Q) = \sum_{q \in Q} \mathrm{IDF}(q) \cdot \frac{f(q, D) \cdot (k_1 + 1)}{f(q, D) + k_1 \cdot \left(1 - b + b \cdot \frac{|D|}{\mathrm{avgdl}}\right)}
### Term-Frequency Saturation & Document Length Normalization
Standard TF-IDF scales linearly with raw term count ff, favoring keyword-stuffed long pages. Okapi BM25 introduces:
1. TF saturation: f(k1+1)f+k1\frac{f (k_1 + 1)}{f + k_1} bounds term contribution at k1+1k_1 + 1 (k1∈[1.2,2.0]k_1 \in [1.2, 2.0]);
2. Length normalization: 1−b+b⋅∣D∣avgdl1 - b + b \cdot \frac{|D|}{\mathrm{avgdl}} (b≈0.75b \approx 0.75) penalizes bloated documents relative to average corpus length;
3. IDF weighting: Downweights ubiquitous tokens.

🔄 Tensor Dimensions & Shape Flow

query tokens -> lookup IDF -> saturating TF * IDF / length_norm -> sum score

🛡️ Numerical Stability & Pitfalls Checklist

  • Use smooth positive IDF (log((N - df + 0.5)/(df + 0.5) + 1.0)) to avoid negative IDF terms.
  • RAG pipelines commonly combine BM25 and dense vector retrieval using Reciprocal Rank Fusion (RRF).

💻 Reference Code Implementation

import numpy as np
import math

class BM25:
    def __init__(self, corpus: list, k1: float = 1.5, b: float = 0.75):
        self.k1 = k1
        self.b = b
        self.corpus_size = len(corpus)
        self.doc_lens = [len(doc) for doc in corpus]
        self.avgdl = sum(self.doc_lens) / max(1, self.corpus_size)
        
        # 统计词频与文档频率 (DF)
        self.doc_freqs = {}
        for doc in corpus:
            unique_words = set(doc)
            for w in unique_words:
                self.doc_freqs[w] = self.doc_freqs.get(w, 0) + 1
                
    def get_idf(self, word: str) -> float:
        df = self.doc_freqs.get(word, 0)
        # 常见平滑形式: ln((N - df + 0.5) / (df + 0.5) + 1.0)
        return math.log((self.corpus_size - df + 0.5) / (df + 0.5) + 1.0)
        
    def score(self, query: list, doc_idx: int) -> float:
        doc = self.corpus[doc_idx] if hasattr(self, 'corpus') else None
        doc_len = self.doc_lens[doc_idx]
        score = 0.0
        
        len_norm = 1.0 - self.b + self.b * (doc_len / self.avgdl)
        for q in query:
            if q not in self.doc_freqs:
                continue
            # 统计词在当前 doc 的词频
            tf = self.count_in_doc(q, doc_idx)
            idf = self.get_idf(q)
            score += idf * (tf * (self.k1 + 1.0)) / (tf + self.k1 * len_norm)
        return float(score)
        
    def count_in_doc(self, word: str, doc_idx: int) -> int:
        return self._corpus_tokens[doc_idx].get(word, 0)

def build_bm25(corpus: list, k1: float = 1.5, b: float = 0.75):
    bm = BM25(corpus, k1, b)
    bm._corpus_tokens = []
    for doc in corpus:
        counts = {}
        for w in doc:
            counts[w] = counts.get(w, 0) + 1
        bm._corpus_tokens.append(counts)
    return bm

🧪 Runnable Assertions & Validation

Copy and run directly in Python / Jupyter:

import numpy as np
corpus = [["deep", "learning"], ["machine", "learning", "deep"], ["apple", "banana"]]
bm = build_bm25(corpus)
# 检索 "deep"
s0 = bm.score(["deep"], 0)
s2 = bm.score(["deep"], 2)
assert s0 > s2 and s2 == 0.0, "不含关键词的文档得分应为 0"
print("✓ BM25 词频检索算法自测通过")

🎯 Core Follow-up Inquiries & Reference Answers

Q1:How does Reciprocal Rank Fusion (RRF) combine dense vector search and BM25 in hybrid retrieval?
Since cosine similarities and BM25 scores live on incompatible numerical scales, RRF sums reciprocal ranks RRF(d)=1k+rdense(d)+1k+rbm25(d)\mathrm{RRF}(d) = \frac{1}{k + r_{\mathrm{dense}}(d)} + \frac{1}{k + r_{\mathrm{bm25}}(d)} (typically k=60k=60), robustly rewarding items ranked highly by both retrievers.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔
← Prev: Cosine Similarity & Vector Top-K RetrievalBack to Part J & All 105Next: Pre-Filtered Hybrid Search with RRF Fusion →