Изменения

'''Расстояние Дамерау {{---}} Левенштейна''' (Damerau {{---}} Levenshtein distance) между двумя строками, состоящими из конечного числа символов {{---}} это минимальное число операций вставки, удаления, замены одного символа и транспозиции двух соседних символов, необходимых для перевода одной строки в другую.}}

Метод динамического программирования позволяет найти расстояние Дамерау {{---}} Левенштейна между двумя строками <tex>S</tex> и <tex>T</tex>, длины которых равны соответственно <tex>m</tex> и <tex>n</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>.

==Наивный алгоритм==Простая модификация алгоритма поиска [[Задача о редакционном расстоянии, алгоритм Левенштейна| расстояния Левенштейна]] не приводит к цели. Рассмотрим псевдокод алгоритма, отличающегося от алгоритма поиска расстояния Левенштейна одной проверкой:

Рассмотрим более сложный алгоритм '''int''' DamerauLevenshteinDistance('''char''' S[1..m], '''char''' T[1..n]) '''declare''' '''int''' d[0..m, 0..n] '''declare''' '''int''' i, j, cost ''// База динамики'' '''for''' i '''from''' 0 '''to''' m d[i, 0] = i '''for''' j '''from''' 1 '''to''' n d[0, j] = j '''for''' i '''from''' 1 '''to''' m '''for''' j '''from''' 1 '''to''' n ''// Стоимость замены'' '''if''' S[i] == T[j] '''then''' cost = 0 '''else''' cost = 1 d[i, j] = minimum( d[i-1, j ] + 1, ''// удаление'' d[i , j-1] + 1, ''// вставка'' d[i-1, который корректно решает задачу поиска расстояния Дамерау {{j-1] + cost ''// замена'' ) '''if'''(i > 1 '''and''' j > 1 '''and''' S[i] == T[j-1] '''and''' S[i-}} Левенштейна.1] == T[j]) '''then''' d[i, j] = minimum( d[i, j], d[i-2, j-2] + costTransposition ''// транспозиция'' ) '''return''' d[m, n]

 Контрпример: <tex>S =</tex> <tex>'CA'</tex> и <tex>T =Оценка сложности</tex> <tex>'ABC'</tex>. Расстояние Дамерау {{---}} Левенштейна между строками равно 2 (<tex>CA \rightarrow AC \rightarrow ABC</tex>), однако функция приведённая выше возвратит 3. Дело в том, что использование этого упрощённого алгоритма накладывает ограничение: любая подстрока может быть редактирована не более одного раза. Поэтому переход <tex>AC \rightarrow ABC</tex> невозможен, и последовательность действий такая: (<tex>CA \rightarrow A \rightarrow AB \rightarrow ABC</tex>). Ниже представлен более сложный алгоритм, который корректно решает задачу поиска расстояния Дамерау {{---}} Левенштейна. ==Алгоритм==В основу алгоритма положена идея динамического программирования по префиксу. будем хранить матрицу <tex>D[m][n]</tex>, где <tex>D[i][j]</tex> {{---}} расстояние Дамерау {{---}} Левенштейна между префиксами строк <tex>S</tex> и <tex>T</tex>, длины префиксов {{---}} <tex>i</tex> и <tex>j</tex> соответственно. Будем редактировать элементы матрицы по формуле: <tex>\rm{D}(i, j) = \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_1[i] = S_2[j]\\\rm{min}(\\&\rm{D}(i, j - 1) + insertCost\\&\rm{D}(i - 1, j) + deleteCost&;&j > 0,\ i > 0,\ S_1[i] \ne S_2[j]\\&\rm{D}(i - 1, j - 1) + replaceCost\\&\rm{D}(i - 2, j - 2) + transpositionCost\\)\end{array}\right.</tex> В оригинальной задаче <tex>deleteCost = insertCost = 1;</tex> <tex>replaceCost = \begin{cases}1, & S[i] \neq T[j], \\ 0, & S[i] = T[j]; \end{cases}</tex> <tex>transpositionCost = \begin{cases}1, & S[i] = T[j - 1] \wedge S[i - 1] = T[j], \\ \infty, & \textnormal{иначе. }\end{cases}</tex> Псевдокод алгоритма: '''int''' DamerauLevenshteinDistance('''char''' S[1..m], '''char''' T[1..n]) '''declare''' '''int''' d[0..m, 0..n] '''declare''' '''int''' i, j, cost ''// База динамики'' '''for''' i '''from''' 0 '''to''' m d[i, 0] = i '''for''' j '''from''' 1 '''to''' т d[0, j] = j '''for''' i '''from''' 1 '''to''' m '''for''' j '''from''' 1 '''to''' n ''// Стоимость замены'' '''if''' S[i] == T[j] '''then''' costChange = 0 '''else''' costChange = 1 '''if''' S[i] == T[j - 1] и S[i - 1] = T[j] '''then''' costTransposition = 1 '''else''' costTransposition = inf ''// значение константы inf очень велико'' ''// costTransposition = inf, то использовать'' ''// транспозицию заведомо невыгодно'' d[i, j] = minimum( d[i-1, j ] + 1, ''// удаление'' d[i , j-1] + 1, ''// вставка'' d[i-1, j-1] + costChange ''// замена'' d[i-2, j-2] + costTransposition ''// транспозиция'' ) '''return''' d[m, n]