汉明距离与编辑距离

汉明距离（Hamming distance）

汉明距离来自于信号处理中，1变0，0变1的错误程度。所以它的算法很简单，异或然后数1的个数。

它也可以用来表征二进制数据的相近程度，比如两张图片的比特位进行异或，数出1的个数。

计算一个整数中1位的个数，有很精巧的算法：

while (n) {
    n &= n-1;
}

编辑距离（Levenshtein Distance）

汉明距离只是简单的替换，串长相等，而编辑距离有三种操作：替换、添加、删除，它更能表征abc和aabc之间的相似性。

编辑距离的算法使用动态规划，比如有两个串a和b，分别长为m和n，那么计算它俩的编辑距离时间复杂度为O(m*n)，空间复杂度为O(min(m, n))。

          c    o    f    f    e    e
     0    1    2    3    4    5    6
c    1    0    1    2    3    4    5
a    2    1    1    2    3    4    5
f    3    2    2    1    2    3    4
e    4    3    3    2    2    2    3

• 如果最上方的字符等于最左方的字符，则为左上方的数字。否则为左上方的数字+1
• 左方数字+1
• 上方数字+1

实现也很简单，python实现如下：

def LevenshteinDistance(s1, s2):
    """
    距离距离
    """
    l1, l2 = len(s1), len(s2)
    if l1 == 0 or l2 == 0:
        return max(l1, l2)

    if l1 < l2:
        l1, l2 = l2, l1
        s1, s2 = s2, s1

    gv = lambda l, n: 100000 if n < 0 else l[n]

    d = range(1, l2 + 1)
    for i in range(l1):
        prev = i
        for j in range(l2):
            tmp = d[j]
            d[j] = min(gv(d, j-1)+1, d[j]+1, prev if s1[i] == s2[j] else prev + 1)
            prev = tmp

    return d[-1]

编辑距离的动态规划算法跟计算最长公共子序列挺相近，一个是求异，一个是求同。

编辑距离在纠错、补全、模糊实体识别、文档相似计算、svm、DNA比对等场景均有运用。