NLP项目中：如何用哈希算法及汉明距离判断文档近似相似？

一、为什么汉明距离能判断文档近似相似 #

首先要明确：必须用局部敏感哈希（LSH）生成文档指纹，比如SimHash、MinHash，不能用MD5/SHA这类普通哈希——普通哈希对文档微小改动会产生完全不同的结果，而LSH的特性是：相似文档的指纹二进制串差异极小，不相似的差异极大。

汉明距离就是两个二进制指纹中，对应位取值不同的数量。比如指纹A是1010，指纹B是1001，汉明距离就是2（第3、4位不同）。LSH保证了相似文档的汉明距离会远小于不相似文档，所以可以用这个距离来量化相似度。

二、汉明距离的计算步骤 #

1. 先生成文档的LSH指纹 #

以SimHash为例，流程是：

• 对文档分词，给每个词赋予权重（比如TF-IDF值）
• 每个词通过哈希函数生成固定长度的二进制串，再根据权重正负翻转对应位（正权重保留，负权重取反）
• 把所有词的二进制串按位求和，最后将求和结果中大于0的位设为1，小于等于0的设为0，得到最终的SimHash指纹（通常是64位或128位整数）

2. 计算汉明距离 #

如果指纹是整数形式（比如64位整数），直接用异或+统计1的个数就能快速计算：

def calc_hamming_distance(fp1, fp2):
    # fp1和fp2是64位整数类型的文档指纹
    xor_val = fp1 ^ fp2
    return bin(xor_val).count('1')

如果是字符串形式的二进制串，直接遍历每一位对比计数：

def calc_hamming_distance_str(fp_str1, fp_str2):
    if len(fp_str1) != len(fp_str2):
        raise ValueError("指纹长度必须一致")
    return sum(c1 != c2 for c1, c2 in zip(fp_str1, fp_str2))

三、相似度判定的阈值选择 #

没有固定的通用阈值，要结合业务场景和指纹长度来定，核心是用真实样本测试找区分点：

• 指纹长度参考：
  • 64位指纹：通常把阈值设为3_{5——汉明距离≤5时，判定为近似相似；>10时基本是不相似；5}10之间属于中度相似，可根据需求调整。
  • 128位指纹：阈值可设为6~10，逻辑和64位一致，长度翻倍阈值也近似翻倍。
• 业务场景调整：
  • 严格查重（比如学术论文抄袭检测）：阈值设低（比如64位取≤3），减少误判。
  • 内容相似推荐（比如新闻聚合）：阈值设高（比如64位取≤7），覆盖更多相似内容。
• 测试验证：
  准备一批已知相似/不相似的文档对，统计它们的汉明距离分布，找到能把两类样本明显分开的阈值——比如相似文档的距离都≤4，不相似的都≥8，那阈值就可以设为5。

注意事项 #

• 不要用普通哈希计算汉明距离，完全没有意义，必须用LSH类的指纹算法。
• 指纹长度越长，能区分的精度越高，但计算和存储成本也会上升，64位是平衡性能和精度的常用选择。

内容的提问来源于stack exchange，提问作者Ankit bk