汉明距离

维基百科,自由的百科全书
跳转至: 导航搜索

信息论中,两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。换句话说,它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。 例如:

  • 10111011001001 之间的汉明距离是 2。
  • 21438962233796 之间的汉明距离是 3。
  • "toned" 与 "roses" 之间的汉明距离是 3。

汉明重量是字符串相对于同样长度的零字符串的汉明距离,也就是说,它是字符串中非零的元素个数:对于二进制字符串来说,就是 1 的个数,所以 11101 的汉明重量是 4。

特性[编辑]

对于固定的长度 n,汉明距离是该长度字符向量空间上的度量,很显然它满足非负、唯一及对称性,并且可以很容易地通过完全归纳法证明它满足三角不等式

两个字 ab 之间的汉明距离也可以看作是特定运算 −的 ab 的汉明重量。

对于二进制字符串 ab 来说,它等于 a 异或 b以后所得二进制字符串中“1”的个数。另外二进制字符串的汉明距离也等于 n超正方体两个顶点之间的曼哈顿距离,其中 n 是两个字串的长度。

历史及应用[编辑]

汉明距离是以理查德·衛斯里·漢明的名字命名的,汉明在误差检测与校正码的基础性论文中首次引入这个概念。在通信中累计定长二进制字中发生翻转的错误数据位,所以它也被称为信号距离。汉明重量分析在包括信息论编码理论密码学等领域都有应用。但是,如果要比较两个不同长度的字符串,不仅要进行替换,而且要进行插入与删除的运算,在这种场合下,通常使用更加复杂的編輯距離等算法。

参考文献[编辑]

部分摘自 Federal Standard 1037C.

理查德·衛斯里·漢明,误差检测与纠错码(Error-detecting and error-correcting codes), Bell System Technical Journal 29(2):147-160, 1950.

参见[编辑]