从零构建现代搜索引擎（03）：在改进排序前建立评测基线

改了分词器，搜"Java 异常"的结果看起来比之前好。真的好了吗？好了多少？有没有别的查询变差了？

没有数字就没有答案。靠肉眼看几条结果来判断质量，和靠"感觉服务器变快了"来判断性能一样不可靠。更危险的是：改了十次之后，已经记不清第一次的结果长什么样，无法判断整体方向是变好还是变差。

本篇的任务是在第一次改进排序之前，先把衡量标准建好。30 个标注查询、一个最小评测器、一份基线报告。之后每次改动，跑一遍评测，看数字说话。

评测的核心材料：查询、文档和相关性判定

搜索评测需要三样东西：

1
2
3

查询集（queries）     ─── 用户会搜什么
文档集（corpus）      ─── 搜索引擎里有什么
相关性判定（qrels）   ─── 哪些文档和哪个查询相关，相关到什么程度

相关性判定是人工标注的。格式沿用 TREC 的 qrels 标准：

1	`query_id 0 doc_id relevance`

中间的 0 是历史遗留的迭代字段，固定填 0。relevance 是相关性等级，本系列用 0–3 四级：

等级	含义	标注标准
3	完美匹配	文档直接回答了查询，是查询的最佳结果
2	高度相关	文档包含查询所需的主要信息
1	部分相关	文档涉及查询话题，但不直接回答
0	不相关	文档与查询无关

一条具体的标注：

1
2
3

q01  0  md:a3f8b21c  3
q01  0  md:7c91d0e5  1
q01  0  html:b42e8f  0

含义：对查询 q01，文档 md:a3f8b21c 完美匹配（3 分），md:7c91d0e5 部分相关（1 分），html:b42e8f 不相关（0 分）。

30 个查询的设计

30 个查询不是随意写的。按 6 种类型各 5 个，覆盖搜索引擎会遇到的典型场景：

类型	数量	示例	测试目的
精确关键词	5	`倒排索引`	词项完全匹配
错误码/标识符	5	`NullPointerException`	长标识符不被切碎
中英混合	5	`Java 并发锁`	跨语言分词
同义改写	5	`全文检索`（期望命中"全文搜索"）	词汇鸿沟
多条件	5	`搜索引擎倒排索引 BM25`	多词项交集
无答案	5	`量子计算入门`（语料中无此话题）	零结果处理

无答案查询容易被忽略，但对评测很重要。如果系统对"量子计算入门"返回了结果，说明误召回——返回的文档和查询毫无关系。零结果不是错误，错误的是把不相关的文档排上去。

每个查询至少标注语料中所有候选文档的相关性。标注时容易犯的错误是只标注搜索引擎返回的结果——这会遗漏系统没有召回但实际相关的文档（漏标）。正确做法是从文档集出发，逐篇判断和查询的关系。语料只有几十篇时这个工作量可以接受。

手算 nDCG：从一个具体例子开始

nDCG（normalized Discounted Cumulative Gain）是本系列的主指标。在写代码之前先手算一次，确保理解公式的每一步。

假设查询 q01 的搜索结果是 5 篇文档，人工标注的相关性如下：

排名位置 i	文档	相关性 rel_i
1	doc_A	3
2	doc_B	0
3	doc_C	2
4	doc_D	1
5	doc_E	3

第一步：计算 DCG@5

DCG 的公式：DCG@k = Σ(i=1 to k) (2^rel_i - 1) / log₂(i + 1)

逐项计算：

i=1: (2³ - 1) / log₂(2) = 7 / 1.000 = 7.000
i=2: (2⁰ - 1) / log₂(3) = 0 / 1.585 = 0.000
i=3: (2² - 1) / log₂(4) = 3 / 2.000 = 1.500
i=4: (2¹ - 1) / log₂(5) = 1 / 2.322 = 0.431
i=5: (2³ - 1) / log₂(6) = 7 / 2.585 = 2.708

DCG@5 = 7.000 + 0.000 + 1.500 + 0.431 + 2.708 = 11.639

