Изменения

A = \left\{\begin{array}{llcl}

0&;\ 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'''):

''<font color=green>// База динамики</font>''

'''for''' j = 1 '''to''' N

'''for''' i = 1 '''to''' M

Тогда если на очередной итерации внутреннего цикла положить: <tex>i' = \mathtt{lastPosition}[T[j]],\ j' = \mathtt{last}</tex>, то

, где

A = \left\{\begin{array}{llcl}

0&;\ 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>.

'''return''' M

D: '''int[0..M + 1][0..N + 1]''' ''<font color=green>// Динамика</font>''

''<font color=green>// База индукции</font>''

D[0][0] = INF

'''for''' i = 0 '''to''' M

D[i + 1][0] = INF

'''for''' j = 0 '''to''' N

D[0][j + 1] = INF

lastPosition[S[i]] = i

==См. также==