返回专栏
· 15 分钟阅读

BM25 全文检索原理:从倒排索引到相关性评分的完整机制


一、什么是 BM25?

BM25(Best Matching 25)是一种基于概率信息检索框架的相关性评分算法,主要用于衡量查询(Query)与文档(Document)之间的相关程度。

它广泛应用于:

  • 搜索引擎全文检索。
  • 企业知识库搜索。
  • 文档管理系统。
  • 日志与技术文档检索。
  • RAG 系统中的关键词召回。
  • 向量检索与关键词检索的混合召回。

BM25 的核心思想是:

一个文档与查询越相关,其查询词在文档中出现得越合理、越具有区分度,文档就应该获得越高的相关性评分。

例如,用户搜索:

Java 线程池如何控制并发数量?

搜索系统可能找到以下文档:

文档 内容
A Java 线程池通过核心线程数和最大线程数控制并发
B Java 并发编程中的线程同步机制
C Python 线程池的使用方法
D Java 基础语法与面向对象编程

BM25 会综合考虑查询词在文档中的出现情况,以及这些词在整个文档集合中的区分能力,为文档计算相关性分数。

与简单的关键词匹配不同,BM25 不只是统计查询词出现了多少次,还会考虑词频饱和和文档长度。

1.1 BM25 的核心组成

BM25 主要涉及三个概念:

概念 英文 主要作用
词频 Term Frequency,TF 衡量查询词在文档中出现的频率
逆文档频率 Inverse Document Frequency,IDF 衡量词语在整个文档集合中的区分能力
文档长度归一化 Document Length Normalization 调整不同长度文档之间的评分偏差

这三个因素共同决定文档的相关性评分。

1.2 BM25 与简单关键词匹配的区别

简单关键词匹配通常只判断查询词是否出现在文档中。

例如:

查询:Java 线程池

文档 A:Java 线程池的核心参数
文档 B:Java 线程池的线程管理机制
文档 C:Java 的基本语法

如果只判断关键词是否存在,A、B、C 都可能获得一定的匹配结果。

BM25 则会进一步考虑:

  • 查询词出现了多少次。
  • 查询词在整个文档集合中是否常见。
  • 文档本身有多长。
  • 高频词是否已经达到收益饱和。

因此,BM25 能够对匹配结果进行更合理的排序。


二、BM25 的底层基础:倒排索引

BM25 负责计算相关性分数,但在大规模全文检索系统中,通常不会逐篇扫描所有文档。

搜索引擎一般使用倒排索引(Inverted Index)快速定位包含查询词的文档。

2.1 什么是倒排索引?

倒排索引是一种以词项为入口组织文档信息的数据结构。

传统文档存储通常按照文档组织:

文档 A:Java 线程池 并发控制
文档 B:Java 锁机制 线程同步
文档 C:Python 线程池 并发处理

倒排索引则反过来,以词项为索引入口:

Java:
    文档 A
    文档 B

线程池:
    文档 A
    文档 C

并发:
    文档 A
    文档 C

锁机制:
    文档 B

这种结构可以快速找到包含指定词项的文档,而不需要扫描全部文档内容。

2.2 倒排索引的基本结构

倒排索引主要包含两个部分:

词典(Dictionary)

保存经过分析处理后的词项及其索引信息。

倒排列表(Posting List)

保存包含该词项的文档记录,以及相关统计信息。

例如:

{
  "java": [
    {
      "doc_id": "A",
      "term_frequency": 3,
      "positions": [1, 5, 9]
    },
    {
      "doc_id": "B",
      "term_frequency": 2,
      "positions": [2, 7]
    }
  ],
  "thread_pool": [
    {
      "doc_id": "A",
      "term_frequency": 2,
      "positions": [3, 8]
    }
  ]
}

其中:

  • doc_id:文档标识。
  • term_frequency:词项在文档中出现的次数。
  • positions:词项在文档中的位置。

实际搜索引擎通常采用压缩、分块、跳表或其他优化结构存储倒排列表,并不一定直接使用上述 JSON 形式。

2.3 倒排索引如何建立?

建立倒排索引通常包含以下步骤:

  1. 获取原始文档。
  2. 对文档进行文本分析。
  3. 执行分词、规范化等处理。
  4. 统计词项出现频率。
  5. 记录词项所属文档。
  6. 构建倒排列表。
  7. 保存文档长度和集合统计信息。