第二步：计算 IDCG@5（理想排序）

把相关性从高到低排列：3, 3, 2, 1, 0。这是能获得的最大 DCG。

i=1: (2³ - 1) / log₂(2) = 7 / 1.000 = 7.000
i=2: (2³ - 1) / log₂(3) = 7 / 1.585 = 4.416
i=3: (2² - 1) / log₂(4) = 3 / 2.000 = 1.500
i=4: (2¹ - 1) / log₂(5) = 1 / 2.322 = 0.431
i=5: (2⁰ - 1) / log₂(6) = 0 / 2.585 = 0.000

IDCG@5 = 7.000 + 4.416 + 1.500 + 0.431 + 0.000 = 13.347

第三步：nDCG@5 = DCG / IDCG

1	`nDCG@5 = 11.639 / 13.347 = 0.872`

0.872 说明这次排序接近理想排序，但不完美。主要扣分来自位置 2 放了一个不相关文档（rel=0），把本应在前面的 doc_E（rel=3）推到了位置 5。

解读 nDCG 的分母

nDCG 的值域是 [0, 1]。1 表示排序和理想排序完全一致。注意 IDCG 只考虑标注过的文档——如果某个相关文档根本没有出现在标注集里（漏标），nDCG 不会惩罚系统漏召回它，但也不会因为召回它而加分。这就是为什么标注覆盖率很重要。

手算 MRR：第一个相关结果在哪里

MRR（Mean Reciprocal Rank）关注的问题更简单：第一个相关结果出现在第几位？

对单个查询，Reciprocal Rank = 1 / (第一个相关结果的排名位置)。"相关"指 rel ≥ 1。

用上面的例子：

1 2	`位置 1: doc_A, rel=3 → 相关 ✓ RR = 1/1 = 1.000`

第一个相关结果就在位置 1，RR 是满分。

换一个差一些的排序：

位置	文档	rel
1	doc_B	0
2	doc_C	0
3	doc_A	3
4	doc_D	1
5	doc_E	2

位置 1: rel=0 → 不相关
位置 2: rel=0 → 不相关
位置 3: rel=3 → 相关 ✓
RR = 1/3 = 0.333

MRR 是所有查询 RR 的平均值。30 个查询的 MRR 越接近 1，用户越快看到有用的结果。

MRR 和 nDCG 互补：nDCG 关注整个排序质量（前 10 个结果的排列好不好），MRR 只关注第一个相关结果的位置（用户要翻多少条才看到有用的）。

最小评测器

评测器读入两个文件：qrels（人工标注）和 run（系统输出），计算 nDCG@10 和 MRR@10。

系统输出的格式同样沿用 TREC：

1	`query_id Q0 doc_id rank score run_name`

示例：

1
2
3

q01  Q0  md:a3f8b21c  1  5.23  sequential-v1
q01  Q0  md:7c91d0e5  2  3.11  sequential-v1
q01  Q0  html:b42e8f  3  1.05  sequential-v1

评测器的核心逻辑（伪代码）：

for each query in queries:
    // 取该查询的 qrels 和 run 结果
    Map<String, Integer> rels = qrels.get(queryId);
    List<String> ranking = run.get(queryId);

    // 计算 DCG@k
    double dcg = 0;
    for (int i = 0; i < Math.min(k, ranking.size()); i++) {
        int rel = rels.getOrDefault(ranking.get(i), 0);
        dcg += (Math.pow(2, rel) - 1) / log2(i + 2);
    }

    // 计算 IDCG@k
    List<Integer> idealRels = rels.values().stream()
        .sorted(Comparator.reverseOrder())
        .limit(k).toList();
    double idcg = 0;
    for (int i = 0; i < idealRels.size(); i++) {
        idcg += (Math.pow(2, idealRels.get(i)) - 1) / log2(i + 2);
    }

    double ndcg = (idcg == 0) ? 0 : dcg / idcg;

    // 计算 RR
    double rr = 0;
    for (int i = 0; i < Math.min(k, ranking.size()); i++) {
        if (rels.getOrDefault(ranking.get(i), 0) >= 1) {
            rr = 1.0 / (i + 1);
            break;
        }
    }

