Задача о расстоянии Дамерау-Левенштейна
| Определение: |
| Расстояние Дамерау — Левенштейна (Damerau — Levenshtein distance) между двумя строками, состоящими из конечного числа символов — это минимальное число операций вставки, удаления, замены одного символа и транспозиции двух соседних символов, необходимых для перевода одной строки в другую. |
Является модификацией расстояния Левенштейна, отличается от него добавлением операции перестановки.
Расстояние Дамерау — Левенштейна является метрикой.
Содержание
Практическое применение
Расстояние Дамерау — Левенштейна, как и метрика Левенштейна, является мерой "схожести" двух строк. Алгоритм его поиска находит применение в реализации нечёткого поиска, а также в биоинформатике (сравнение ДНК), несмотря на то, что изначально алгоритм разрабатывался для сравнения текстов, набранных человеком (Дамерау показал, что 80% человеческих ошибок при наборе текстов составляют перестановки соседних символов, пропуск символа, добавление нового символа, и ошибка в символе. Поэтому метрика Дамерау — Левенштейна часто используется в редакторских программах для проверки правописания).
Описание алгоритма
Метод динамического программирования позволяет найти расстояние Дамерау — Левенштейна между двумя строками и , длины которых равны соответственно и , затратив сравнительно небольшое количество вычислительных ресурсов. Сложность алгоритма: . Затраты памяти: . Однако скорость работы алгоритма может быть улучшена до .
Наивный алгоритм
Простая модификация алгоритма поиска расстояния Левенштейна не приводит к цели. Рассмотрим псевдокод алгоритма, отличающегося от алгоритма поиска расстояния Левенштейна одной проверкой:
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]
Контрпример: и . Расстояние Дамерау — Левенштейна между строками равно 2 (), однако функция приведённая выше возвратит 3. Дело в том, что использование этого упрощённого алгоритма накладывает ограничение: любая подстрока может быть редактирована не более одного раза. Поэтому переход невозможен, и последовательность действий такая: ().
Ниже представлен более сложный алгоритм, который корректно решает задачу поиска расстояния Дамерау — Левенштейна.
Алгоритм
В основу алгоритма положена идея динамического программирования по префиксу. будем хранить матрицу , где — расстояние Дамерау — Левенштейна между префиксами строк и , длины префиксов — и соответственно.
Псевдокод алгоритма:
int DamerauLevenshteinDistance(char S[1..m], char T[1..n])
// Обработка крайних случаев
if (S == "") then
if (T == "") then
return 0
else
return n
else if (T == "") then
return m
declare int D[0..m + 1, 0..n + 1] // Динамика
declare int INF = m + n // Большая константа
// База индукции
D[0, 0] = INF;
for i from 0 to m
D[i + 1, 1] = i
D[i + 1, 0] = INF
for j from 0 to n
D[1, j + 1] = j
D[0, j + 1] = INF
declare sd[0..количество различных символов в S и T] — отсортированный алфавит
//для каждого элемента C алфавита задано значение sd[C]
foreach (char Letter in (S + T))
if Letter не содержится в sd
добавить Letter в sd
sd[Letter] = 0
for i from 1 to m
declare int DB = 0
for j from 1 to n
declare int i1 = sd[target[j - 1]]
declare int j1 = DB
if source[i - 1] == target[j - 1] then
D[i + 1, j + 1] = D[i, j]
DB = j
else
D[i + 1, j + 1] = minimum(D[i, j], D[i + 1, j], D[i, j + 1]) + 1
D[i + 1, j + 1] = minimum(D[i + 1, j + 1], D[i1, j1] + (i - i1 - 1) + 1 + (j - j1 - 1))
sd[S[i - 1]] = i
return D[m + 1, n + 1]