flowchart TD
    A["原始文档集合"] --> B["文本解析"]
    B --> C["分词与文本规范化"]
    C --> D["生成词项序列"]
    D --> E["统计词频与词项位置"]
    E --> F["按词项组织文档记录"]
    F --> G["构建倒排列表"]
    G --> H["保存文档长度与集合统计"]
    H --> I["生成倒排索引"]

    style A fill:#DCEFE5,stroke:#4F8B70,color:#24563F
    style B fill:#EAF3EC,stroke:#83A995,color:#315D49
    style C fill:#EAF3EC,stroke:#83A995,color:#315D49
    style D fill:#EAF3EC,stroke:#83A995,color:#315D49
    style E fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style F fill:#EAF3EC,stroke:#83A995,color:#315D49
    style G fill:#EAF3EC,stroke:#83A995,color:#315D49
    style H fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style I fill:#E5F0E9,stroke:#83A995,color:#315D49

2.4 倒排索引与 BM25 的关系

需要区分两个概念:

  • 倒排索引负责快速找到包含查询词的候选文档。
  • BM25 负责计算候选文档与查询之间的相关性分数。

两者协同工作。

倒排索引解决的是检索效率问题,BM25 解决的是相关性排序问题。


三、BM25 的数学公式

BM25 的经典评分公式为:

\operatorname{BM25}(D,Q) = \sum_{q_i\in Q} IDF(q_i) \cdot \frac{ f(q_i,D)(k_1+1) }{ f(q_i,D)+ k_1 \left( 1-b+b\frac{|D|}{avgdl} \right) }

其中:

