搜索的秩序——1972年，为什么一个罕见的词，比一千次重复更值得注意？

序幕：你找的是哪一篇？

假设你走进一座有一百万份文件的档案馆。

你想找一份讨论“缓存一致性”的材料。

管理员给你两篇文章。第一篇有五百页，“缓存”出现了一百次，但绝大部分内容在讨论别的问题。第二篇只有两页，却准确解释了多个处理器怎样协调同一份数据。

哪篇更值得先读？

只要听到这个问题，你已经开始设计一个搜索引擎了。

上一章的 PageRank 研究网页链接之间的重要性。本章换一个方向：先不管谁引用谁，只看用户输入的词与文档内容，怎样找到候选文章，又怎样安排它们的顺序？

这里有两个问题，不能混在一起：找得到，是索引问题；排得好，是相关性问题。

第一幕：先把目录翻转过来

档案馆原本按照文件编号保存内容。

这种方向是“文档到词”。如果每次查询都从头读完全部文档，即使只是寻找一个很罕见的词，也要扫描整座档案馆。

我们不妨提前建立另一份目录：

缓存    → D1, D2
一致性  → D1, D3
协议    → D1, D3
命中    → D2
性能    → D2
分布式  → D3

现在方向变成了“词到文档”。这就是倒排索引（Inverted Index）。每个词后面的文档记录叫倒排列表，列表中的一条记录常被称为 posting。

查询“缓存”，直接读取它的列表。查询“缓存 AND 一致性”，求两个列表的交集，得到 D1。若采用 OR，则取并集，得到 D1、D2、D3，再进行排序。

如果列表按文档编号排序，两个列表求交可以使用两个指针。较小的编号向前走，相同的编号加入结果。长度分别为 a、b 的两个列表，朴素归并求交的时间为 O(a+b)。真实系统还有跳跃指针、压缩编码与提前终止等优化。

**索引的代价也很明确：我们用额外存储和预处理，换取查询时少做工作。**这与数组、哈希表和缓存章节中的取舍一脉相承。

分词规则同样属于索引设计。英文可以先从空格与标点切分入手；中文通常需要明确分词策略。索引和查询若使用不同的切分方式，文章明明存在，也可能匹配不到。短语搜索还需要词的位置，仅有“包含哪些词”通常不够。

第二幕：1972年，Karen Spärck Jones 换了一个提问方式

1972年，Karen Spärck Jones 在《Journal of Documentation》发表《A Statistical Interpretation of Term Specificity and Its Application in Retrieval》。她研究的一个核心方向，是用词在文档集合中的分布，解释它对检索的区分能力。原始论文

我们用一个现代化例子体会这个问题。

在一千篇计算机文章中，“计算机”可能出现九百次；“拜占庭”也许只出现在十篇中。如果你输入“拜占庭”，它便能把注意范围大幅缩小。

注意，这里的“出现十篇”不是说这个词一共只写了十次。某一篇文章重复一百次，文档频率仍然只增加一。

设文档总数为 N，包含词 t 的文档数为 df(t)。一种经典的逆文档频率写法是：

$$\operatorname{IDF}(t)=\ln\frac{N}{\operatorname{df}(t)}$$

对数底数固定后，更换底数只会带来共同的常数比例。本章使用自然对数。这个公式要求词已出现在集合中；如果查询词根本不在索引里，本章直接将其视为没有匹配，而不是计算除以零。

当 N=1000、df=10 时，IDF 约为 4.605；df=900 时，约为 0.105。它表达的是当前文档集合里的区分能力，不是这个词在语言或现实世界中“有多重要”。

如果集合改成一千篇专门研究拜占庭协议的论文，“拜占庭”也可能变成一个很普通的词。

第三幕：一个词出现很多次，是否说明文章很相关？

逆文档频率比较不同的词。接下来还要比较不同的文章。

设 f(t,d) 表示词 t 在文档 d 中出现的次数。一种最简单的教学版 TF-IDF 分数，是把查询里各个不同词的贡献相加：

$$\operatorname{score}(d,q)=\sum_{t\in\operatorname{unique}(q)}f(t,d)\operatorname{IDF}(t)$$

这里的 TF 直接使用原始计数。TF-IDF 是一类权重方法，并不是只有这一种固定公式；实际系统常对词频、文档长度和向量归一化另作处理。

