Skip to content

打分与 Top-K

学习目标

完成本章后，你将能够：

  1. 计算 MiniLucene 用于一项 BM25 词项贡献的四类输入；
  2. 追踪 DAAT 匹配/打分、Top-K 收集与后置 stored-field fetch；
  3. 解释确定性同分规则，以及为什么 top_k=0 仍会统计匹配数；
  4. 找出当前 phrase 打分与 DAAT fallback 边界；以及
  5. 验证已删除文档不会贡献 MiniLucene 的语料统计。

1. 匹配与打分是两个阶段

查询先决定哪些文档有资格，再给它们分数。 src/minilucene/search/scorer.py 的 iter_scored_docs() 会把 rewrite 后的 term、match-all 与 Boolean 树编译为 DAAT scorer 游标，每次产出一个 (doc_id, score)。保留的 score_query() 会从 match_query() 的完整 set[int] 开始；它现在是正确性 oracle，也是 phrase 或未 rewrite prefix 叶子的整树 fallback。

对于 TermQuery，DAAT term scorer 与 oracle _term_scores() 都读取：

  • tf：该文档该字段内的词频；
  • df：该字段该词项的存活文档频率；
  • n：reader 快照的存活文档总数；
  • dl：该文档的分析后字段长度；以及
  • avgdl：存活且拥有该字段的文档平均分析长度。

实现从 src/minilucene/search/stats.py 的 CorpusStats 获得 df、n 与 avgdl；这些值由 src/minilucene/search/reader.py 的 ReaderView._build_corpus_stats() 冻结。该函数只迭代快照中的存活段内 ID。因此，新删除的文档既不贡献匹配，也不贡献背景统计。

这是 MiniLucene 有意选择的语义。它让显式 merge 前后的打分保持稳定，因为 merge 精确复制同一份存活语料。

2. BM25 奖励证据，但重复收益会饱和

src/minilucene/search/bm25.py 的 BM25.term_score() 实现：

idf = log(1 + (n - df + 0.5) / (df + 0.5))
normalized_length = dl / avgdl if avgdl != 0 else 0
norm = 1 - b + b * normalized_length
tf_weight = tf * (k1 + 1) / (tf + k1 * norm)
score = idf * tf_weight

默认参数为 k1=1.2、b=0.75。

IDF 让更稀有的词项信息量更高。tf_weight 的分数随词项重复而增长，但分子与分母都随 tf 增长，所以收益会饱和，而非线性增长。长度归一化削弱长文档仅仅因为容纳词项机会更多而获得的优势。当 avgdl 为零时，代码令 normalized_length=0，所以 norm=1-b（默认值为 0.25），而不是把 norm 替换成 1.0。在 n=df=tf=1、dl=avgdl=0 和默认参数下，分数是 0.486846584149；若误用 norm 1.0，才会得到 0.287682072452。

BM25.__post_init__() 拒绝负数或非有限 k1，以及 [0, 1] 之外的 b。term_score() 拒绝非法计数和长度；当 tf == 0、df == 0 或 n == 0 时返回零。

随后，MiniLucene 在 _term_scores() 中把贡献乘以 schema 字段 boost。这适合教学，但方向与现代 Lucene 相反：当前 Lucene 使用 BoostQuery 等查询时 boost，并已移除索引时字段 boost。该差异明确记录在 MiniLucene 到 Lucene 映射中。

BM25 分数既不是概率，也不是百分比。它适合在相同查询、reader 快照、similarity 参数、schema boost 和语料统计下排列文档。改变存活语料可能改变 IDF 与平均长度，因此不同快照的绝对数值不能直接校准。仓库测试在冻结输入下比较受控排序或近似分数，并未给出通用的“相关性良好”阈值。

3. 复合分数

