74
правки
Изменения
Нет описания правки
|definition=
'''Расстояние Дамерау {{---}} Левенштейна''' (Damerau {{---}} Levenshtein distance) между двумя строками, состоящими из конечного числа символов {{---}} это минимальное число операций вставки, удаления, замены одного символа и транспозиции двух соседних символов, необходимых для перевода одной строки в другую.}}
Является модификацией [[Задача о редакционном расстоянии, алгоритм ЛевенштейнаВагнера-Фишера| расстояния Левенштейна]], отличается от него добавлением операции перестановки.
Расстояние Дамерау {{---}} Левенштейна является метрикой. (Предполагаем, что цены операций таковы, что выполнено правило треугольника: если две последовательные операции можно заменить одной, то это не ухудшает общую цену.)
==Практическое применение==
Расстояние Дамерау {{---}} Левенштейна, как и метрика [http://ru.wikipedia.org/wiki/Левенштейн,_Владимир,_Иосифович _Владимир_Иосифович Левенштейна], является мерой "схожести" двух строк. Алгоритм его поиска находит применение в реализации нечёткого поиска, а также в биоинформатике (сравнение ДНК), несмотря на то, что изначально алгоритм разрабатывался для сравнения текстов, набранных человеком ([http://en.wikipedia.org/wiki/Frederick_J._Damerau Дамерау] показал, что 80% человеческих ошибок при наборе текстов составляют перестановки соседних символов, пропуск символа, добавление нового символа, и ошибка в символе. Поэтому метрика Дамерау {{---}} Левенштейна часто используется в редакторских программах для проверки правописания).
==Упрощённый алгоритм==
Здесь и далее будем использовать следующие обозначения: <tex>S</tex> и <tex>T</tex> {{---}} строки, между которыми требуется найти расстояние Дамерау {{---}} Левенштейна; <tex>M</tex> и <tex>N</tex> {{---}} их длины соответственно.
Рассмотрим алгоритм, отличающийся от алгоритма поиска расстояния Левенштейна одной проверкой (храним матрицу <tex>D</tex>, где <tex>D(i, j)</tex> — расстояние между префиксами строк: первыми i символами строки <tex>S</tex> и первыми j символами строки <tex>T</tex>). Рекуррентное соотношение имеет вид:
Ответ на задачу {{---}} <tex> D(S, T) = D(M,N)</tex> , где
<tex>A = \left\{\begin{array}{llcl}
</tex>
<tex>D(i, j) = \left\{\begin{array}{llcl}
min(A, D(i - 2, j - 2) + transpositionCosttransposeCost)&&;&i > 1,\ j > 1,\ S[i] = T[j-1],\ S[i-1] = T[j])\\A&&; \text{иначеotherwise}\\
\end{array}\right.
</tex>
'''int''' DamerauLevenshteinDistance('''char''' S[1..m], '''char''' T[1..n])
''// База динамики''
d[i, j] = minimum(
d[i-1, j ] + 1deleteCost, ''// удаление'' d[i , j-1] + 1insertCost, ''// вставка'' d[i-1, j-1] + cost replaceCost ''// замена''
)
'''if'''(i > 1 '''and''' j > 1
d[i, j] = minimum(
d[i, j],
d[i-2, j-2] + costTransposition transposeCost ''// транспозиция''
)
==Алгоритм==
В интересах краткости положим <tex>insertCost = deleteCost = replaceCost = transposeCost = 1</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>.
Тогда если на очередной итерации внутреннего цикла положить: <tex>i1 = sd[T[j]],\ j1 = DB</tex>, то
<tex>D(i, j) = min(A, D(i1, j1) + (i - i1 - 1) + 1 + (j - j1 - 1)) </tex> <tex>(*)</tex>
, где
D(i - 1, j - 1)&&;&S[i] = T[j]\\
\rm{min}(\\
&D(i, j - 1) + insertCost1\\&D(i - 1, j) + deleteCost1&;&j > 0,\ i > 0,\ S[i] \ne T[j]\\&D(i - 1, j - 1) + replaceCost1\\
)
\end{array}\right.
</tex>
Доказательства требует лишь утверждение формула <tex>(*)</tex>, так как смысл которой {{---}} сравнение стоимости перехода без использования транспозиции (<tex>A</tex>) со стоимостью перехода, включающего в число операций транспозицию; остальные формулы обосновываются так же, как и в доказательстве [[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера|алгоритма Вагнера {{---}} Фишера]]. Но действительно, при редактировании подпоследовательности несколько раз всегда существует оптимальная последовательность операций одного из двух видов:
*Переставить местами соседние символы, затем вставить некоторое количество символов между ними;
*Удалить некоторое количество символов, а затем переставить местами символы, ставшие соседними.
Тогда если символ <tex>S[i]</tex> встречался в <tex>T[1]..T[j]</tex> на позиции <tex>j1</tex>, а символ <tex>T[j]</tex> встречался в <tex>S[1]..S[i]</tex> на позиции <tex>i1</tex>; то <tex>T[1]..T[j]</tex> может быть получена из <tex>S[1]..S[i]</tex> удалением символов <tex>S[i1 + 1]..S[i - 1]</tex>, транспозицией ставших соседними <tex>S[i1]</tex> и <tex>S[i]</tex> и вставкой символов <tex>T[j1 + 1]..T[j - 1]</tex>. Суммарно на это будет затрачено <tex>D(i1, j1) + (i - i1 - 1) + 1 + (j - j1 - 1)</tex> операций. Следовательно выражение с условием , что описано в <tex>(*)</tex> выбирает . Поэтому мы выбирали оптимальную последовательность операций, рассматривая рассматрев случай с транспозицией и без неё.
Псевдокод алгоритма:
'''else''' '''if''' (T == "") '''then'''
'''return''' m
''// База индукции''
D[0, j + 1] = INF
'''declareint''' sd[0..количество различных символов в S и T]
''//для каждого элемента C алфавита задано значение sd[C]''
'''for''' i '''from''' 1 '''to''' m
'''for''' j '''from''' 1 '''to''' n
'''if''' S[i] == T[j] '''then'''
D[i + 1, j + 1] = D[i, j]
