汉明距离与编辑距离

汉明距离(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比对等场景均有运用。

发表于2017-03-15 23:43   修改于2017-03-15 23:45   评论:0   阅读:185  



回到顶部

首页 | 关于我 | 关于本站 | 站内留言 | rss
python logo   django logo