Levenshtein距离，又称为编辑距离，或者成为字符串相似度，意思是一个字符串转换为另一个字符串所需要的最小编辑次数。编辑包含：插入、删除和替换三种操作。例如字符串：yurnom和yunum的编辑距离为2，因为需要插入一个r和将u替换为o两次操作。
Levenshtein算法由俄罗斯科学家Vladimir Levenshtein在1965年提出，该算法现在广泛用于DNA匹配、字符串纠错、实体共指等领域。
算法简介
将2个字符串转换为一个矩阵，为了简单起见，采用字符串heqi和hoi。转换后进行初始化，如下所示：
| h | e | q | i | ||
| 0 | 1 | 2 | 3 | 4 | |
| h | 1 | A | |||
| o | 2 | ||||
| i | 3 |
其中数字部分为初始化的值，现计算绿色格子A处的值，其算法为：
- 若A所对应的两个字符相同，则左上角蓝色格子的值+0，否则+1，结果记为R1
- 选取上方和左方紫色格子中较小的值，并+1，结果记为R2
- 选取R1和R2中的较小值为绿色格子A处的值
经过计算可以得出A处的值为0，当A处计算完毕后，其右方和下方的值可以接着进行计算了，如此整个矩阵的值将可全部计算出来。最后矩阵右下方红色格子的值即为两个字符串的编辑距离。
至于为何左方和上方的值加1、左上角的值根据不同的情况加0或1的原因（也就是这么算的原理）比较简单，在此不再详述。
Java实现
|
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 |
public class Levenshtein { public static int min(int first, int... others) { //求一组int中的最小值 for(int i : others) { first = Math.min(first, i); } return first; } public static int distance(String str1, String str2) { int n = str1.length(); int m = str2.length(); if(n == 0) return m; if(m == 0) return n; int[][] d = new int[n+1][m+1]; //记录矩阵 for(int i = 0; i <= n; i++) d[i][0] = i; //初始化行 for(int i = 0; i <= m; i++) d[0][i] = i; //初始化列 for(int i = 1; i <= n; i++) { char ch1 = str1.charAt(i - 1); for(int j = 1; j <= m; j++) { char ch2 = str2.charAt(j - 1); int temp = ch1 == ch2 ? 0: 1; //若两字符相等这斜上方的加权值为0,否则为1 d[i][j] = min(d[i-1][j] + 1, d[i][j-1] + 1, d[i-1][j-1] + temp); } } return d[n][m]; } public static double similarity(String str1, String str2) { //计算相似度 int distance = distance(str1, str2); return 1.0 - (double)distance / Math.max(str1.length(), str2.length()); } public static void main(String[] args) { String str1 = "yurnom"; String str2 = "yrnum"; System.out.println("distance=" + Levenshtein.distance(str1, str2)); System.out.println("sim=" + Levenshtein.similarity(str1, str2)); } } |
运行结果：
|
1 2 |
distance=2 sim=0.6666666666666667 |
不足之处与改造方法
原算法采用矩阵来记录中间的结果，矩阵的大小为
然而实际计算过程中，该矩阵记录的绝大部分值都为中间值，这些中间值在完成后续的计算后就毫无用处了。通过观察Levenshtein算法的具体过程，可以发现，实际上只需要2“行”或者2“列”值来记录中间结果即可满足计算的要求。
算法过程
为了简单起见，现展示计算字符串heqi、hoi的过程：
- 初始化rowB，用rowB来计算rowA
h e q i rowB 0 1 2 3 4 rowA h 1 0 1 2 3 o 2 i 3 - rowA此时为历史数据，用于计算rowB
h e q i 0 1 2 3 4 rowA h 1 0 1 2 3 rowB o 2 1 1 2 3 i 3 - 再次交换rowA和rowB的角色，利用rowB来计算rowA
h e q i 0 1 2 3 4 h 1 0 1 2 3 rowB o 2 1 1 2 3 rowA i 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 ld(String str1, String str2) { int n = str1.length(); int m = str2.length(); if(n == 0) return m; if(m == 0) return n; int[] rowA = new int[n]; int[] rowB = new int[n]; for(int i = 0; i < n; i++){ rowB[i] = i + 1; } boolean even = true; for(int i = 0; i < m; i++) { char ch1 = str2.charAt(i); even = i % 2 == 0; for(int j = 0; j < n; j++) { char ch2 = str1.charAt(j); int temp = ch1 == ch2 ? 0: 1; if(even) //若为偶数行，rowA记录新结果，rowB为历史结果 rowA[j] = min(j==0? i+1: rowA[j-1]+1, rowB[j]+1, j==0? i: rowB[j-1]+temp); else //若为奇数行，rowB记录新结果，rowA为历史结果 rowB[j] = min(j==0? i+1: rowB[j-1]+1, rowA[j]+1, j==0? i: rowA[j-1]+temp); } } return even ? rowA[n-1] : rowB[n-1]; //根据最后是奇数行还是偶数行返回对应的值 } |
最后
可以看到改进后的方法占用空间在数量级上下降了，时间复杂度保持不变，依然是O(mn)，m和n为两个字符串的长度。对于此方法，可以进一步改进：将较长的字符串“竖着”放，较短的字符串横着放（参考上述算法过程中的三个表格理解），这样在时间复杂度不变的情况下，所占用的空间最小化了，只不过一般情况下该方法意义不大，只有当两个字符串长度相差悬殊的情况下有意义，例如一个字符串100W长度，一个字符串1W长度。
