文本去重的工程方法MinHash 到 SimHash在精度与速度间选择一、当十亿级文本库的重复率超过预期在大模型训练数据的清洗流程中文本去重是最耗时但最关键的步骤之一。常见的情况是爬取了 50TB 的网页文本经过 HTML 标签清洗、语言检测之后需要做全文去重。Naive 的做法是逐条比对哈希值时间复杂度和空间复杂度迅速爆炸。实际场景中重复文本的形态远比想象中复杂。除了完全相同的文本还有轻微修改的复读文本、翻译后回译的文本、以及模板化生成的内容。这些近重复Near-Duplicate文本对模型训练的影响与完全重复文本一样大——它们会降低训练数据的多样性导致模型过拟合某些低频模式。去重的工程挑战在于三个维度精度能否检测出所有重复、速度十亿级规模下能否在可接受时间内完成、和近重复识别能否识别非完全相同的重复。这三个维度构成一个不可能三角任何单一方法都无法同时满足。见证奇迹的时刻不是发现某个算法能完美解决所有问题而是理解每种方法的适用边界并根据实际场景做出组合选择。二、MinHash 与 SimHash 的算法原理对比两种算法都用于大规模文本的近重复检测但设计思路截然不同。graph LR A[原始文本] -- B{选择算法} B --|侧重召回率| C[MinHash 路径] B --|侧重速度| D[SimHash 路径] C -- C1[Shingling: 生成 n-gram 集合] C1 -- C2[多哈希函数映射到最小签名] C2 -- C3[LSH 分桶: Banding 策略] C3 -- C4[Jaccard 相似度候选对] D -- D1[分词加权: TF-IDF 或词频] D1 -- D2[哈希投影: 每位加权求和] D2 -- D3[生成定长二进制指纹] D3 -- D4[汉明距离筛选] C4 -- E[最终去重结果] D4 -- E style C fill:#e3f2fd style D fill:#fff8e1MinHash 原理将文本转化为 n-gram通常 n3~5集合通过多个哈希函数对集合元素取最小值生成固定长度的签名。两个文本的 MinHash 签名重叠比例近似等于原始集合的 Jaccard 相似度。配合局部敏感哈希LSH的分桶策略可以将 O(N^2) 的比较降低到近似线性。SimHash 原理将文本分词后对每个词计算哈希值并加权将所有词的加权哈希值按位求和最后将每位上的和与阈值比较生成定长的二进制指纹。相似文本的指纹间的汉明距离Hamming Distance较小。SimHash 的优势在于指纹是定长二进制存储和比较的成本极低。两种算法的本质区别MinHash 近似 Jaccard 相似度集合重合度更适合检测内容重叠但顺序可能不同的文本SimHash 近似 Cosine 相似度向量方向一致性更适合检测结构和主题相似的文本。三、MinHash LSH 的完整实现以下代码实现了一个基于 MinHash LSH 的近重复检测器。import hashlib from collections import defaultdict from typing import List, Set, Tuple def n_grams(text: str, n: int 3) - Set[str]: 生成文本的 n-gram 集合 设计原因n3 是经验最优值在中文场景平衡了粒度与性能。 n 太大会丢失重叠信息n 太小会增加误匹配。 text text.lower().strip() return {text[i:in] for i in range(len(text) - n 1)} class MinHash: MinHash 签名生成器 设计原因使用多哈希函数的最小值构成签名签名碰撞概率 近似于 Jaccard 相似度是理论基础扎实的近似算法。 def __init__(self, num_perm: int 128): self.num_perm num_perm # 使用 sha256 模拟多个哈希函数 self.seeds [hashlib.sha256(fseed_{i}.encode()).digest() for i in range(num_perm)] def signature(self, shingle_set: Set[str]) - List[int]: 计算 MinHash 签名 sig [] for seed in self.seeds: min_hash float(inf) for shingle in shingle_set: h int(hashlib.sha256( seed shingle.encode(utf-8) ).hexdigest(), 16) min_hash min(min_hash, h) sig.append(min_hash) return sig class LSH: 局部敏感哈希索引 设计原因Banding 策略将签名切分为 b 个 band 每个 band 包含 r 行。b * r num_perm。 只有当两个文本在至少一个 band 中完全相同时 才进入候选集合。参数 b 控制召回率r 控制精确率。 def __init__(self, b: int 16, r: int 8): self.b b # band 数量 self.r r # 每个 band 的行数 def get_lsh_keys(self, signature: List[int]) - List[Tuple[int, int]]: 生成 LSH 桶键 keys [] for band_idx in range(self.b): start band_idx * self.r end start self.r band_sig tuple(signature[start:end]) bucket_key hash(band_sig) keys.append((band_idx, bucket_key)) return keys def find_candidates(self, signatures: List[List[int]]) - Set[Tuple[int, int]]: 找出候选重复对 buckets defaultdict(list) for doc_id, sig in enumerate(signatures): for band_idx, bucket_key in self.get_lsh_keys(sig): buckets[(band_idx, bucket_key)].append(doc_id) candidates set() for bucket_docs in buckets.values(): if len(bucket_docs) 1: for i in range(len(bucket_docs)): for j in range(i 1, len(bucket_docs)): candidates.add(( min(bucket_docs[i], bucket_docs[j]), max(bucket_docs[i], bucket_docs[j]) )) return candidates上述实现中num_perm128, b16, r8是一个常用的参数组合。在这个配置下对于 Jaccard 相似度为 0.5 的文本对被 LSH 分到同一桶的概率约为 0.996误判率约 0.003。这意味着召回率很高但候选集可能包含一些假阳性需要后续做精确 Jaccard 验证。四、MinHash 与 SimHash 的工程 Trade-off两种算法不存在绝对的优劣选择取决于数据特征和业务目标。MinHash 适用场景原始文本重复率未知需要高召回文本可能被大量编辑插入、删除、重排对精确率要求不过分苛刻可以接受后验证的成本SimHash 适用场景已知大部分是原始文本检测近修改版本对计算和存储资源敏感需要极低延迟海明距离阈值可调可以灵活控制召回/精确平衡组合策略推荐阶段方法目的第一轮SimHash粗筛快速排除完全不同的文本将候选集缩小 100 倍第二轮MinHash LSH精筛在候选集上做高召回近重复检测第三轮精确编辑距离确认对候选对做最终确认清理误匹配见证奇迹的时刻在于三轮组合后计算量从 O(10^9 对) 下降到 O(10^5 对)而检测准确率不降反升。工程优化的关键在于分阶段降低候选集规模而不是在一个阶段追求完美。五、总结文本去重的工程方案需要根据数据规模和重复特征选择算法组合。MinHash 基于 Jaccard 相似度近似适合高召回场景SimHash 基于汉明距离筛选适合低延迟场景。推荐的实践是将两者组合先用 SimHash 粗筛再用 MinHash LSH 精筛最后做精确验证。参数选择上n-gram 的 n 值、MinHash 签名长度、LSH 的 band 和 row 数量都需要根据数据集的规模和期望的重复率来调优没有一套参数能适应所有场景。