什么是汉明距离（Hamming Distance）？从原理到实现与实际应用

Hamming Distance 是一种非常简单的距离度量。对于两个长度相同的字符串、数组或比特序列，它表示对应位置上不同元素的数量。

虽然概念简单，但它广泛应用于算法、编码理论、错误检测、通信、二进制特征比较以及部分机器学习任务。

核心思想

例如：

karolin
kathrin

逐个位置比较：

k a r o l i n
k a t h r i n
    ↑ ↑ ↑

共有三个不同位置，因此：

Hamming Distance = 3

经典定义要求两个序列长度相同。

数学定义

对于长度为 n 的两个序列 x 和 y：

H(x, y) = Σ [x[i] ≠ y[i]]

对应位置相同记为 0，不同记为 1。

算法步骤

1. 检查两个输入长度是否相同。
2. 初始化计数器 distance = 0。
3. 遍历所有位置。
4. 如果两个元素不同，计数器加一。
5. 返回结果。

function hammingDistance(a, b):
    if length(a) != length(b):
        error

    distance = 0

    for i from 0 to length(a) - 1:
        if a[i] != b[i]:
            distance++

    return distance

TypeScript 实现

function hammingDistance(a: string, b: string): number {
  if (a.length !== b.length) {
    throw new Error("Inputs must have the same length.");
  }

  let distance = 0;

  for (let i = 0; i < a.length; i++) {
    if (a[i] !== b[i]) {
      distance++;
    }
  }

  return distance;
}

时间与空间复杂度

Time Complexity: O(n)
Space Complexity: O(1)

算法只需要遍历一次输入，并且不需要额外的大型数据结构。

二进制整数与 XOR

比较两个整数的二进制位时，XOR 非常方便。

1010
XOR
1110
----
0100

XOR 结果中的每个 1 都表示原始两个数在该位置不同。

因此：

Hamming Distance = (x XOR y) 中 1 的数量

可以使用 Brian Kernighan 技巧：

function hammingDistanceBits(x: number, y: number): number {
  let value = x ^ y;
  let distance = 0;

  while (value !== 0) {
    value &= value - 1;
    distance++;
  }

  return distance;
}

value & (value - 1) 每次都会清除一个最低位的 1。

实际应用

1. 错误检测与纠错编码

Hamming Distance 是 Error Detection 和 Error-Correcting Codes 中的重要概念，可用于分析传输数据发生了多少位变化。

2. 数字系统与通信

它可以快速比较两个二进制模式之间的差异。

3. 计算机视觉

当图像特征使用 Binary Descriptor 表示时，可以利用 Hamming Distance 高效比较特征。

4. 机器学习

对于二进制特征向量或编码后的类别数据，它可以作为简单的距离度量。

A = [1, 0, 1, 1, 0]
B = [1, 1, 1, 0, 0]

Distance = 2

Hamming Distance 与 Levenshtein Distance

Hamming Distance 只比较对应位置，并且通常要求长度相同。

Levenshtein Distance 则支持：

• Insert
• Delete
• Replace

例如 cat 和 cats 长度不同，因此经典 Hamming Distance 不适用，而 Levenshtein Distance 为 1。

什么时候适合使用？

当满足以下情况时很适合：

• 两个序列长度相同。
• 元素位置很重要。
• 只关心不匹配数量。
• 数据是二进制形式。
• 需要简单、高效的距离计算。

如果还需要考虑插入和删除，则 Levenshtein Distance 通常更合适。

常见面试题

给定两个整数 x 和 y，计算把 x 变成 y 需要改变多少个比特。

解决方法：

1. 计算 x XOR y
2. 统计结果中 1 的数量

例如：

1 = 0001
4 = 0100
XOR = 0101

因此：

Hamming Distance = 2

总结

Hamming Distance 可以概括为：

两个等长序列在对应位置上不同的数量。

对于字符串，可以通过一次线性遍历实现；对于整数，常见方法是 XOR + set-bit counting。由于简单、高效，它在算法、通信、编码、数据处理、计算机视觉和技术面试中都很实用。