编辑距离的定义
编辑距离 (Edit Distance) 最常用的定义就是 Levenstein 距离, 是由俄国科学家 Vladimir Levenshtein 于 1965 年提出的, 所以编辑距离一般又称 Levenshtein 距离. 它主要作用是测量两个字符串的差异化程度, 表示字符串 a 至少要经过多少个操作才能转换为字符串 b, 这里的操作包括三种: 增加, 删除, 替换.
举个例子:
(1)增加: 对于字符串 a:abc 和 字符串 b:abcde, 显然, 只需要在字符串 a 的末尾增加字符'd'和'e'就能变成字符串 b 了, 所以 a 和 b 的最短编辑距离为 2.
(2)删除: 对于字符串 a:abcd 和字符串 b:abc, 显然, 只需要在字符串 a 的末尾删除字符'd'就能变成字符串 b 了, 所以 a 和 b 的最短编辑距离为 1.
(3)替换: 对于字符串 a:abcd 和 字符串 b:abce, 显然, 只需要把字符串 a 的'd'替换成'e'就可以了, 此时二者的最短编辑距离是 1.
一般字符串都是需要增加, 删除, 替换三者结合起来一起使用, 因为字符串 a 到 b 可能存在多种变化的方法, 而我们往往最关心的是最短的编辑距离, 这样才能得出 a 和 b 的相似程度, 最短编辑距离越小, 表示 a 到 b 所需要的操作越少, a 和 b 的相似度也就越高. 因此, Levenstein 距离的一个应用场景就是判断两个字符串的相似度, 可以用在字符串的模糊搜索上面.
Levenshtein 算法原理
先从一个问题谈起: 对于字符串 "xyz" 和 "xcz", 它们的最短距离是多少? 我们从两个字符串的最后一个字符开始比较, 它们都是'z', 是相同的, 我们可以不用做任何操作, 此时二者的距离实际上等于 "xy" 和 "xc" 的距离, 即 d(xyz,xcz) = d(xy,xc). 也即是说, 如果在比较的过程中, 遇到了相同的字符, 那么二者的距离是除了这个相同字符之外剩下字符的距离. 即 d(i,j) = d(i - 1,j-1).
接着, 我们把问题拓展一下, 最后一个字符不相同的情况: 字符串 A("xyzab")和字符串 B("axyzc"), 问至少经过多少步操作可以把 A 变成 B.
我们还是从两个字符串的最后一个字符来考察即'b'和'c'. 显然二者不相同, 那么我们有以下三种处理办法:
(1)增加: 在 A 末尾增加一个'c', 那么 A 变成了 "xyzabc",B 仍然是 "axyzc", 由于此时末尾字符相同了, 那么就变成了比较 "xyzab" 和 "axyz" 的距离, 即 d(xyzab,axyzc) = d(xyzab,axyz) + 1. 可以写成 d(i,j) = d(i,j - 1) + 1. 表示下次比较的字符串 B 的长度减少了 1, 而加 1 表示当前进行了一次字符的操作.
(2)删除: 删除 A 末尾的字符'b', 考察 A 剩下的部分与 B 的距离. 即 d(xyzab,axyzc) = d(xyza,axyzc) + 1. 可以写成 d(i,j) = d(i - 1,j) + 1. 表示下次比较的字符串 A 的长度减少了 1.
(3)替换: 把 A 末尾的字符替换成'c', 这样就与 B 的末尾字符一样了, 那么接下来就要考察出了末尾'c'部分的字符, 即 d(xyzab,axyzc) = d(xyza,axyz) + 1. 写成 d(i,j) = d(i -1,j-1) + 1 表示字符串 A 和 B 的长度均减少了 1.
由于我们要求的是最短的编辑距离, 所以我们取以上三个步骤得出的距离的最小值为最短编辑距离. 由上面的步骤可得, 这是一个递归的过程, 因为除掉最后一个字符之后, 剩下的字符串的最后一位仍然是最后一个字符, 我们仍然可以按照上面的三种操作来进行, 经过这样的不断递归, 直到比较到第一个字符为止, 递归结束.
按照以上思路, 我们很容易写出下面的方程:
最短编辑距离方程
注释: 该方程的第一个条件 min(i,j) = 0, 表示若某一字符串为空, 转换成另一个字符串所需的操作次数, 显然, 就是另一个字符串的长度(添加 length 个字符就能转换). 这个条件可以看成是递归的出口条件, 此时 i 或 j 减到了 0.
根据以上方程, 我们能快速写出递归代码, 但由于递归包含了大量的重复计算, 并且如果初始字符串过长, 会造成递归层次过深, 容易造成栈溢出的问题, 所以我们这里可以用动态规划来实现. 如果说递归是自顶向下的运算过程, 那么动态规划就是自底向上的过程. 它从 i 和 j 的最小值开始, 不断地增大 i 和 j, 同时对于一个 i 和 j 都会算出当前地最短距离, 因为下一个 i 和 j 的距离会与当前的有关, 所以通过一个数组来保存每一步的运算结果来避免重复的计算过程, 当 i 和 j 增加到最大值 length 时, 结果也就出来了, 即 d[length][length]为 A,B 的最短编辑距离.
动态规划中, i 和 j 的增加需要两层循环来完成, 外层循环遍历 i, 内层循环遍历 j, 也即是, 对于每一行, 会扫描行内的每一列的元素进行运算. 因此, 时间复杂度为 o(n²), 空间复杂度为 o(n²).
图解动态规划求最短编辑距离过程
在写代码之前, 为了让读者对动态规划有一个直观的感受, 笔者以表格的形式, 列出动态规划是如何一步步地工作的.
下面以字符串 "xyzab" 和 "axyzc" 为例来讲解.
图解
由上面可以看出, 动态规划就是逐行逐列地运算, 逐渐填满整个数组, 最后得到结果恰好保存在数组的最后一行和最后一列的元素上.
代码实现
一, 基本实现
- public class LevenshteinDistance {
- private static int minimum(int a,int b,int c){
- return Math.min(Math.min(a,b),c);
- }
- public static int computeLevenshteinDistance(CharSequence src,CharSequence dst){
- int[][] distance = new int[src.length() + 1][dst.length() + 1];
- for (int i = 0;i <= src.length();i++)
- distance[i][0] = i;
- for (int j = 0;j <= dst.length();j++)
- distance[0][j] = j;
- for (int i = 1;i <= src.length();i++){
- for (int j = 1;j <= dst.length();j++){
- int flag = (src.charAt(i - 1) == dst.charAt(j - 1)) ? 0 : 1;
- distance[i][j] = minimum(
- distance[i - 1][j] + 1,
- distance[i][j - 1] + 1,
- distance[i - 1][j - 1] + flag);
- }
- }
- return distance[src.length()][dst.length()];
- }
- // 测试方法
- public static void main(String args[]){
- String s1 = "xyzab";
- String s2 = "axyzc";
- String s3 = "等啊高原";
- String s4 = "阿登高原";
- String s5 = "xyz 阿登高原";
- String s6 = "1y3 等啊高原 x";
- System.out.println("字符串 (\"" + s1 + "\") 和字符串 (\""+ s2 +"\") 的最小编辑距离为:"+ computeLevenshteinDistance(s1,s2));
- System.out.println("字符串 (\"" + s3 + "\") 和字符串 (\""+ s4 +"\") 的最小编辑距离为:"+ computeLevenshteinDistance(s3,s4));
- System.out.println("字符串 (\"" + s5 + "\") 和字符串 (\""+ s6 +"\") 的最小编辑距离为:"+ computeLevenshteinDistance(s5,s6));
- }
- }
上面的代码是利用了动态规划的思想来实现的最短编辑距离算法, 它的实现与原理方程基本上是一致的, 都是先对第一行和第一列的数据进行初始化, 然后开始逐行逐列进行计算, 填充满整个数组, 即自底向上的思想, 通过这样减少了大量的递归重复计算, 实现了运算速度的提升. 上面提到, 这种实现的时间复杂度和空间复杂度都是 n² 级别的(实际上是 m*n, 两个字符串长度的乘积). 实际上, 我们可以对代码进行优化, 降低空间复杂度.
二, 利用滚动数组进行空间复杂度的优化
滚动数组是动态规划中一种常见的优化思想. 为了理解滚动数组的思想, 我们先来看看如何进行空间复杂度的优化. 回到原理方程, 我们可以观察到 d(i,j)只与上一行的元素 d(i-1,j),d(i,j-1)和 d(i-1,j-1)有关, 而上一行之前的元素没有关系, 也就是说, 对于某一行的 d(i,j), 我们只需要知道上一行的数据就行, 别的数据都是无效数据. 实际上, 我们只需要两行的数组就可以了.
举个例子: 还是上面的 "xyzab" 和 "axyzc", 当我们计算完第一行和第二行的数据后, 到达第三行时, 我们以第二行为上一行结果来计算, 并把计算结果放到第一行内; 到达第四行时, 由于第三行的数据实际上保存在第一行, 所以我们根据第一行来计算, 把结果保存在第二行...... 以此类推, 直到计算到最后一行, 即不断交替使用两行数组的空间,"滚动数组" 也因此得名. 通过使用滚动数组的形式, 我们不需要 n*m 的空间, 只需要 2*min(n,m)的空间, 这样便能把空间复杂度降到线性范围内, 节省了大量的空间.
利用滚动数组后的空间复杂度为 o(2*n)或者 o(2*m), 这取决于代码的实现, 即取字符串 A 还是 B 的长度为数组的列数.(因为无论把哪一个字符串作为 src 或 dst, 都是等价的, 结果都是一样的.)其实我们可以通过判断 A,B 的长度, 来选取一个最小值作为列数, 此时空间复杂度变为 o(2*min(n,m)). 下面给出基于滚动数组的最小编辑距离的优化版本, 由 Java 实现.
/** * 利用滚动数组优化过的最小编辑距离算法. 空间复杂度为 O(2*min(lenSrc,lenDst)) * @param src 动态规划数组的行元素 * @param dst 动态规划数组的列元素 * @return */ public static int computeLevenshteinDistance_Optimized(CharSequence src,CharSequence dst){ int lenSrc = src.length() + 1; int lenDst = dst.length() + 1; CharSequence newSrc = src; CharSequence newDst = dst; // 如果 src 长度比 dst 的短, 表示数组的列数更多, 此时我们 // 交换二者的位置, 使得数组的列数变为较小的值. if (lenSrc < lenDst){ newSrc = dst; newDst = src; int temp = lenDst; lenDst = lenSrc; lenSrc = temp; } // 创建滚动数组, 此时列数为 lenDst, 是最小的 int[] cost = new int[lenDst]; // 当前行依赖的上一行数据 int[] newCost = new int[lenDst];// 当前行正在修改的数据 // 对第一行进行初始化 for(int i = 0;i < lenDst;i++) cost[i] = i; for(int i = 1;i < lenSrc;i++){ // 对第一列进行初始化 newCost[0] = i; for(int j = 1;j < lenDst;j++){ int flag = (newDst.charAt(j - 1) == newSrc.charAt(i - 1)) ? 0 : 1; int cost_insert = cost[j] + 1; // 表示 "上面" 的数据, 即对应 d(i - 1,j) int cost_replace = cost[j - 1] + flag;// 表示 "左上方的数据", 即对应 d(i - 1,j - 1) int cost_delete = newCost[j - 1] + 1; // 表示 "左边的数据", 对应 d(i,j - 1) newCost[j] = minimum(cost_insert,cost_replace,cost_delete); // 对应 d(i,j) } // 把当前行的数据交换到上一行内 int[] temp = cost; cost = newCost; newCost = temp; } return cost[lenDst - 1]; }
把 main()方法的方法调用改为上述方法, 比较前后两个方法的输出结果, 结果一致, 符合预期.
输出结果
三, 对空间复杂度的进一步优化
实际上, 我们还能对这个进行进一步的优化, 把空间复杂度减少为 o(min(n,m)), 即我们只需要一行的数组 d 加一个额外的临时变量就可以实现. 比如说我们要修改 d[i]的值时, 只需知道它的左边, 上边和左上方的元素的值, 而左边的值就是 d[i-1], 上边的值是修改之前的 d[i], 左上方的值是 d[i-1]修改之前的值. 每一次需要修改 d[i-1]的时候, 都用临时变量把他保存起来, 这样 i 位置就能直接获取这三个值进行比较, 得到结果之后, 先用这个临时变量把 d[i]保存起来, 然后再写入 d[i]内,...... 以此类推, 直到遍历完一行.
其核心思想是: 把求得的数据, 再次写回这一行数据对应下标元素的位置, 而临时变量 temp 则保存当前位置左上方元素的值, 以提供给下一个位置的计算. 总的来说, 数据的操作只集中在一行之内, 所以空间复杂度就是 o(n).
下面以图解的形式表达这一过程, 方便读者理解.
单行数组
代码实现也不复杂, 有兴趣的同学可以根据上图或者思路来实现, 这里就不再实现了.
好了, 这篇文章写到这里就结束了, 希望能对各位同学有所裨益, 谢谢你们的耐心阅读~
来源: http://www.jianshu.com/p/12e9b9a9a350