Javascript 查找编辑距离未返回正确值

Question

我正在研究一个计算两个字符串的编辑距离的函数，但是根据这个唯一的计算器，我得到了一个不正确的值。我得到 19，计算器返回 7。我不确定我的程序有什么问题我基于 算法设计手册。

var recFindEditDistance = function(P, T, i, j) {
    if (i === undefined || j === undefined) return recFindEditDistance(P, T, P.length - 1, T.length - 1);
    if (i === 0 && j === 0) return 0;
    if (i === 0) return j;
    if (j === 0) return i;

    var sub = recFindEditDistance(P, T, i-1, j-1) + (P[i]===T[j] ? 0 : 1);
    var del = recFindEditDistance(P, T, i, j-1) + 1;
    var add = recFindEditDistance(P, T, i-1, j) + 1;

    return Math.max(sub, add, del);
};

console.log(recFindEditDistance('ffadsfsadfasf', 'asdfasdf'));

Answer 1

每个位置的 Levenshtein 距离算法都试图达到到达下一个位置的最小距离。

同时，您正在尝试获得最大的一个:)

简单改变

return Math.max(sub, add, del);

到

return Math.min(sub, add, del);

它会起作用:)

演示：

function recFindEditDistance(P, T, i, j) {
    if (i === undefined || j === undefined) return recFindEditDistance(P, T, P.length - 1, T.length - 1);
    if (i === 0 && j === 0) return 0;
    if (i === 0) return j;
    if (j === 0) return i;

    var sub = recFindEditDistance(P, T, i-1, j-1) + (P[i]===T[j] ? 0 : 1);
    var del = recFindEditDistance(P, T, i, j-1) + 1;
    var add = recFindEditDistance(P, T, i-1, j) + 1;

    return Math.min(sub, add, del);
};

document.body.innerText = recFindEditDistance('ffadsfsadfasf', 'asdfasdf');

Answer 2

我完全意识到这个问题已经很久了，我发布它只是因为它出现在我的 google 搜索中。尽管 Yeldar Kurmangaliyev 接受的答案正确回答了手头的问题，但必须注意的是，上述解决方案仍然存在至少 2 个缺陷：

它没有正确处理所有情况 - 它不适用于仅第一个符号不同的字符串：例如对于字符串 can 和 pan，它会错误地 return 距离为 0。要解决这个问题，我们可以执行以下操作：

function recFindEditDistance(P, T, i, j) {
    if (i === undefined || j === undefined) return recFindEditDistance(P, T, P.length - 1, T.length - 1);
    if (i === 0 && j === 0) return (P.charAt(i) === T.charAt(j)) ? 0 : 1;
    if (i === 0) return j;
    if (j === 0) return i;
    var sub = recFindEditDistance(P, T, i-1, j-1) + (P[i]===T[j] ? 0 : 1);
    var del = recFindEditDistance(P, T, i, j-1) + 1;
    var add = recFindEditDistance(P, T, i-1, j) + 1;
    return Math.min(sub, add, del);
};

console.log(recFindEditDistance('can', 'can'));

效率不高，因为递归会多次经历许多相同的子问题，例如：我们可能会多次解决 recFindEditDistance(P, T, 3, 2)。我们不需要这样做，因为结果是确定性的，一旦我们找到特定子问题的解决方案，我们就不需要再次计算它。由于寻找 Levenstein 距离是一个动态规划问题，因此我们可以使用 memoizatation or tabulation. For a full fletched solution using tabulation, see here

Javascript 查找编辑距离未返回正确值

Javascript find edit distance not returning correct value

javascript

recursion

edit-distance

levenshtein-distance