编程部落

Python最小哈希实现海量文档去重的具体方案

作者：

风君子

在

文章目录
  • Jaccard相似度衡量两个集合的相似程度： J(A,B) = |A ∩ B| / |A ∪ B| 在文档去重中，我们首先将文档转换为特征集合。常用方法包括：
  • 最小哈希结合局部敏感哈希为大规模文档去重提供了高效的解决方案数学基础坚实：基于Jaccard相似度的概率估计计算高效：将O(n²)复杂度降为近似O(n)内存友好：固定维度签名大幅减少存储需求可扩展性强：支持分布式和流式处理 以上就是Python最小哈希实现海量文档去重的具体方案的详细内容，更多关于Python最小哈希文档去重的资料请关注风君子博客其它相关文章！ 您可能感兴趣的文章: citespace数据处理:用python对Ref文档进行去重方式 python对excel文档去重及求和的实例 Python列表去重的3种最常用方法 Python使用CRC实现图片去重
    • 目录
    • 一、 Jaccard相似度：相似性度量的基础
      • 1. 词级别的Shingles
      • 2. 字符级别的n-grams
    • 二、 最小哈希：从集合相似度到签名相似度
      • 1. 数学原理
      • 2. 最小哈希过程
      • 3. N维哈希签名
    • 三、 为什么需要多个哈希函数？
      • 1. 统计精度原理
      • 2. 不同哈希数量下的精度
    • 四、 局部敏感哈希：加速相似搜索
      • 1. LSH核心思想
      • 2. 签名分片示例
      • 3. 数学原理
      • 4. LSH索引构建
    • 五、 应用场景
      • 1. 适用场景
      • 2. 技术限制
    • 六、 总结

      对百万级以上的数据做相似文档去重时，往往会面临性能瓶颈。最小哈希（MinHash）结合局部敏感哈希（LSH）为我们提供了高效的解决方案。

      Jaccard相似度衡量两个集合的相似程度：

      J(A,B) = |A ∩ B| / |A ∪ B|

      在文档去重中，我们首先将文档转换为特征集合。常用方法包括：

      对于中文文档，通常先分词，然后生成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)
# 输出: {'我 在 学习', '在 学习 编程'}


      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)

      对于一次随机排列π：

      P[min(π(A)) = min(π(B))] = J(A,B)

      其中min(π(S))表示集合S在排列π中的最小元素

      我们使用哈希函数模拟随机排列。以下示例展示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)

      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）

      根据大数定律，当哈希函数足够多时，签名相似度会收敛到真实Jaccard相似度

      通过计算签名相似度估计值的置信区间，展示随着哈希函数数量的增加，最小哈希方法对真实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]

      如果两个文档整体相似，那么它们的签名在某些局部片段很可能完全相同。LSH将长签名切分成多个片段（bands），只要求某些片段匹配。

      在实际应用中，我们通常设计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

      设两个文档相似度为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放到同一个桶中

      键值 片 文档
      0x1a2b3c [123, 456, 789, …, …] [文档A, 文档X, 文档Y]
      0x4d5e6f […, …, …, …, …] [文档B, 文档C]
      0x7a8b9c […, …, …, …, …] [文档D]

      到此，我们便构建完成了LSH哈希与文档的对应关系，在使用时，只检查文档的各个片在哈希表中是否存在，将匹配的文档再合并为候选集，进一步精确相似度计算。

      搜索引擎去重：去除重复网页
      新闻聚合：识别同一事件的不同报道
      论文查重：检测学术不端
      代码查重：识别抄袭代码
      商品去重：合并相似商品描述

      短文本效果差：shingles数量不足时精度下降
      语义相似度：对同义替换不敏感
      参数敏感：需要根据数据调整参数
      近似算法：存在假阳性和假阴性

      最小哈希结合局部敏感哈希为大规模文档去重提供了高效的解决方案
      数学基础坚实：基于Jaccard相似度的概率估计
      计算高效：将O(n²)复杂度降为近似O(n)
      内存友好：固定维度签名大幅减少存储需求
      可扩展性强：支持分布式和流式处理

      以上就是Python最小哈希实现海量文档去重的具体方案的详细内容，更多关于Python最小哈希文档去重的资料请关注风君子博客其它相关文章！

      您可能感兴趣的文章:

      • citespace数据处理:用python对Ref文档进行去重方式
      • python对excel文档去重及求和的实例
      • Python列表去重的3种最常用方法
      • Python使用CRC实现图片去重

      更多文章

      站内搜索

      标签云

      iphone 三星 信用卡 信贷 华为 小米 微软 快科技 手机 投资理财 支付宝 特斯拉 理财知识 电脑 科技 程序 股票 芯片 苹果 贷款 路由器 银行 银行卡 额度

      热门文章

      友情链接