MinHash / LSH 模糊去重
一句话定位：面试高频必问。在十亿级文档里找出”内容近似重复”的文档簇——两两比对是 O(N²) 不可行，MinHash 把相似度压成签名、LSH 把候选集缩小到桶内，使近似去重在大规模下可行。去重能显著提升语言模型效果（减少记忆化、提高有效 token 占比）。
1. 完整流水线
1 Shingling（分片）
把文档切成长度为 k 的连续片段集合（k-shingle / k-gram，可按词或字符）。文档由此变成一个集合，文档相似度 = 两集合的 Jaccard 相似度 J(A,B) = |A∩B| / |A∪B|。
k 的选择：k 太小则不同文档偶然共享大量 shingle（假阳性高）；k 太大则对微小改写过于敏感（召回下降）。
2 MinHash 签名
- 对集合施加一个哈希置换 h，取集合中所有元素哈希值的最小值作为一个签名分量。
- 关键性质：
P(minhash(A) == minhash(B)) = J(A,B)——两个集合最小哈希相等的概率恰好等于 Jaccard 相似度。 - 用 n 个独立哈希函数得到长度为 n 的签名向量，则”签名相同分量的比例”就是 Jaccard 的无偏估计。作用是把任意大的集合压成定长 n 的签名，把集合比较变成定长向量比较。
3 分带（Banding）分桶
把长度 n 的签名切成 b 个 band，每个 band 含 r 行（n = b × r）。对每个 band 做哈希分桶：只要有任一 band 完全相同，两文档即成为候选对。
碰撞概率（相似度为 s 的两文档成为候选的概率）：
P(候选) = 1 - (1 - s^r)^b
这是一条 S 形曲线，其陡峭的转折点（近似阈值）约在 s ≈ (1/b)^(1/r)。
4 桶内两两比对
只对落入同桶的候选对计算真实（或签名估计的）相似度，超过阈值判为重复。候选集远小于全量对，这是复杂度从 O(N²) 降下来的根本原因。
5 连通图求重复簇
把”判定为重复”的文档对看作图的边，用并查集 / 连通分量求出重复簇，每簇保留一篇代表文档（或按质量分挑最优），其余丢弃。
2. 工程要点
2.1 签名长度 n 与 band 数 b 决定精确率/召回率权衡
由 P = 1 - (1 - s^r)^b 可知：
- b 增大（r 减小） → 曲线阈值左移，更”宽松”：召回高、假阳性多、候选对暴涨（后续比对更贵）；
- r 增大（b 减小） → 阈值右移，更”严格”：精确率高、漏掉中等相似的重复；
- n 增大 → 相似度估计方差更小（更准），但哈希计算与存储成本线性上升。
调参思路：先定业务上的相似度阈值 s₀（如 0.8），再选 b、r 使 S 曲线的陡升区间对齐 s₀。
2.2 Hash 计算是 CPU 热点
每篇文档要算 n 个（常见 128~256）MinHash，是纯 CPU 密集的大头。优化：用快速哈希（MurmurHash/xxHash）、一次哈希多次置换的技巧（如 (a*h + b) mod p）、向量化与批处理、提高并行度。
2.3 桶内比对易数据倾斜
分桶后桶大小严重不均：模板化页面、超高频近重复内容会让某些桶极度膨胀，桶内两两比对是 O(m²)，单个大桶就能拖死整个作业——这正是 1.2 数据倾斜的典型现场。
治理手段可直接复用 1.2：
- 对超大桶加盐拆分或做二次分桶；
- 设桶大小上限，超限的桶采样或单独处理（隔离热键）；
- 提前对桶大小分布做抽样探测，而非等作业跑挂（对应”提前发现而非事后救火”）。
参考：《Mining of Massive Datasets》第 3 章（Finding Similar Items）；论文《Deduplicating Training Data Makes Language Models Better》(Lee et al., 2022)