Задача о расстоянии Дамерау-Левенштейна

Определение:

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

Является модификацией расстояния Левенштейна, отличается от него добавлением операции перестановки.

Расстояние Дамерау — Левенштейна является метрикой.

Практическое применение

Расстояние Дамерау — Левенштейна, как и метрика Левенштейна, является мерой "схожести" двух строк. Алгоритм его поиска находит применение в реализации нечёткого поиска, а также в биоинформатике (сравнение ДНК), несмотря на то, что изначально алгоритм разрабатывался для сравнения текстов, набранных человеком (Дамерау показал, что 80% человеческих ошибок при наборе текстов составляют перестановки соседних символов, пропуск символа, добавление нового символа, и ошибка в символе. Поэтому метрика Дамерау — Левенштейна часто используется в редакторских программах для проверки правописания).

Описание алгоритма

Метод динамического программирования позволяет найти расстояние Дамерау — Левенштейна между двумя строками [math]S[/math] и [math]T[/math], длины которых равны соответственно [math]m[/math] и [math]n[/math], затратив сравнительно небольшое количество вычислительных ресурсов. Сложность алгоритма: [math]O\left (m \cdot n \cdot \max(m, n) \right )[/math]. Затраты памяти: [math]O\left (M \cdot N \right)[/math]. Однако скорость работы алгоритма может быть улучшена до [math]O\left (M \cdot N \right)[/math].

Наивный алгоритм

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

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]

Контрпример: [math]S =[/math] [math]'CA'[/math] и [math]T =[/math] [math]'ABC'[/math]. Расстояние Дамерау — Левенштейна между строками равно 2 ([math]CA \rightarrow AC \rightarrow ABC[/math]), однако функция приведённая выше возвратит 3. Дело в том, что использование этого упрощённого алгоритма накладывает ограничение: любая подстрока может быть редактирована не более одного раза. Поэтому переход [math]AC \rightarrow ABC[/math] невозможен, и последовательность действий такая: ([math]CA \rightarrow A \rightarrow AB \rightarrow ABC[/math]).

Ниже представлен более сложный алгоритм, который корректно решает задачу поиска расстояния Дамерау — Левенштейна.

Алгоритм

В основу алгоритма положена идея динамического программирования по префиксу. будем хранить матрицу [math]D[m][n][/math], где [math]D[i][j][/math] — расстояние Дамерау — Левенштейна между префиксами строк [math]S[/math] и [math]T[/math], длины префиксов — [math]i[/math] и [math]j[/math] соответственно. Будем редактировать элементы матрицы по формуле:

[math]\rm{D}(i, j) = \left\{\begin{array}{llcl} 0&&;&i = 0,\ j = 0\\ i&&;&j = 0,\ i \gt 0\\ j&&;&i = 0,\ j \gt 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 \gt 0,\ i \gt 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. [/math]

В оригинальной задаче [math]deleteCost = insertCost = 1;[/math]

[math]replaceCost = \begin{cases}1, & S[i] \neq T[j], \\ 0, & S[i] = T[j]; \end{cases}[/math]

[math]transpositionCost = \begin{cases}1, & S[i] = T[j - 1] \wedge S[i - 1] = T[j], \\ \infty, & \textnormal{иначе. }\end{cases}[/math]

Псевдокод алгоритма:

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]

См. также

• Задача о редакционном расстоянии, алгоритм Левенштейна

Cсылки

• статья на английской Википедии
• Нечёткий поиск в тексте и словаре (Хабрахабр)