MinHash

定义

MinHash(最小哈希)是 Andrei Broder 在 AltaVista 搜索引擎从事网页去重研究时提出的算法,用于在不比较完整集合的情况下快速估计两个集合的 Jaccard 相似度。

原理

核心性质:对全集做一次随机排列,两个集合各自最小元素相同的概率恰好等于它们的 Jaccard 相似度。实践中用多个独立哈希函数模拟随机排列,取每个哈希函数下集合元素的最小哈希值组成定长签名;两个签名中对应位置相等的比例即为相似度的无偏估计。

应用

MinHash 常与 LSH 分桶结合,用于海量网页与文档去重、抄袭检测、推荐系统中的用户或物品相似度计算,以及生物信息学中的基因组序列比对(如 Mash 工具)。

特点

优点是签名远小于原集合、误差随哈希函数数量增加而收敛;缺点是仅适用于集合(无权重)相似度,带权场景需使用加权 MinHash 变体。