1632
правки
Изменения
м
Для корректного алгоритма Дамерау-Левенштейна правило треугольника выполняется: <tex>\mathtt{DLD}(S,\ V) + \mathtt{DLD}(V,\ T) \geqslant \mathtt{DLD}(S,\ T)</tex>. Предположим обратное: <tex>\mathtt{DLD}(S,\ V) + \mathtt{DLD}(V,\ T) < \mathtt{DLD}(S,\ T)</tex>, тогда приходим к противоречию, так как <tex>\mathtt{DLD}(S,\ T)</tex> является минимальным ответом по определению. При <tex>insertCost = deleteCost</tex> расстояние Дамерау-Левенштейна будет являться метрикой.
i', j', last: '''int'''
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>i' = \mathtt{lastPosition}[T[j]],\ j' = \mathtt{last}</tex>, то
<tex>D(i, j) = \min{(A, D(i', j') + (i - i' - 1) \cdot deleteCost + transposeCost + (j - j' - 1) \cdot insertCost)}</tex><tex>(*)</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{(}\\
Тогда если символ <tex>S[i]</tex> встречался в <tex>T[1]..T[j]</tex> на позиции <tex>j'</tex>, а символ <tex>T[j]</tex> встречался в <tex>S[1]..S[i]</tex> на позиции <tex>i'</tex>; то <tex>T[1]..T[j]</tex> может быть получена из <tex>S[1]..S[i]</tex> удалением символов <tex>S[i' + 1]..S[i - 1]</tex>, транспозицией ставших соседними <tex>S[i']</tex> и <tex>S[i]</tex> и вставкой символов <tex>T[j' + 1]..T[j - 1]</tex>. Суммарно на это будет затрачено <tex>D(i', j') + (i - i' - 1) \cdot deleteCost + transposeCost + (j - j' - 1) \cdot insertCost</tex> операций, что описано в <tex>(*)</tex>. Поэтому мы выбирали оптимальную последовательность операций, рассмотрев случай с транспозицией и без неё.
Сложность алгоритма: <tex>O\left (M \cdot N \cdot \max{(M, N)} \right )</tex>. Затраты памяти: <tex>O\left (M \cdot N \right)</tex>. Однако скорость работы алгоритма может быть улучшена до <tex>O\left (M \cdot N \right)</tex>.
'''else''' '''if''' (T == "")
'''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: '''int[0..количество различных символов в S и T]'''
''<font color=green>//для каждого элемента C алфавита задано значение lastPosition[C]</font>''
lastPosition[S[i]] = i
'''return''' D[M + 1][N + 1]
==См. также==
