63
правки
Изменения
→Упрощённый алгоритм: Замена min на /min, перевод переменных в tex, визуальное форматирование псевдокода
Здесь и далее будем использовать следующие обозначения: <tex>S</tex> и <tex>T</tex> {{---}} строки, между которыми требуется найти расстояние Дамерау {{---}} Левенштейна; <tex>M</tex> и <tex>N</tex> {{---}} их длины соответственно.
Рассмотрим алгоритм, отличающийся от алгоритма поиска расстояния Левенштейна одной проверкой (храним матрицу <tex>D</tex>, где <tex>D(i, j)</tex> — расстояние между префиксами строк: первыми <tex>i </tex> символами строки <tex>S</tex> и первыми <tex>j </tex> символами строки <tex>T</tex>). Рекуррентное соотношение имеет вид:
Ответ на задачу {{---}} <tex>D(M,N)</tex> , где
<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&&;&j = 0,\ i > 0\\
j&&;&i = 0,\ j > 0\\
D(i - 1, j - 1)&&;&S[i] = T[j]\\
\rmmin{min(}(\\
&D(i, j - 1) + insertCost\\
&D(i - 1, j) + deleteCost&;&j > 0,\ i > 0,\ S[i] \ne T[j]\\
</tex>
Таким образом для получения ответа необходимо заполнить матрицу <tex>D</tex>, пользуясь рекуррентным соотношением.
Сложность алгоритма: <tex>O\left (M \cdot N \right )</tex>. Затраты памяти: <tex>O\left (M \cdot N \right)</tex>.
'''int''' DamerauLevenshteinDistance('''char''' S[1..M], '''char''' T[1..N])
'''int''' d[0..M, 0..N]
'''int''' i, j, cost, deleteCost = 1, insertCost = 1, replaceCost = 1, transposeCost = 1
''<font color=green>// База динамики</font>''
'''for''' i '''from''' 0 '''to''' M
d[i, 0] = i
'''for''' i '''from''' 1 '''to''' M
'''for''' j '''from''' 1 '''to''' N
''<font color=green>// Стоимость замены</font>'' '''if''' S[i] == T[j] '''then''' replaceCost = 0 '''else''' replaceCost = 1
d[i, j] = minimum(
d[i-1, j ] + deleteCost, ''<font color=green>// удаление</font>'' d[i , j-1] + insertCost, ''<font color=green>// вставка</font>'' d[i-1, j-1] + replaceCost ''<font color=green>// замена</font>''
)
'''if'''(i > 1 '''and''' j > 1
d[i, j] = minimum(
d[i, j],
d[i-2, j-2] + transposeCost ''<font color=green>// транспозиция</font>''
)
