Levenshtein Distance是最小编辑距离的一种实现,网上搜到的一些python的实现,现在用前端的JavaScript来实现一下。什么是最小编辑距离?请看斯坦福的课件。简单地说就是将string1变成string2需要的最少步骤。
例如string1是abc,sting2是123abc。把string1变成string2的最小编辑距离是3,即新增1,新增2,新增3。
例如string1是abc,string2是abd。把string1变成string2的最小编辑距离是1,即c替换成d。(也有的将其计算成2,先删除c,再新增d,因此是要编辑2次)。
用Levenshtein Distance来实现最小编辑距离的算法逻辑见图:
核心思想是用二维数组记录每次计算的值,核心技巧当然还是递归。D(i-1, j) + 1代表将算法思想转化成:将string1去掉末尾一个字符后,变成string2的最小编辑距离是多少。最终不管值是多少,还需要加1,因为之前去掉了一个字符。
同理D(i, j-1) + 1代表将算法思想转化成:将string2去掉末尾一个字符后,变成string1的最小编辑距离是多少。最终不管值是多少,还需要加1,因为之前去掉了一个字符。
D(i-1, j-1)代表将算法思想转化成:将string1和string2都去掉末尾一个字符后,变成相同字符串的最小编辑距离是多少。因为两个字符串都去掉了一个字符,因此存在两种情况:如果被去掉的字符相同,就抵消。如果不同,就+1,表示替换字符。
最终的最小编辑距离是上面3种方法求出来的值的最小值。二维数组执行计算的效果图如下,最终的结果就是矩阵右上角的值:
JavaScript版的代码已经上传仓库:
static Minimum = (a, b, c) => { return a < b ? (a < c ? a : c) : (b < c ? b : c); }; static LevenshteinDistance = (v1, v2) => { const len1 = v1.length; const len2 = v2.length; const matrix = []; // matrix let i; // iterates through v1 let j; // iterates through v2 let sIndex; // ith character of v1 let tIndex; // jth character of v2 let cost; // cost // Step 1 if (len1 === 0) return len2; if (len2 === 0) return len1; // Step 2 for (i = 0; i <= len1; i++) { matrix[i] = []; matrix[i][0] = i; } for (j = 0; j <= len2; j++) { matrix[0][j] = j; } // Step 3 for (i = 1; i <= len1; i++) { sIndex = v1.charAt(i - 1); for (j = 1; j <= len2; j++) { tIndex = v2.charAt(j - 1); if (sIndex === tIndex) { cost = 0; } else { cost = 1; } matrix[i][j] = Demo.Minimum( matrix[i - 1][j] + 1, matrix[i][j - 1] + 1, matrix[i - 1][j - 1] + cost, ); } } // Step 4 return matrix[len1][len2]; };