【lucene核心】impacts的由来

在 Lucene 的 Impact 概念（出现在 `ImpactsEnum` / `Impact` 对象里）中：

字段 含义 

freq 当前 term 在该文档中出现了多少次（即词频 term frequency）。 

norm 当前 文档在该字段中的长度因子（即之前 norms 里保存的压缩长度值，用来归一化打分）。 

---

举个例子

文档 7：

- 字段 `title` 内容：`"lucene lucene search"`  

- 分词后：`lucene`(2 次)、`search`(1 次)

- 对 term `"lucene"` 的 `Impact`  

  - freq = 2（出现了 2 次）  

  - norm = 压缩后的字段长度 3（3 个 token）

---

一句话

- freq → term 在文档里的出现次数  

- norm → 文档在该字段的总 token 数（压缩后的长度因子）

/** Get the set of competitive freq and norm pairs, ordered by increasing freq and norm. */

  public Collection<Impact> getCompetitiveFreqNormPairs() {

    List<Impact> impacts = new ArrayList<>();

    int maxFreqForLowerNorms = 0;

    for (int i = 0; i < maxFreqs.length; ++i) {

      int maxFreq = maxFreqs[i];

      if (maxFreq > maxFreqForLowerNorms) {

        impacts.add(new Impact(maxFreq, (byte) i));

        maxFreqForLowerNorms = maxFreq;

      }

    }

    if (otherFreqNormPairs.isEmpty()) {

      // Common case: all norms are bytes

      return impacts;

    }

    TreeSet<Impact> freqNormPairs = new TreeSet<>(this.otherFreqNormPairs);

    for (Impact impact : impacts) {

      add(impact, freqNormPairs);

    }

    return Collections.unmodifiableSet(freqNormPairs);

}

这段代码的作用是：

把当前 term 所有可能出现的 “最大词频 + 对应 norm” 组合，按 freq 升序、norm 升序整理成一条紧凑的 “上限表”（Impact 列表），

供 Block-Max WAND 等跳表算法 在查询时快速判断 “剩下这些文档再也不可能超过当前阈值”，从而提前剪枝、加速 Top-k 检索。

---

1. 背景：为什么要 “competitive pairs”  

在 Block-Max WAND / MaxScore 算法里，必须知道 “一个块内最大可能的 score 是多少”。  

- 已知 score 只跟 freq（词频）和 norm（字段长度）有关。  

- 因此把 每个 norm level 对应的最大 freq 记录下来 → 形成 `(freq, norm)` 的上限数组。  

- 只要 当前阈值 大于块内最大的 `(freq, norm)` 上限，整个块即可跳过。

---

2. 代码拆读

2.1 先把 “简单情况” 处理掉  

```java

List<Impact> impacts = new ArrayList<>();

int maxFreqForLowerNorms = 0;

for (int i = 0; i < maxFreqs.length; ++i) {

  int maxFreq = maxFreqs[i]; // 对 norm = i 的最大词频

  if (maxFreq > maxFreqForLowerNorms) {

    impacts.add(new Impact(maxFreq, (byte) i));

    maxFreqForLowerNorms = maxFreq; // 保证单调递增

  }

}

```

- `maxFreqs[i]` 保存的是 “norm 为 i 的所有文档里，该 term 出现的 最大频次”。  

- 通过条件 `maxFreq > maxFreqForLowerNorms` 去掉冗余，确保列表严格按 `(freq ↑, norm ↑)` 排序。

2.2 再合并 “其他 norm”  

```java

if (otherFreqNormPairs.isEmpty()) {

  return impacts; // 全是 byte 值，直接返回

}

TreeSet<Impact> freqNormPairs = new TreeSet<>(otherFreqNormPairs);

for (Impact impact : impacts) {

  add(impact, freqNormPairs);

}

return Collections.unmodifiableSet(freqNormPairs);

```

- `otherFreqNormPairs` 里存的是非 byte 型 norm（罕见）或额外手工添加的组合。  

- 用 `TreeSet` 统一排序、去重，最终得到 全局有序且无冗余 的 competitive 列表。

---

3. 一句话总结  

`getCompetitiveFreqNormPairs()` 生成的就是 “score 上限表”（Impact 列表），

查询阶段用它来 快速判定某个文档块是否还有竞争力，从而实现 Block-Max WAND 的提前剪枝与加速。

不是“随着 norm 的增加取最大的 freq”那么简单，而是：

