74
правки
Изменения
Нет описания правки
Является модификацией [[Задача о редакционном расстоянии, алгоритм Левенштейна| расстояния Левенштейна]], отличается от него добавлением операции перестановки.
Расстояние Дамерау {{---}} Левенштейна является метрикой.(Предполагаем, что цены операций таковы, что выполнено правило треугольника: если две последовательные операции можно заменить одной, то это не ухудшает общую цену.)
Расстояние Дамерау {{---}} Левенштейна, как и метрика [http://ru.wikipedia.org/wiki/Левенштейн,_Владимир,_Иосифович Левенштейна], является мерой "схожести" двух строк. Алгоритм его поиска находит применение в реализации нечёткого поиска, а также в биоинформатике (сравнение ДНК), несмотря на то, что изначально алгоритм разрабатывался для сравнения текстов, набранных человеком ([http://en.wikipedia.org/wiki/Frederick_J._Damerau Дамерау] показал, что 80% человеческих ошибок при наборе текстов составляют перестановки соседних символов, пропуск символа, добавление нового символа, и ошибка в символе. Поэтому метрика Дамерау {{---}} Левенштейна часто используется в редакторских программах для проверки правописания).
==Описание алгоритмаУпрощённый алгоритм==Метод динамического программирования позволяет найти расстояние Дамерау {{---}} Рассмотрим алгоритм, отличающийся от алгоритма поиска расстояния Левенштейна между двумя строками <tex>S</tex> и одной проверкой (храним матрицу <tex>TD</tex>, длины которых равны соответственно где <tex>m</tex> и <tex>n</tex>, затратив сравнительно небольшое количество вычислительных ресурсов. Сложность алгоритма: <tex>O\left (m \cdot n \cdot \maxD(mi, n) \right j)</tex>. Затраты памяти — расстояние между префиксами строк: первыми i символами строки <tex>O\left (M \cdot N \right)S</tex>. Однако скорость работы алгоритма может быть улучшена до и первыми j символами строки <tex>O\left (M \cdot N \right)T</tex>).Рекуррентное соотношение имеет вид:
<tex> D(S, T) = D(M,N)</tex> , где <tex>A = \left\{\begin{array}{llcl}0&&;&i = 0,\ j = 0\\i&&;&j =0,\ i > 0\\j&&;&i =Наивный алгоритм0,\ j > 0\\D(i - 1, j - 1)&&;&S[i] =T[j]\\\rm{min}(\\&D(i, j - 1) + insertCost\\&D(i - 1, j) + deleteCost&;&j > 0,\ i > 0,\ S[i] \ne T[j]\\&D(i - 1, j - 1) + replaceCost\\)\end{array}\right.</tex><tex>D(i, j) =\left\{\begin{array}{llcl}Простая модификация алгоритма поиска min(A, D(i - 2, j - 2) + transpositionCost)&&;&i > 1,\ j > 1,\ S[i] = T[Задача о редакционном расстоянииj-1], алгоритм Левенштейна| расстояния Левенштейна\ S[i-1]= T[j] не приводит к цели)\\A&&; \text{иначе}\\\end{array}\right.</tex> Таким образом для получения ответа необходимо заполнить матрицу D, пользуясь рекуррентным соотношением. Рассмотрим псевдокод Сложность алгоритма, отличающегося от : <tex>O\left (m \cdot n \right )</tex>. Затраты памяти: <tex>O\left (M \cdot N \right)</tex>. Псевдокод алгоритма поиска расстояния Левенштейна одной проверкой:
'''int''' DamerauLevenshteinDistance('''char''' S[1..m], '''char''' T[1..n])
Контрпример: <tex>S =</tex> <tex>'CA'</tex> и <tex>T =</tex> <tex>'ABC'</tex>. Расстояние Дамерау {{---}} Левенштейна между строками равно 2 (<tex>CA \rightarrow AC \rightarrow ABC</tex>), однако функция приведённая выше возвратит 3. Дело в том, что использование этого упрощённого алгоритма накладывает ограничение: любая подстрока может быть редактирована не более одного раза. Поэтому переход <tex>AC \rightarrow ABC</tex> невозможен, и последовательность действий такая: (<tex>CA \rightarrow A \rightarrow AB \rightarrow ABC</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>D[0..m + 1][0..n + 1]</tex>, где <tex>D[i + 1][j + 1]</tex> {{---}} расстояние Дамерау {{---}} Левенштейна между префиксами строк <tex>S</tex> и <tex>T</tex>, длины префиксов {{---}} <tex>i</tex> и <tex>j</tex> соответственно. Будем хранить дополнительную информацию. Инвариант: <tex>sd[x]</tex> {{---}} индекс последнего вхождения <tex>x</tex> в <tex>S</tex> <tex>db</tex> {{---}} индекс последнего символа <tex>T: T[db] = S[i]</tex>
Псевдокод алгоритма:
D[0, j + 1] = INF
'''declare''' sd[0..количество различных символов в S и T] {{---}} отсортированный алфавит
''//для каждого элемента C алфавита задано значение sd[C]''
'''declare''' '''int''' DB = 0
'''for''' j '''from''' 1 '''to''' n
'''declare''' '''int''' i1 = sd[targetT[j - 1]]
'''declare''' '''int''' j1 = DB
'''if''' sourceS[i - 1] == targetT[j - 1] '''then'''
D[i + 1, j + 1] = D[i, j]
DB = j
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]
==См. также==
*[[Задача о редакционном расстоянии, алгоритм ЛевенштейнаВагнера-Фишера]]
==Cсылки==
*[http://en.wikipedia.org/wiki/Damerau–Levenshtein_distance статья Статья на английской Википедии]
*[http://habrahabr.ru/blogs/algorithm/114997/ Нечёткий поиск в тексте и словаре (Хабрахабр)]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Динамическое программирование]]
