详解编辑距离(Edit Distance)及其代码实现

2018-12-11 本文已影响81人 DejavuMoments

概述

编辑距离（Minimum Edit Distance，MED），由俄罗斯科学家 Vladimir Levenshtein 在1965年提出，也因此而得名 Levenshtein Distance。在信息论、语言学和计算机科学领域，Levenshtein Distance 是用来度量两个序列相似程度的指标。通俗地来讲，编辑距离指的是在两个单词 $<w_1,w_2>$ 之间，由其中一个单词 $w_1$ 转换为另一个单词 $w_2$ 所需要的最少单字符编辑操作次数。

在这里定义的单字符编辑操作有三种：

插入（Insertion）
删除（Deletion）
替换（Substitution）

譬如，"kitten" 和 "sitting" 这两个单词，由 "kitten" 转换为 "sitting" 需要的最少单字符编辑操作有：

1.kitten → sitten (substitution of "s" for "k")
2.sitten → sittin (substitution of "i" for "e")
3.sittin → sitting (insertion of "g" at the end)

因此，"kitten" 和 "sitting" 这两个单词之间的编辑距离为 3 。

形式化定义

我们将两个字符串 $a,b$ 的 Levenshtein Distance 表示为 $lev_{a,b}(|a|, |b|)$ ，其中 $|a|$ 和 $|b|$ 分别对应 $a,b$ 的长度。那么，在这里 $lev_{a,b}(|a|, |b|)$ 可用如下的数学语言描述：

$lev_{a,b}(i, j)$ 指的是 $a$ 中前 $i$ 个字符和 $b$ 中前 $j$ 个字符之间的距离。为了方便理解，这里的 $i,j$ 可以看作是 $a,b$ 的长度。这里的字符串的字符 index 从 1 开始，因此最后的编辑距离便是 $i = |a|, j = |b|$ 时的距离： $lev_{a,b}(|a|, |b|)$
当 $min(i, j) = 0$ 的时候，对应着 $a$ 中前 $i$ 个字符和 $b$ 中前 $j$ 个字符，此时的 $i,j$ 有一个值为 0 ，所以它们之间的距离为 $max(i, j)$ ，即 $i,j$ 中的最大者。
当 $min(i, j) \ne 0$ 的时候， $lev_{a,b}(|a|, |b|)$ 为如下三项的最小值：
1. $lev_{a,b}(i-1, j)$ 表示删除 $a_i$
2. $lev_{a,b}(i, j-1)$ 表示插入 $b_j$
3. $lev_{a,b}(i-1, j-1)+1_{(a_i \ne b_j)}$ 表示替换 $b_j$
$1_{(a_i \ne b_j)}$ 为一个指示函数，表示当 $a_i = b_j$ 的时候取 1 ;当 $a_i \ne b_j$ 的时候，其值为 0。

过程示例

以 $xxc$ 和 $xyz$ 为例，建立一个矩阵，通过矩阵记录计算好的距离：

当 $min(i, j) = 0$ 时， $lev_{a,b}(i, j) = max(i, j)$ ，根据此初始化矩阵的第一行和第一列:

第一行（index = 0）初始化：
min(0, 0) = 0 ->  lev_{a, b}(0, 0) = max(0, 0) = 0
min(0, 1) = 0 ->  lev_{a, b}(0, 1) = max(0, 1) = 1
min(0, 2) = 0 ->  lev_{a, b}(0, 2) = max(0, 2) = 2
min(0, 3) = 0 ->  lev_{a, b}(0, 3) = max(0, 3) = 3

第一列（index = 0）初始化：
min(0, 0) = 0 ->  lev_{a, b}(0, 0) = max(0, 0) = 0
min(1, 0) = 0 ->  lev_{a, b}(1, 0) = max(1, 0) = 1
min(2, 0) = 0 ->  lev_{a, b}(2, 0) = max(2, 0) = 2
min(3, 0) = 0 ->  lev_{a, b}(3, 0) = max(3, 0) = 3

依据上面的公式可以继续推导出第二行：

第二行（index = 1）推导

$min(1, 0) \ne 0 \Rightarrow min(lev_{a, b}(0, 0)+1, lev_{a, b}(1, -1), lev_{a, b}(0, 0)) = max(1, 0) = 1$
$min(1, 1) \ne 0 \Rightarrow lev_{a, b}(1, 1) = max(1, 1) = 1$
$min(1, 2) \ne 0 \Rightarrow lev_{a, b}(1, 2) = max(1, 2) = 2$
$min(1, 3) \ne 0 \Rightarrow lev_{a, b}(1, 3) = max(1, 3) = 3$

继续迭代，直至推导出最终结果：

算法实现

1 递归方式

def Levenshtein_Distance_Recursive(str1, str2):

    if len(str1) == 0:
        return len(str2)
    elif len(str2) == 0:
        return len(str1)
    elif str1 == str2:
        return 0

    if str1[len(str1)-1] == str2[len(str2)-1]:
        d = 0
    else:
        d = 1
    
    return min(Levenshtein_Distance_Recursive(str1, str2[:-1]) + 1,
                Levenshtein_Distance_Recursive(str1[:-1], str2) + 1,
                Levenshtein_Distance_Recursive(str1[:-1], str2[:-1]) + d)

print(Levenshtein_Distance_Recursive("abc", "bd"))
>>>
2

2 动态规划
递归是从后向前分解，那与之相对的就是从前向后计算，逐渐推导出最终结果，此法被称之为动态规划，动态规划很适用于具有重叠计算性质的问题，但这个过程中会存储大量的中间计算的结果，一个好的动态规划算法会尽量减少空间复杂度。

def Levenshtein_Distance(str1, str2):
    """
    计算字符串 str1 和 str2 的编辑距离
    :param str1
    :param str2
    :return:
    """
    matrix = [[ i + j for j in range(len(str2) + 1)] for i in range(len(str1) + 1)]

    for i in range(1, len(str1)+1):
        for j in range(1, len(str2)+1):
            if(str1[i-1] == str2[j-1]):
                d = 0
            else:
                d = 1
            
            matrix[i][j] = min(matrix[i-1][j]+1, matrix[i][j-1]+1, matrix[i-1][j-1]+d)

    return matrix[len(str1)][len(str2)]


print(Levenshtein_Distance("abc", "bd"))

>>>
2

应用与思考

编辑距离是NLP基本的度量文本相似度的算法，可以作为文本相似任务的重要特征之一，其可应用于诸如拼写检查、论文查重、基因序列分析等多个方面。但是其缺点也很明显，算法基于文本自身的结构去计算，并没有办法获取到语义层面的信息。

由于需要利用矩阵，故空间复杂度为O(MN)。这个在两个字符串都比较短小的情况下，能获得不错的性能。不过，如果字符串比较长的情况下，就需要极大的空间存放矩阵。例如：两个字符串都是20000字符，则 LD 矩阵的大小为：20000 * 20000 * 2=800000000 Byte=800MB。

参考文献

[1] https://blog.csdn.net/ghsau/article/details/78903076
[2] https://en.wikipedia.org/wiki/Levenshtein_distance
[3] https://www.dreamxu.com/books/dsa/dp/edit-distance.html
[4] https://www.jianshu.com/p/a96095aa92bc