注意 log2(i + 2) 而不是 log2(i + 1)——因为 i 从 0 开始，对应排名位置 1，分母应该是 log₂(1+1) = log₂(2)。这个 off-by-one 是手算和代码对不上的最常见原因。

IDCG 为 0 的情况：该查询在 qrels 中所有文档的 rel 都是 0，即没有相关文档。此时 nDCG 定义为 0，不是除以零。

零结果查询和漏标查询

两种容易混淆的情况：

零结果查询：查询"量子计算入门"，语料中确实没有相关文档。系统返回空结果是正确行为。在评测中，这个查询的 nDCG = 0，MRR = 0。这不是系统的问题，是语料覆盖范围的问题。

漏标查询：查询"倒排索引"，语料中有一篇相关文档，但标注时漏掉了，qrels 里没有这个 query-doc 对。系统召回了这篇文档，评测器把它当作 rel=0 处理——实际相关但被标错为不相关。

区分方法：

	零结果查询	漏标查询
语料中有相关文档？	没有	有
qrels 中有标注？	有，全部 rel=0	缺少条目
系统返回空结果	正确	可能漏召回
系统返回结果	误召回，nDCG 应为 0	nDCG 被低估

漏标比零结果更危险，因为它悄悄降低了评测分数，让正确的改进看起来没有效果。解决方法是标注时从文档集出发逐篇判断，而不是只标注系统返回的结果。语料几十篇时这个成本可控。

顺序扫描基线的评测结果

用第 01 篇的顺序扫描搜索器跑 30 个查询，生成 run 文件，和 qrels 一起输入评测器。

预期结果会很差。顺序扫描用子串匹配，没有评分排序，返回顺序是文件系统的遍历顺序。对"倒排索引"这个查询，即使命中了正确文档，排名位置取决于文件名的字典序而不是相关性。

===== 评测报告 =====
run: sequential-v1
queries: 30
nDCG@10:  0.XXX   (预期 0.2-0.4 之间)
MRR@10:   0.XXX   (预期 0.3-0.5 之间)
零结果查询: 5/30  (无答案类查询)
有结果但 nDCG=0: X/30  (全部召回不相关)

这组数字就是基线。之后每次改进——加分词、加 BM25、加倒排索引——都和这组数字比较。如果 nDCG 从 0.3 升到 0.6，说明改进有效；如果"错误码"类查询的 nDCG 反而下降了，说明新分词器可能把长标识符切碎了。

评测纪律

三条规矩，从现在开始遵守：

开发集调参，测试集只报告。 30 个查询现在全部用作开发集。第 16 篇扩展到 100 个查询时，冻结其中 50 个作为测试集。在测试集上反复调参等于作弊——选出了在这 50 个查询上恰好最优的参数，换一批查询可能完全不行。

每次只改一个主要变量。 同时换分词器和改 BM25 参数，nDCG 变了不知道是谁的贡献。先换分词器跑一次，再改参数跑一次。

保留逐查询结果。 只看平均 nDCG 会掩盖细节。平均分从 0.5 涨到 0.55，可能是 5 个查询大幅提升、3 个查询严重退化的净效果。逐查询对比才能发现退化。

评测基线建好了，但搜索引擎还只能搜本地 fixture。第 04 篇「实现有边界的网页爬虫」会实现一个受控的爬虫：白名单站点、robots.txt 遵守、重试预算、超时断点。数据量从几十篇扩展到几百篇。

练习：

用上面的手算方法计算以下排序的 nDCG@5：排名依次为 rel = [2, 3, 0, 0, 1]。和文中的例子比较，哪个排序更好？差距主要来自哪个位置？
设计一个查询，使得 MRR@10 = 1.0 但 nDCG@10 < 0.5。提示：第一个结果相关但后面的排序很差。
如果把 nDCG 的相关性等级从 4 级（0-3）改为 2 级（0 和 1），公式中哪一项受影响最大？对排序区分度有什么影响？