符号 含义
D 当前待评分文档
Q 用户查询
q_i 查询中的第 i 个词项
f(q_i,D) 查询词在文档 D 中的词频
( D
avgdl 文档集合的平均长度
k_1 控制词频饱和程度的参数
b 控制文档长度归一化程度的参数
IDF(q_i) 查询词的逆文档频率

公式可以拆成三个核心部分:

  1. IDF:判断查询词的重要程度。
  2. TF 饱和:判断词频对相关性评分的贡献。
  3. 长度归一化:调整文档长度造成的评分偏差。

理解这三个部分,就能理解 BM25 的主要工作机制。


四、第一部分:TF 词频与词频饱和

TF(Term Frequency)表示某个词项在文档中出现的次数。

例如:

文档 A:
Java 线程池可以管理线程。
线程池支持并发控制。
线程池可以复用线程。

文档 B:
Java 提供了多种并发编程机制。

如果查询词是“线程池”:

  • 文档 A 中出现 3 次。
  • 文档 B 中出现 0 次。

从词频角度看,文档 A 应该获得更高的匹配贡献。

但如果只根据词频进行评分,会产生一个问题:

词语出现次数越多,分数就会无限增长。

这并不合理。

4.1 为什么需要词频饱和?

假设查询词“Java”在一篇文档中出现:

出现次数 简单词频
1 1
5 5
10 10
20 20
100 100

如果直接使用词频,出现 100 次的文档会获得出现 1 次文档的 100 倍分数。

但对于搜索相关性而言:

  • 从 0 次增加到 1 次,可能非常重要。
  • 从 1 次增加到 2 次,通常仍然有价值。
  • 从 20 次增加到 21 次,新增价值可能已经很小。

也就是说,词频对相关性的贡献应逐渐趋于饱和。

4.2 BM25 的词频饱和公式

先忽略文档长度归一化,BM25 的词频部分可以写成:

TF_{\text{BM25}} = \frac{f(k_1+1)}{f+k_1}

其中:

  • f:查询词在文档中的词频。
  • k_1:控制饱和速度的参数。

当词频增加时,TF 贡献会逐渐接近上限:

\lim_{f\to\infty} \frac{f(k_1+1)}{f+k_1} = k_1+1

因此,BM25 不会因为某个词重复出现大量次数,就无限提高文档评分。

4.3 k1 参数的作用

k_1 控制词频饱和速度。

一般情况下:

  • k_1 较小:词频更快达到饱和。
  • k_1 较大:词频增加带来的贡献持续时间更长。

常见取值范围大致在 1.2 到 2.0 左右,但并不是固定标准,应结合具体检索任务进行评估。

4.4 词频饱和示例

假设:

k_1=1.5

词频贡献为:

TF= \frac{2.5f}{f+1.5}

不同词频对应的结果:

词频 f TF 贡献
1 1.000
2 1.429
3 1.667
5 1.923
10 2.174
20 2.326
100 2.463

可以观察到:

词频从 1 增加到 5,评分贡献明显增长;但从 20 增加到 100,贡献增长已经很有限。

这就是词频饱和机制。


五、第二部分:IDF 逆文档频率

IDF(Inverse Document Frequency)用于衡量一个词在整个文档集合中的区分能力。

一个词在越多文档中出现,通常越难帮助系统区分不同文档。

反过来,一个词越少见,往往越具有区分价值。

5.1 为什么需要 IDF?

假设一个知识库中有 10000 篇文档。

查询:

Java 线程池参数配置

不同词项的分布可能如下:

词项 包含该词的文档数
Java 6000
线程池 800
参数 4000
配置 3000
ThreadPoolExecutor 50

其中:

  • Java 出现在大量文档中。
  • 参数和配置也比较常见。
  • ThreadPoolExecutor 相对少见。

如果某个词出现在几乎所有文档中,它的区分能力就比较弱。

BM25 通过 IDF 对不同词项赋予不同权重。

5.2 IDF 的经典公式

BM25 常见的一种 IDF 形式为:

IDF(q_i) = \ln \left( 1+ \frac{ N-n(q_i)+0.5 }{ n(q_i)+0.5 } \right)

其中:

  • N:文档集合中的文档总数。
  • n(q_i):至少包含查询词 q_i 的文档数量。
  • \ln:自然对数。

这里需要注意:

n(q_i) 统计的是包含该词的文档数量,而不是该词在所有文档中出现的总次数。

5.3 IDF 的计算示例

假设:

N=10000

某个词出现在 100 篇文档中:

n(q_i)=100

代入公式:

IDF(q_i) = \ln \left( 1+ \frac{10000-100+0.5}{100+0.5} \right)
IDF(q_i)\approx4.60

再假设另一个词出现在 8000 篇文档中:

n(q_i)=8000

则:

IDF(q_i) = \ln \left( 1+ \frac{10000-8000+0.5}{8000+0.5} \right)
IDF(q_i)\approx0.22

对比可知:

  • 只出现在少量文档中的词,IDF 较高。
  • 出现在大量文档中的词,IDF 较低。

因此,稀有词通常具有更高的区分权重。

5.4 为什么 IDF 公式中有 0.5?

公式中的 0.5 属于平滑处理的一部分。

它能够避免某些边界情况下出现除零等问题,并使 IDF 计算更加稳定。

例如:

当一个词出现在全部文档中时:

n(q_i)=N

如果不进行适当平滑,IDF 的数值可能出现不合理的边界行为。

需要注意,BM25 在不同搜索系统中可能采用不同的 IDF 实现或变体。上面给出的是经典 Robertson 风格的 BM25 IDF 形式,不应假设所有搜索引擎的内部实现完全一致。

5.5 IDF 的工程意义

IDF 对搜索质量非常重要。

例如,查询:

ERR_CONNECTION_RESET 网络错误

其中:

  • “网络”是较常见的词。
  • “错误”也是较常见的词。
  • “ERR_CONNECTION_RESET”通常具有较强的区分能力。

合理的 IDF 能够提升精确术语在相关性排序中的影响力。


六、第三部分:文档长度归一化

BM25 的第三个重要机制是文档长度归一化。

它用于解决不同长度文档之间的评分偏差。

6.1 为什么文档长度会影响评分?

假设有两个文档:

文档 A:
Java 线程池可以控制线程数量。

文档 B:
Java 线程池可以控制线程数量。
Java 线程池可以管理任务队列。
Java 线程池可以复用工作线程。
Java 线程池可以配置拒绝策略。
Java 线程池可以控制并发执行。
……

文档 B 比文档 A 长得多。

如果只考虑词频,长文档往往有更多机会出现查询词,因此可能获得更高的分数。

但长文档不一定比短文档更加相关。

BM25 通过文档长度归一化,对这种偏差进行调整。

6.2 文档长度归一化公式

BM25 中的长度调整项为:

1-b+b\frac{|D|}{avgdl}

其中:

  • |D|:当前文档长度。
  • avgdl:整个文档集合的平均长度。
  • b:长度归一化参数。

当:

|D|=avgdl

则:

1-b+b\frac{|D|}{avgdl}=1

此时文档长度不会额外改变词频部分的分母。

6.3 b 参数的作用

b 控制文档长度归一化程度。

通常:

0\leq b\leq1

不同取值的含义:

b 值 作用
0 不进行文档长度归一化
0.5 进行部分长度归一化
0.75 常见默认取值之一
1 完全按照文档长度比例进行归一化

当 b=0:

1-b+b\frac{|D|}{avgdl}=1

文档长度不再参与调整。

当 b=1:

1-b+b\frac{|D|}{avgdl} = \frac{|D|}{avgdl}

文档长度会完整参与归一化。

6.4 长文档与短文档的影响

假设:

avgdl=100
b=0.75

对于长度为 50 的文档:

1-0.75+0.75\times\frac{50}{100} =0.625

对于长度为 200 的文档:

1-0.75+0.75\times\frac{200}{100} =1.75

在其他条件相同的情况下:

  • 短文档的长度调整项较小。
  • 长文档的长度调整项较大。

由于长度调整项位于 BM25 词频分式的分母中,因此长文档通常会受到更强的长度惩罚。

不过,实际分数仍然取决于词频、IDF 和其他参数,不能仅根据文档长度判断最终排序。


七、完整理解 BM25 的评分机制

现在将 TF、IDF 和文档长度归一化结合起来。

完整公式:

\operatorname{BM25}(D,Q) = \sum_{q_i\in Q} IDF(q_i) \cdot \frac{ f(q_i,D)(k_1+1) }{ f(q_i,D)+ k_1 \left( 1-b+b\frac{|D|}{avgdl} \right) }

可以将其理解为:

每个查询词分别计算贡献,再将所有查询词的贡献累加,得到文档的最终评分。

7.1 评分过程拆解

假设查询为:

Java 线程池

文档为:

Java 线程池能够管理工作线程,并通过线程池参数控制并发数量。

系统需要分别计算:

  • Java 对该文档的贡献。
  • 线程池对该文档的贡献。

然后将两部分相加:

Score(D,Q) = Score(Java,D) + Score(线程池,D)

其中每个词项的评分都包含 IDF、词频和长度归一化。

7.2 完整评分流程

flowchart TD
    A["用户提交查询"] --> B["查询文本分析与分词"]
    B --> C["提取查询词项"]
    C --> D["倒排索引查找候选文档"]
    D --> E["读取词频与文档长度"]
    E --> F["计算查询词 IDF"]
    F --> G["计算词频饱和"]
    G --> H["执行文档长度归一化"]
    H --> I["累加各查询词评分"]
    I --> J["得到 BM25 分数"]
    J --> K["按分数降序排序"]
    K --> L["返回 Top-K 文档"]

    style A fill:#DCEFE5,stroke:#4F8B70,color:#24563F
    style B fill:#EAF3EC,stroke:#83A995,color:#315D49
    style C fill:#EAF3EC,stroke:#83A995,color:#315D49
    style D fill:#EAF3EC,stroke:#83A995,color:#315D49
    style E fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style F fill:#EAF3EC,stroke:#83A995,color:#315D49
    style G fill:#EAF3EC,stroke:#83A995,color:#315D49
    style H fill:#EAF3EC,stroke:#83A995,color:#315D49
    style I fill:#EAF3EC,stroke:#83A995,color:#315D49
    style J fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
    style K fill:#EAF3EC,stroke:#83A995,color:#315D49
    style L fill:#E5F0E9,stroke:#83A995,color:#315D49

八、BM25 完整计算示例

通过一个具体例子理解 BM25 的计算过程。

假设文档集合中有 1000 篇文档,用户查询:

Java 线程池

当前需要计算文档 A 的相关性。

文档 A:

Java 线程池能够管理工作线程,线程池可以控制并发任务数量。

假设经过分词后,查询包含两个词项:

Java
线程池

已知统计数据:

参数 Java 线程池
文档集合总数 N 1000 1000
包含该词的文档数 n 600 100
当前文档中的词频 f 1 2

另外:

|D|=80
avgdl=100
k_1=1.5
b=0.75

8.1 计算长度归一化项

K= 1-b+b\frac{|D|}{avgdl}

代入:

K= 1-0.75+0.75\times\frac{80}{100}
K=0.85

8.2 计算 Java 的 IDF

IDF(Java) = \ln \left( 1+ \frac{1000-600+0.5}{600+0.5} \right)
IDF(Java)\approx0.511

8.3 计算线程池的 IDF

IDF(线程池) = \ln \left( 1+ \frac{1000-100+0.5}{100+0.5} \right)
IDF(线程池)\approx2.299

可以看到,“线程池”出现的文档更少,因此 IDF 更高。

8.4 计算 Java 的词频贡献

TF(Java) = \frac{1\times(1.5+1)}
TF(Java)\approx1.075

因此:

Score(Java) = 0.511\times1.075
Score(Java)\approx0.549

8.5 计算线程池的词频贡献

TF(线程池) = \frac{2\times(1.5+1)}
TF(线程池)\approx1.639

因此:

Score(线程池) = 2.299\times1.639
Score(线程池)\approx3.768

8.6 计算最终 BM25 分数

BM25(D,Q) = Score(Java)+Score(线程池)
BM25(D,Q) \approx0.549+3.768
\boxed{BM25(D,Q)\approx4.317}

这个结果说明,在给定统计数据和参数的条件下,文档 A 与查询具有一定的相关性。

需要注意,BM25 分数不是概率,也没有统一的最大值。它主要用于同一检索系统、相同评分配置下的候选文档排序。


九、BM25 的实际实现

理解公式之后,可以通过 Python 实现一个简化版本。

下面的实现假设输入已经完成分词,并且查询与文档都使用相同的词项规范化规则。