Изменения
→Корректный алгоритм
<tex>D(i, j) = \left\{\begin{array}{lllc}
\min{(A, D(i - 2, j - 2) + transposeCost)}&&;\ i > 1,\ j > 1,\ S[i] = T[j - 1],\ S[i - 1] = T[j]\\A&&;\ \text{otherwise}\\
\end{array}\right.
</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{(}\\
\qquad\ begin{array}{llcl}&D(i, j - 1) + insertCost\\&D(i - 1, j) + deleteCost&&\qquad\ &D(i - 1, j- 1) + deleteCost&replaceCost\\\end{array}&;&\ j > 0,\ i > 0,\ S[i] \ne T[j]\\\qquad\ D(i - 1, j - 1) + replaceCost\\
)
\end{array}\right.
'''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>
, где
<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{(}\\
\qquad\ begin{array}{llcl}&D(i, j - 1) + insertCost\\&D(i - 1, j) + deleteCost&&\qquad\ &D(i - 1, j- 1) + deleteCost&replaceCost\\\end{array}&;&\ j > 0,\ i > 0,\ S[i] \ne T[j]\\\qquad\ D(i - 1, j - 1) + replaceCost\\
)
\end{array}\right.
Тогда если символ <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]
==См. также==
