汉明距离
长度相同的两个字符串之间的汉明距离，是指它们在对应位置上字符不同的个数。
换句话说，汉明距离表示把一个字符串转换成另一个字符串时，至少需要进行多少次字符替换。
设 \( s \) 和 \( t \) 是两个长度均为 \( n \) 的字符串，则它们的汉明距离 \( D_H(s,t) \) 定义为：
$$ D_H(s, t) = \sum_{i=1}^{n} \delta(s_i, t_i) $$
其中，\( s_i \) 和 \( t_i \) 分别表示字符串 \( s \) 和 \( t \) 在第 \( i \) 个位置上的字符。函数 \( \delta(s_i,t_i) \) 的定义如下：当 \( s_i \neq t_i \) 时取值为 1，否则取值为 0。
需要注意的是，汉明距离仅适用于长度相同的字符串。
示例
来看一个简单的例子：
$$ s = \text{"karbon"} $$
$$ t = \text{"carbon"} $$
由于两个字符串只有第一个字符不同（k 与 c），因此它们的汉明距离为 1。
例 2
下面这两个英文单词的汉明距离为 2：
$$ s = \text{"thing"} $$
$$ t = \text{"thank"} $$
它们共有两个位置不同：
第三个字母分别为 “i” 和 “a”，第五个字母分别为 “g” 和 “k”。
汉明距离诱导的度量拓扑
汉明距离满足度量的全部公理，因此能够在所有长度相同的字符串集合上定义一个度量空间。对于任意三个长度相同的字符串 \( x \)、\( y \) 和 \( z \)，它具有以下性质：
- 非负性
$$ D_H(x, y) \geq 0 \quad \text{且} \quad D_H(x, y)=0 \ \text{当且仅当} \ x=y $$
汉明距离统计的是对应位置上的不同字符数量，因此其值始终不小于 0。只有当两个字符串完全相同时，距离才等于 0。 - 对称性
$$ D_H(x, y) = D_H(y, x) $$
从 \( x \) 到 \( y \) 的距离与从 \( y \) 到 \( x \) 的距离完全相同，因为汉明距离只与对应位置是否相同有关，与比较方向无关。 - 三角不等式
$$ D_H(x, z) \leq D_H(x, y) + D_H(y, z) $$
对任意三个字符串 \( x \)、\( y \) 和 \( z \)，直接比较 \( x \) 与 \( z \) 得到的距离，不会超过经过中间字符串 \( y \) 所得到的两段距离之和。因为 \( x \) 与 \( z \) 的每一处差异，至少会出现在 \( x \) 与 \( y \) 或 \( y \) 与 \( z \) 的比较过程中。
因此，汉明距离在固定长度字符串组成的集合上定义了一个度量空间。
既然有了度量，就可以根据距离定义字符串之间的“邻近关系”，进一步建立相应的拓扑结构。
因此，汉明距离还可以诱导出一种度量拓扑。
设 \( x \) 是一个长度为 \( n \) 的字符串，\( r \) 为半径，则以 \( x \) 为中心、半径为 \( r \) 的开球（邻域）定义为所有与 \( x \) 的汉明距离小于 \( r \) 的字符串组成的集合：
$$ B(x,r)=\{y \mid D_H(x,y)
这些开球构成了度量拓扑的一组基。拓扑中的所有开集，都可以表示为这些开球的任意并集。
说明。长度固定为 \( n \) 的所有二进制字符串（或符号串）组成的是一个有限集合。因此，由汉明距离诱导出的拓扑实际上是离散拓扑。这意味着每个字符串既是一个开集，也是一个闭集。原因在于，只需取一个足够小的半径（例如 \( r=1 \)），每个开球中就只包含中心字符串本身，而不会包含其他字符串。
因此，对于有限个长度相同的字符串，汉明距离诱导出的度量拓扑就是离散拓扑。
例子
考虑下面这个由若干长度为 3 的二进制字符串组成的集合：
$$ X=\{000,001,011,110,111\} $$
下面以半径 \( r=2 \) 为例，构造由汉明距离诱导出的拓扑。
$$ B(x,r)=\{y \mid D_H(x,y)<2\} $$
由于汉明距离必须是整数，因此距离小于 2 等价于距离为 0 或 1。也就是说，每个开球包含中心字符串本身，以及所有仅有一个位置不同的字符串。
- 以 \( 000 \) 为中心的开球： $$ B(000,2)=\{000,001\} $$ 只有字符串 \( 001 \) 与 \( 000 \) 相差一个位置。
- 以 \( 001 \) 为中心的开球： $$ B(001,2)=\{001,000,011\} $$ 字符串 \( 000 \) 和 \( 011 \) 都与 \( 001 \) 相差一个位置。
- 以 \( 011 \) 为中心的开球： $$ B(011,2)=\{011,001,111\} $$ 字符串 \( 001 \) 和 \( 111 \) 都与 \( 011 \) 相差一个位置。
- 以 \( 110 \) 为中心的开球： $$ B(110,2)=\{110,111\} $$ 只有字符串 \( 111 \) 与 \( 110 \) 相差一个位置。
- 以 \( 111 \) 为中心的开球： $$ B(111,2)=\{111,011,110\} $$ 字符串 \( 011 \) 和 \( 110 \) 都与 \( 111 \) 相差一个位置。
这些开球共同构成了诱导拓扑的一组基。通过对它们进行任意并运算，可以得到拓扑中的其他开集。
说明。这里采用的是开球，因此使用严格不等式：$$ B(x,r)=\{y \mid D_H(x,y)<2\} $$ 如果需要定义闭球，则应改为小于等于： $$ C(x,r)=\{y \mid D_H(x,y)\le2\} $$
例如，集合 \( B(000,2) \) 与 \( B(110,2) \) 的并集为：
$$ B(000,2)\cup B(110,2) $$
已知
$$ B(000,2)=\{000,001\} $$
$$ B(110,2)=\{110,111\} $$
因此：
$$ B(000,2)\cup B(110,2)=\{000,001\}\cup\{110,111\} $$
即：
$$ B(000,2)\cup B(110,2)=\{000,001,110,111\} $$
因此，集合 \( \{000,001,110,111\} \) 也是该拓扑中的一个开集。
综上所述，汉明距离不仅能够定义度量空间，还能够诱导出相应的度量拓扑。在有限个等长字符串构成的集合上，这种拓扑最终表现为离散拓扑，而所有开集都可以由开球通过并运算构造得到。
其他情况也可以采用相同的方法进行分析。
