Levenshtein Distance最小编辑距离

张歆琳

关注

2017.09.07 20:47* 字数 527 阅读 145评论 1喜欢 3

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];
};

小礼物走一走，来简书关注我