MinHash最小哈希算法是一种在计算机科学中用于快速估计两个集合之间相似度的算法。它由 Andrei Broder 在1997年提出最初用于搜索引擎中网页去重和聚类。在大数据环境下如果直接比对两个海量集合的交集和并集计算量会呈爆炸式增长。MinHash 的核心思想是将庞大的集合“压缩”为一个短小的特征向量签名通过比对签名来估算原始集合的相似度。1. 核心数学基础Jaccard 相似度在了解 MinHash 之前需要先知道它所估计的指标——Jaccard 相似度Jaccard Similarity。对于两个集合A AA和B BB它们的 Jaccard 相似度定义为两个集合的交集大小除以并集大小。J ( A , B ) ∣ A ∩ B ∣ ∣ A ∪ B ∣ J(A, B) \frac{|A \cap B|}{|A \cup B|}J(A,B)∣A∪B∣∣A∩B∣结果在0 00到1 11之间。1 11表示集合完全相同0 00表示完全没有交集。2. MinHash 的工作原理MinHash 的巧妙之处在于利用哈希函数的随机性将 Jaccard 相似度的计算转化为概率问题。核心定理假设有一个随机的哈希函数h hh它将集合中的元素映射为一个整数。对于集合A AA和B BB它们的所有元素在经过h hh哈希后最小哈希值相等的概率正好等于它们的 Jaccard 相似度。P ( min ( h ( A ) ) min ( h ( B ) ) ) J ( A , B ) P(\min(h(A)) \min(h(B))) J(A, B)P(min(h(A))min(h(B)))J(A,B)为什么想象把A ∪ B A \cup BA∪B的所有元素随机排列。在这个排列中第一个出现的元素要么属于A AA且不属于B BB要么属于B BB且不属于A AA要么属于A ∩ B A \cap BA∩B交集。只有当第一个出现的元素同时属于A AA和B BB即属于交集时min ( h ( A ) ) \min(h(A))min(h(A))才会等于min ( h ( B ) ) \min(h(B))min(h(B))。因此相等的概率就是∣ A ∩ B ∣ ∣ A ∪ B ∣ \frac{|A \cap B|}{|A \cup B|}∣A∪B∣∣A∩B∣。3. 算法实现步骤MinHash Signature单个哈希函数只能给出0 00不相等或1 11相等的结果。为了准确估计相似度我们需要使用k kk个不同的随机哈希函数通常k 100 ∼ 500 k 100 \sim 500k100∼500为每个集合生成一个长度为k kk的签名Signature。步骤拆解行特征矩阵化将所有文档/集合中的元素比如文本去重中的 单词或 Shingle作为行文档作为列构建一个0 / 1 0/10/1矩阵1 11表示文档包含该元素。应用k kk个哈希函数创建k kk个独立的哈希函数h 1 , h 2 , . . . , h k h_1, h_2, ..., h_kh1,h2,...,hk。计算签名向量对于每一个文档列计算其所有包含的元素行为1在各个哈希函数下的最小值。文档A AA的签名向量 [ min ( h 1 ( A ) ) , min ( h 2 ( A ) ) , . . . , min ( h k ( A ) ) ] [\min(h_1(A)), \min(h_2(A)), ..., \min(h_k(A))][min(h1(A)),min(h2(A)),...,min(hk(A))]估算相似度对比文档A AA和文档B BB的签名向量计算它们相同位置元素相等的比例。这个比例就是A AA和B BB相似度的极佳估计。4. 为什么需要 MinHash优势空间极度压缩原始文档可能包含数万个单词而 MinHash 签名只需要几百个整数比如 200 个整型数字极大地减少了存储空间。计算速度飞跃比对两个几百维的数组是否相等比比对两个几万词的文本交集要快得多。大数据利器由于签名长度固定可以将海量文本的对比转化为矩阵并行运算非常适合 MapReduce、Spark 等分布式架构。5. 经典应用场景网页去重 / 文本近似查重搜索引擎如 Google在爬取海量网页时用 MinHash 快速找出内容高度相似的镜像网页或抄袭文章。推荐系统计算用户协同过滤中的相似度。如果两个用户看过的电影集合 MinHash 相似度高就可以互相推荐。生物信息学在 DNA 序列比对中用于快速寻找相似的基因片段。总结与延伸MinHash 解决了“单个配对太慢”的问题。但在面对数亿级别的数据时两两比对签名依然会有O ( N 2 ) O(N^2)O(N2)的复杂度。因此在实际工程中MinHash 通常会配合LSH局部敏感哈希Locality-Sensitive Hashing一起使用。LSH 能够将相似的 MinHash 签名分到同一个“桶”中让系统只需要比对同一个桶内的文档从而将时间复杂度降到接近O ( N ) O(N)O(N)。
minhash算法
发布时间：2026/6/10 1:14:08
MinHash最小哈希算法是一种在计算机科学中用于快速估计两个集合之间相似度的算法。它由 Andrei Broder 在1997年提出最初用于搜索引擎中网页去重和聚类。在大数据环境下如果直接比对两个海量集合的交集和并集计算量会呈爆炸式增长。MinHash 的核心思想是将庞大的集合“压缩”为一个短小的特征向量签名通过比对签名来估算原始集合的相似度。1. 核心数学基础Jaccard 相似度在了解 MinHash 之前需要先知道它所估计的指标——Jaccard 相似度Jaccard Similarity。对于两个集合A AA和B BB它们的 Jaccard 相似度定义为两个集合的交集大小除以并集大小。J ( A , B ) ∣ A ∩ B ∣ ∣ A ∪ B ∣ J(A, B) \frac{|A \cap B|}{|A \cup B|}J(A,B)∣A∪B∣∣A∩B∣结果在0 00到1 11之间。1 11表示集合完全相同0 00表示完全没有交集。2. MinHash 的工作原理MinHash 的巧妙之处在于利用哈希函数的随机性将 Jaccard 相似度的计算转化为概率问题。核心定理假设有一个随机的哈希函数h hh它将集合中的元素映射为一个整数。对于集合A AA和B BB它们的所有元素在经过h hh哈希后最小哈希值相等的概率正好等于它们的 Jaccard 相似度。P ( min ( h ( A ) ) min ( h ( B ) ) ) J ( A , B ) P(\min(h(A)) \min(h(B))) J(A, B)P(min(h(A))min(h(B)))J(A,B)为什么想象把A ∪ B A \cup BA∪B的所有元素随机排列。在这个排列中第一个出现的元素要么属于A AA且不属于B BB要么属于B BB且不属于A AA要么属于A ∩ B A \cap BA∩B交集。只有当第一个出现的元素同时属于A AA和B BB即属于交集时min ( h ( A ) ) \min(h(A))min(h(A))才会等于min ( h ( B ) ) \min(h(B))min(h(B))。因此相等的概率就是∣ A ∩ B ∣ ∣ A ∪ B ∣ \frac{|A \cap B|}{|A \cup B|}∣A∪B∣∣A∩B∣。3. 算法实现步骤MinHash Signature单个哈希函数只能给出0 00不相等或1 11相等的结果。为了准确估计相似度我们需要使用k kk个不同的随机哈希函数通常k 100 ∼ 500 k 100 \sim 500k100∼500为每个集合生成一个长度为k kk的签名Signature。步骤拆解行特征矩阵化将所有文档/集合中的元素比如文本去重中的 单词或 Shingle作为行文档作为列构建一个0 / 1 0/10/1矩阵1 11表示文档包含该元素。应用k kk个哈希函数创建k kk个独立的哈希函数h 1 , h 2 , . . . , h k h_1, h_2, ..., h_kh1,h2,...,hk。计算签名向量对于每一个文档列计算其所有包含的元素行为1在各个哈希函数下的最小值。文档A AA的签名向量 [ min ( h 1 ( A ) ) , min ( h 2 ( A ) ) , . . . , min ( h k ( A ) ) ] [\min(h_1(A)), \min(h_2(A)), ..., \min(h_k(A))][min(h1(A)),min(h2(A)),...,min(hk(A))]估算相似度对比文档A AA和文档B BB的签名向量计算它们相同位置元素相等的比例。这个比例就是A AA和B BB相似度的极佳估计。4. 为什么需要 MinHash优势空间极度压缩原始文档可能包含数万个单词而 MinHash 签名只需要几百个整数比如 200 个整型数字极大地减少了存储空间。计算速度飞跃比对两个几百维的数组是否相等比比对两个几万词的文本交集要快得多。大数据利器由于签名长度固定可以将海量文本的对比转化为矩阵并行运算非常适合 MapReduce、Spark 等分布式架构。5. 经典应用场景网页去重 / 文本近似查重搜索引擎如 Google在爬取海量网页时用 MinHash 快速找出内容高度相似的镜像网页或抄袭文章。推荐系统计算用户协同过滤中的相似度。如果两个用户看过的电影集合 MinHash 相似度高就可以互相推荐。生物信息学在 DNA 序列比对中用于快速寻找相似的基因片段。总结与延伸MinHash 解决了“单个配对太慢”的问题。但在面对数亿级别的数据时两两比对签名依然会有O ( N 2 ) O(N^2)O(N2)的复杂度。因此在实际工程中MinHash 通常会配合LSH局部敏感哈希Locality-Sensitive Hashing一起使用。LSH 能够将相似的 MinHash 签名分到同一个“桶”中让系统只需要比对同一个桶内的文档从而将时间复杂度降到接近O ( N ) O(N)O(N)。
