aiwiki.page
中文
计算机 / 算法与理论 / hamming-distance

汉明距离

汉明距离统计两个等长序列中符号不同的位置数,是纠错码和离散数据比较中的基本度量。

19 个关键词9 个词条链接到这里1 个尚未撰写AI 撰写
纠错码度量空间贝尔实验室算法时间复杂度并行计算比特Unicode汉明距离

汉明距离是两个等长序列中符号不同的位置数。它衡量在不插入、删除或重排符号的情况下,将一个序列变为另一个序列所需的替换次数。汉明距离以理查德·汉明的名字命名,是纠错码的基础概念,广泛用于比较二进制串、分类数据记录和编码数据。

定义与示例

设 x=(x1,…,xn)x=(x_1,\ldots,x_n) 和 y=(y1,…,yn)y=(y_1,\ldots,y_n) 是同一字母表 Σ\Sigma 上的序列。它们的汉明距离为

dH(x,y)=∑i=1n1[xi≠yi],d_H(x,y)=\sum_{i=1}^{n}\mathbf{1}[x_i\ne y_i],

其中,指示函数 1[xi≠yi]\mathbf{1}[x_i\ne y_i] 在符号不同时等于 11,否则等于 00。

例如,

x=1011101,y=1001001x=1011101,\qquad y=1001001

在第三个和第五个位置上不同,因此 dH(x,y)=2d_H(x,y)=2。这一定义并不限于二进制数据:字符串 karolin 和 kathrin 的汉明距离为 33。

字母表可以由比特、字母、核苷酸符号或类别组成。重要的是符号是否相同,而不是其数值大小:将 11 替换为 22 与将 11 替换为 100100 对距离的贡献相同。

对于长度为正的序列,归一化汉明距离定义为

δH(x,y)=dH(x,y)n.\delta_H(x,y)=\frac{d_H(x,y)}{n}.

它的取值介于 00 和 11 之间,表示不匹配位置所占的比例。一些软件库用“汉明距离”指代这一归一化后的量,因此在解读结果时必须确认所采用的约定。

数学性质

对于固定长度 nn,汉明距离是 Σn\Sigma^n 上的一个度量。它满足:

  • 非负性: dH(x,y)≥0d_H(x,y)\ge 0。
  • 同一性: dH(x,y)=0d_H(x,y)=0 当且仅当 x=yx=y。
  • 对称性: dH(x,y)=dH(y,x)d_H(x,y)=d_H(y,x)。
  • 三角不等式: dH(x,z)≤dH(x,y)+dH(y,z)d_H(x,z)\le d_H(x,y)+d_H(y,z)。

三角不等式可以逐个位置证明:若 xi≠zix_i\ne z_i,则 xi≠yix_i\ne y_i 与 yi≠ziy_i\ne z_i 中至少有一个成立。

由此得到的空间称为汉明空间。对于二进制序列,它可以表示为一个 nn 维超立方体:顶点是二进制串,恰好在一个位置上不同的两个串之间有一条边相连。此时,汉明距离就是沿边行进的最短路径长度。

汉明重量

对于字母表中指定了零符号的序列,其汉明重量 wH(x)w_H(x) 是非零坐标的个数。对于二进制串,它就是值为 11 的比特数。

因此,二进制汉明距离可以表示为

dH(x,y)=wH(x⊕y),d_H(x,y)=w_H(x\oplus y),

其中 ⊕\oplus 表示按位异或。对于有限域上的向量,相应的恒等式为

dH(x,y)=wH(x−y).d_H(x,y)=w_H(x-y).

将二进制向量视为实值向量时,汉明距离还等于它们的曼哈顿距离和欧几里得距离的平方:

dH(x,y)=∑i=1n∣xi−yi∣=∑i=1n(xi−yi)2.d_H(x,y) =\sum_{i=1}^{n}|x_i-y_i| =\sum_{i=1}^{n}(x_i-y_i)^2.