这个简单版本已经比“含有关键词就一视同仁”更细致。但它也有一个明显弱点：只要不停重复查询词，分数就能一直增长。

一篇真正的教程也许只把“缓存”写了三次；另一篇页面却把“缓存”复制了一千遍。后者真的应该得到三百多倍的信任吗？

这不是由一次词频统计就能回答的问题。我们需要重新设计：重复提供的证据，应不应该边际递减？

第四幕：BM25 把“越多越好”改成“增加，但逐渐饱和”

BM25 来自概率相关性检索的研究路线，并在 Okapi 系统与评测实践中发展。它不是某人在一个下午突然写出的孤立公式。Robertson 与 Zaragoza 的综述系统回顾了这条路线。研究综述

本章采用下面这个常见实现变体：

$$\operatorname{score}(d,q)=\sum_{t\in\operatorname{unique}(q)} \operatorname{IDF}_{+}(t) \frac{f(t,d)(k_1+1)}{f(t,d)+k_1\left(1-b+b\frac{|d|}{\operatorname{avgdl}}\right)}$$

其中，文档长度 |d| 按分词后的词数计算，avgdl 是集合的平均文档长度。k₁ 控制词频饱和的速度，b 控制长度归一化的强度。

为了避免高频词产生负权重，我们明确使用加一对数的正值 IDF 变体：

$$\operatorname{IDF}_{+}(t)=\ln\left(1+\frac{N-\operatorname{df}(t)+0.5}{\operatorname{df}(t)+0.5}\right)$$

不同实现的 IDF 平滑方式可能不同，数值不能脱离公式直接比较。BM25 分数也不是“相关概率百分比”。本章不重复计算查询中的同一词，不引入查询词频因子。

先让文档长度等于平均长度。公式中的词频部分就简化为：

$$\frac{f(k_1+1)}{f+k_1}$$

假设 k₁=1.2，f=1 时，这部分等于 1；f=3 时约为 1.571；f=10 时约为 1.964。词频继续增加，数值逐渐接近 2.2，而不会无限增长。

它仍然允许重复出现提供证据，但不允许重复无限兑换分数。

第五幕：长文章为什么不能无条件占便宜？

一篇三百词的文章里出现三次关键词，与一篇三万词的文章里出现三次关键词，提供的信息并不完全相同。

BM25 用文档长度相对平均长度的比例，调整词频的贡献。

当 b=0 时，不进行长度归一化。b 越接近 1，长度差异的影响越明显。保持其他条件相同，较长文档的同一次词频通常获得较低贡献。

这也不是“文章越短越好”。如果一个长文档包含更多与查询有关的内容，它仍然可能取得更高分。参数的选择需要在具体数据集上评估，不能仅凭看起来顺眼就宣布最优。

更不能把参数调大调小，当成了改善文章质量。搜索排序衡量的是一组信号，它无法直接证明文章正确、完整或适合某位读者。

第六幕：亲手运行一座有1200份文档的小型档案馆

下面的实验包含1200份合成的中文分词文档。它们由固定主题与词汇规则生成，不是外部真实文章。索引和评分都在当前浏览器计算。

输入“缓存 一致性”，比较 OR 和 AND；再切换原始计数 TF-IDF 与 BM25，观察结果顺序。调整 k₁、b 后，分数会立即重新计算。

实验展示每个查询词的倒排列表长度，也展示候选数量。你看到的不是预先写好的排名，而是索引检索和公式计算的结果。为了可读性只列出前十条；全部候选都会参与评分。

现在可以做三个小实验：

1. 查询“缓存”，看文档频率与结果数量。
2. 查询“缓存 一致性”，切换 AND，让两个倒排列表求交。
3. 选择 BM25，改变 b。观察同样包含关键词、长度不同的文章怎样变化。

这个实验按空格切词，输入“缓存一致性”会被视为一个完整词，与“缓存 一致性”不同。你可以用这个差别亲自验证：分词不是一个可忽略的界面细节。

第七幕：自己写一个可以核对分数的版本

下面的 Python 只使用标准库，实现相同的正值 IDF 与 BM25 计分公式。它保留完整倒排索引；本例按 OR 语义返回候选，查询词去重。

from collections import Counter, defaultdict
import math


def build_index(documents):
    postings = defaultdict(dict)
    lengths = {}
    for doc_id, text in documents.items():
        counts = Counter(text.lower().split())
        lengths[doc_id] = sum(counts.values())
        for term, count in counts.items():
            postings[term][doc_id] = count
    return dict(postings), lengths


