BM25搜索优化之 Block-WeakAnd算法

"喂！搞搜索的！"

"你的BM25还在龟速爬行吗？"

"这篇Block-WeakAnd算法就是你的火眼金睛！"

"比俺老孙的七十二变还灵！"

"把搜索优化得比我的筋斗云还快！"

"效率高得能让玉皇大帝都点赞！"

"那些说'BM25过时'的..."

"都是没见识过这招的呆瓜！"

"紫霞仙子看了都得说：猴哥，这算法绝了！"

"再不看？"

"你的搜索速度就要比猪八戒减肥还慢啦！"

一个跟头翻出十万八千里

"俺去优化搜索啦！"

BM25搜索优化之 Block-WeakAnd算法

我们来通俗易懂地聊聊计算BM25分数的Block-WeakAnd算法。如何快速找到与query最相关的top-k文档?

涉及项目: https://deepwiki.com/tensorchord/VectorChord-bm25/2-core-components

BM25分数计算的Block-WeakAnd算法

在搜索引擎中，我们需要根据用户查询（Query）找出最相关的文档（Document），并给它们打分。BM25（Best Match 25）是一种非常流行的打分算法。

核心问题： 语料库（所有文档）非常庞大，用户每次查询时，不可能把所有文档都完整计算一遍BM25分数。那样太慢了！我们需要一种高效的方法来快速找出Top-K（前K个）最相关的文档。

Block-WeakAnd（Block-Wand） 就是为了解决这个效率问题而诞生的算法之一。

1. 为什么需要它？

想象一下，你在一个巨大的图书馆里找10本最符合你主题的书。

• 传统做法： 把所有书都翻一遍，详细阅读内容，然后打分，最后选出前10本。—— 太慢了！
• Block-WeakAnd做法：
• WeakAnd（Wand）部分： 你设定一个门槛。如果你看一本书的封面、目录甚至前几页，就发现它“即使内容完全符合要求，最高也只能得80分”，而你已经找到了几本90分的书，那你就不再看这本80分的书了，直接跳过。这叫剪枝（Pruning）。
• Block部分： 你不是一本一本看，而是把图书馆的书分成很多区域（Blocks）。你在一个区域里，高效地处理这个区域的书。比如，你发现这个区域有几本书肯定能得高分，有些书一看就不行，就直接跳过。

2. 算法核心思想

Block-WeakAnd结合了两种优化策略：

1. WeakAnd (WAND) 弱且（Weak-AND）:

• 目标： 快速估计一个文档的最高可能得分（Upper Bound）。
• 原理： 对于每个查询词，我们知道它在一个文档中能贡献的最大分数（例如，如果它只出现一次，但这个词本身很重要）。
• 剪枝： 当我们遍历文档时，我们可以计算出该文档目前为止已经匹配到的词的分数总和，再加上它所有未匹配但有可能匹配的词的最大可能贡献。如果这个“最高可能得分”仍然低于我们当前已找到的Top-K文档中的最低分，那么这个文档就不可能进入Top-K，可以直接跳过，无需计算完整分数。

• Block（块）处理:

• 目标： 更高效地遍历倒排索引。
• 原理： 倒排索引（Inverted Index）是搜索引擎的基础，它存储了每个词出现在哪些文档中。为了提高读取效率，这些倒排列表通常被分成固定大小的“块”（Block）。
• 优势： 当我们处理一个查询时，我们可以在一个块内进行更紧凑、更并行的操作。例如，CPU的缓存利用率更高，甚至可以利用SIMD指令（单指令多数据）来加速计算。

3. Block-WeakAnd 工作流程 (简化版)

1. 查询分析： 用户输入查询词，分词，并计算每个查询词的BM25权重（重要性）。
2. 词排序： 根据查询词的权重（或它们在文档中贡献的最大分数），将查询词进行排序。通常重要的词优先处理。
3. 初始化Top-K： 维护一个最小堆（Min-Heap），里面存放当前已找到的Top-K文档及其BM25分数。堆顶是当前Top-K中的最低分数（MinScore）。
4. 遍历文档块：
• WeakAnd上限计算： 快速计算 Doc_i 的WeakAnd上限分数（Upper Bound, UB）。这个UB是 Doc_i 已经匹配到的词的分数，加上所有未匹配但有可能匹配的词的最大可能贡献。
• 剪枝判断： 如果 UB 小于当前的 MinScore，那么 Doc_i 无论如何都不可能进入Top-K。直接跳过Doc_i，处理块中的下一个文档。
• 完整计算： 如果 UB 大于或等于 MinScore，说明 Doc_i 有可能进入Top-K。此时，计算 Doc_i 的完整BM25分数。
• 更新Top-K： 如果 Doc_i 的完整分数大于 MinScore，则将其加入Top-K堆，并更新 MinScore。
• 算法会同时（或协调地）遍历所有查询词的倒排列表。
• 它会跳跃式地前进，一次处理一个文档ID范围的块。
• 块内处理： 对于当前块中的每个文档 Doc_i：
• 返回结果： 当所有相关文档块都被处理完毕后，Top-K堆中的文档就是最终结果。

4. Mermaid 图表解释







5. 总结

Block-WeakAnd算法通过提前预估文档的最高可能得分（WeakAnd）并在文档块级别进行高效处理（Block），大大减少了需要进行完整BM25计算的文档数量。它就像一个精明的筛选器：先快速淘汰掉那些“不可能”的文档，再对“有可能”的文档进行精确打分，从而实现大规模搜索场景下的高性能BM25打分。