WAND 和 MAXSCORE 简介
如何使用倒排索引快速识别析取查询的前 k 个匹配项？这就是 WAND1 和 MAXSCORE2 算法试图解决的问题。这两种算法基于相同的思想：利用每个词语的最大影响分数（特定词语对整体分数的最大贡献），从而跳过其分数不可能高于当前第 k 个最佳匹配项（以下称为“最小竞争分数”）的匹配项。例如，如果您正在搜索包含 the 或 fox 的匹配项，而 the 对分数的最大贡献为 0.2，而最小竞争分数为 0.5，那么就没有必要再评估仅包含 the 的匹配项了，因为它们没有机会成为最佳匹配项。
但是，WAND 和 MAXSCORE 具有不同的性能特征：WAND 通常比 MAXSCORE 评估的匹配项更少，但每个匹配项的开销更高。这使得 MAXSCORE 在较高的 k 值或较多词语的情况下通常表现更好 - 当跳过匹配项很困难时，而 WAND 在其他情况下表现更好。
Block-max MAXSCORE & Lucene 中的 MAXSCORE
虽然 Lucene 最初实现了一种名为 block-max WAND 的 WAND 变体，但后来它被 MAXSCORE 的较低开销所吸引，并于 2022 年 7 月开始在顶级析取中使用 block-max MAXSCORE（Lucene 夜间基准测试中的注释 EN）。MAXSCORE 算法相当简单：它按最大影响分数递增的顺序对词语进行排序，并将它们分成两组：基本词语和非基本词语。非基本词语是指最大影响分数较低且最大分数之和小于最小竞争分数的词语。基本词语是所有其他词语。基本词语用于查找候选匹配项，而非基本词语仅用于计算候选匹配项的分数。
MAXSCORE 使用示例
让我们举个例子：您正在搜索 the quick fox，每个词语的最大影响分数分别为 the 的 0.2、quick 的 0.5 和 fox 的 1。当您开始收集匹配项时，最小竞争分数为 0，因此所有词语都是基本词语，没有词语是非基本词语。然后在某个时刻，最小竞争分数达到例如 0.3，这意味着仅包含 the 的匹配项没有机会成为前 k 个匹配项。the 从基本词语集合移动到非基本词语集合，查询有效地运行为 (the) +(quick fox)。这里的 + 符号用于表示查询子句是必需的，例如在 Lucene 的经典查询解析器 中。换句话说，从那时起，查询将只匹配包含 quick 或 fox 的匹配项，并且将仅使用 the 来计算最终分数。下表总结了 MAXSCORE 考虑的情况
| 最小竞争分数区间 | 查询运行为 |
|---|---|
| [0, 0.2] | +(the quick fox) |
| (0.2, 0.7] | (the) +(quick fox) |
| (0.7, 1.7] | (the quick) +(fox) |
| (1.7, +Infty) | 不再有匹配项 |
当最小竞争分数大于所有词语的所有最大影响分数之和时，就会发生最后一种情况。在常规 MAXSCORE 中，这种情况通常不会发生，但在 block-max MAXSCORE 的某些块中可能会发生。
改进 MAXSCORE 以对词语进行交集
WAND 比 MAXSCORE 做得更好的一点是，随着最小竞争分数的增加，它会逐渐减少查询的析取评估，并逐渐增加合取评估，从而实现更多跳过。这引发了一个问题：是否可以改进 MAXSCORE 以同样对词语进行交集？答案是肯定的：例如，如果最小竞争分数为 1.3，那么如果匹配项不匹配 quick 和 fox，则该匹配项不会具有竞争力。因此，我们修改了我们的 block-max MAXSCORE 实现，以考虑以下情况
| 最小竞争分数区间 | 查询运行为 |
|---|---|
| [0, 0.2] | +(the quick fox) |
| (0.2, 0.7] | (the) +(quick fox) |
| (0.7, 1.2] | (the quick) +(fox) |
| (1.2, 1.5] | (the) +quick +fox |
| (1.5, 1.7] | +the +quick +fox |
| (1.7, +Infty) | 不再有匹配项 |
现在有趣的问题是我们添加的这些新情况是否可能发生？答案取决于您的分数上限有多好、您的实际 k 值、词语是否确实存在共同的匹配项等，但它似乎在实践中尤其经常在具有两个词语或结合了两个高分词语和零个或多个低分词语（例如停用词）的查询中触发，例如我们在上述示例中看到的查询。预计这将在许多查询日志中涵盖相当数量的查询。
实现此 优化 在 Lucene 的夜间基准测试中产生了明显的改进（注释 FU），请参阅 OrHighHigh（加速 11%）和 OrHighMed（加速 6%）。它已在 Lucene 9.9 中发布，并应包含在 Elasticsearch 8.12 中。我们希望您能享受速度提升！
脚注
- Broder, A. Z., Carmel, D., Herscovici, M., Soffer, A., & Zien, J. (2003, November)。使用两级检索过程进行高效查询评估。在第十二届国际信息与知识管理会议论文集中（第 426-434 页）。 ↩
- Turtle, H., & Flood, J. (1995)。查询评估：策略和优化。信息处理与管理，31（6），831-850。 ↩
相关内容
