前面的章节用布尔查询找到匹配的文档，但所有结果按 docId 返回——排在前面的不是最相关的文档，只是最先被索引的文档。搜索 “Java 垃圾回收” 时，一篇通篇讲 GC 调优的文章应该排在只在页脚提了一句 “Java” 的文章前面。

评分排序需要量化"相关性"。BM25（Best Matching 25）是目前最广泛使用的词法检索评分函数，Lucene、Elasticsearch、Solr 的默认评分都基于 BM25。它的输入只有三样：词频、文档长度和文档频率——全部可以从倒排索引中直接获取。

从 TF 到 TF-IDF

词频（Term Frequency）

直觉上，一个词在文档中出现次数越多，这篇文档与该词越相关。这就是词频（TF）。

但原始词频有问题：一个词出现 10 次不意味着相关性是出现 1 次的 10 倍。从 1 次到 2 次的信息增益远大于从 9 次到 10 次。对数平滑是常见处理：

1
2
tf_log(t, d) = 1 + ln(tf(t, d))    如果 tf > 0
             = 0                     如果 tf = 0

文档频率与 IDF

"的"在几乎所有中文文档中都出现，"NullPointerException"只在少数文档中出现。一个词出现在越少的文档中，它的区分能力越强。

逆文档频率（Inverse Document Frequency）量化这种区分能力：

1
idf(t) = ln(N / df(t))

N 是总文档数，df(t) 是包含词项 t 的文档数。

"的"的 df 接近 N，idf 接近 0——几乎没有区分能力。"NullPointerException"的 df 很小，idf 很高——有强区分能力。

手算示例

假设 5 篇文档：

文档 内容摘要 “java” tf “gc” tf
doc1 Java GC 调优详解 8 12
doc2 Java 基础教程 5 0
doc3 Python 内存管理 0 1
doc4 Java 并发与 GC 3 4
doc5 前端 CSS 布局 0 0

对查询 “java gc”：

1
2
df("java") = 3, idf("java") = ln(5/3) ≈ 0.51
df("gc") = 3,   idf("gc") = ln(5/3) ≈ 0.51

TF-IDF 评分（简化版）= Σ tf_log(t, d) × idf(t)：

1
2
3
doc1: (1 + ln(8)) × 0.51 + (1 + ln(12)) × 0.51 = 1.57 + 1.78 = 3.35
doc2: (1 + ln(5)) × 0.51 + 0 = 1.33
doc4: (1 + ln(3)) × 0.51 + (1 + ln(4)) × 0.51 = 1.07 + 1.22 = 2.29

排序：doc1 > doc4 > doc2。直觉上正确——doc1 对 “java gc” 最相关。

BM25 公式

TF-IDF 有一个问题：长文档天然包含更多词项，词频更高，会系统性地排在短文档前面。一篇 10,000 词的文档提到 “java” 20 次，不一定比一篇 200 词的文档提到 “java” 5 次更相关。

BM25 通过文档长度归一化解决这个问题。完整公式：

1
2
3
BM25(q, d) = Σ idf(t) × tf(t,d) × (k1 + 1)
                        ─────────────────────────────
                        tf(t,d) + k1 × (1 - b + b × dl/avgdl)

其中：

  • tf(t,d)：词项 t 在文档 d 中的原始词频
  • dl：文档 d 的长度（总词数）
  • avgdl：所有文档的平均长度
  • k1：词频饱和参数，默认 1.2
  • b：长度归一化参数，默认 0.75
  • idf(t)：逆文档频率

IDF 变体

Lucene 使用的 IDF 公式：

1
idf(t) = ln(1 + (N - df + 0.5) / (df + 0.5))

与经典 ln(N/df) 的区别：加了 0.5 平滑，避免 df=0 时除零，且当 df > N/2 时 IDF 为负——表示过于常见的词反而是负信号。

参数含义

k1 = 1.2：控制词频饱和的速度。k1 越大，高词频的收益越高，但增长始终有上界（趋近于 k1+1）。k1 = 0 时退化为纯 IDF，完全忽略词频。

b = 0.75：控制长度归一化的强度。b = 1 时完全按长度比例惩罚长文档。b = 0 时不做长度归一化。b = 0.75 是折中——长文档受到一定惩罚，但不会被过度压制。

手算 BM25

沿用上面的 5 篇文档，假设：

1
2
avgdl = (100 + 80 + 90 + 120 + 60) / 5 = 90
k1 = 1.2, b = 0.75
文档 dl “java” tf “gc” tf
doc1 100 8 12
doc2 80 5 0
doc4 120 3 4

IDF（Lucene 变体）：

1
2
idf("java") = ln(1 + (5 - 3 + 0.5) / (3 + 0.5)) = ln(1 + 0.714) = ln(1.714) ≈ 0.539
idf("gc")   = ln(1 + (5 - 3 + 0.5) / (3 + 0.5)) = ln(1.714) ≈ 0.539

doc1 的 BM25：

