74
правки
Изменения
м
d[i, 0] = i
d[0, j] = j
'''for''' j '''from''' 1 '''to''' n ''// Стоимость замены'' '''if''' S[i] == T[j] '''then''' cost = 0 '''else''' cost = 1 d[i, j] = minimum( d[i-1, j ] + 1, ''// удаление'' d[i , j-1] + 1, ''// вставка'' d[i-1, j-1] + cost ''// замена'' ) '''if'''(i > 1 '''and''' j > 1 '''and''' S[i] == T[j-1] '''and''' S[i-1] == T[j]) '''then''' d[i, j] = minimum( d[i, j], d[i-2, j-2] + costTransposition ''// транспозиция'' )
→Наивный алгоритм
''// База динамики''
'''for''' i '''from''' 0 '''to''' m
'''for''' j '''from''' 1 '''to''' n
'''for''' i '''from''' 1 '''to''' m
'''return''' d[m, n]
Контрпример: <tex>S =</tex> <tex>'CA'</tex> и <tex>T =</tex> <tex>'ABC'</tex>. Расстояние Дамерау {{---}} Левенштейна между строками равно 2 (<tex>CA \rightarrow AC \rightarrow ABC</tex>), однако функция приведённая выше возвратит 3. Дело в том, что использование этого упрощённого алгоритма накладывает ограничение: любая подстрока может быть редактирована не более одного раза. Поэтому переход <tex>AC \rightarrow ABC</tex> невозможен, и последовательность действий такая: (<tex>CA \rightarrow A \rightarrow AB \rightarrow ABC</tex>).
