1632
правки
Изменения
м
rollbackEdits.php mass rollback
A = \left\{\begin{array}{llcl}
0&;\ i = 0,\ j = 0\\
i* deleteCost&;\ j = 0,\ i > 0\\j* insertCost&;\ i = 0,\ j > 0\\
D(i - 1, j - 1)&;\ S[i] = T[j]\\
\min{(}\\
'''int''' DamerauLevenshteinDistance(S: '''char[1..M]''', T: '''char[1..N]'''; deleteCost, insertCost, replaceCost, transposeCost: '''int'''):
d: '''int[0..M][0..N]'''
''<font color=green>// База динамики</font>''
d[0][0] = 0 '''for''' i = 0 1 '''to''' M d[i][0] = d[i- 1][0] + deleteCost
'''for''' j = 1 '''to''' N
d[0][j] = d[0][j- 1] + insertCost
'''for''' i = 1 '''to''' M
Контрпример: <tex>S =</tex> <tex>'CA'</tex> и <tex>T =</tex> <tex>'ABC'</tex>. Расстояние Дамерау-Левенштейна между строками равно <tex>2\ (CA \rightarrow AC \rightarrow ABC)</tex>, однако функция приведённая выше возвратит <tex>3</tex>. Дело в том, что использование этого упрощённого алгоритма накладывает ограничение: любая подстрока может быть редактирована не более одного раза. Поэтому переход <tex>AC \rightarrow ABC</tex> невозможен, и последовательность действий такая: <tex>(CA \rightarrow A \rightarrow AB \rightarrow ABC)</tex>.
Упрощенный алгоритм Дамерау-Левенштейна не является метрикой, так как не выполняется правило треугольника: <tex>\mathtt{DLD}('CA',\ 'AC') + \mathtt{DLD}('AC',\ 'ABC') \ngeqslant \mathtt{DLD}('CA',\ 'ABC')</tex>.
Условие многих практических задач не предполагает многократного редактирования подстрок, поэтому часто достаточно упрощённого алгоритма. Ниже представлен более сложный алгоритм, который корректно решает задачу поиска расстояния Дамерау-Левенштейна.
A = \left\{\begin{array}{llcl}
0&;\ i = 0,\ j = 0\\
i* deleteCost&;\ j = 0,\ i > 0\\j* insertCost&;\ i = 0,\ j > 0\\
D(i - 1, j - 1)&;\ S[i] = T[j]\\
\min{(}\\
'''return''' M
D: '''int[0..M + 1][0..N + 1]''' ''<font color=green>// Динамика</font>''
INF = (M + N ) * max(deleteCost, insertCost, replaceCost, transposeCost) ''<font color=green>// Большая константа</font>''
''<font color=green>// База индукции</font>''
D[0][0] = INF
'''for''' i = 0 '''to''' M
D[i + 1][1] = i* deleteCost
D[i + 1][0] = INF
'''for''' j = 0 '''to''' N
D[1][j + 1] = j* insertCost
D[0][j + 1] = INF
lastPosition[S[i]] = i
'''return''' D[M + 1][N + 1]
==См. также==