1
2
3
4
5
6
7
8
9
10
11
12
// "java" 部分
norm_java = 1 - 0.75 + 0.75 × (100/90) = 1 - 0.75 + 0.833 = 1.083
score_java = 0.539 × (8 × 2.2) / (8 + 1.2 × 1.083)
           = 0.539 × 17.6 / 9.3
           = 0.539 × 1.892 = 1.020

// "gc" 部分
score_gc = 0.539 × (12 × 2.2) / (12 + 1.2 × 1.083)
         = 0.539 × 26.4 / 13.3
         = 0.539 × 1.985 = 1.070

BM25(doc1) = 1.020 + 1.070 = 2.090

doc4 的 BM25：

1
2
3
4
5
6
7
8
9
norm = 1 - 0.75 + 0.75 × (120/90) = 1 - 0.75 + 1.0 = 1.25
score_java = 0.539 × (3 × 2.2) / (3 + 1.2 × 1.25)
           = 0.539 × 6.6 / 4.5
           = 0.539 × 1.467 = 0.791
score_gc = 0.539 × (4 × 2.2) / (4 + 1.2 × 1.25)
         = 0.539 × 8.8 / 5.5
         = 0.539 × 1.6 = 0.862

BM25(doc4) = 0.791 + 0.862 = 1.653

排序：doc1 (2.090) > doc4 (1.653) > doc2 (1.020)。doc4 虽然 “gc” 词频不低，但文档更长（dl=120 > avgdl=90），被长度归一化惩罚。

Top-K 堆

搜索引擎通常只返回前 K 个最相关的结果。用最小堆可以在 O(n log K) 时间内完成：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
PriorityQueue<ScoredDoc> topK(int k) {
    PriorityQueue<ScoredDoc> heap = new PriorityQueue<>(
        Comparator.comparingDouble(ScoredDoc::score));

    for (int docId : matchingDocs) {
        double score = bm25(queryTerms, docId);
        if (heap.size() < k) {
            heap.offer(new ScoredDoc(docId, score));
        } else if (score > heap.peek().score()) {
            heap.poll();
            heap.offer(new ScoredDoc(docId, score));
        }
    }

    List<ScoredDoc> result = new ArrayList<>(heap);
    result.sort(Comparator.comparingDouble(ScoredDoc::score).reversed());
    return result;
}

record ScoredDoc(int docId, double score) {}

堆始终保持 K 个元素。每个候选文档只需一次比较（与堆顶比），不进堆就丢弃。

标题字段加权

标题中出现查询词通常比正文中出现更有意义。对标题字段单独计算 BM25，然后加权合并：

1
finalScore = α × BM25(query, title) + β × BM25(query, body)

常见设置：α = 2.0，β = 1.0——标题匹配的权重是正文的两倍。

实现上需要为标题和正文分别维护倒排索引（不同的 posting list、不同的 docLength 统计）。查询时对两个索引分别计算 BM25 再合并。

平分规则

当两篇文档的 BM25 分数相同时（浮点数比较使用 epsilon 容差），需要一个确定性的 tiebreaker。常见选择：

  1. docId 较小的排前面——先索引的文档优先（稳定但无语义）
  2. 文档较短的排前面——假设短文档更精炼
  3. 较新的文档排前面——新鲜度偏好

本篇使用 docId 作为 tiebreaker，保证排序稳定且可复现。

验证

手算结果与程序结果必须一致。验证方法：

  1. 准备 5 篇 fixture 文档，内容和长度已知
  2. 对一个两词查询，手算每篇文档的 BM25 分数（精确到小数点后三位）
  3. 运行程序，比较分数和排序
  4. 调整 k1 和 b 参数，观察排序变化是否符合预期

当前局限

  • k1 和 b 使用默认值，没有针对语料调参——第 16 篇处理
  • 没有查询词权重（所有查询词等权）——可以扩展为加权求和
  • 浮点精度在大规模计算时可能累积误差——对教学规模可忽略
  • 没有考虑词项邻近度对评分的影响——BM25 只看词频，不看位置

练习

  1. 用 3 篇文档和一个单词查询，手算 BM25 分数，验证与程序一致
  2. 将 b 从 0 调到 1（步长 0.25），观察长文档和短文档的排序变化
  3. 将 k1 从 0 调到 3，观察高词频文档的分数变化曲线
  4. 构造一个标题加权改变排序的案例：文档 A 正文包含查询词 10 次，文档 B 标题包含查询词 1 次。调整 α 和 β 使 B 排在 A 前面
  5. 使用第 03 篇的评测基线，比较布尔匹配和 BM25 排序的 nDCG@5

延伸阅读

  • Robertson, S. E., & Zaragoza, H. (2009). The Probabilistic Relevance Framework: BM25 and Beyond.
  • Introduction to Information Retrieval, Chapter 6: Scoring, term weighting, and the vector space model
  • Lucene 源码：org.apache.lucene.search.similarities.BM25Similarity