DAAT 节点与保留的 score_query() 遵循同一个封闭查询 AST：

  • term 获得一个 BM25 贡献；
  • prefix 通常先被 rewrite，随后由匹配的展开词项贡献分数；
  • Boolean 查询汇总非 prohibited 子查询的分数，但只保留通过 Boolean 匹配的文档；
  • match-all 给每个候选文档 0.0 分；以及
  • phrase 先要求位置匹配，再为合格文档汇总组成词项的 BM25 贡献。

phrase 分支必须诚实标注。MiniLucene 用 positions 证明相邻关系，但不计算 phrase frequency。某文档只包含一次短语，却散落着许多组成词项，也可能比多次包含完整短语的文档分数更高。Apache Lucene 的 PhraseQuery 通过 phrase matcher 和 similarity 使用短语频率。因此，两套系统可能对同一批 phrase 匹配项排出不同顺序。

prefix 打分同样汇总展开词项贡献。展开本身有界并且超限立即失败，第 9 章会详细讨论。

4. 堆最多保留 K 个命中

src/minilucene/search/collector.py 的 TopKCollector 把总匹配数与保留结果分开。每次调用 collect() 都递增 total_hits。当 top_k == 0 时，到此即止：调用者可以统计匹配而不保留命中对象。

K 为正时，collector 维护最多 K 个条目的最小堆。键为：

(score, -segment_generation, -local_doc_id)

最小的保留键最容易被淘汰。高分胜出；同分时，较小段代际胜出；同段内，较小本地文档 ID 胜出。top_docs() 最后按分数降序、段代际升序、本地 ID 升序排列胜者。相同快照在不同运行中的顺序确定。

collector 为命中对象使用 O(K) 内存，同时 total_hits 仍统计完整匹配集合。max_retained 是可观察测试钩子，永远不超过 K。

同分规则使用段和本地 ID，而不是 stored 应用 ID。这些物理 ID 在一份 reader 快照内稳定，但 merge 后可能改变，因此应用不能把该兜底顺序当作永久外部身份。MiniLucene 通过仅活文档统计保持 merge 前后分数，但同分文档可能获得新的稠密本地 ID。需要稳定业务顺序的产品必须添加显式排序键；字段排序本身不在 V1 范围内。

5. 先 collect，再 fetch 胜者

src/minilucene/search/searcher.py 的 IndexSearcher.search() 现在把查询执行 与结果物化明确分开。

第一阶段 rewrite 查询、消费 iter_scored_docs()、解析轻量 address，并把 score/doc identity 交给 TopKCollector。第二阶段取得排好序的胜出候选，此时才 调用 stored_fields() 与 highlight_document()。

MiniLucene
postings 迭代器/scorer → 收集 Top-K 文档 ID 与分数
→ 只为胜者 fetch stored fields/highlight

因此 stored-field 与 highlighting 工作受 K 限制，top_k=0 时两者均为零。 这不代表全部搜索工作是 O(K)：每个 DAAT 命中仍会打分，含 phrase 的树会走完整 集合/字典 fallback，而且没有 postings skip、block-max WAND、phrase two-phase iterator 或 leaf collector。

第 11 章会跟踪游标算法，并给出可执行的 10 matched / 3 fetched 与 4 matched / 0 fetched 观察。

6. 与 Apache Lucene 对照

BM25 概念可以迁移：词频饱和、逆文档频率、长度归一化和 similarity 对象同样是真实 Lucene 的核心。保留竞争性命中的 collector 和确定性同分策略也一样。

若干生产细节不能直接迁移：

  • MiniLucene 现在已经迁移基本 iterator/scorer 方向，但仍使用一个教学用全局 reader，而不是真实 Lucene 的 leaf scorer。
  • Lucene 可以跳过无竞争力 postings，并使用优化的 conjunction、disjunction、two-phase 和 top-score 收集机制。
  • 两者现在都在收集胜出文档 ID 后才 fetch stored fields。
  • Lucene 的已删除文档可能在 merge 前仍留在段统计中；MiniLucene 立刻排除它们。
  • MiniLucene phrase 打分汇总词项分数，而不是 phrase frequency。
  • MiniLucene 在 schema 中固定 boost，而不是用查询时 boost 包装查询。

