整理日期：2026-10-17。
适用范围：两向量筛法中的源对重复、候选结果去重、数据库接纳，以及去重成本与搜索质量的比较。
前置笔记：19 筛法中的近邻搜索与分桶、22 BGJ 递归分桶与多层筛选、23 多层分桶的参数选择与优化。
第 23 篇讨论怎样在覆盖要求下选择参数。本篇进一步区分：重复发生在哪里，哪些重复值得消除，以及去重是否真正减少了完整筛法的成本。
符号约定： \(C,H,U\) 沿用第 19、22 篇，分别表示全部候选对检查次数、含重复的有效命中次数、不同有效源对的覆盖数量。比较去重方案时，它们均指同一候选流在不做源对去重时的基线计数；去重后的实际检查次数另行说明。
1. 三种重复对应不同对象#
设当前筛法维数为 \(s\)，固定一轮输入池 \(D=\{x_1,\ldots,x_N\}\)，所有向量非零。按照第 19 篇的符号选择，为无序源对 \((i,j)\) 生成较短的和或差，并按真实范数判断是否有效。记 \(E\) 为该固定输入池中的有效源对集合。
需要区分三种重复：
- 源对重复： 同一个 \((i,j)\) 进入多个共同桶或叶子，被反复提出检查。
- 结果重复： 不同源对产生相同的非零向量，或互为相反数的向量。
- 数据库中的重复： 候选结果已经存在于当前池中，或者已经由其他任务提交、等待插入。
消除源对重复，可以减少重复的约化检查；消除结果重复，可以减少重复构造、传输和插入。两者作用的位置不同。
沿用 \(m_{ij}\) 表示源对在原始候选流中的出现次数，引入
表示出现过的不同候选源对数量，包括有效对与无效对。因此，
是可以归因于源对重复的检查次数；其中有效源对的重复命中次数为
这两个差值不能混用：\(H-U\) 只统计有效对，遗漏了重复检查无效对的成本。
2. 覆盖增加时，重复也会增加#
先考虑单层、\(t\) 个独立同分布过滤器。对固定源对 \((i,j)\)，记一次共同通过的概率为 \(q_{ij}\)，则
所以
前者统计包含重复的出现次数，后者统计是否至少出现一次。二者之差给出该源对的期望重复次数：
若 \(0<q_{ij}\ll1\)，且 Poisson 近似适用，令 \(\lambda=tq_{ij}\)，则
\(\lambda\) 较小时，命中的源对通常只出现一次；\(\lambda\) 增大后，覆盖概率趋近于 \(1\)，出现次数却继续增长。
再增加一个独立过滤器时，该源对新增覆盖的概率为
因此，增加搜索次数的边际覆盖收益会递减。易命中的源对可能被反复发现，难命中的源对仍未被覆盖，不能仅根据平均命中次数判断搜索是否充分。
以上是独立过滤器模型的直接推导。在第 23 篇的独立随机中心、完整递归树模型中，多层覆盖由 \(R_0(\theta_{ij})\) 计算，不能把共享父桶的全部叶子当作独立过滤器。一般的计数恒等式仍然成立：
精确去重本身不会扩大原始候选流覆盖的源对集合。 它消除的是重复工作；若节省的时间被用于更多搜索，才可能在相同时间预算下获得更大覆盖。
3. 在约化检查前做源对去重#
在固定输入池中，可以为每个无序对使用规范键
下面是一个用于说明语义的精确方案。输入池、约化判据和桶序列在整个流程中固定，集合按完整源对键判断相等：
SeenPairs ← 空集合
依次遍历各个叶子：
对叶子内每个无序源对 (i, j)：
key ← (min(i,j), max(i,j))
如果 key 已在 SeenPairs 中：
跳过
将 key 加入 SeenPairs
检查 x_i 与 x_j 的真实约化条件
若有效，输出源对及其候选结果无论第一次检查是否成功，都记录该源对。因为输入与判据固定，重复检查同一对不会改变结果。
完整执行时，真实约化检查次数从基线 \(C\) 降为 \(C_{\mathrm{distinct}}\)；覆盖的不同有效源对仍为 \(U\)。
代价是保存源对集合，需要 \(O(C_{\mathrm{distinct}})\) 条键，最坏可达到 \(O(N^2)\)。因此，这个方案适合作为正确性与成本分析的基线，是否适合大规模筛法还要看内存预算。
可以把去重范围限制在一个父桶或一批叶子中，以减少驻留空间。这样能消除范围内的重复，但跨范围的同一源对仍可能被再次检查。
这里的编号必须对应稳定的向量身份。若数据库槽位已经被新向量覆盖，相同的数组下标对就可能代表新的源对。动态实现需要按输入批次重置记录，或使用带版本的向量标识。
4. 结果去重与线性指纹#
源对不同，不代表结果不同。固定当前格基 \(B\)，写成
若本轮选择的符号为 \(\sigma_{ij}\in\{-1,1\}\)，则候选结果的整数系数为
在同一个基下，比较完整整数系数就能判断向量是否相同。为合并正负号，可以把非零系数向量的首个非零分量统一为正。零结果单独排除。
记 \(K\) 为已覆盖有效源对产生的不同非零结果数，按正负号合并，但尚未排除池中已有的结果。由于一个有效源对按固定规则产生一个结果，
实际实现常先使用短指纹。一个线性指纹模型为
其中系数 \(a_r\) 在当前哈希函数初始化时固定。线性性给出
因此，可以由已有指纹计算候选指纹，避免为每个重复结果构造完整向量。处理正负等价时，还需在查表层统一 \(h(z)\) 与 \(-h(z)\)；原始线性指纹本身不必满足 \(h(z)=h(-z)\)。
G6K 的 UID 使用 64 位值，作用于格基下的整数系数，并在哈希表层处理正负号对称。参见 G6K 的 UidHashTable 与 Entry 说明，kernel/siever.h，检索于 2026-10-17。
指纹相同不保证向量相同。 若要求精确去重，需要在指纹冲突时比较完整系数；只依据短指纹拒绝候选，会存在把不同向量误判为重复的可能。这里的身份指纹，也不同于用来筛选相近方向的 LSH 或 SimHash。
还要看查重发生的时机。G6K 的 bgj1 约化函数先计算内积与候选长度，通过长度条件后，再计算候选 UID 并尝试登记；登记成功才构造完整候选。它减少了后续的构造与重复提交，但该次内积已经计算过。参见 kernel/bgj1_sieve.cpp，bgj1_reduce_with_delayed_replace，检索于 2026-10-17。
所以，“实现中已有 UID 去重”不能直接解释为“已经消除了重复源对的内积检查”。
5. 去重何时能降低成本#
先只比较源对查重与真实约化检查两项。令：
- \(a_{\mathrm{check}}\)：一次真实约化检查的平均成本。
- \(a_{\mathrm{lookup}}\)：一次源对集合查询与必要登记的平均成本。
- \(T_{\mathrm{maint}}\)：集合初始化、扩容和清理等额外成本。
不做源对去重时，这部分成本约为
采用第 3 节的精确去重后，约为
因此，在这个简化模型中，去重有利的条件是
右边是省下的检查成本，左边是新增的查重与维护成本。这是成本分解，不是对任意实现的性能保证；加入去重还可能改变批处理、缓存命中率与并行效率。
即使哈希查询具有期望常数次操作，也可能需要代价较高的随机访存。相比之下，桶内内积可以批量执行。因此，“重复率较高”仍不足以单独证明全局源对哈希表会更快。
对于结果和数据库去重，还可以考虑批量排序与归并：按向量身份聚集相同结果，去重后再按长度及接纳规则保留候选。这会增加批处理与排序工作，但有机会使用更连续的数据访问。
Zhao–Ding–Yang 在 《Sieving with Streaming Memory Access》§4.2，所链接 PDF 第 10 页讨论了将旧列表与新结果合并排序、删除重复和过长向量的流式处理思路。这个例子说明：去重方案也应放进完整的访存模型中比较。
6. 从去重结果到数据库接纳#
候选结果没有重复，也不意味着一定会被接纳。它还可能已经在输入池中、不满足当前替换阈值，或在候选竞争中被更短的结果淘汰。
对于同一固定输入批次，若每个结果最多接纳一次，记实际接纳的不同向量数为 \(N_{\mathrm{ins}}\)，则
这些量分别对应数据库更新、不同结果、不同有效源对、有效命中和全部检查，不能互相替代。
并行处理中，去重还应覆盖已经提交、尚未真正写入数据库的候选，否则多个任务可能同时认为同一个结果尚不存在。G6K 的 UID 表说明明确包含当前数据库向量及已提交、等待潜在插入的向量，见 kernel/siever.h 中 uid_hash_table 的状态说明。
跨越多轮更新时，需要重新明确统计范围。同一数组位置可能已经改变，同一结果也可能在不同阶段再次出现，不能直接把所有轮次混成一个固定池模型。
7. 怎样验证去重方案#
可以先固定输入池、过滤器和叶子遍历序列，比较不去重与精确源对去重两种执行：
- 原始候选流相同，检查基线 \(C,H,U\) 与 \(C_{\mathrm{distinct}}\)。
- 精确源对去重后，不同有效源对集合与不同结果集合应保持一致。
- 分别测量真实约化检查、查重维护、结果处理的时间，以及峰值内存。
- 再接入完整筛法，比较达到同一长度质量或饱和标准所需的总时间。
启用源对去重后，实际成功检查次数通常不再等于基线 \(H\)。要恢复原始候选流的 \(H\)，需要知道各源对的重复次数及有效性；可以在小规模验证中保留这些信息，大规模实验则注明抽样或估计方法。
如果使用仅凭指纹拒绝候选的方案，还应单独检查误判对覆盖和结果集合的影响。不能把有损过滤与精确去重混在一起解释。
本篇保留的核心区别是：源对去重节省重复检查，结果去重合并相同输出，数据库接纳决定实际更新。 三者需要分别计数，并在相同搜索质量下比较完整成本。