MinHash 大规模文本近似去重策略详解
为什么需要近似去重？
- 完全重复：两篇文章一字不差，用普通哈希（如 MD5）就能轻松检测。
- 近似重复：有人改了几个词、加了广告、换了标题……内容 90% 一样，这时候普通哈希就失效了。
MinHash 的强项就是捕捉这种'近似重复'，特别适合新闻聚合、爬虫去重、AI 训练数据清洗等场景。
MinHash 的核心思路：把文本变成集合，再估算相似度
第一步：把文本切成'小瓦片'（Shingling）
我们先把一篇文本切成很多重叠的小片段，这些片段叫 shingle（也叫 k-gram）。
举个例子，句子：'我喜欢吃苹果'
用 k=3 的 3-gram（每个片段 3 个字符）切分：
- '我喜欢'
- '喜欢吃'
- '欢吃苹'
- '吃苹果'
得到一个集合：{'我喜欢', '喜欢吃', '欢吃苹', '吃苹果'}
如果用 k=2 的 2-gram：
- '我喜'
- '喜欢'
- '欢吃'
- '吃苹'
- '苹果'
两篇文章越相似，它们的 shingle 集合重叠的部分就越多。
小贴士：实际项目中，中文常用 k=3
5，英文常用 k=510。k 越大越能捕捉长距离相似，但计算量也更大。
第二步：用 Jaccard 相似度衡量集合相似性
两个集合 A 和 B 的 Jaccard 相似度公式很简单：
相似度 = |A ∩ B| / |A ∪ B|
（交集元素个数 ÷ 并集元素个数）
- 完全一样 → 相似度 = 1
- 完全没重叠 → 相似度 = 0
- 改了几个字 → 相似度可能 0.85~0.95
理论上完美，但问题来了：当你有上亿篇文章时，两两计算 Jaccard 根本不可能，太慢了！
第三步：MinHash 登场——用'签名'快速估算 Jaccard
MinHash 的神奇之处在于：它能把一个巨大的 shingle 集合压缩成一个短小的'数字签名'（signature），而且两个签名的相似比例 ≈ 原来集合的 Jaccard 相似度。
怎么做到的呢？
- 准备很多个（比如 100~200 个）随机哈希函数（可以理解为随机'洗牌'规则）。
- 对集合里的每个 shingle，用所有哈希函数算出一个数字。
- 对每个哈希函数，取它在集合中产生的最小值 → 这就是这个哈希函数对应的 MinHash 值。
- 把所有 MinHash 值排成一列，就得到了这个文档的'签名'。
关键性质（概率魔力）：
两个集合的 MinHash 签名在同一位置取值相同的概率，正好等于它们的 Jaccard 相似度！
所以，我们只需比较两个短签名中有多少位置相同，就能估算出原始文本的相似度。超级高效！
第四步：再加速——LSH（局部敏感哈希）
光有 MinHash 签名还不够，上亿文档两两比还是太慢。我们再加一层 LSH（Locality-Sensitive Hashing）技巧：
- 把签名分成若干段（比如分成 20 段，每段 5~10 个值）。
- 对每一段再做一次普通哈希，得到一个'桶号'。
- 只有落在同一个桶里的文档，才拿去精确比较完整签名。
原理：高度相似的文档，大概率会在至少某一'段'里撞桶；不相似的基本不会撞。
这样，候选对的数量大幅减少，整体速度能提升几百上千倍！
MinHash 去重完整流程
- 对每篇文档做 shingling → 得到集合
- 计算 MinHash 签名（固定长度，比如 128 或 256）
- 用 LSH 把签名分桶，找出候选相似对
- 对候选对计算签名相似度，超过阈值（如 0.8）就视为重复，只保留一篇
实际应用场景
- 搜索引擎：检测重复网页（Google 早期就用过类似技术）
- AI 大模型训练：清洗万亿级文本数据，去除重复样本
- 新闻聚合：把同一事件的报道聚成一类
- 爬虫系统：避免抓取重复页面
- 抄袭检测：快速筛查高度相似文章
优点与缺点
优点：
- 速度快、内存省，能处理亿级数据
- 准确度可控（多用几个哈希函数就更准）
- 实现简单，有现成库
缺点：
- 是概率算法，有极小概率漏掉或误判（实际影响很小）
- 需要调参（哈希函数数量、LSH 分段数、相似度阈值）
代码实现
Python 有超级好用的库 datasketch，几行代码就能实现：
from datasketch import MinHash, MinHashLSH
# 创建 LSH
lsh = MinHashLSH(threshold=0.8, num_perm=128)
# 对每篇文档创建 MinHash
m1 = MinHash(num_perm=128)
for shingle in doc1_shingles:
m1.update(shingle.encode('utf8'))
lsh.insert("doc1", m1)
# 查询相似文档
result = lsh.query(m1)
# 返回所有相似 doc 的 id