02. 数据去重的常见方法有哪些？MinHash 的原理是什么？

简单回答

数据去重分精确去重和模糊去重两类。精确去重用 MD5/SHA 哈希，速度快但只能处理完全相同的文档。模糊去重用 MinHash + LSH（Locality Sensitive Hashing），能高效找出"几乎相同"的近似重复文档。大规模预训练数据通常用 MinHash+LSH，因为网页数据里更多的是改写转载，而不是完全相同的副本。

详细解答

为什么去重如此重要

预训练语料里的重复比例远比人们直觉上认为的高。一篇爆款文章可能被几百个网站转载，一个热门的 Stack Overflow 回答可能出现在无数技术博客里，一段代码可能被 Fork 到成千上万个仓库。如果不做去重，模型会对这些重复内容产生过度记忆，一方面降低泛化能力，另一方面会让模型在推理时更容易"背答案"而不是真正理解。

DeepMind 的研究（Deduplicating Training Data Makes Language Models Better, 2022）明确验证了这一点——在相同参数量和训练计算量的条件下，去重后的数据训练出来的模型，各项指标都更好。去重带来的提升有时候相当于多训练了一倍数据。

另一个重要原因是评测集污染。如果训练集里大量包含了评测集（MMLU、HumanEval 等）相同或高度相似的内容，模型看起来分数很高，但实际上是"作弊"。这个问题在后面的数据污染章节会详细讲。

精确去重

精确去重就是对每个文档计算哈希值（MD5 或 SHA256），然后按哈希值去重。速度极快，但只能处理内容完全相同的文档。对于预训练语料这种大规模场景，精确重复只是一小部分问题，更多的是"近似重复"（转载、改写、格式变换）。

模糊去重：MinHash + LSH

MinHash 的核心思路是用一组哈希函数来近似估计两个文档的 Jaccard 相似度，而不需要真正把两个文档两两比较。

Jaccard 相似度的定义是两个集合交集与并集的比值：

$J(A,B)=\frac{|A\cap B|}{|A\cup B|}$

对文档来说，通常把文档切成 N-gram（比如 5-gram 或 13-gram），每个文档就变成一个 N-gram 的集合，然后计算两个集合的 Jaccard 相似度。

直接计算 Jaccard 相似度的问题在于计算量太大——文档数量是亿级别，两两比较是 $O(n^2)$ 的复杂度，不可行。

MinHash 的解法是：对每个文档，用 $k$ 个不同的哈希函数分别对它的所有 N-gram 取哈希值，然后对每个哈希函数只保留最小的那个哈希值。这 $k$ 个最小哈希值（每个哈希函数一个）组成这个文档的 MinHash 签名，是一个 $k$ 维的向量。

数学上可以证明，两个文档 MinHash 签名中相同位置值相等的概率，恰好等于这两个文档的 Jaccard 相似度：

$P({\text{MinHash}}_i(A)={\text{MinHash}}_i(B))=J(A,B)$

所以通过比较 MinHash 签名的相似度，就可以估计文档的 Jaccard 相似度，不需要存储和比较原始文本。

但光有 MinHash 还不够，还是需要两两比较签名，复杂度还是 $O(n^2)$。LSH（局部敏感哈希）是配套的加速方案：把 $k$ 维签名切成 $b$ 个分段（band），每个分段有 $r=k/b$ 个维度。两个文档只要在任意一个分段内完全相同，就把它们放进同一个候选对（candidate pair）里。Jaccard 相似度越高，两个文档在某个分段内完全相同的概率就越大。通过调整 $b$ 和 $r$，可以控制相似度阈值（比如只找 Jaccard ≥ 0.8 的重复对）。

$P(\text{共享至少一个 band})=1-(1-s^r{)}^b$

其中 $s$ 是真实的 Jaccard 相似度。这个公式是一个 S 型曲线，$b$ 和 $r$ 控制这条曲线的陡峭程度和中心位置，也就是实际的阈值和精度/召回权衡。

实际工程中，整个 MinHash + LSH 流程用 Spark 或 DataTrove、text-dedup 这类工具来跑，能在合理时间内处理 TB 级别的数据。

语义去重

MinHash 去重针对的是字面级别的相似。如果一段话被改写成不同的表达但语义完全相同，MinHash 可能发现不了。语义去重是用 Embedding 模型把文档编码成向量，然后找向量空间中距离很近的文档对。代价是计算量大很多，通常只用在数据量较小或对质量要求极高的场景（比如 SFT 数据去重）。

面试时可以这样答

去重分两类。精确去重就是哈希，MD5 或 SHA，处理完全相同的副本，快但覆盖不了改写转载的情况。大规模预训练数据里更多的是近似重复，就要用模糊去重，标准方案是 MinHash + LSH。

MinHash 的思路是：把文档切成 N-gram 集合，用多个哈希函数对这些 N-gram 取哈希值并只保留最小值，得到一个签名向量。数学上可以证明两个文档签名相同位置相等的概率等于它们的 Jaccard 相似度。LSH 是加速手段，把签名向量分成多个 band，只要两个文档在任意一个 band 里完全匹配，就认为它们是候选重复对，不需要两两全量比较。

工程上这套流程用 DataTrove、text-dedup 这类工具来跑，处理百亿 token 级别的数据是没问题的。另外有个点值得提：去重的重要性经常被低估，DeepMind 有论文专门验证过，去重后的数据训练出的模型比未去重的要好，效果相当于多训了一倍数据。

常见追问

1. N-gram 的 N 怎么选？选 5-gram 和 13-gram 有什么区别？
2. MinHash 的哈希函数数量 k 怎么定？太多或太少分别有什么影响？
3. 语义去重在什么场景下比 MinHash 更合适？