def search(documents, query, k1=1.2, b=0.75):
    if k1 < 0 or not 0 <= b <= 1:
        raise ValueError("invalid BM25 parameters")
    postings, lengths = build_index(documents)
    n = len(documents)
    avgdl = sum(lengths.values()) / n if n else 0
    if not avgdl:
        return []
    scores = defaultdict(float)
    for term in set(query.lower().split()):
        hits = postings.get(term, {})
        df = len(hits)
        if not df:
            continue
        idf = math.log(1 + (n - df + 0.5) / (df + 0.5))
        for doc_id, frequency in hits.items():
            norm = 1 - b + b * lengths[doc_id] / avgdl
            scores[doc_id] += (
                idf * frequency * (k1 + 1)
                / (frequency + k1 * norm)
            )
    return sorted(scores.items(), key=lambda pair: (-pair[1], pair[0]))


docs = {
    "D1": "缓存 一致性 协议",
    "D2": "缓存 命中 性能",
    "D3": "分布式 一致性 协议",
}
print(search(docs, "缓存 一致性"))
# D1 同时匹配两个词，分数约为 0.9400。
# D2、D3 各匹配一个词，分数均约为 0.4700。

构建索引需要读取文档中的词。查询不再重新解析每篇文章，而是遍历查询词的倒排记录并累计分数。若把倒排表和统计信息预先保存，便可以让许多查询复用一次建索引的工作。

这个教学版把每次 search 都重新建索引，是为了让函数独立可运行。网站实验则在初始化时建好索引。真实系统还需要处理更新、删除、并发访问、存储和评测等问题。

第八幕：PageRank 与 BM25，能不能互相代替？

想象一篇广受引用的数学文章。它很重要，但如果你想学习做面包，它仍然不是合适的答案。

反过来，一篇新写的面包教程可能几乎没有入链，却恰好解释了你关心的问题。

PageRank 从链接图提供重要性信号。BM25 从文档词项与查询的匹配提供相关性信号。两者观察的是不同方面，不能把其中一个的高分直接当作另一个问题的答案。

在概念上，我们可以先用倒排索引筛选候选，再综合词项相关性、链接信号等信息。实际怎样组合与校准，需要明确目标、数据和评测，本章不把简单加权公式冒充任何搜索公司的生产系统。

还要记住：词项匹配不等于理解全部语义。“汽车”与“轿车”可能表达相近意思，却没有相同的字面词。否定、讽刺和上下文也可能让高匹配分数产生误导。一个运行得很快的排序器，仍然可能把错误答案放在前面。

终章挑战：关键词复制一千次，发生了什么？

某个页面为了提高排名，把“缓存”重复了一千次。

在本章的原始计数 TF-IDF 下，词频贡献会线性增长。

在 BM25 下，词频部分趋于饱和；如果文档因此变得很长，长度归一化也会介入。但这不等于 BM25 已经解决作弊，它只是限制了一种分数增长方式。

如果用户查询还包含“一致性”，而页面只重复“缓存”，它也没有凭空获得另一个词的匹配证据。

请自己回答：为什么“包含关键词”“与问题相关”“内容可信”必须作为三个不同的判断？

尾声：让信息更容易找到，也要知道答案从哪里来

从词到文档的倒排目录，让我们不必每次走遍整个档案馆。

IDF 让我们在当前集合中衡量词的区分能力。

词频与长度归一化，让排序不再只是简单数数。

这些方法共同完成了一件很实际的事：在大量候选里，把更值得检查的内容放到前面。

我们已经从第一章的内存布局，一路走到分布式计算和信息检索。每一步似乎都让计算机更有能力。但还有一个问题不能回避：是不是所有问题，最终都能靠更好的算法解决？

下一章，第30章，也是全系列终章。我们将回到图灵的研究，讨论计算的能力与边界。

本章研究资料

• Karen Spärck Jones（1972）：A Statistical Interpretation of Term Specificity and Its Application in Retrieval
• Spärck Jones / Robertson：IDF 研究资料页
• Robertson 与 Zaragoza（2009）：The Probabilistic Relevance Framework: BM25 and Beyond
• Manning、Raghavan、Schütze：Introduction to Information Retrieval，官方教材

本章所用排序数值是教学模型的实际计算结果。历史叙述依据上述资料，示例和交互实验为本次原创补充。