1 简介

编辑距离,也叫莱文斯坦距离(Levenshtein),是针对二个字符串例如英文字的差异程度的量化量测，量测方式是看至少需要多少次的处理才能将一个字符串变成另一个字符串。

三种转换方式：

插入一个字符
删除一个字符
替换一个字符

2 分析

对于两个字符串str1和str2，一共有六种操作：

对str1 插入一个字符，对str2删除一个字符
对str1删除一个字符，对str2插入一个字符
对str1替换一个字符，对str2替换一个字符

实际上只有三种操作 不难看出上述六种操作种，成对出现的操作结果是一样的，只需要选一个就可以，例如1中，假设str1位hllo,str2为hello,则对str1插入e变为hello与str2删除e变为hllo是等价的，其他两种情况类似。

总结下来就是：

对str1 插入一个字符
对str2插入一个字符
修改str1的一个字符

3 转移方程

假设我们现在知道了str1的字串sub_str1 hll 到 str2的字串 sub_str2 he的编辑距离, 那么

假设我们经过k次操作后sub_str1 变为了h, sub_str2为 he, 那么这时只需经过一步操作 sub_str1加一个e就可以将两个变为相同的字符串
假设我们经过k次操作后sub_str1变为了hle, sub_str2为he，那么这时只需经过一步操作 sub_str2中间插入l就可以使得两个字符相同。
假设我们经过k次操作后sub_str1变为了hl，sub_str2为he , 那么这时只需一步操作替换sub_str1的l为e就可以使得两个字符相同

从这里我们可以看出经过次操作，下一步的编辑距离和上一次的相关，不管是对str1插入、str2插入还是str1替换，在多一步操作便可以得到这一次的状态。

好了，既然是和上一步的状态有关，那么我们该考虑动态规划了。

设 D[i][j] 表示 str1 的前 i 个字母和 str2 的前 j 个字母之间的编辑距离。

下面是重点

对于D[i][j],变为它的方式无非就三种：

由str1插入一个字符得到。那么此时应该是D[i][j-1]【我们现在匹配的是str2中第j个，前面我们已经匹配好它的前j-1个，即D[i][j-1],现在在给str1插入一个字符，使得和str2的第j个相等，故D[i][j] = D[i][j-1]+1)】
由str2插入一个字符得到。那么此时应该是D[i-1][j]【我们现在匹配的是str1中第i个，前面我们已经匹配好它的前i-1个，即D[i-1][j],现在在给str2插入一个字符，使得和str1的第i个相等，故D[i][j] = D[i-1][j]+1)】
由str1修改一个字符得到。那么此时应该是D[i-1][j-1]【现在问题是str1前i-1个和str2前j-1个匹配好了，即D[i-1][j-1], 但是呢现在的问题是str1第i个和str2第j个字符不相等。怎么办，修改str1第i个为str2第j个不就好了。故D[i][j] = D[i-1][j-1]+1)】。但是呢str1第i个字符可能和str2第j个字符相等，那么这时D[i][j] = D[i-1][j-1])

也就是，D[i][j]可能来自三中状态，那既然是求最优，min一下就好了。

D[i][j] = min(D[i][j−1]+1,D[i−1][j]+1,D[i−1][j−1]) + (1 if str[i]==str[j])

4 源码

4.1 dp1


def levenshtein(str1, str2):
    """

    计算 str1 与 str2 的 levenshtein distance
    :param str1: str
    :param str2: str
    :return:  a number, int
    """

    str1_len = len(str1)
    str2_len = len(str2)

    """ 有一个str 为空 """
    if str1_len == 0 or str2_len == 0:
        return str1_len + str2_len

    dp = [[0] * (str2_len+1) for _ in range(str1_len+1)]

    """ init dp """
    for i in range(str1_len+1):
        dp[i][0] = i
    for j in range(str2_len+1):
        dp[0][j] = j

    for i in range(1, str1_len+1):
        for j in range(1, str2_len+1):
            str1_add = dp[i][j - 1] + 1
            str2_add = dp[i - 1][j] + 1
            str1_rpc = dp[i - 1][j - 1] + 1 if str1[i - 1] != str2[j - 1] else dp[i - 1][j - 1]

            dp[i][j] = min(str1_add, str2_add, str1_rpc)

    return dp[str1_len][str2_len]

4.2 dp2

D[i][j] = min(D[i][j−1]+1,D[i−1][j]+1,D[i−1][j−1]) + (1 if str[i]==str[j])

从状态转移方程中可以看出，D[i][j]只和三个量有关，但是我们开辟了一个n*m的list, 那么问题来了，可以在空间上优化吗？解决办法来了，我们只需开辟一个m维的list的就可以了，来表示原先二维数组中的列的个数，即存放一行的值。在迭代的过程中，一行一行计算，利用这一次算出来的数据，将数组覆盖掉，即将这一行的结果存放进数组，然后计算下一行，以此类推，直到最后一行。

计算当前 d[j]是，实际上d[j]前面存放的相当于原先二维数组中中的d[i][0],d[i][1],...,d[i][j-1],从d[j]到d[m-1]存放的是

d[i-1][j],d[i-1][j+1],...,d[i-1],d[m-1],只是其左上的元素没有记录下来，那么我们用一个变量来保存它就可以了。

画图解释起来可能比较好，但比较麻烦，如果你还没有听懂，那么我建议你画个图就秒懂。

具体代码如下：


def levenshtein2(str1, str2):
    """

    计算 str1 与 str2 的 levenshtein distance
    :param str1: str
    :param str2: str
    :return:  a number, int
    """
    str1_len = len(str1)
    str2_len = len(str2)

    """ 有一个str 为空 """
    if str1_len == 0 or str2_len == 0:
        return str1_len + str2_len

    dp = list(range(str2_len + 1))

    for i in range(str1_len):
        str1_rpc = dp[0]
        dp[0] = i + 1
        for j in range(1, 1 + str2_len):
            dp[j], str1_rpc = min(dp[j - 1] + 1, dp[j] + 1, str1_rpc + 1 if str1[i] != str2[j - 1] else str1_rpc), dp[
                j]

    return dp[-1]

4.3 dp3

根据dp3我们知道了，可以节约空间，那么问题来了，可不可以进一步呢，答案是肯定的。

例如我们现在有str1长度为2，str2长度为10000,那么按照dp2的代码，我们需要开辟一个10001的数组(python中为list), 那么如果我们交换一下str1和str2不就好了，开辟一个长度为3 的数组就可以了。同时时间复杂是不变的，都是两层循环，复杂度都是n*m.

def levenshtein3(str1, str2):
    if len(str1) < len(str2):
        str1, str2 = str2, str1

    return levenshtein2(str1, str2)

str1 = "1f"
str2 = "execution"

得到的结果如下：

5 文本相似度

编辑距离算法被数据科学家广泛应用，是用作机器翻译和语音识别评价标准的基本算法

公式如下；

ED(A,B)表示的是A，B两个句子之间的编辑距离。

def similarity_levenshtein(str1, str2):
    """

    利用 levenshtein 距离计算两个句子相似度
    :param str1:
    :param str2:
    :return:  a double, 0-1
    """
    max_len = max(len(str1), len(str2))

    return 1 - levenshtein3(str1, str2) / max_len