在把 MiniLucene 实测分数当作 Apache Lucene 预测之前，请查阅 行为矩阵中的 global BM25、bounded Top-K、live statistics 与 ranking 条目，以及映射中的 “Semantics reversed” 行。

7. 动手实验：饱和、长度与堆

在仓库根目录运行：

UV_CACHE_DIR=/tmp/minilucene-uv-cache uv run python - <<'PY'
from minilucene import MemoryIndex, Schema, TextField
from minilucene.query import TermQuery
from minilucene.search.bm25 import BM25

schema = Schema(body=TextField(stored=True))
index = MemoryIndex(schema)
index.add_document(body="kafka")
index.add_document(body="kafka kafka kafka kafka")
index.add_document(body="kafka filler filler filler filler filler")
index.add_document(body="unrelated")

results = index.search(TermQuery("body", "kafka"), top_k=2)
print(f"total_hits={results.total_hits}")
print(f"retained={len(results.hits)}")
for hit in results.hits:
    print(f"{hit.stored_fields['body']!r} score={hit.score:.6f}")

count_only = index.search(TermQuery("body", "kafka"), top_k=0)
print(
    f"count_only total={count_only.total_hits} "
    f"retained={len(count_only.hits)}"
)
print(
    "zero_avgdl="
    f"{BM25().term_score(tf=1, df=1, n=1, dl=0, avgdl=0):.12f}"
)
PY

实测输出：

total_hits=3
retained=2
'kafka kafka kafka kafka' score=0.570680
'kafka' score=0.490428
count_only total=3 retained=0
zero_avgdl=0.486846584149

重复四次的分数高于一次，但并非四倍。只出现一次的更长文档因长度归一化而落在 Top-2 之外。top_k=0 仍遍历并统计三个匹配。

还可以运行可执行公式检查：

UV_CACHE_DIR=/tmp/minilucene-uv-cache uv run pytest tests/unit/search/test_bm25.py tests/unit/search/test_topk.py -q

实测输出：

10 passed in 0.04s

耗时会变化；稳定证据是通过数量和零失败。

8. 练习

练习 1——计算题

若 n=10、df=2、tf=1 且 dl=avgdl，当 tf 变为 4 时，BM25 公式的哪些部分会变化？

参考答案

因为 n 和 df 不变，idf 不变。因为 dl/avgdl 不变，长度归一化不变。只有 tf_weight 变化，并以次线性方式趋向饱和上限。

练习 2——架构题

为什么 TopKCollector.max_retained <= K 不能证明搜索内存为 O(K)？

参考答案

collector 限制的是保留候选与后置命中物化，不是全部查询工作。DAAT 仍会为 每个匹配 doc 打分；含 phrase 的树还会回退完整候选与分数集合。系统没有 skip/WAND 剪枝。

练习 3——动手题

不要修改 src/。把 collect-then-fetch 契约测试复制到临时目录，扩展 counting reader：除 stored_fields() 外也记录 address() 调用。

验收方式：十个匹配、top_k=3 时应观察十次 address 解析、三次 stored-field fetch；top_k=0 时保持 total_hits=10 且 fetch 为零。

参考答案

address 解析属于第一阶段，因为确定性 Top-K 同分规则使用 segment/local identity。stored fields 与 highlights 属于第二阶段，因此次数跟保留候选数， 而不是总命中数。

小结

MiniLucene 把匹配资格与 BM25 贡献分开，冻结仅活文档统计，并用确定性堆最多保留 K 个命中。受支持的 term/Boolean 树执行 DAAT，stored fields/highlights 只为胜者 生成。Phrase 树仍使用全量物化 oracle，phrase 分数也仍汇总词项证据，而不是短语 频率。第 9 章前移到 query AST；第 11 章展开 iterator 执行模型。