汉明距离是以理查德·卫斯里·汉明的名字命名的,汉明在误差检测与校正码的基础性论文中首次引入这个概念这个所谓的距离,是指两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。
汉明距离有一个最为鲜明的特点就是它比较的两个字符串必须等长,否则距离不成立。它的核心原理就是如何通过字符替换(最初应用在通讯中实际上是二进制的0-1替换),能将一个字符串替换成另外一个字符串。维基百科给定了几个样例。(字符下标0为起始下标)
- “karolin” 和 “kathrin” 的汉明距离为(字符2 3 4替换)
- “karolin” 和 “kerstin” 的汉明距离为(字符1 3 4替换)
- 1011101 和 1001001 的汉明距离为(字符2 4替换)
- 2173896 和 2233796 的汉明距离为(字符1 2 4替换)
Python实现:
1 2 3 4 5 |
def hamming_distance(s1, s2): """Return the Hamming distance between equal-length sequences""" if len(s1) != len(s2): raise ValueError("Undefined for sequences of unequal length") return sum(el1 != el2 for el1, el2 in zip(s1, s2)) |
汉明距离主要应用在通信编码领域上,用于制定可纠错的编码体系。在机器学习领域中,汉明距离也常常被用于作为一种距离的度量方式。在LSH算法汉明距离也有重要的应用。
与汉明距离比较相近的是编辑距离,具体请查看:使用Python计算文本相似性之编辑距离
打赏作者微信支付

支付宝
