显示 Levenshtein 距离的结果

Question

给定两个字符串 (s1, s2)，编辑距离是将 s1 更改为 s2 或反之所需的最少操作数。

我想显示将 s1 更改为 s2 的结果。例如，将周日更改为周六需要 3 次操作。我需要展示 S++u+day。 "+" 用于每个需要的操作。

Answer 1

这是一个 javascript 片段，return 就是您想要的。如果您熟悉 dynamic programming algorithm，您应该能够遵循此代码。 return 字符串 r 的所有字符串 operations/manipulation 和 min/curMin 的处理都是相对于原始版本的更改。

function edits(t, s) {
    var r = "";
    if (s === t) {
        return s;
    }
    var n = s.length, m = t.length;
    if (n === 0 || m === 0) {
        return "+".repeat(n + m);
    }
    var x, y, a, b, c, min = 0;
    var p = new Array(n);
    for (y = 0; y < n;)
        p[y] = ++y;
    for (x = 0; x < m; x++) {
        var e = t.charCodeAt(x);
        c = x;
        b = x + 1;
        var currMin = min;
        min = n + 1;
        for (y = 0; y < n; y++) {
            a = p[y];
            if (a < c || b < c) {
                b = (a > b ? b + 1 : a + 1);
            }
            else {
                if (e !== s.charCodeAt(y)) {
                    b = c + 1;
                }
                else {
                    b = c;
                }
            }
            if (b < min) {
                min = b;
            }
            p[y] = b;
            c = a;
        }
        if (min > currMin) {
            r += "+";
        }
        else {
            r += t[x];
        }
    }
    return r;
}

编辑：上面的实现是针对速度和 space 进行了优化的版本，因此可能更难阅读。下面的实现是 JS version from Wikipedia 的修改版本，应该更容易理解。

function getEditDistance(a, b) {
    if(a.length === 0) return "+".repeat(b.length);
    if(b.length === 0) return "+".repeat(a.length);

    var matrix = [];

    // increment along the first column of each row
    var i;
    for(i = 0; i <= b.length; i++){
        matrix[i] = [i];
    }

    // increment each column in the first row
    var j;
    for(j = 0; j <= a.length; j++){
        matrix[0][j] = j;
    }

    var r = "", min = 0;;

    // Fill in the rest of the matrix
    for(i = 1; i <= b.length; i++){

        var currMin = min;
        min = a.length + 1;

        for(j = 1; j <= a.length; j++){

            if(b.charAt(i-1) == a.charAt(j-1)){
                matrix[i][j] = matrix[i-1][j-1];
            } else {
                matrix[i][j] = Math.min(matrix[i-1][j-1] + 1, // substitution
                    Math.min(matrix[i][j-1] + 1, // insertion
                        matrix[i-1][j] + 1)); // deletion
            }

            if (matrix[i][j] < min) {
                min = matrix[i][j];
            }
        }

        if (min > currMin) {
            r += "+";
        }
        else {
            r += b[i-1];
        }
    }
    return r;
}

EDIT2：添加了对算法和示例输出的解释

下面是来自输入字符串 "kitten" 和 "sitting" 的编辑矩阵。我在原始算法中所做的更改是，我添加了检查当前行的最小值是否大于前几行的最小值，如果是，则当前行中有一个编辑，因此添加了一个“+”。如果不是，则当前行的“编辑成本”与前一行相同。然后不需要编辑，我们只需将当前字符添加到结果字符串中。您可以在图像中逐行执行算法（从第 1 行和第 1 列开始）

示例：

> getEditDistance("kitten", "sitting");
'+itt+n+'
> getEditDistance("Sunday", "Saturday");
'S++u+day'

显示 Levenshtein 距离的结果

Showing the result of Levenshtein Distance

levenshtein-distance