文本去重的工程方法：MinHash 到 SimHash，在精度与速度间选择-北京尧图网络

文本去重的工程方法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 数量都需要根据数据集的规模和期望的重复率来调优没有一套参数能适应所有场景。

文本去重的工程方法：MinHash 到 SimHash，在精度与速度间选择

相关推荐

Git 标签实战：从 v1.0 创建到 origin 推送的 3 步完整流程

Git 标签 vs 分支：3 个核心差异与 4 种典型应用场景解析

etmem与PSI策略：实现cgroup粒度内存扩展的完整指南

更多资讯

东莞光明复审电工证怎么考？学历不高也能过！考前押题帮你上岸

初中应届考电工证多久拿证？刚毕业想找工作的你必须知道！

永兴考电工证在哪良心建议：别被中介坑了，自己搞懂流程更靠谱

襄汾电工证培训：上岗必备，先考证再找工作

卢氏哪里能办电工证多久拿证？急需特种作业证才能上岗找工作

工地太忙根本没时间复习考试？北京低压电工证刷题千万别踩坑

今日更新

河南特种工八大员含金量高吗？别被中介坑了，这些关键点你要知道

电工证ps软件多少钱？工地太忙根本没时间复习考试怎么办

牡丹江报考高压电工证在哪考？新手避坑指南

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？