这是一个非常敏锐的质疑!你之所以觉得“这怎么跟帕累托最优有关系呢”,是因为在传统的经济学或运筹学中,帕累托最优通常意味着“资源分配已经达到了某种最优状态”。而在 Lucene 这里,它其实是被借用来解决一个多维目标冲突(Multi-objective Optimization)的问题。
我们可以把整个推导过程拆解成以下 3 步,你就能瞬间看透它们之间的数学联系:
1. 目标冲突:Freq 和 Norm 是“跷跷板”
在 BM25 打分公式中,文档的最终得分是由 Freq(词频)和 Norm(文档长度归一化)共同决定的:
* Freq 越高,得分越高。
* Norm 越低(文档越短),得分越高。
这两个指标在影响得分时,方向是相反的。这就构成了一个典型的多目标优化问题:你不可能找到一个文档,它的 Freq 是全局最高,同时 Norm 又是全局最低。
2. 什么是“支配(Dominated)”?
在帕累托理论中,有一个核心概念叫“支配”。
假设有两个文档 A 和 B,如果 A 的 Freq 大于等于 B 的 Freq,并且 A 的 Norm 小于等于 B 的 Norm(即 A 的文档比 B 短),同时至少有一项是严格优于 B 的。
结论:A 的得分永远、绝对会大于 B 的得分。
这时候,我们就说 A 支配了 B(A dominates B)。
既然 A 的得分永远比 B 高,那么在评估这个 Block 的“最高可能得分”时,B 还有存在的价值吗?完全没有。B 就是一个纯粹的“累赘”。
3. 帕累托前沿 = 潜在的最高分集合
把所有被支配的“累赘”(比如 Freq 低且文档长的文档)全部剔除掉,剩下的那些互不支配的文档组合,在数学上就构成了帕累托前沿(Pareto Frontier)。
回到 Lucene 的代码:
assert impact.freq > previous.freq;
assert Long.compareUnsigned(impact.norm, previous.norm) > 0;
这段代码在断言什么?它在断言:我存下来的每一个 Impact,它的 Freq 都比前一个大,它的 Norm 也比前一个大(文档更长)。
为什么必须这样?
假设前一个是 (Freq=10, Norm=5),如果下一个存的是 (Freq=12, Norm=4)。
这说明下一个文档不仅词频更高,而且文档更短!那它必然得分更高,它就应该把前一个 (10, 5) 给支配掉。
既然前一个被支配了,就不该存在于这个列表里。所以,为了让列表里的点互不支配,当 Freq 上升时,Norm 必须跟着上升(即文档变长,牺牲 Norm 换取 Freq)。
总结
你觉得“没关系”,可能是因为平时见到的帕累托最优是静态的。但在 Lucene 中:
* 帕累托最优在这里被具象化为:在 (Freq, Norm) 这个二维空间里,剔除掉所有“既不如别人词频高,又比别人文档长”的废柴文档。
* 留下来的这条“帕累托前沿线”,就是当前 Block 里所有有可能成为最高分的文档的集合。
查询时,引擎不需要看 Block 里的几千个文档,它只需要沿着这条“帕累托前沿线”算一下,就能知道这个 Block 的得分天花板(Block Max Score)到底在哪里。
这样解释,是不是就把“帕累托最优”和“Lucene 存 Freq/Norm”完美地闭环了?
要不要我展开讲讲查询时是怎么用这条帕累托前沿线算出 Block Max Score 的?理论闭环了,实战逻辑也补上会更完整。