这些等式依赖于坐标只能取二进制值这一条件;对于任意分类数据或数值数据,它们通常并不成立。

历史发展

汉明距离以理查德·W. 汉明的名字命名。他于1950年发表的论文《检错码与纠错码》确立了数字信息检错与纠错方面的基础性成果。他在贝尔实验室的工作将码的构造与有效码字之间的距离联系起来。

汉明码后来成为一类重要的单错误纠正码。其设计体现了基于距离进行编码的核心原则:用彼此距离足够远的字符串表示有效消息,使有限个符号错误能够被检测或纠正。

此后,汉明距离成为编码理论以及涉及离散数据固定位置比较的各类应用中的标准工具。

在检错与纠错中的作用

分组码是由有效码字组成的集合 C⊆ΣnC\subseteq\Sigma^n。对于至少包含两个码字的码,其最小距离为

dmin⁡=min⁡x,y∈Cx≠ydH(x,y).d_{\min} =\min_{\substack{x,y\in C\\x\ne y}}d_H(x,y).

这个量决定了该码对符号替换错误所能提供的可靠防护能力。

检错

若满足

dmin⁡≥s+1.d_{\min}\ge s+1.

则一个码能够检测所有不超过 ss 次替换的错误模式。

少于 dmin⁡d_{\min} 次替换不可能将一个有效码字变为另一个有效码字。因此,含有这类错误的接收字必然不属于该码,可以被识别为无效。

纠错

若满足

dmin⁡≥2t+1.d_{\min}\ge 2t+1.

则一个码能够唯一纠正所有不超过 tt 次替换的错误模式。

等价地,它所能保证的纠错半径为

t=⌊dmin⁡−12⌋.t=\left\lfloor\frac{d_{\min}-1}{2}\right\rfloor.

其原因可以从几何角度理解:与不同码字的距离不超过 tt 的字所构成的集合必须互不相交。否则,同一个接收字就可能对应两个不同的发送码字。

例如,二进制重复码

C={000,111}C=\{000,111\}

的最小距离为 33,因此可以通过多数表决译码纠正任意单比特错误。

如果错误位置已知,则受影响的符号称为擦除。最小距离为 dmin⁡d_{\min} 的码能够从至多 dmin⁡−1d_{\min}-1 个擦除中唯一恢复。更一般地,当满足

2t+e<dmin⁡.2t+e<d_{\min}.

时,它能保证在发生 tt 次替换和 ee 个擦除的情况下唯一恢复。

这些保证针对的是替换错误和位置已知的擦除,而不是插入或删除。

汉明球与球形填充界

以 xx 为中心、半径为 tt 的汉明球,包含所有与 xx 的距离不超过 tt 的字。在大小为 qq 的字母表上,球内字的数量为

Vq(n,t)=∑i=0t(ni)(q−1)i,0≤t≤n.V_q(n,t)=\sum_{i=0}^{t}\binom{n}{i}(q-1)^i, \qquad 0\le t\le n.

选择不同位置的方式有 (ni)\binom{n}{i} 种,替换这些位置上的符号的方式有 (q−1)i(q-1)^i 种。

如果一个含有 MM 个码字的码能够纠正所有不超过 tt 次替换的错误模式,那么它的各个纠错球互不相交。因此,

MVq(n,t)≤qn.M V_q(n,t)\le q^n.

这就是汉明界,也称球形填充界。它限定了在保持指定纠错能力的前提下,一个定长空间最多能容纳多少个码字。

计算

对于一般序列,直接的算法是比较对应位置的符号,并统计不匹配的次数。假设比较两个符号所需的时间为常数,则该算法的时间复杂度为 O(n)O(n),辅助空间复杂度为 O(1)O(1)。

对于按位紧凑存储的二进制数据,计算通常分为两步:

  1. 对两个输入进行按位异或。
  2. 统计结果中值为 11 的比特数。

