63
правки
Изменения
м
→Корректный алгоритм: Замена min на /min, перевод переменных в tex, визуальное форматирование псевдокода
В интересах краткости положим <tex>insertCost = deleteCost = replaceCost = transposeCost = 1</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>.
В основу алгоритма положена идея динамического программирования по префиксу. Будем хранить матрицу <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> соответственно.
<tex>lastPosition[x]</tex> {{---}} индекс последнего вхождения <tex>x</tex> в <tex>S</tex>
<tex>last</tex> {{---}} на <tex>i</tex>-й итерации внешнего цикла индекс последнего символа <tex>T: T[last] = S[i]</tex>
Тогда если на очередной итерации внутреннего цикла положить: <tex>i' = lastPosition[T[j]],\ j' = last</tex>, то
j&&;&i = 0,\ j > 0\\
D(i - 1, j - 1)&&;&S[i] = T[j]\\
\rmmin{min(}(\\
&D(i, j - 1) + 1\\
&D(i - 1, j) + 1&;&j > 0,\ i > 0,\ S[i] \ne T[j]\\
'''int''' DamerauLevenshteinDistance('''char''' S[1..M], '''char''' T[1..N])'''
''<font color=green>// Обработка крайних случаев</font>''
'''if''' (S == "") '''then'''
'''if''' (T == "") '''then'''
'''else''' '''if''' (T == "") '''then'''
'''return''' M
'''int''' D[0..M + 1, 0..N + 1] ''<font color=green>// Динамика</font>'' '''int''' INF = M + N ''<font color=green>// Большая константа</font>''
''<font color=green>// База индукции</font>''
D[0, 0] = INF;
'''for''' i '''from''' 0 '''to''' M
'''int''' lastPosition[0..количество различных символов в S и T]
''<font color=green>//для каждого элемента C алфавита задано значение lastPosition[C]</font>''
'''foreach''' ('''char''' Letter '''in''' (S + T))
