距索引 0 的 Levenshtein 距离

Question

我一直在研究 "The Algorithm Design Manual" 部分 8.2.1 通过递归编辑距离。在这一部分 Skiena 写道，"We can define a recursive algorithm using the observation that the last character in the string must either be matched, substituted, inserted, or deleted." 这让我想知道，为什么是最后一个字符？对于仅基于问题定义的任何角色来说都是如此。实际的 Levenshtein 距离算法从字符串的后面进行递归调用。为什么？没有理由你不能做相反的事情，对吧？它只是一种更简单、更优雅的语法吗？

我正在翻转算法，所以它从字符串的前面开始迭代。我的尝试如下。我知道我的实现并不完全有效（例如：minDistance("industry", "interest") returns 5 而不是 6）。我花了几个小时试图找出我做错了什么，但我没有看到。任何帮助将不胜感激。

var matchChar = (c,d) => c === d ? 0 : 1;
var minDistance = function(word1, word2) {
    var stringCompare = function(s, t, i, j) {
        if(i === s.length) return Math.max(t.length-s.length-1,0)
        if(j === t.length) return Math.max(s.length-t.length-1,0)
        if(cache[i][j] !== undefined) {
            return cache[i][j]
        }
        let match = stringCompare(s,t,i+1,j+1) + matchChar(s[i], t[j]);
        let insert = stringCompare(s,t,i,j+1) + 1;
        let del = stringCompare(s,t,i+1,j) + 1;

        let lowestCost = Math.min(match, insert, del)
        cache[i][j] = lowestCost

        return lowestCost
    };

    let s = word1.split('')
    s.push(' ')
    s = s.join('')

    let t = word2.split('')
    t.push(' ')
    t = t.join('')

    var cache = []
    for(let i = 0; i < s.length; i++) {
        cache.push([])
        for(let j = 0; j < t.length; j++) {
            cache[i].push(undefined)
        }
    }

    return stringCompare(s, t, 0, 0)
}

Answer 1

线条

    if(i === s.length) return Math.max(t.length-s.length-1,0)
    if(j === t.length) return Math.max(s.length-t.length-1,0)

我看错了。我觉得应该是

    if(i === s.length) return t.length-j
    if(j === t.length) return s.length-i

距索引 0 的 Levenshtein 距离

Levenshtein distance from index 0

javascript

algorithm

recursion

edit-distance

levenshtein-distance