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');