> 对每个 norm level，记录该 level 内出现的最大 freq，然后在所有 level 上再做一个“剪枝”：只有当某 level 的 maxFreq 比之前所有更低 level 的 maxFreq 都大时，才保留这个 (maxFreq, norm) 对。

这样做的目的：

- 保证最终列表 按 freq 严格递增，  

- 保证 norm 也单调递增，  

- 让 Block-Max WAND 在“从低打到高”的顺序里，能直接用 最大 freq 作为上限 来剪枝。

---

举个具体数字

假设：

norm (i) 该 norm 内最大 freq 

0 3 

1 5 

2 4 

3 6 

代码流程：

- i=0 → maxFreq=3 > 0 → 保留 (3, 0)  

- i=1 → maxFreq=5 > 3 → 保留 (5, 1)  

- i=2 → maxFreq=4 ≯ 5 → 丢弃  

- i=3 → maxFreq=6 > 5 → 保留 (6, 3)

最终 competitive 列表：

`(3,0), (5,1), (6,3)` —— 既 freq 递增，norm 也递增。

level 就是 norm 本身的整数值（byte 或 int），

在代码里直接体现为循环变量 `i` 和 `Impact` 构造器里的第二个参数 `norm`：

```java

for (int i = 0; i < maxFreqs.length; ++i) { // i 就是 level

    ...

    impacts.add(new Impact(maxFreq, (byte) i)); // (byte) i 就是 norm level

}

```

- `maxFreqs` 数组的下标 `i` 就对应 norm level 0、1、2 …。  

- 因此 level 没有额外存储，它就是 norm 的数值本身。

这是一种 “分层/分级上限（level-wise upper-bound）思想”，

在 Lucene 里具体对应 Block-Max WAND / MaxScore 这类 Top-k 查询剪枝算法。

---

1. 核心思想一句话  

> 把 每级（level = norm 值）内的最大可能得分 提前算成一张 单调递增的上限表，

搜索时 按表从小到大扫描，一旦发现剩余块的上限已经低于当前第 k 个结果的真实得分，就整段跳过，不再计算。

---

2. 算法家族

名称 出处 说明 

WAND Broder et al. 2003 经典倒排链跳跃算法 

Block-Max WAND Ding & Suel 2011 在倒排链的“块”内预存上限，块级跳过 

MaxScore Turtle & Flood 1995 类似思路，用于 Lucene 早期 

Lucene 8+ 实现 `ImpactsEnum` + `Impact` 把 norm-level 上限 预生成，驱动 Block-Max WAND 

---

3. 为什么要“分层”(level = norm)

- norm 越小 → 字段越短 → 相同词频的得分越高  

- 因此把 norm 离散化成若干 level，每级算一次 max freq  

- 对 Block-Max WAND：

  只要当前阈值 > level L 的 maxScore，所有 norm ≥ L 的文档都可以一次性跳过，节省大量 I/O 与计算。

---

4. 一句话总结

这段代码体现的算法思想就是 “Block-Max WAND 的分层上限剪枝”，

通过 norm level + max freq 生成单调递增的 Impact 表，实现 Top-k 查询中的早期终止与跳跃。

在 同一 term、同一词频（freq） 的情况下：  

- norm 越小 → 字段越短 → 该 term 的权重越大 → 得分越高。  

因此，  

> 在 `Impact` 表中，相同 freq 时，norm 越小，对应的潜在得分反而越高。  

这也是 Block-Max WAND 把 `(freq, norm)` 按 freq 升序 + norm 升序 排序后，就能用单调上限剪枝的根本原因：  

- 先处理 低频或长字段（高 norm）的块，它们的得分上限低，容易跳过；  

- 后处理 高频或短字段（低 norm）的块，上限高，需要真正计算。

对于impacts 跳表的高层是低层impacts的和是吧？

不是简单的“求和”关系，而是 “高层 impact 是对自己管辖区间内所有低层 impact 的最大值的上界”。

- 高层（higher level） 的 `Impact` 只是 该层所覆盖文档块内最大的 `(freq, norm)` 对。  

- 它保证：

  任何落在这个块里的文档，其真实 `(freq, norm)` 都不会超过这条高层记录的 `(freq, norm)`。  

- 因此搜索时可以 用高层 impact 直接做块级剪枝，而不必逐条遍历低层。

---

类比

- 高层 impact ≈ 块级“最大值”  

- 低层 impacts ≈ 块内真实值  

- 关系是 “max 覆盖”（max bound），而非 “累加”（sum）。

剪枝流程可以拆成 两步：

1. 高层剪枝：一次跳过整块  

