二、汉明距离

简介

汉明距离是以理查德·卫斯里·汉明的名字命名的，汉明在误差检测与校正码的基础性论文中首次引入这个概念

这个所谓的距离，是指两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。

维基百科

中文维基：快戳我；

英文维基：英文不好别戳我。

基本原理

汉明距离有一个最为鲜明的特点就是它比较的两个字符串必须等长，否则距离不成立。

它的核心原理就是如何通过字符替换（最初应用在通讯中实际上是二进制的0-1替换），能将一个字符串替换成另外一个字符串。

维基百科给定了几个样例。(字符下标0为起始下标)

• "karolin" 和 "kathrin" 的汉明距离为 3.(字符2 3 4替换)
• "karolin" 和 "kerstin" 的汉明距离为 3.(字符1 3 4替换)
• 1011101 和 1001001 的汉明距离为 2.(字符2 4替换)
• 2173896 和 2233796 的汉明距离为 3.(字符1 2 4替换)

Python实现

python3中已经内置汉明距离函数了，几点说明：

• zip函数接收两个字符串，并返回一个元组列表。假如str1 = ’abc‘， str2 = ’123‘，则返回[('a', '1'), ('b', '2'), ('c', '3')]。
• 这只是python内置的函数实现，如果觉得zip效率太低，则可以考虑自己实现。

#!/user/bin/env python  
# -*- coding: utf-8 -*-  
  
def hammingDistance(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))