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 个值）。
- 对每一段再做一次普通哈希，得到一个'桶号'。
- 只有落在同一个桶里的文档，才拿去精确比较完整签名。
原理：高度相似的文档，大概率会在至少某一'段'里撞桶；不相似的基本不会撞。
这样，候选对的数量大幅减少，整体速度能提升几百上千倍！
