Расстояние Левенштейна от индекса 0 - PullRequest
Новая
       27

Расстояние Левенштейна от индекса 0

0 голосов
/ 26 февраля 2019

Я работал через раздел «Руководство по разработке алгоритма» 8.2.1 Редактирование расстояния по рекурсии.В этом разделе Скиена пишет: «Мы можем определить рекурсивный алгоритм, используя наблюдение, что последний символ в строке должен быть сопоставлен, заменен, вставлен или удален».Это заставило меня задуматься, почему последний персонаж?Это верно для любого персонажа, основанного только на определении проблемы.Фактический алгоритм расстояния Левенштейна делает рекурсивные вызовы с конца строк.Зачем?Нет причины, по которой ты не мог сделать обратное, верно?Это просто более простой и элегантный синтаксис?

Я переворачиваю алгоритм, поэтому он повторяется с начала строки.Моя попытка ниже.Я знаю, что моя реализация не работает полностью (например: minDistance("industry", "interest") возвращает 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)
}

1 Ответ

0 голосов
/ 26 февраля 2019

Линии 

    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
...