NLP——数据去重方法总结

注：本文包含 AI 辅助创作

整体总结

  • 在 NLP 数据去重中，常用的方法有 精确 Hash，N-gram，MinHash 和 SimHash 等，其中
    • 精确 Hash ：完全重复检测
    • N-gram 、MinHash 和 SimHash 主要用于近似重复（Near-duplicate）检测
  • 各种去重方法的核心是，他们对“局部修改”的敏感度不同
  • 实战经验：
    • 极短文本或极少数据，可以直接使用 Query（或样本）Key，构造 dict 即可
    • 短文本 + 少数据量，建议使用 N-gram + 精确 Jaccard
    • 长文本建议使用 SimHash 方法
    • 其他情况建议使用类似 MinHash + LSH 或 Embedding + FAISS 方法

精确 Hash (Exact Hash)

  • 核心思想是使用加密级哈希算法（如 MD5、SHA-1）将文本映射为固定长度的字符串
    • 只要文本有一个字节不同，哈希值就完全不同
    • 部分处理中我们也会考虑将文本转换为小写并去除多余空格再进行比较
  • 适用场景于去除完全一致的日志、系统报错、重复爬取的完全相同网页
  • 速度极快、无碰撞（概率忽略不计）
  • 缺点是完全无法识别“差一个标点”或“差几个字”的近似文本
  • 代码示例： 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    import hashlib

    def exact_hash(text: str) -> str:
        return hashlib.md5(text.encode('utf-8')).hexdigest()

    # 测试
    t1 = "我爱自然语言处理"
    t2 = "我爱自然语言处理！"  # 多了一个感叹号
    print(f"文本1 Hash: {exact_hash(t1)}")
    print(f"文本2 Hash: {exact_hash(t2)}")
    # 输出两个完全不同的字符串

N-gram (基于集合的相似度)

  • 核心思想是将文本切分成连续的 N 个字符（或词） 组成的滑动窗口集合
    • 通过计算两个集合的 Jaccard 相似度（交集大小 / 并集大小）来判断重复程度
  • 适用于短文本查重、数据清洗时的初步过滤
  • 优点是直观、可解释性强，能捕捉局部字词顺序
  • 缺点是计算开销大（需存储全量集合），N 太大漏匹配，N 太小噪音多
    • N-gram 的复杂度是很大的，在大规模数据集（百万级）上时几乎不可用，除非其中一个是比较小的数据集（其实也慢）
      • 长度为 L 的文本，提取 N-gram 为复杂度时 \(O(L)\)
    • 在使用 N-gram 前，也可以考虑使用一些其他方法先过滤一些，缩小量级
      • 比如对于绝对重复很多的场景，可以使用精确 Hash (MD5) 做第一轮极速过滤，剩下的再用 N-gram 精细看
  • 代码示例： 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    def get_ngrams(text: str, n: int = 3):
        """提取字符级 N-gram"""
        # 在文本首尾添加特殊边界符，防止短文本扰动
        padded = f"^{text}$"
        return {padded[i:i+n] for i in range(len(padded) - n + 1)}

    def jaccard_similarity(text1: str, text2: str, n: int = 3):
        set1 = get_ngrams(text1, n)
        set2 = get_ngrams(text2, n)
        intersection = len(set1 & set2)
        union = len(set1 | set2)
        return intersection / union if union != 0 else 0

    # 测试
    t1 = "我爱自然语言处理"
    t2 = "我爱自然语言处理技术"  # 仅多了"技术"
    print(f"N-gram 相似度: {jaccard_similarity(t1, t2, n=2):.2f}") 
    # 输出通常在 0.7~0.9 之间，说明很相似

MinHash

  • 核心思想是为了解决 N-gram 在大规模数据集（百万级）上两两比较的 \(O(N^2)\) 难题
    • 将高维的 N-gram 集合通过多个随机哈希函数映射为 固定长度的签名向量（指纹）
    • 通过签名向量来无偏估计 原始的 Jaccard 相似度
  • 一般配合 LSH (局部敏感哈希) 使用，将相似文档分到同一个桶中，避免全量比对
  • 优点是海量数据下计算极快，内存占用小
  • 缺点是实现复杂，结果是概率估计（非精确值）
  • 示例代码： 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    from datasketch import MinHash

    def create_minhash(text: str, num_perm: int = 128):
        """将文本转换为 MinHash 签名"""
        # 提取 N-gram (这里用字符级 3-gram)
        ngrams = get_ngrams(text, n=3) 
        m = MinHash(num_perm=num_perm)  # num_perm 越大，估计越准
        for gram in ngrams:
            m.update(gram.encode('utf-8'))
        return m

    # 测试
    t1 = "我爱自然语言处理"
    t2 = "我爱自然语言处理技术"
    m1 = create_minhash(t1)
    m2 = create_minhash(t2)

    # 计算 Jaccard 相似度的估计值
    estimated_sim = m1.jaccard(m2)
    print(f"MinHash 估计的 Jaccard 相似度: {estimated_sim:.2f}")
    # 该值非常接近上面 N-gram 直接计算的 Jaccard 结果

SimHash

  • 核心思想是专门针对长文本（如整篇文章、网页）设计的指纹算法
    • SimHash 将文本中的每个词（带权重，如 TF-IDF）映射到固定位数（通常是 64 位或 128 位）的二进制向量，通过累加降维得到最终的哈希指纹
    • 两个文本的相似度通过汉明距离（二进制中不同位的个数）来衡量
  • 适用于海量网页去重（Google 早期使用）、搜索引擎索引去重
  • 优点是指纹极短（64bit），存储方便，使用汉明距离比较速度极快
  • 缺点是对短文本效果很差（噪声占主导），实现需要加权
  • 示例笔记： 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    import hashlib

    def simhash(text: str, hash_bits: int = 64):
        # 1. 简单分词（这里按字符切分，实际应用会用 jieba 结合 TF-IDF 权重）
        tokens = list(text) 
        
        # 2. 初始化长度为 hash_bits 的向量
        v = [0] * hash_bits
        
        for token in tokens:
            # 计算 token 的哈希值（这里用 MD5 取前 hash_bits 位）
            h = int(hashlib.md5(token.encode('utf-8')).hexdigest(), 16)
            # 3. 加权累加（这里权重设为 1，实际应用按词频调大，SimHash 的核心优势在于加权（通常用 TF-IDF））
            for i in range(hash_bits):
                bit = (h >> i) & 1
                if bit:
                    v[i] += 1   # 该位为1，加权重
                else:
                    v[i] -= 1   # 该位为0，减权重
                    
        # 4. 降维：大于0置1，小于等于0置0
        fingerprint = 0
        for i in range(hash_bits):
            if v[i] > 0:
                fingerprint |= (1 << i)
        return fingerprint

    def hamming_distance(fp1: int, fp2: int) -> int:
        return bin(fp1 ^ fp2).count('1')

    # 测试
    t1 = "自然语言处理是人工智能的重要分支"
    t2 = "自然语言处理是AI的重要分支"  # 仅将"人工智能"替换为"AI"
    fp1 = simhash(t1, hash_bits=16)  # 为了演示取16位
    fp2 = simhash(t2, hash_bits=16)

    print(f"指纹1 (二进制): {bin(fp1)}")
    print(f"指纹2 (二进制): {bin(fp2)}")
    print(f"汉明距离: {hamming_distance(fp1, fp2)}")
    # 汉明距离越小（通常 < 3~5），说明文本越近似重复