1. 项目概述当海量数据遇上“相似性”难题在数据爆炸的时代我们每天都在和“相似性”打交道。比如一个新闻聚合平台如何判断两篇来自不同媒体的文章是否在讲同一件事一个电商平台如何从海量商品中找出描述不同但实质相同的产品以进行去重或关联推荐又或者一个内容审核系统如何快速发现抄袭或高度相似的文本这些问题的核心都指向一个计算任务大规模集合的相似度估算。传统方法比如直接计算两个集合的杰卡德相似系数Jaccard Similarity在概念上很简单交集大小除以并集大小。但当你面对的是动辄包含数百万甚至上亿个元素如网页中的分词、商品的属性词、用户的兴趣标签的集合时计算精确的相似度就成了一场噩梦。你需要将两个庞大的集合完全加载到内存进行复杂的集合运算其时间复杂度和空间开销都是难以承受的。正是在这种背景下minHash最小哈希技术脱颖而出。它不是一种机器学习模型而是一种精巧的、基于概率的降维与近似计算技术是处理海量数据相似性问题的“瑞士军刀”。我第一次在工程中接触minHash是为了解决一个用户画像相似度匹配的实时计算问题。当用户标签集达到千万级别时传统的比对方法完全不可行而minHash方案将比对时间从分钟级压缩到了毫秒级并且保证了可接受的精度。它的核心思想非常优雅与其笨拙地比较整个集合不如为每个集合生成一个极短的“指纹”即哈希签名通过比较这些指纹的相似度来近似地推断原始集合的相似度。这种方法牺牲了一点精确性换来了几个数量级的性能提升在许多大数据和机器学习场景中这是非常划算的交易。接下来我将为你彻底拆解minHash的原理从直觉理解到数学证明再到手把手的实现和应用。无论你是正在构建推荐系统、处理自然语言还是从事任何需要处理大规模稀疏高维数据的领域理解minHash都将是你的得力工具。2. 核心原理拆解从直觉到数学要理解minHash我们不能一上来就扔公式。让我们从一个具体的场景开始逐步建立起直觉。2.1 问题定义与杰卡德相似度假设我们有两个集合 A 和 B A {“机器学习” “算法” “Python” “深度学习”} B {“算法” “Python” “大数据” “统计”}我们想知道它们有多相似。杰卡德相似度 J(A, B) 给出了一个精确的度量 J(A, B) |A ∩ B| / |A ∪ B| 其中|A ∩ B| 是交集的大小|A ∪ B| 是并集的大小。对于上面的例子 A ∩ B {“算法” “Python”} 大小为2。 A ∪ B {“机器学习” “算法” “Python” “深度学习” “大数据” “统计”} 大小为6。 所以J(A, B) 2 / 6 ≈ 0.333。计算过程需要完整遍历两个集合。如果集合是网页中所有shingle文本片段的集合大小可能是数万那么计算代价就很高。2.2 MinHash的巧妙构思minHash的核心洞察是我们可以设计一个随机过程使得在一次随机试验中某个特定事件发生的概率恰好等于这两个集合的杰卡德相似度。这个随机过程是这样的我们把全集A和B所有可能元素的集合进行一个随机的全排列。你可以想象把所有的元素随机打乱排成一长队。我们沿着这个被打乱的队伍从头开始往后走。我们记录下在队伍中第一个同时出现在集合A和集合B中的元素其位置索引。同时我们也记录下在队伍中第一个出现在集合A或集合B中的元素即出现在A∪B中的位置。现在关键来了在随机全排列下“第一个出现的A∪B中的元素恰好也属于A∩B”的概率是多少让我们仔细分析这个随机试验的样本空间。第一个出现在A∪B中的元素它可能是A∪B中的任何一个元素并且由于排列是随机的每个元素成为“第一个”的机会是均等的。那么这个“幸运儿”恰好也落在A∩B中的概率就是A∩B中的元素数量占A∪B中元素数量的比例。这正是杰卡德相似度的定义P(第一个A∪B中的元素 ∈ A∩B) |A∩B| / |A∪B| J(A, B)这就是minHash的基石。一次随机排列下的观察其结果的概率等于我们想要求的相似度。2.3 从单次试验到最小哈希函数上面的随机试验虽然巧妙但一次试验的结果要么是1第一个元素在交集中要么是0不在方差太大无法用作估计。我们需要多次独立重复试验来得到一个稳定的估计值。这就是最小哈希族的概念。我们不再进行物理上的“随机排列”那效率太低。我们使用一组精心设计的哈希函数来模拟无穷多次的随机排列。每个哈希函数 h 将任意元素映射到一个整数哈希值。对于一个集合 S我们定义该集合在哈希函数 h 下的minHash值为minHash_h(S) min_{x ∈ S} h(x)即对集合S中的所有元素应用哈希函数h然后取得到的哈希值中的最小值。为什么这个“最小值”能模拟“随机排列下的第一个元素”呢想象一下如果哈希函数h很好它产生的哈希值可以看作是给所有元素一个随机的、唯一的“排队号码”。那么拥有最小“排队号码”即最小哈希值的那个元素不就相当于在一次随机排列中排在“第一”位的元素吗因此minHash_h(S)这个值可以看作是这次随机排列下集合S的“代表元素”的哈希值。2.4 最小哈希签名与相似度估计现在对于两个集合A和B我们使用同一个哈希函数h。 我们来思考事件minHash_h(A) minHash_h(B)。什么时候这两个最小值会相等只有当拥有全局最小哈希值的那个元素同时存在于集合A和集合B中时才会发生。如果这个最小元素只存在于A中而不在B中那么minHash_h(A)是这个最小元素的哈希值而minHash_h(B)会是B中某个其他元素的更大的哈希值两者必然不相等。因此事件minHash_h(A) minHash_h(B)发生的概率就等于“全局最小哈希值对应的元素属于A∩B”的概率。根据我们之前的分析这个概率就是 J(A, B)。于是我们得到了minHash最关键的定理P[minHash_h(A) minHash_h(B)] J(A, B)这意味着单个哈希函数下两个集合的最小哈希值相等的概率等于它们的杰卡德相似度。在实践中我们使用k个不同的、独立的哈希函数 h1, h2, ..., hk为每个集合S计算一个签名SignatureSignature(S) [minHash_{h1}(S), minHash_{h2}(S), ..., minHash_{hk}(S)]这个签名是一个长度为k的整数向量。对于集合A和B我们比较它们的签名向量统计在k个位置上值相等的数量记为X。那么X/k 就是 J(A, B) 的一个无偏估计J(A, B) ≈ X / kk越大这个估计就越准确但计算和存储开销也越大。我们需要在精度和效率之间做权衡。实操心得哈希函数的选择理论上哈希函数需要是独立的并且将元素均匀地映射到足够大的整数空间以避免碰撞。在实践中我们通常使用形式如h(x) (a*x b) mod p的哈希函数族其中a和b是随机选取的系数p是一个大质数。对于字符串元素需要先将其转换为一个整数例如用另一个哈希函数如MurmurHash再应用上述线性变换。选择不同的(a, b)对就可以快速生成大量“独立”的哈希函数这是工程实现中的常见技巧。3. 算法实现与关键细节理解了原理我们来看看如何具体实现它。这里我会用一个文本集合的例子展示从原始数据到minHash签名的完整流程并讨论每一个环节的工程细节。3.1 数据预处理从文本到集合minHash处理的是集合。对于文本数据我们首先需要将其转化为集合表示。最常用的方法是k-shingling。什么是shingle对于一段文本我们提取所有长度为k的连续字符序列或分词后的词序列。例如对于文本“机器学习”当k2字符级时得到的shingle集合是{“机器” “器学” “学习”}。这个集合就是我们要计算minHash签名的对象。如何选择kk值越大每个shingle的区分度越高但集合也会越稀疏。k值越小则相反。通常需要根据具体任务和文本长度来调整。对于网页去重k5到10是常见范围。一个经验法则是k应该大到足以使任意两个不同的文档产生大量不同的shingle。def get_k_shingles(text, k5): 生成文本的k-shingle集合字符级 if len(text) k: return {text} shingles set() for i in range(len(text) - k 1): shingle text[i:ik] shingles.add(shingle) return shingles # 示例 doc1 我爱机器学习 doc2 机器学习真有趣 shingles1 get_k_shingles(doc1, k2) # {我爱 爱机 机器 器学 学习} shingles2 get_k_shingles(doc2, k2) # {机器 器学 学习 习真 真有 有趣}预处理后每个文档都表示为一个由shingle组成的集合。这些集合就是minHash的输入。3.2 生成最小哈希签名这是算法的核心步骤。假设我们有N个文档它们的shingle集合组成了一个巨大的、稀疏的“元素-文档”矩阵。矩阵的行是所有可能的shingle全集列是文档。如果文档j包含shingle i则矩阵元素(i, j)为1否则为0。我们的目标是为每一列文档计算一个长度为k的签名向量。经典算法步骤如下选择k个独立的哈希函数 h1, h2, ..., hk。每个函数将行号或shingle的哈希值映射到一个大整数。初始化一个 k x N 的签名矩阵sig将所有值初始化为无穷大或一个非常大的数。对于矩阵的每一行 r即每一个shingle a. 计算该行在k个哈希函数下的值[h1(r), h2(r), ..., hk(r)]。 b. 对于每一列文档c - 如果行r在列c中的值为1即文档c包含该shingle - 对于每一个 i 从 1 到 k - 如果hi(r) sig[i][c]则令sig[i][c] hi(r)。 即如果这个shingle在当前哈希函数下产生的值比文档c当前记录的最小值还小就更新它。处理完所有行后sig矩阵的第c列就是文档c的minHash签名。这个算法需要遍历所有shingle行对于海量数据上百万行和大量文档上百万列其复杂度是 O(行数 * 列数 * k)这仍然是不可行的。3.3 工程优化行哈希与签名生成在实际工程中我们几乎从不显式构建那个庞大的“元素-文档”矩阵也几乎不真的去遍历所有可能的shingle全集。我们采用一种更高效的方法直接针对每个文档的shingle集合进行计算。优化后的算法针对单个文档集合S预先定义好k个哈希函数h1, h2, ..., hk。初始化一个长度为k的签名向量signature全部填充为MAX_INT。对于文档集合S中的每一个元素x即每一个shingle a. 将x转换成一个整数例如用hash(x)或mmh3.hash(x)。 b. 对于每一个哈希函数hi(i从1到k) - 计算hash_val hi(x)。这里hi作用于x的整数表示上。 - 如果hash_val signature[i]则signature[i] hash_val。遍历完S中所有元素后得到的signature向量就是该文档的minHash签名。这个算法的复杂度是 O(|S| * k)其中|S|是文档的shingle集合大小。由于k是一个固定的常数通常几十到几百而|S|是文档本身的属性这比遍历全集要高效得多。import mmh3 # 一个非加密的快速哈希库 class MinHash: def __init__(self, num_perm128): 初始化MinHash num_perm: 签名长度k即排列哈希函数的数量 self.num_perm num_perm # 生成num_perm个哈希函数的参数 (a, b) # 使用一个大质数作为模数这里用2^32-1 self.max_hash (1 32) - 1 self.permutations self._init_permutations(num_perm) def _init_permutations(self, num_perm): import random permutations [] for _ in range(num_perm): # 为每个哈希函数生成随机系数 a, b a random.randint(1, self.max_hash - 1) b random.randint(0, self.max_hash - 1) permutations.append((a, b)) return permutations def hash_func(self, x, a, b): 哈希函数h(x) (a * x b) % max_hash # 首先用mmh3将输入字符串哈希成一个整数 if isinstance(x, str): x mmh3.hash(x, signedFalse) # 得到无符号32位整数 return (a * x b) self.max_hash # 使用位与操作代替取模因为max_hash是2^n-1形式 def signature(self, shingle_set): 计算一个shingle集合的minHash签名 sig [self.max_hash] * self.num_perm # 初始化为最大值 for shingle in shingle_set: # 将shingle转换为整数种子 seed mmh3.hash(shingle, signedFalse) for i, (a, b) in enumerate(self.permutations): hash_val (a * seed b) self.max_hash if hash_val sig[i]: sig[i] hash_val return sig def jaccard_est(self, sig_a, sig_b): 根据两个签名估计杰卡德相似度 if len(sig_a) ! len(sig_b): raise ValueError(Signatures must have the same length) equal_count sum(1 for a, b in zip(sig_a, sig_b) if a b) return equal_count / len(sig_a) # 使用示例 minhasher MinHash(num_perm128) sig1 minhasher.signature(shingles1) sig2 minhasher.signature(shingles2) estimated_jaccard minhasher.jaccard_est(sig1, sig2) print(fEstimated Jaccard similarity: {estimated_jaccard:.4f})注意事项哈希种子的重要性在上面的实现中我们为每个哈希函数使用了固定的随机系数(a, b)。这意味着同一个MinHash对象产生的签名才是可比较的。在分布式系统中必须保证所有节点使用的哈希函数参数permutations完全一致否则计算出的签名将失去可比性。通常的做法是将这些参数序列化保存作为算法配置的一部分进行分发。4. 核心应用场景深度解析minHash的价值在于其效率这使得它能在一些对实时性要求高、数据量大的场景中成为核心技术。下面我们深入几个典型应用。4.1 大规模文档去重与抄袭检测这是minHash最经典的应用。在搜索引擎的爬虫系统中需要避免索引大量内容重复的网页。直接比较网页内容的编辑距离或余弦相似度成本极高。应用流程预处理对每个网页进行标准化去除HTML标签、广告、导航栏等提取正文文本。Shingling对正文文本生成k-shingle集合例如k9的字符shingle。生成签名为每个网页的shingle集合计算minHash签名例如长度k100。局部敏感哈希LSH这是minHash的“好搭档”。我们不会直接比较所有签名对那是O(N²)。LSH将长签名向量分段band只有那些在至少一个分段上完全相同的文档对才被认为是候选相似对需要进行进一步的精确相似度验证通过比较签名估计的Jaccard值。这极大地减少了需要比较的对数。去重决策对于LSH筛选出的候选对如果其估计的Jaccard相似度超过预设阈值如0.8则判定为重复或高度相似仅保留其中一个。优势将数十亿网页级别的两两比较问题转化为对固定长度签名如100个整数的快速比对和哈希分桶问题效率提升是指数级的。4.2 推荐系统中的近邻搜索在协同过滤中我们需要为用户寻找兴趣相似的其他用户UserCF或者为物品寻找相似的物品ItemCF。用户-物品交互矩阵是极其稀疏的用户只对少量物品有行为。用户的兴趣可以表示为一个物品ID的集合。应用流程集合表示每个用户表示为其有过正反馈点击、购买、评分高的物品ID集合。MinHash签名为每个用户的物品集合计算minHash签名。快速相似用户检索当需要为用户A进行推荐时 a. 计算用户A的签名。 b. 使用LSH在全体用户签名中快速检索出与A签名相似的候选用户集合B。这个过程避免了与所有用户逐一比较。 c. 对候选用户集合B可以进一步用签名精确估计与A的Jaccard相似度筛选出最相似的前K个用户。 d. 聚合这些相似用户喜欢的、且用户A未接触过的物品生成推荐列表。优势实现了在超大规模用户库中的实时近邻搜索使得UserCF算法能够在线应用。4.3 生物信息学中的序列比对在基因组学中比较两个DNA或蛋白质序列的相似性是常见任务。全序列比对如Smith-Waterman算法非常耗时。minHash提供了一种快速的近似方法尤其适用于宏基因组学中海量短序列的聚类和分类。应用流程以基因组序列为例K-mer表示将一条长序列切割成所有长度为k的连续子串称为k-mer。这类似于文本的shingle。一条序列就表示为其k-mer集合。MinHash签名为每个序列的k-mer集合计算签名。由于k-mer集合可能很大这里通常采用一种变体——最小消减哈希Minimizer或模块化minHash来进一步压缩签名大小。相似度估计与聚类通过比较序列签名的相似度可以快速评估序列之间的进化距离或功能相似性用于快速聚类大量测序读段或在大规模基因组数据库中进行同源性搜索如Mash、sourmash等工具的核心思想。优势将序列比对这个复杂的字符串匹配问题转化为集合相似度比较问题处理速度极快内存消耗小非常适合初步筛选和大型数据集分析。4.4 图像与视频特征匹配在计算机视觉中图像可以用局部特征点如SIFT、ORB的描述子集合来表示。直接匹配两幅图像的所有特征点是O(N²)的。应用流程特征提取从图像中提取大量局部特征描述子每个描述子是一个高维向量。特征量化/聚类通过聚类如K-Means构建一个视觉词汇表Visual Vocabulary。每个特征描述子被映射到最近的视觉单词聚类中心上。一幅图像就可以表示为其包含的视觉单词ID的集合词袋模型。MinHash签名为每幅图像的视觉单词集合计算minHash签名。快速图像检索给定一张查询图像计算其签名然后通过LSH在图像库中快速找到签名相似的候选图像再进行更精细的几何验证如RANSAC。优势将高维稠密的特征向量匹配转化为稀疏集合的相似度比较结合LSH可以实现海量图像库的实时检索。实操心得签名长度k与LSH参数的选择这是应用中最关键的调参环节。签名长度k直接影响估计的精度。k越大估计方差越小越接近真实Jaccard值但签名也越长计算和存储成本越高。通常k在128到512之间是一个较好的起点。LSH参数bands b, rows r我们将长度为k的签名分成b个band每个band有r行k b * r。LSH的判定规则是如果两个签名在至少一个band上完全相同则它们成为候选对。这个规则对应一个S形曲线的相似度概率函数。两个集合的真实相似度s成为候选对的概率是1 - (1 - s^r)^b。b和r的选择决定了召回率和精确率的权衡。增加r减少b会使曲线更陡峭只有相似度非常高的对才会被召回精确率高但召回率低。减少r增加b会使曲线更平缓较低相似度的对也有机会被召回召回率高但会混入更多不相似的对精确率低。通常我们需要根据业务对相似度的阈值要求来调整。假设我们想召回相似度t的文档对一个经验法则是选择b和r使得S形曲线在st处的概率较高如0.95而在s远小于t处的概率较低。5. 性能优化与高级变种基础的minHash已经很强大但在面对极端数据时仍有优化空间。下面介绍几种重要的变体和优化技术。5.1 加权MinHash (Weighted MinHash)标准的minHash处理的是集合二元特征存在或不存在。但在很多场景下特征是加权的。例如在文本中词频TF-IDF是权重在用户-物品矩阵中评分是权重。加权MinHash也称为ICWS MinHash扩展了minHash使其能够处理带权重的向量并估计加权杰卡德相似度或余弦相似度。其核心思想是将权重信息通过一种特定的变换融入到哈希值的生成过程中。一种常见的实现是“主动丢弃”法。对于向量的每一个非零维度根据其权重生成一系列“虚拟元素”然后对这些虚拟元素应用标准minHash。这样权重高的维度有更高的概率影响最终的minHash值。# 加权MinHash概念性伪代码简化 import numpy as np def weighted_minhash(feature_vector, weights, num_perm): feature_vector: 稀疏向量的非零维度索引列表 weights: 对应维度的权重列表 num_perm: 签名长度 signature [float(inf)] * num_perm for idx, weight in zip(feature_vector, weights): # 关键根据权重生成多个哈希值样本 # 一种方法是对于每个哈希函数hi生成一个“调整后的哈希值” # hash_val hi(idx) / weight (或类似变换) # 然后取所有idx, weight对中调整后哈希值的最小值 pass # 具体实现较复杂通常使用现成库如datasketch return signature使用datasketch库可以方便地计算加权MinHash。5.2 并行化与分布式计算当数据量极大时单机计算签名或进行LSH分桶可能成为瓶颈。MinHash天然适合并行化。签名计算的并行化数据并行将文档集合分片在不同机器上为各自分片的文档计算签名。由于每个文档的签名计算是独立的这很容易实现。任务并行针对单个大集合如果一个集合本身非常大例如一个巨型图的节点邻居集合可以将该集合的元素分片分别计算每个分片在哈希函数下的最小值然后再进行一次归并取最小值。但更常见的做法是使用“合并”Union操作。LSH的分布式处理 LSH分桶后每个桶内的文档对是候选对。在分布式系统如Spark中可以这样操作为所有文档计算签名。将每个文档的签名按照LSH的band进行切分。对于每个band将(band_id, band_hash_value)作为键文档ID作为值形成一个键值对。进行groupByKey操作将所有具有相同(band_id, band_hash_value)的文档ID分到同一个组里。这个组内的所有文档两两之间都是候选对。在每个组内进行文档对的相似度计算比较签名和过滤。这个过程可以很好地利用MapReduce范式进行分布式计算。5.3 流式MinHash与集合更新在很多场景下集合是动态变化的。例如用户的兴趣集合会随着新行为而增加新闻文章的热度词集合也会更新。我们不需要每次都从头重新计算整个集合的minHash签名。MinHash签名有一个非常好的性质对于集合的并操作其minHash签名可以通过对应位置取最小值来合并。 即如果Signature(A) [minHash_h1(A), ..., minHash_hk(A)]Signature(B)同理。 那么Signature(A ∪ B) [min(minHash_h1(A), minHash_h1(B)), ..., min(minHash_hk(A), minHash_hk(B))]。这意味着增量更新当向集合S中添加新元素x时我们只需要计算x在k个哈希函数下的值然后与S当前的签名向量逐位比较取最小值即可更新签名。复杂度是O(k)非常高效。流式计算在数据流中我们可以为每个键如用户ID维护一个minHash签名。当收到该键的一个新元素时就执行上述增量更新。这允许我们在流式系统中实时计算和追踪大规模集合的相似度。class StreamingMinHash: def __init__(self, num_perm128): self.num_perm num_perm self.permutations self._init_permutations(num_perm) self.max_hash (1 32) - 1 # 初始签名设为最大值 self.signature [self.max_hash] * num_perm def update(self, element): 向当前集合中添加一个元素并更新签名 seed mmh3.hash(str(element), signedFalse) for i, (a, b) in enumerate(self.permutations): hash_val (a * seed b) self.max_hash if hash_val self.signature[i]: self.signature[i] hash_val def merge(self, other_signature): 合并另一个签名对应集合的并操作 if len(self.signature) ! len(other_signature): raise ValueError(Signature length mismatch) merged_sig [min(a, b) for a, b in zip(self.signature, other_signature)] return merged_sig6. 常见陷阱、问题排查与实战技巧即使理解了原理和算法在实际应用中还是会遇到各种坑。下面是我在多次项目中总结的一些经验。6.1 精度不足与方差控制问题使用minHash估计的相似度与真实Jaccard值偏差较大结果不稳定。排查与解决检查签名长度kk太小是导致估计方差大的首要原因。根据切比雪夫不等式估计误差与1/√k成正比。将k从64增加到256通常能显著提升稳定性。可以通过在验证集上计算估计误差的均方根RMSE来选择合适的k。检查哈希函数质量确保使用的哈希函数具有良好的均匀性和独立性。使用简单的hash(x) % p可能因哈希碰撞导致偏差。推荐使用像MurmurHash3、CityHash这类经过验证的非加密哈希函数并结合(a*x b) mod p的形式生成哈希族。元素分布极端如果集合大小差异巨大小集合的minHash值可能更容易受到哈希随机性的影响。可以考虑对集合进行采样或加权但要注意这会改变相似度的定义。实操心得如何确定合适的k值一个实用的方法是准备一个小的标注数据集包含一些文档对及其真实Jaccard相似度。然后尝试不同的k值如32, 64, 128, 256, 512为每对文档计算minHash估计值。绘制估计值与真实值的散点图并计算相关系数R²和平均绝对误差MAE。选择那个在可接受的计算成本下能提供足够精度例如MAE 0.05的最小k值。6.2 计算性能瓶颈问题为海量文档计算签名或进行LSH连接时速度太慢。排查与解决剖析耗时环节Shingle生成对于长文本k-shingle集合可能非常大。尝试增大k值以减少集合大小或使用word shingle基于词代替char shingle基于字符后者集合通常更小。签名计算循环for shingle in set: for i in range(k): ...是热点。确保内层哈希计算是高效的使用整数运算。考虑使用NumPy向量化操作一次性计算一个shingle在所有k个哈希函数下的值。语言瓶颈Python等解释型语言在双层循环上可能较慢。对于性能关键部分可以考虑使用Cython、Numba加速或换用Java/Scala、Go等编译型语言实现。利用稀疏性大多数文档的shingle集合相对于全集是极稀疏的。使用高效的稀疏集合数据结构如Python的set或专门的结构如roaring bitmap进行存储和遍历。并行化如前所述签名计算是“令人尴尬的并行”任务。使用多进程如Python的multiprocessing或多机框架如Spark并行处理不同文档。6.3 内存消耗过大问题存储所有文档的minHash签名或LSH索引占用内存过多。排查与解决签名压缩minHash签名通常是32位或64位整数。可以考虑使用更短的整数类型如16位但要注意哈希值范围缩小可能增加碰撞风险。也可以使用压缩算法如Delta编码存储差值后使用变长整数编码。LSH索引优化LSH需要存储(band_id, hash_value) - [doc_ids]的映射。对于海量数据这个映射可能很大。使用外部存储当内存放不下时可以考虑使用Redis、RocksDB等键值存储来存放LSH桶。布隆过滤器如果只是为了快速判断是否存在候选对可以在每个LSH桶中使用布隆过滤器来近似表示文档ID集合能极大节省内存但会有一定的误报率。签名采样在LSH阶段不一定需要使用全部k个哈希值。可以只使用前k个k k来构建LSH索引以节省内存和计算量但这会进一步影响精度需要权衡。6.4 LSH调参与效果调优问题LSH返回的候选对要么太多包含大量不相似对要么太少漏掉了许多相似对。排查与解决理解S曲线回顾LSH的概率函数P 1 - (1 - s^r)^b。你需要根据业务定义的“相似”阈值t来调整b和r。目标让相似度t的文档对以高概率如0.95成为候选而相似度远低于t的文档对以低概率如0.05成为候选。你可以绘制不同(b, r)组合下的S曲线选择在st处有陡峭上升的曲线。多级LSH如果单一组(b, r)参数无法满足需求可以尝试使用多组参数构建多个LSH索引。查询时合并所有索引的结果。这相当于用更多的计算和存储来换取更好的召回率。动态参数对于相似度分布不均匀的数据可以对不同相似度区间的数据使用不同的LSH参数。但这需要先对数据分布有了解实现更复杂。6.5 哈希碰撞与签名冲突问题两个完全不同的元素经过哈希函数后得到了相同的值碰撞。在minHash中这会导致签名估计产生偏差。排查与解决增大哈希空间使用64位甚至128位的哈希值可以极大降低碰撞概率。在(a*x b) mod p中使用更大的质数p。使用抗碰撞哈希虽然minHash不要求密码学安全的哈希但使用像SHA-256这样的强哈希函数可以彻底避免碰撞但计算会更慢。通常像MurmurHash332位或128位在速度和碰撞率之间取得了很好的平衡。理解影响偶尔的哈希碰撞对minHash估计的期望值是无偏的但会引入额外的方差。如果k足够大这种方差可以被平均掉。如果对精度要求极高需要评估碰撞带来的影响。最后再分享一个在构建实时去重系统时的小技巧将minHash签名与布隆过滤器结合使用。首先用布隆过滤器快速过滤掉绝对不重复的新文档如果其大部分shingle都不在过滤器中然后只对通过过滤的文档计算minHash签名并进行LSH查询。这种两级过滤机制可以应对突发的高流量写入在保证去重效果的同时大幅降低计算负载。