Вопросы Левенштейна

Question

В алгоритме Расстояние Левенштейна , что делает эта строка?:

    d[i][j] = Minimum (d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1] + cost);

Хотя он получает минимум всех этих значений, почему стоимость добавляется в конец, и почему у нас + 1 в конце каждого индексатора массива (первые два параметра)?

Answer 1

Вот формула:

m(a,b) = if a==b then 0 else 1

Строка с "min" - это сама рекурсивная формула, остальные - нерекурсивные случаи, к которым приводит рекурсия.

Ваша строка использует "кэширование" результатов в массиве. Попробуйте посмотреть на это так:

 d(i, j) = Minimum (d(i-1, j)+1, d(i, j-1)+1, d(i-1, j-1) + cost);

cost равен m(a,b), и равен нулю, если a==b, и одному в другом случае

Answer 2

Из статьи:

                (
                  d[i-1, j] + 1,  // deletion
                  d[i, j-1] + 1,  // insertion
                  d[i-1, j-1] + 1 // substitution
                )

Цель алгоритма - найти самый дешевый путь для преобразования одной строки (или списка) в другую строку. «Стоимость» для любой данной операции рассматривается в строке, на которую вы ссылаетесь. По вашему, «удаления» считаются стоимостью 1, «вставляет» также 1 и «замена» с переменной стоимостью.

Answer 3

если бы вы читали дальше, вы бы знали: Мы можем назначить разные штрафы за вставку, удаление и замену. Мы также можем указать стоимость штрафа, которая зависит от того, какие символы вставлены, удалены или заменены.

вы бы, например, включить некоторую стоимость> 0 в часть формулы удаления, если вы полагаете, что удаление буквы имеет большее значение, чем замена буквы