编辑距离是针对二个字符串（例如英文字）的差异程度的量化量测，量测方式是看至少需要多少次的处理才能将一个字符串变成另一个字符串。编辑距离可以用在自然语言处理中，例如拼写检查可以根据一个拼错的字和其他正确的字的编辑距离，判断哪一个（或哪几个）是比较可能的字。DNA 也可以视为用 A、C、G 和 T 组成的字符串，因此编辑距离也用在生物信息学中，判断二个 DNA 的类似程度。Unix 下的 diff 及 patch 即是利用编辑距离来进行文本编辑对比的例子。

编辑距离有几种不同的定义，差异在可以对字符串进行的处理。

在莱文斯坦距离中，可以删除、加入、取代字符串中的任何一个字元，也是较常用的编辑距离定义，常常提到编辑距离时，指的就是莱文斯坦距离。 也存在其他编辑距离的定义方式，例如 Damerau-Levenshtein 距离是一种莱文斯坦距离的变种，但允许以单一操作交换相邻的两个字符（称为字符转置），如 AB→BA 的距离是 1（交换）而非 2（先删除再插入、或者两次替换）。 LCS（最长公共子序列）距离只允许删除、加入字元。 Jaro 距离只允许字符转置。 汉明距离只允许取代字元。

用处#

编辑距离可以用来查看两个字符串之间至少需要修改多少字符才能一致。来判断两个字符串的相似度. 配合分词技术或者是 NLP 技术,还能更进一步判断两个字符串的语义是否一致.

例如: 单词纠错，内容相似度 等。

原理#

本文将以 莱文斯坦距离 (Levenshtein distance) 为例。

他通过构建一个二维数组, 从左上角开始, 向右遍历, 到最右边则换行, 一直计算到右下角处. 每次取左上角,上面,和左面的最小值, 若字符值相等则当前格值不加一,反之加一. 计算结束时,右下角的值就是两个字符串之间的最小距离 (即莱文斯坦距离).

例子#

kitten -> sitten (k->s) sitten -> sittin (e->i) sittin -> sitting (add g)

实现#

def levenshtin_distance(str1, str2):
    m = [[x if y == 0 else y if x == 0 else 0 for y in range(len(str2)+1)] for x in range(len(str1)+1)]
    for x in range(1,len(str1)+1):
        for y in range(1,len(str2)+1):
            if str1[x-1] == str2[y-1]:
                substitutionCost = 0
            else:
                substitutionCost = 1
            m[x][y] = min(m[x-1][y] + 1, m[x][y-1] + 1, m[x-1][y-1] + substitutionCost)
    return m[-1][-1]

总结#

编辑距离的思路非常简单, 就是检查字符串中字符的变化情况,而且算法时间复杂度在 O2, 用来纠正错误的单词, 也是非常方便的,如果用在中文的相似度分析,大部分情况也是勉强能用吧,要怪就怪中文博大精深,多一个字少一个字寓意差距非常大.