# 24 重复配对、去重与有效覆盖 整理日期：2026-10-17。 适用范围：两向量筛法中的源对重复、候选结果去重、数据库接纳，以及去重成本与搜索质量的比较。 前置笔记：[19 筛法中的近邻搜索与分桶](/knowledge/nearest-neighbor-search-and-bucketing/)、[22 BGJ 递归分桶与多层筛选](/knowledge/bgj-recursive-bucketing/)、[23 多层分桶的参数选择与优化](/knowledge/multilevel-bucketing-optimization/)。 第 23 篇讨论怎样在覆盖要求下选择参数。本篇进一步区分：重复发生在哪里，哪些重复值得消除，以及去重是否真正减少了完整筛法的成本。 **符号约定：** $C,H,U$ 沿用第 19、22 篇，分别表示全部候选对检查次数、含重复的有效命中次数、不同有效源对的覆盖数量。比较去重方案时，它们均指同一候选流在**不做源对去重**时的基线计数；去重后的实际检查次数另行说明。 ## 1. 三种重复对应不同对象 设当前筛法维数为 $s$，固定一轮输入池 $D=\{x_1,\ldots,x_N\}$，所有向量非零。按照第 19 篇的符号选择，为无序源对 $(i,j)$ 生成较短的和或差，并按真实范数判断是否有效。记 $E$ 为该固定输入池中的有效源对集合。 需要区分三种重复： - **源对重复：** 同一个 $(i,j)$ 进入多个共同桶或叶子，被反复提出检查。 - **结果重复：** 不同源对产生相同的非零向量，或互为相反数的向量。 - **数据库中的重复：** 候选结果已经存在于当前池中，或者已经由其他任务提交、等待插入。 消除源对重复，可以减少重复的约化检查；消除结果重复，可以减少重复构造、传输和插入。两者作用的位置不同。 沿用 $m_{ij}$ 表示源对在原始候选流中的出现次数，引入 $$ C_{\mathrm{distinct}} =\sum_{i0\}, $$ 表示出现过的不同候选源对数量，包括有效对与无效对。因此， $$ C-C_{\mathrm{distinct}} =\sum_{i0\}\right) $$ 是可以归因于源对重复的检查次数；其中有效源对的重复命中次数为 $$ H-U. $$ 这两个差值不能混用：$H-U$ 只统计有效对，遗漏了重复检查无效对的成本。 ## 2. 覆盖增加时，重复也会增加 先考虑单层、$t$ 个独立同分布过滤器。对固定源对 $(i,j)$，记一次共同通过的概率为 $q_{ij}$，则 $$ m_{ij}\sim\operatorname{Binomial}(t,q_{ij}). $$ 所以 $$ \mathbb E[m_{ij}]=tq_{ij}, \qquad \Pr[m_{ij}>0]=1-(1-q_{ij})^t. $$ 前者统计包含重复的出现次数，后者统计是否至少出现一次。二者之差给出该源对的期望重复次数： $$ \boxed{ \mathbb E\!\left[m_{ij}-\mathbf 1\{m_{ij}>0\}\right] =tq_{ij}-\left[1-(1-q_{ij})^t\right]. } $$ 若 $00]\approx1-e^{-\lambda}, \qquad \mathbb E[m_{ij}\mid m_{ij}>0] =\frac{tq_{ij}}{1-(1-q_{ij})^t} \approx\frac{\lambda}{1-e^{-\lambda}}. $$ $\lambda$ 较小时，命中的源对通常只出现一次；$\lambda$ 增大后，覆盖概率趋近于 $1$，出现次数却继续增长。 再增加一个独立过滤器时，该源对新增覆盖的概率为 $$ \bigl[1-(1-q_{ij})^{t+1}\bigr] -\bigl[1-(1-q_{ij})^t\bigr] =q_{ij}(1-q_{ij})^t. $$ 因此，增加搜索次数的边际覆盖收益会递减。易命中的源对可能被反复发现，难命中的源对仍未被覆盖，不能仅根据平均命中次数判断搜索是否充分。 以上是独立过滤器模型的直接推导。在第 23 篇的独立随机中心、完整递归树模型中，多层覆盖由 $R_0(\theta_{ij})$ 计算，不能把共享父桶的全部叶子当作独立过滤器。一般的计数恒等式仍然成立： $$ \mathbb E[H-U] =\sum_{(i,j)\in E} \left( \mathbb E[m_{ij}] -\Pr[m_{ij}>0] \right). $$ **精确去重本身不会扩大原始候选流覆盖的源对集合。** 它消除的是重复工作；若节省的时间被用于更多搜索，才可能在相同时间预算下获得更大覆盖。 ## 3. 在约化检查前做源对去重 在固定输入池中，可以为每个无序对使用规范键 $$ \operatorname{key}(i,j) =(\min\{i,j\},\max\{i,j\}). $$ 下面是一个用于说明语义的精确方案。输入池、约化判据和桶序列在整个流程中固定，集合按完整源对键判断相等： ~~~text 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$，写成 $$ x_i=Bz_i,\qquad z_i\in\mathbb Z^s. $$ 若本轮选择的符号为 $\sigma_{ij}\in\{-1,1\}$，则候选结果的整数系数为 $$ z_{ij}=z_i-\sigma_{ij}z_j. $$ 在同一个基下，比较完整整数系数就能判断向量是否相同。为合并正负号，可以把非零系数向量的首个非零分量统一为正。零结果单独排除。 记 $K$ 为已覆盖有效源对产生的不同非零结果数，按正负号合并，但尚未排除池中已有的结果。由于一个有效源对按固定规则产生一个结果， $$ K\le U. $$ 实际实现常先使用短指纹。一个线性指纹模型为 $$ h(z)=\sum_{r=1}^{s}a_rz_r\pmod{2^b}, $$ 其中系数 $a_r$ 在当前哈希函数初始化时固定。线性性给出 $$ h(z_i-\sigma_{ij}z_j) =h(z_i)-\sigma_{ij}h(z_j)\pmod{2^b}. $$ 因此，可以由已有指纹计算候选指纹，避免为每个重复结果构造完整向量。处理正负等价时，还需在查表层统一 $h(z)$ 与 $-h(z)$；原始线性指纹本身不必满足 $h(z)=h(-z)$。 G6K 的 UID 使用 64 位值，作用于格基下的整数系数，并在哈希表层处理正负号对称。参见 [G6K 的 UidHashTable 与 Entry 说明，kernel/siever.h，检索于 2026-10-17](https://github.com/fplll/g6k/blob/master/kernel/siever.h)。 **指纹相同不保证向量相同。** 若要求精确去重，需要在指纹冲突时比较完整系数；只依据短指纹拒绝候选，会存在把不同向量误判为重复的可能。这里的身份指纹，也不同于用来筛选相近方向的 LSH 或 SimHash。 还要看查重发生的时机。G6K 的 bgj1 约化函数先计算内积与候选长度，通过长度条件后，再计算候选 UID 并尝试登记；登记成功才构造完整候选。它减少了后续的构造与重复提交，但该次内积已经计算过。参见 [kernel/bgj1_sieve.cpp，bgj1_reduce_with_delayed_replace，检索于 2026-10-17](https://github.com/fplll/g6k/blob/master/kernel/bgj1_sieve.cpp)。 所以，“实现中已有 UID 去重”不能直接解释为“已经消除了重复源对的内积检查”。 ## 5. 去重何时能降低成本 先只比较源对查重与真实约化检查两项。令： - $a_{\mathrm{check}}$：一次真实约化检查的平均成本。 - $a_{\mathrm{lookup}}$：一次源对集合查询与必要登记的平均成本。 - $T_{\mathrm{maint}}$：集合初始化、扩容和清理等额外成本。 不做源对去重时，这部分成本约为 $$ T_{\mathrm{plain}}\approx a_{\mathrm{check}}C. $$ 采用第 3 节的精确去重后，约为 $$ T_{\mathrm{dedup}} \approx a_{\mathrm{lookup}}C +a_{\mathrm{check}}C_{\mathrm{distinct}} +T_{\mathrm{maint}}. $$ 因此，在这个简化模型中，去重有利的条件是 $$ \boxed{ a_{\mathrm{lookup}}C+T_{\mathrm{maint}} < a_{\mathrm{check}} \left(C-C_{\mathrm{distinct}}\right). } $$ 右边是省下的检查成本，左边是新增的查重与维护成本。这是成本分解，不是对任意实现的性能保证；加入去重还可能改变批处理、缓存命中率与并行效率。 即使哈希查询具有期望常数次操作，也可能需要代价较高的随机访存。相比之下，桶内内积可以批量执行。因此，“重复率较高”仍不足以单独证明全局源对哈希表会更快。 对于结果和数据库去重，还可以考虑批量排序与归并：按向量身份聚集相同结果，去重后再按长度及接纳规则保留候选。这会增加批处理与排序工作，但有机会使用更连续的数据访问。 Zhao–Ding–Yang 在 [《Sieving with Streaming Memory Access》§4.2，所链接 PDF 第 10 页](https://csrc.nist.gov/csrc/media/events/2025/sixth-pqc-standardization-conference/sieving%20with%20streaming%20memory%20access.pdf)讨论了将旧列表与新结果合并排序、删除重复和过长向量的流式处理思路。这个例子说明：去重方案也应放进完整的访存模型中比较。 ## 6. 从去重结果到数据库接纳 候选结果没有重复，也不意味着一定会被接纳。它还可能已经在输入池中、不满足当前替换阈值，或在候选竞争中被更短的结果淘汰。 对于同一固定输入批次，若每个结果最多接纳一次，记实际接纳的不同向量数为 $N_{\mathrm{ins}}$，则 $$ N_{\mathrm{ins}}\le K\le U\le H\le C, \qquad U\le C_{\mathrm{distinct}}\le C. $$ 这些量分别对应数据库更新、不同结果、不同有效源对、有效命中和全部检查，不能互相替代。 并行处理中，去重还应覆盖已经提交、尚未真正写入数据库的候选，否则多个任务可能同时认为同一个结果尚不存在。G6K 的 UID 表说明明确包含当前数据库向量及已提交、等待潜在插入的向量，见 [kernel/siever.h 中 uid_hash_table 的状态说明](https://github.com/fplll/g6k/blob/master/kernel/siever.h)。 跨越多轮更新时，需要重新明确统计范围。同一数组位置可能已经改变，同一结果也可能在不同阶段再次出现，不能直接把所有轮次混成一个固定池模型。 ## 7. 怎样验证去重方案 可以先固定输入池、过滤器和叶子遍历序列，比较不去重与精确源对去重两种执行： - 原始候选流相同，检查基线 $C,H,U$ 与 $C_{\mathrm{distinct}}$。 - 精确源对去重后，不同有效源对集合与不同结果集合应保持一致。 - 分别测量真实约化检查、查重维护、结果处理的时间，以及峰值内存。 - 再接入完整筛法，比较达到同一长度质量或饱和标准所需的总时间。 启用源对去重后，实际成功检查次数通常不再等于基线 $H$。要恢复原始候选流的 $H$，需要知道各源对的重复次数及有效性；可以在小规模验证中保留这些信息，大规模实验则注明抽样或估计方法。 如果使用仅凭指纹拒绝候选的方案，还应单独检查误判对覆盖和结果集合的影响。不能把有损过滤与精确去重混在一起解释。 本篇保留的核心区别是：**源对去重节省重复检查，结果去重合并相同输出，数据库接纳决定实际更新。** 三者需要分别计数，并在相同搜索质量下比较完整成本。 ## 引用此笔记 - [00 概览与阅读路线](/knowledge/lattices-overview/) - [25 渐进筛法与向量池复用](/knowledge/progressive-sieving-and-vector-pool-reuse/) - [26 G6K 与 Pump](/knowledge/g6k-and-pump/) - [27 筛法的并行化与平台成本模型](/knowledge/parallel-lattice-sieving-and-platform-costs/) - [28 BGJ 筛法的流式访存组织](/knowledge/bgj-streaming-memory-organization/)