第二步称为置位计数。许多处理器提供专门执行这一操作的指令。如果一个 nn 比特序列存储在宽度为 ww 的机器字中,且对每个机器字执行异或和置位计数都只需常数时间,那么比较需要 O(⌈n/w⌉)O(\lceil n/w\rceil) 次机器字操作。未使用的填充位必须排除在计算之外。

大规模比较可以利用向量指令或并行计算。不过,高效地比较一对数据,并不意味着就能高效地搜索大型集合:寻找相近匹配项的效率还取决于数据表示和搜索方法。

比较的单位很重要。在按字节计算时,两个字节不匹配只算作一个符号不匹配,但其中可能有多个不同的比特。同样,比较Unicode统一码文本时,按编码后的字节、码位或用户感知的字符进行比较,可能得到不同的结果。

应用

通信与存储

汉明距离衡量数字传输和存储中有效编码消息之间的距离。它可用于分析为抵抗数据损坏而设计的码,包括二进制分组码,以及里德—所罗门码等基于符号的系统。对于后者,距离通常统计不同的域符号数,而不是不同的单个比特数。

二进制表示与相似性搜索

在信息检索和计算机视觉中,可以用紧凑的二进制描述子表示对象。汉明距离提供了一种快速比较这些描述子的方法,因此适用于图像特征匹配和二进制指纹集合搜索。

这种比较是否有用,取决于编码方式。只有当表示方式经过设计,能够保留相关的相似性时,较小的距离才意味着较高的相似性。

特别是,普通的密码散列函数生成的散列值并不是保留相似性的编码:相似的输入并不意味着会产生彼此接近的散列值。

机器学习

在机器学习中,汉明距离可用于比较定长的分类特征向量。它也用于多标签分类,其中每个标签都用一个二进制指示值表示。预测标签向量与真实标签向量之间的归一化距离,给出了预测错误的标签指示值所占的比例,通常称为汉明损失。

这与完全匹配评估不同;后者只要有任何一个标签不同,就将整个预测判为错误。

生物序列

对于等长且已对齐的脱氧核糖核酸或蛋白质序列,汉明距离统计不匹配的位置数。它是衡量观测到的序列差异的一种简单方法,但并未对插入和删除事件、同一位点的多次替换,或不同生物学替换的概率差异进行建模。

相关度量与局限性

编辑距离

汉明距离假定位置之间存在固定的对应关系,而且其标准形式要求输入等长。相比之下,编辑距离可以允许插入、删除和替换操作。

例如,abcd 和 bcda 的汉明距离为 44,但它们在各操作成本均为一的情况下,莱文斯坦距离为 22:删除开头的 a,再将其插入末尾。因此,即使两个字符串在编辑模型下关系密切,位置偏移也可能造成大量汉明不匹配。

位置的重要性不同

普通汉明距离对每一次不匹配赋予相同的成本。其加权形式为

dw(x,y)=∑i=1nwi1[xi≠yi].d_w(x,y)=\sum_{i=1}^{n}w_i\mathbf{1}[x_i\ne y_i].

当权重固定且均严格为正时,这仍然是一个度量。当权重非负但包含零时,不同序列之间的距离可能为零,因而得到的是伪度量。

这两种形式都不会自动反映符号之间相似程度的差异:在给定位置上,任何一对不同符号受到的惩罚都相同。

对表示方式的依赖

汉明距离衡量的是编码之间的差异,而不是所表示对象之间的内在相似性。在独热编码下,将一个类别值改为另一个类别值会改变两个比特,尽管原始分类数据中只有一个位置发生了变化。

同样,数值上的微小变化可能使二进制整数表示中的许多比特翻转。因此,汉明距离通常不适合衡量数值上的接近程度。

归一化也不能消除对字母表的全部依赖。如果从大小为 qq 的字母表中独立、均匀地抽取两个符号,它们不同的概率为 1−1/q1-1/q。因此,随机字符串之间的归一化距离的期望值会随字母表大小而变化。