63
правки
Изменения
Нет описания правки
j&&;&i = 0,\ j > 0\\
D(i - 1, j - 1)&&;&S[i] = T[j]\\
\min{(}\left(\begin{array}{llcl}\qquad\ D(i, j - 1) + insertCost\\D(i - 1, j) + deleteCost\qquad\D(i - 1, j - 1) + replaceCost\\\end{array}\right)}deleteCost&&;&j > 0,\ i > 0,\ S[i] \ne T[j]\\\qquad\ D(i - 1, j - 1) + replaceCost\\)
\end{array}\right.
</tex>
==Корректный алгоритм==
В основу алгоритма положена идея [[Динамическое программирование#.D0.9F.D1.80.D0.B8.D0.BD.D1.86.D0.B8.D0.BF_.D0.BE.D0.BF.D1.82.D0.B8.D0.BC.D0.B0.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B8_.D0.BD.D0.B0_.D0.BF.D1.80.D0.B5.D1.84.D0.B8.D0.BA.D1.81.D0.B5|динамического программирования по префиксу]]. Будем хранить матрицу <tex>D[0..M + 1][0..N + 1]</tex>, где <tex>D[i + 1][j + 1]</tex> {{---}} расстояние Дамерау-Левенштейна между префиксами строк <tex>S</tex> и <tex>T</tex>, длины префиксов {{---}} <tex>i</tex> и <tex>j</tex> соответственно.
Для учёта транспозиции потребуется хранение следующей информации. Инвариант:
j&&;&i = 0,\ j > 0\\
D(i - 1, j - 1)&&;&S[i] = T[j]\\
\min{(}\left(\begin{array}{llcl}\qquad\ D(i, j - 1) + insertCost\\D(i - 1, j) + deleteCost\qquad\D(i - 1, j - 1) + replaceCost\\\end{array}\right)}deleteCost&&;&j > 0,\ i > 0,\ S[i] \ne T[j]\\\qquad\ D(i - 1, j - 1) + replaceCost\\)
\end{array}\right.
</tex>
Тогда если символ <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>\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>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>.
''<font color=green>// База индукции</font>''
D[0][0] = INF;
'''for''' i = 0 '''to''' M
D[i + 1][1] = i
D[0][j + 1] = INF
i', j', last: '''int''' lastPosition: '''int[0..количество различных символов в S и T]: '''int'''
''<font color=green>//для каждого элемента C алфавита задано значение lastPosition[C]</font>''
'''for''' i = 1 '''to''' M
last = 0: '''int'''
'''for''' j = 1 '''to''' N
i' = lastPosition[T[j]]: '''int''' j' = last: '''int'''
'''if''' S[i] == T[j]
D[i + 1][j + 1] = D[i][j]
