我要评论对百万级以上的数据做相似文档去重时，往往会面临性能瓶颈。最小哈希（minhash）结合局部敏感哈希（lsh）为我们提供了高效的解决方案。
一、 jaccard相似度：相似性度量的基础
jaccard相似度衡量两个集合的相似程度：
j(a,b) = |a ∩ b| / |a ∪ b|
在文档去重中，我们首先将文档转换为特征集合。常用方法包括：
1. 词级别的shingles
对于中文文档，通常先分词，然后生成k个连续词的片段：
# 示例：文档"我在学习编程"
分词后：["我", "在", "学习", "编程"]
3-shingles：{"我 在 学习", "在 学习 编程"}
代码实现：
import jieba
def generate_word_shingles(text, k=3):
"""
生成词级别的shingles
"""
# 分词
words = list(jieba.cut(text))
# 生成k个连续词的片段
shingles = set()
for i in range(len(words) - k + 1):
shingle = ' '.join(words[i:i + k])
shingles.add(shingle)
return shingles
# 示例
text = "我在学习编程"
shingles = generate_word_shingles(text, k=3)
print("3-shingles:", shingles)
# 输出: {'我 在 学习', '在 学习 编程'}
2. 字符级别的n-grams
text1的3-grams集合: {"我在学", "在学习", "学习编", "习编程"}
text2的3-grams集合: {"我现在", "现在学", "在学习", "学习编", "习编程"}
交集 = {"在学习", "学习编", "习编程"} = 3个
并集 = {"我在学", "在学习", "学习编", "习编程", "我现在", "现在学"} = 6个
jaccard相似度 = 3/6 = 0.5
代码实现：
def generate_char_ngrams(text, n=3):
"""
生成字符级别的n-grams
参数：
text: 输入文本
n: n-gram的大小
返回：
set: n-grams集合
"""
ngrams = set()
for i in range(len(text) - n + 1):
ngram = text[i:i + n]
ngrams.add(ngram)
return ngrams
# 示例
text1 = "我在学习编程"
text2 = "我现在学习编程"
ngrams1 = generate_char_ngrams(text1, n=3)
ngrams2 = generate_char_ngrams(text2, n=3)
print("text1的3-grams集合:", ngrams1)
print("text2的3-grams集合:", ngrams2)
# 计算jaccard相似度
intersection = ngrams1.intersection(ngrams2)
union = ngrams1.union(ngrams2)
jaccard_sim = len(intersection) / len(union)
print("交集:", intersection)
print("并集:", union)
print("jaccard相似度:", jaccard_sim)
二、 最小哈希：从集合相似度到签名相似度
1. 数学原理
对于一次随机排列π：
p[min(π(a)) = min(π(b))] = j(a,b)
其中min(π(s))表示集合s在排列π中的最小元素
2. 最小哈希过程
我们使用哈希函数模拟随机排列。以下示例展示3个不同哈希函数的工作过程：
文档a的shingles: {"我在学", "在学习", "学习编", "习编程"}
文档b的shingles: {"我现在", "现在学", "在学习", "学习编", "习编程"}
哈希函数h₁:
h₁("我在学") = 150
h₁("在学习") = 80 ← 两个文档的最小值！
h₁("学习编") = 200
h₁("习编程") = 180
h₁("我现在") = 250
h₁("现在学") = 300
文档a的min-hash₁ = min(150,80,200,180) = 80
文档b的min-hash₁ = min(250,300,80,200,180) = 80
结果：相等
哈希函数h₂:
h₂("我在学") = 30 ← 文档a的最小值！
h₂("在学习") = 150
h₂("学习编") = 200
h₂("习编程") = 180
h₂("我现在") = 25 ← 文档b的最小值！
h₂("现在学") = 300
文档a的min-hash₂ = 30
文档b的min-hash₂ = 25
结果：不相等
哈希函数h₃:
h₃("我在学") = 400
h₃("在学习") = 250
h₃("学习编") = 50 ← 两个文档的最小值！
h₃("习编程") = 150
h₃("我现在") = 300
h₃("现在学") = 350
文档a的min-hash₃ = 50
文档b的min-hash₃ = 50
结果：相等
代码实现（注：与示例数据不同）：
import hashlib
def hash_shingle(shingle, hash_func_num):
"""
对shingle进行哈希
"""
# 使用不同的哈希函数模拟随机排列
# 使用不同的盐值来模拟不同的哈希函数
salt = f"salt_{hash_func_num}"
data = (shingle + salt).encode('utf-8')
# 使用md5哈希并转换为整数
hash_hex = hashlib.md5(data).hexdigest()
hash_int = int(hash_hex, 16) % (10 ** 6) # 取模得到合适大小的整数
return hash_int
def calculate_minhash(shingles_set, num_hash_funcs=3):
"""
计算文档的最小哈希签名
"""
# 初始化最小哈希值为无穷大
minhash_signature = [float('inf')] * num_hash_funcs
for shingle in shingles_set:
for i in range(num_hash_funcs):
hash_value = hash_shingle(shingle, i)
if hash_value < minhash_signature[i]:
minhash_signature[i] = hash_value
return minhash_signature
# 文档a和b的shingles（使用字符级别的3-grams）
doca_shingles = {"我在学", "在学习", "学习编", "习编程"}
docb_shingles = {"我现在", "现在学", "在学习", "学习编", "习编程"}
# 计算最小哈希签名
minhash_a = calculate_minhash(doca_shingles, num_hash_funcs=300)
minhash_b = calculate_minhash(docb_shingles, num_hash_funcs=300)
print("文档a的300维哈希签名:", minhash_a)
print("文档b的300维哈希签名:", minhash_b)
# 计算签名相似度
def signature_similarity(siga, sigb):
"""计算两个签名的jaccard相似度估计值"""
matches = sum(1 for a, b in zip(siga, sigb) if a == b)
return matches / len(siga)
similarity = signature_similarity(minhash_a, minhash_b)
print("签名相似度估计值:", similarity)
3. n维哈希签名
n维哈希签名包含n个哈希函数对应的n个最小值：
文档a的3维哈希签名: [80, 30, 50] 文档b的3维哈希签名: [80, 25, 50]
签名的相似度计算
def signature_similarity(siga, sigb):
"""计算两个签名的jaccard相似度估计值"""
matches = sum(1 for a, b in zip(siga, sigb) if a == b)
return matches / len(siga)
# 示例
similarity = signature_similarity([80, 30, 50], [80, 25, 50])
# 2/3 ≈ 0.667（接近真实值0.5）
三、 为什么需要多个哈希函数？
1. 统计精度原理
根据大数定律，当哈希函数足够多时，签名相似度会收敛到真实jaccard相似度
2. 不同哈希数量下的精度
通过计算签名相似度估计值的置信区间，展示随着哈希函数数量的增加，最小哈希方法对真实jaccard相似度的估计精度如何提升。
置信区间表示在一定的置信水平下（此处为95%），真实相似度落在一个区间内的概率。
- 区间越窄，表示估计越精确。
- 区间越宽，表示估计的不确定性越高。
import math
def confidence_interval(n, s=0.5):
"""计算95%置信区间"""
std = math.sqrt(s * (1 - s) / n)
margin = 1.96 * std
return [max(0, s - margin), min(1, s + margin)]
print(confidence_interval(1, s=0.5))
print(confidence_interval(10, s=0.5))
print(confidence_interval(100, s=0.5))
print(confidence_interval(500, s=0.5))
print(confidence_interval(1000, s=0.5))
[0, 1] [0.19009678930349883, 0.8099032106965012] [0.402, 0.598] [0.4561730676410041, 0.5438269323589959] [0.4690096789303499, 0.5309903210696502]
四、 局部敏感哈希：加速相似搜索
1. lsh核心思想
如果两个文档整体相似，那么它们的签名在某些局部片段很可能完全相同。lsh将长签名切分成多个片段（bands），只要求某些片段匹配。
2. 签名分片示例
在实际应用中，我们通常设计bands数量能被签名长度整除
假设120维原始签名： [123, 456, 789, 321, 654, 987, ..., 888] 以切成20个片为例（每片6维）： 片 1: [123, 456, 789, ..., ...] 片 2: [..., ..., ..., ..., ...] ... 片 20: [..., ..., ..., ..., 888]
为每个片哈希成一个键值
片 1: = hash(tuple(band1)) # 如 0x1a2b3c 片 2: = hash(tuple(band2)) # 如 0x4d5e6f 片 3: = hash(tuple(band3)) # 如 0x7a8b9c 片 4: = hash(tuple(band4)) # 如 0xd1e2f3
3. 数学原理
设两个文档相似度为s，每个片有r行，共有b个片(band)：
def lsh_probability(s, r=6, b=20):
"""计算lsh匹配概率"""
prob_one_band = s ** r # 单个band匹配的概率
prob_at_least_one = 1 - (1 - prob_one_band) ** b
return prob_at_least_one
# 示例：相似度0.8的文档
prob = lsh_probability(0.8, 6, 20) # ≈ 0.9940
# 99.4%的概率会被lsh放到同一个桶中
4. lsh索引构建
| 键值 | 片 | 文档 |
|---|---|---|
| 0x1a2b3c | [123, 456, 789, …, …] | [文档a, 文档x, 文档y] |
| 0x4d5e6f | […, …, …, …, …] | [文档b, 文档c] |
| 0x7a8b9c | […, …, …, …, …] | [文档d] |
到此，我们便构建完成了lsh哈希与文档的对应关系，在使用时，只检查文档的各个片在哈希表中是否存在，将匹配的文档再合并为候选集，进一步精确相似度计算。
五、 应用场景
1. 适用场景
搜索引擎去重：去除重复网页
新闻聚合：识别同一事件的不同报道
论文查重：检测学术不端
代码查重：识别抄袭代码
商品去重：合并相似商品描述
2. 技术限制
短文本效果差：shingles数量不足时精度下降
语义相似度：对同义替换不敏感
参数敏感：需要根据数据调整参数
近似算法：存在假阳性和假阴性
六、 总结
最小哈希结合局部敏感哈希为大规模文档去重提供了高效的解决方案
数学基础坚实：基于jaccard相似度的概率估计
计算高效：将o(n²)复杂度降为近似o(n)
内存友好：固定维度签名大幅减少存储需求
可扩展性强：支持分布式和流式处理
以上就是python最小哈希实现海量文档去重的具体方案的详细内容，更多关于python最小哈希文档去重的资料请关注代码网其它相关文章！
发表评论