汉明距离（Hamming Distance）

​1. 定义​

汉明距离是指两个等长字符串在相同位置上不同字符的个数。它常用于衡量两个字符串的相似度，广泛应用于编码理论、信息论、密码学、生物信息学等领域。

​2. 数学表达​

给定两个等长的字符串 x 和 y，汉明距离 d(x,y) 定义为：

其中：

• n 是字符串的长度，
• xi​ 和 yi​ 分别是 x 和 y 的第 i 个字符，
• Ⅱ(⋅) 是指示函数（当条件成立时返回 1，否则返回 0）。

​3. 示例​

• ​二进制字符串​：

  • x="10110", y="11110"
  • 比较每一位：
    • 第 1 位：1=1 → 相同
    • 第 2 位：0 != 1 → 不同（+1）
    • 第 3 位：1=1 → 相同
    • 第 4 位：1=1 → 相同
    • 第 5 位：0=0 → 相同
  • ​汉明距离 d(x,y)=1​​

• ​ASCII 字符串​：

  • x="karolin", y="kathrin"
  • 比较每一位：
    • k = k → 相同
    • a = a → 相同
    • r ≠ t → 不同（+1）
    • o ≠ h → 不同（+1）
    • l = r → 不同（+1） 
    • i = i → 相同
    • n = n → 相同
  • ​汉明距离 d(x,y)=3

​4. 计算方法​

• ​逐位比较法​（适用于短字符串）：
  • 直接遍历两个字符串的每一位，统计不同字符的数量。
• ​异或运算（XOR）​​（适用于二进制字符串）：
  • 对两个二进制数进行按位异或，然后统计结果中 1 的个数（即 popcount 或 bit_count）。

​5. 代码实现（Python）​​

def hamming_distance(x: str, y: str) -> int:
    if len(x) != len(y):
        raise ValueError("Strings must be of equal length")
    return sum(c1 != c2 for c1, c2 in zip(x, y))

# 示例
x = "10110"
y = "11110"
print(hamming_distance(x, y))  # 输出: 1

​6. 应用场景​

1. ​纠错编码（Error-Correcting Codes）​​：
   • 如汉明码（Hamming Code），用于检测和纠正数据传输中的错误。
2. ​模式识别（Pattern Recognition）​​：
   • 比较两个特征向量的相似度。
3. ​生物信息学（Bioinformatics）​​：
   • 比较 DNA 序列的相似性（如 SNP 分析）。
4. ​密码学（Cryptography）​​：
   • 衡量密钥或哈希值的差异。

​7. 扩展：加权汉明距离​

如果不同字符的“代价”不同，可以定义加权汉明距离​：

其中 wi​ 是第 i 位的权重。

​8. 相关概念​

• ​编辑距离（Levenshtein Distance）​​：
  • 允许插入、删除、替换操作，计算两个字符串的最小编辑步数。
• ​Jaccard 相似度​：
  • 用于集合相似度计算，不要求等长。

​9. 总结​

汉明距离是衡量等长字符串差异的基础工具，在计算机科学和工程领域有广泛应用。