字符串编辑距离

发表于 | 分类于 | 评论数： | 阅读次数：

编辑距离（Edit Distance），这里指的是Levenshtein距离，也就是字符串S1通过插入、修改、删除三种操作最少能变换成字符串S2的次数。接下来介绍利用动态规划来求解字符串的编辑距离。

定义：$s_1$和$s_2$表示两字符串，$dist(i, j)$表示字符串$s_1$的前$i$个字符串和$s_2$的前$j$个字符串的编辑距离，$s_1(i)$和$s_2(j)$分别表示$s1$的第$i$个字符和$s2$的第$j$字符。

  • 若$s_1(i) = s_2(j)$,则$dist(i, j)$就等于$s_1$的前$i-1$个字符串和$s_2$的前$j-1$个字符串的编辑距离即 $dist(i, j) = dist(i-1,j-1) $
  • 若$s_1(i) \neq s_2(j)$,则为了使$s_1(i) = s_2(j)$,可以通过在$s_1$的第$i$个字符处插入$s_2$的第$j$个字符，或替换$s_1$的第$i$个字符为$s_2$的第$j$个字符,或删除$s_1(s_2)$的第$i(j)$个字符(即使删除之后还是会出现不同),但是上述都是在进行了一次字符的操作之后,将转化为字问题求解，如上述的替换使$s_1(i) = s_2(j)$，则 $dist(i, j) = dist(i-1,j-1) + 1$ ，插入和删除使 $dist(i, j) = dist(i-1,j) +1$或者 $dist(i, j) = dist(i,j-1) +1$ 。

基于上述的情况可以得出递推公式：
$$
dist(i,j) = \begin{equation}
\left\{
\begin{array}{lr}
i, & j = 0 \\
j, & i = 0 \\
dist(i-1,j-1), & s_1(i) = s_2(j) \\
min(d(i-1,j), d(i,j-1),d(i-1,j-1)), & s_1(i) \neq s_2(j) \\
\end{array}
\right.
\end{equation}
$$
例如：$s_1 = “abcd”$,$s_2 = “abfce”$,则利用动态规划求解的矩阵为

a b f c e
0 1 2 3 4 5
a 1 0 1 2 3 4
b 2 1 0 1 2 3
c 3 2 1 1 1 2
d 4 3 2 2 2 2

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public static int levenshtein(String s1, String s2){
    if(s1 == null){
        return s2 == null? 0:s2.length();
    }
    if(s2 == null){
        return s1 == null? 0:s1.length();
    }
    int n = s1.length();
    int m = s2.length();
    int[][] matrix = new int[n+1][m+1];

    for(int i = 0;i <= n;i++){
        matrix[i][0] = i;
    }
    for(int j = 0;j <= m;j++){
        matrix[0][j] = j;
    }

    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            if(s1.charAt(i-1) == s2.charAt(j-1)){
                matrix[i][j] = matrix[i-1][j-1];
            }else {
                matrix[i][j] = Math.min(Math.min(matrix[i-1][j], matrix[i][j-1]), matrix[i-1][j-1]) + 1;
            }
        }
    }
    return matrix[n][m];
}

上述的方法其中有一个不足之处是当两个字符串太长时，则对应申请的数组占用的空间也变大。而上述的算法中，在更新$dist(i,j)$的过程中只用到了$dist(i-1,j)$、$dist(i,j-1)$、$dist(i-1,j-1)$这三个数，因此我们可以只存储更新的上一行的数据，这样就可以得到$dist(i-1,j)$，$dist(i-1,j-1)$这两个数，而$d(i,0) = i$,可以在此基础上根据上一行的$d(i-1,0)$和$d(i-1,1)$推出$d(i-1,1)$,在结合上一行的$d(i-1,1)$和$d(i-1,2)$推出$d(i-1,2)$…以此类推得到第$i$行的数据。接下来是改进后的代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public static int levenshteinImprove(String s1, String s2){
    if(s1 == null)
        return s2 == null? 0:s2.length();
    if(s2 == null)
        return s1 == null? 0:s1.length();
    int n = s1.length(),m = s2.length();
    int[] matrix = new int[m+1];
    for(int i = 0;i <= m;i++){
        matrix[i] = i;
    }

    for(int i = 1;i <= n;i++){
        int pre = matrix[0];
        matrix[0] = i;
        for(int j = 1;j <= m;j++){
            int tmp = matrix[j];
            if(s1.charAt(i-1) == s2.charAt(j-1)){
                matrix[j] = pre;
            }else {
                matrix[j] = Math.min(Math.min(pre, matrix[j-1]),  matrix[j]) + 1;
            }
            pre = tmp;
        }
    }
    return matrix[m];
}

上述代码还可以改进一个小细节，当比较的字符串长短一个很长，一个很短时，我们可以比较其长短，取较短的字符串长度作为开辟的数组的长度。

0%