编辑距离问题

发表于 | 分类于

编辑距离问题

概念描述：编辑距离，又称Levenshtein距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。

问题解析：

计算编辑距离的问题，符合动态规划的几个特征：

最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。

无后效性。即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。

子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。

因此考虑用动态规划求解。

首先，我们可以定义一个函数——edit(i,j)，它表示第一个字符串的长度为i的子串到第二个字符串的长度为j的子串的编辑距离。这也就是动态规划过程中状态的定义，接下来我们就要探讨状态转移方程是如何描述的。

状态转移可以分为以下几个情况来讨论：

  • if i == 0 && j == 0 ,edit(i,j) = 0
  • if i == 0 && j > 0 ,edit(i,j) = j
  • if i > 0 && j == 0 ,edit(i,j) = i
  • if i > 0 && j > 0 ,edit(i,j) = min{edit(i - 1,j) + 1 ,edit(i,j - 1) + 1 ,edit(i - 1,j - 1) + f(i,j)},当第一个字符串的第i个字符不等于第二个字符串的第j个字符的时候，f(i,j) = 1,否则 f(i,j) = 0

根据状态的定义与状态转移方程的描述，我们在解决问题的过程中只需要完成一个二维数组作为DP表就行。

代码如下所示：

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
public static void main(String[] args) {
    System.out.println(getEditDistance("ab", "abaaa"));
    System.out.println(getEditDistance("abcca", "abaaa"));
    System.out.println(getEditDistance("ab", "aba"));
    System.out.println(getEditDistance("cafe", "coffee"));
}
private static int getEditDistance(String s, String t) {
    int dp[][];
    int n;//字符串s的长度
    int m;//字符串t的长度
    int i;
    int j;
    char s_i;//字符串s的第i个字符
    char t_j;//字符串t的第j个字符
    n = s.length();
    m = t.length();
    if (n == 0) {
        return m;
    }
    if (m == 0) {
        return n;
    }
    dp = new int[n + 1][m + 1];
    //初始化第一列
    for (i = 0; i <= n; i++) {
        dp[i][0] = i;
    }
    //初始化第一行
    for (j = 0; j <= m; j++) {
        dp[0][j] = j;
    }
    //根据状态转移方程完成DP表
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) {
            s_i = s.charAt(i - 1);
            t_j = t.charAt(j - 1);
            int f;
            if (s_i == t_j) {
                f = 0;
            } else {
                f = 1;
            }
            dp[i][j] = mininum(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + f);
        }
    }
    return dp[n][m];
}
/*
３个数取最小值方法
 */
private static int mininum(int a, int b, int c) {
    int min = a < b ? a : b;
    return min < c ? min : c;
}
0%