Задача о расстоянии Дамерау-Левенштейна
Определение: |
Расстояние Дамерау — Левенштейна (Damerau — Levenshtein distance) между двумя строками, состоящими из конечного числа символов — это минимальное число операций вставки, удаления, замены одного символа и транспозиции двух соседних символов, необходимых для перевода одной строки в другую. |
Является модификацией расстояния Левенштейна, отличается от него добавлением операции перестановки.
Расстояние Дамерау — Левенштейна является метрикой. (Предполагаем, что цены операций таковы, что выполнено правило треугольника: если две последовательные операции можно заменить одной, то это не ухудшает общую цену.)
Содержание[убрать] |
[править] Практическое применение
Расстояние Дамерау — Левенштейна, как и метрика Левенштейна, является мерой "схожести" двух строк. Алгоритм его поиска находит применение в реализации нечёткого поиска, а также в биоинформатике (сравнение ДНК), несмотря на то, что изначально алгоритм разрабатывался для сравнения текстов, набранных человеком (Дамерау показал, что 80% человеческих ошибок при наборе текстов составляют перестановки соседних символов, пропуск символа, добавление нового символа, и ошибка в символе. Поэтому метрика Дамерау — Левенштейна часто используется в редакторских программах для проверки правописания).
[править] Упрощённый алгоритм
Не решает задачу корректно, но бывает полезен на практике.
Здесь и далее будем использовать следующие обозначения: и
— строки, между которыми требуется найти расстояние Дамерау — Левенштейна;
и
— их длины соответственно.
Рассмотрим алгоритм, отличающийся от алгоритма поиска расстояния Левенштейна одной проверкой (храним матрицу , где
— расстояние между префиксами строк: первыми i символами строки
и первыми j символами строки
). Рекуррентное соотношение имеет вид:
Ответ на задачу — , где
Таким образом для получения ответа необходимо заполнить матрицу D, пользуясь рекуррентным соотношением.
Сложность алгоритма: . Затраты памяти:
.
Псевдокод алгоритма:
int DamerauLevenshteinDistance(char S[1..M], char T[1..N]) int d[0..M, 0..N] 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 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]