2. 低层剪枝：在块内再逐条跳过

---

1. 高层剪枝（先发生）

- 搜索线程维护一个 当前第 k 名的阈值 `minCompetitiveScore`。  

- 从 高层 Impact 表 顺序扫描 `(maxFreq, maxNorm)`。  

- 把 `(maxFreq, maxNorm)` 代入 BM25 公式得到一个 “这块的最高可能得分” `upperBoundScore`。  

- 如果 `upperBoundScore < minCompetitiveScore` → 整块 4 篇文档直接丢弃，指针跳到下一高层块。

```

高层表顺序：(3,0) (5,2) (6,0) (7,1) …

            ↑

            只要这个上限 < 阈值，整块 0-3 全跳过

```

---

2. 低层剪枝（块内发生）

- 如果 `upperBoundScore ≥ minCompetitiveScore`，说明 块里可能还有候选，就进入该块。  

- 用低层的 `ImpactsEnum` 逐条读真正的 `(freq, norm)`；  

- 每读一条就 立即计算真实得分；  

- 一旦 真实得分 < minCompetitiveScore，就利用低层 跳表指针 跳到下一个可能大于阈值的文档，继续比较。

---

流程小结

```

高层 Impact 表

├─ block0 上限 < 阈值 → 整块跳过

├─ block1 上限 ≥ 阈值 → 进入块内

│ ├─ doc4 (7,1) 得分 ≥ 阈值 → 保留

│ ├─ doc5 (2,2) 得分 < 阈值 → 跳到下一条

│ └─ …

└─ …

```

高层 先快速丢大段，低层 再精准丢小段，这就是 Block-Max WAND 的剪枝节奏。

第 0 层（最底层）跳表也是以 block 为单位来剪枝的 —— 只不过这里的 block 已经是最细粒度的 “文档块”，而不是高层那种更大的逻辑块。

第 0 层的剪枝规则：

- 第 0 层的每个 block 会提前计算一个 该块内最大的 `(freq, norm)` 对（即该块内最高的 Impact）。  

- 这个 最大值 被用来估算 该 block 的最高可能得分 `upperBoundScore`。  

- 只要这个 `upperBoundScore < minCompetitiveScore`，整个 block 就可以直接跳过；  

- 否则，就必须逐文档处理（因为块内可能有文档得分 ≥ 阈值）。

---

用之前的例子具体说明：

假设第 0 层有 4 个 block（每块 4 篇文档）：

第 0 层 block 该块最大 Impact 估算最高得分 

block-0 `(5,2)` `score_upper0` 

block-1 `(7,1)` `score_upper1` 

block-2 `(6,0)` `score_upper2` 

block-3 `(4,3)` `score_upper3` 

- 如果 `minCompetitiveScore = 6.5`，而：

  - `score_upper0 = 5.1 < 6.5` → 整 block-0 直接跳过  

  - `score_upper1 = 7.2 ≥ 6.5` → 必须逐文档处理 block-1  

  - `score_upper2 = 6.0 < 6.5` → 整 block-2 直接跳过  

  - `score_upper3 = 4.8 < 6.5` → 整 block-3 直接跳过

---

一句话总结

第 0 层同样以 block 为单位做剪枝；

只要某个 最底层 block 的最高可能得分 低于当前阈值，就整块跳过，否则逐文档处理。

private float computeMaxScore(List<Impact> impacts) {

    float maxScore = 0;

    for (Impact impact : impacts) {

      maxScore = Math.max(scorer.score(impact.freq, impact.norm), maxScore);

    }

    return maxScore;

  }

这段代码的用途一句话就能说清：

> 把一个 impacts 列表里所有 `(freq, norm)` 对的“最高分”算出来，作为该段（或该 block）的得分上限。

---

具体过程

1. 遍历列表中的每一条 `Impact`  

2. 用 scorer 的公式当场算出这条 `(freq, norm)` 的得分  

3. 取最大值 `maxScore` 返回

---

在算法流程中的位置

- 上层（高层）

  先调 `computeMaxScore(impacts)` 得到 `maxScore`，

  然后与当前 第 k 名的阈值 `minCompetitiveScore` 比较：  

  - `maxScore < minCompetitiveScore` → 整块/整段直接跳过  

  - 否则才继续逐文档精确打分或更细粒度剪枝。

---

注意点

- 这里只是 “估算” 上限，不会真的去遍历文档。  

- 由于 `score(freq, norm)` 是单调函数，列表里最大的 `(freq, norm)` 必然给出最大分，所以只需要比较一次即可。