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