Изменения

'''Расстояние Дамерау {{---}} Левенштейна''' (англ. ''Damerau {{---}} Levenshtein distance'') между двумя строками, состоящими из конечного числа символов {{---}} это минимальное число операций вставки, удаления, замены одного символа и транспозиции двух соседних символов, необходимых для перевода одной строки в другую.}}Является модификацией [[Задача о редакционном расстоянии, алгоритм ЛевенштейнаВагнера-Фишера| расстояния Левенштейна]], отличается от него добавлением операции перестановки.

==Практическое применение==Расстояние Дамерау -Левенштейна, как и метрика Левенштейна, является мерой "схожести" двух строк. Алгоритм его поиска находит применение в реализации нечёткого поиска, а также в биоинформатике (сравнение ДНК), несмотря на то, что изначально алгоритм разрабатывался для сравнения текстов, набранных человеком (Дамерау показал, что 80% человеческих ошибок при наборе текстов составляют перестановки соседних символов, пропуск символа, добавление нового символа, и ошибка в символе. Поэтому метрика Дамерау-Левенштейна часто используется в редакторских программах для проверки правописания).  ==Упрощённый алгоритм==Не решает задачу корректно, но бывает полезен на практике. Здесь и далее будем использовать следующие обозначения: <tex>S</tex> и <tex>T</tex> {{---}} строки, между которыми требуется найти расстояние Дамерау-Левенштейна; <tex>M</tex> и <tex>N</tex> {{---}} их длины соответственно. Рассмотрим алгоритм, отличающийся от алгоритма поиска расстояния Левенштейна является метрикойодной проверкой (храним матрицу <tex>D</tex>, где <tex>D(i, j)</tex> — расстояние между префиксами строк: первыми <tex>i</tex> символами строки <tex>S</tex> и первыми <tex>j</tex> символами строки <tex>T</tex>). Рекуррентное соотношение имеет вид: Ответ на задачу {{---}} <tex>D(M,N)</tex> , где <tex>D(i, j) = \left\{\begin{array}{lllc}\min{(A, D(i - 2, j - 2) + transposeCost)}&&;\ i > 1,\ j > 1,\ S[i] = T[j - 1],\ S[i - 1] = T[j]\\A&&;\ \text{otherwise}\\\end{array}\right.</tex> <tex>A = \left\{\begin{array}{llcl}0&;\ i = 0,\ j = 0\\i * deleteCost&;\ j = 0,\ i > 0\\j * insertCost&;\ i = 0,\ j > 0\\D(i - 1, j - 1)&;\ S[i] = T[j]\\\min{(}\\\begin{array}{llcl}&D(i, j - 1) + insertCost\\&D(i - 1, j) + deleteCost&&\\&D(i - 1, j - 1) + replaceCost\\\end{array}&;\ j > 0,\ i > 0,\ S[i] \ne T[j]\\)\end{array}\right.</tex> Таким образом для получения ответа необходимо заполнить матрицу <tex>D</tex>, пользуясь рекуррентным соотношением.Сложность алгоритма: <tex>O\left (M \cdot N \right )</tex>. Затраты памяти: <tex>O\left (M \cdot N \right)</tex>. Псевдокод алгоритма:  '''int''' DamerauLevenshteinDistance(S: '''char[1..M]''', T: '''char[1..N]'''; deleteCost, insertCost, replaceCost, transposeCost: '''int'''): d: '''int[0..M][0..N]''' ''<font color=green>// База динамики</font>'' d[0][0] = 0 '''for''' i = 1 '''to''' M d[i][0] = d[i - 1][0] + deleteCost '''for''' j = 1 '''to''' N d[0][j] = d[0][j - 1] + insertCost '''for''' i = 1 '''to''' M '''for''' j = 1 '''to''' N ''<font color=green>// Стоимость замены</font>'' '''if''' S[i] == T[j] d[i][j] = d[i - 1][j - 1] '''else''' d[i][j] = d[i - 1][j - 1] + replaceCost d[i][j] = min( d[i][j], ''<font color=green>// замена</font>'' d[i - 1][j ] + deleteCost, ''<font color=green>// удаление</font>'' d[i ][j - 1] + insertCost ''<font color=green>// вставка</font>'' ) '''if'''(i > 1 '''and''' j > 1 '''and''' S[i] == T[j - 1] '''and''' S[i - 1] == T[j]) d[i][j] = min( d[i][j], d[i - 2][j - 2] + transposeCost ''<font color=green>// транспозиция</font>'' ) '''return''' d[M][N]

==Практическое применение==Расстояние Упрощенный алгоритм Дамерау {{---}} Левенштейнане является метрикой, так как и метрика [httpне выполняется правило треугольника://ru.wikipedia.org/wiki/Левенштейн<tex>\mathtt{DLD}('CA',_Владимир\ 'AC') + \mathtt{DLD}('AC',_Иосифович Левенштейна], является мерой "схожести" двух строк. Алгоритм его поиска находит применение в реализации нечёткого поиска\ 'ABC') \ngeqslant \mathtt{DLD}('CA', а также в биоинформатике (сравнение ДНК\ 'ABC'), несмотря на то, что изначально алгоритм разрабатывался для сравнения текстов, набранных человеком ([http:/</entex>.wikipedia Условие многих практических задач не предполагает многократного редактирования подстрок, поэтому часто достаточно упрощённого алгоритма.org/wiki/Frederick_J._Damerau Дамерау] показалНиже представлен более сложный алгоритм, что 80% человеческих ошибок при наборе текстов составляют перестановки соседних символов, пропуск символа, добавление нового символа, и ошибка в символе. Поэтому метрика который корректно решает задачу поиска расстояния Дамерау {{---}} Левенштейна часто используется в редакторских программах для проверки правописания).

==Описание алгоритмаКорректный алгоритм==Метод В основу алгоритма положена идея [[Динамическое программирование#.D0.9F.D1.80.D0.B8.D0.BD.D1.86.D0.B8.D0.BF_.D0.BE.D0.BF.D1.82.D0.B8.D0.BC.D0.B0.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B8_.D0.BD.D0.B0_.D0.BF.D1.80.D0.B5.D1.84.D0.B8.D0.BA.D1.81.D0.B5|динамического программирования позволяет найти расстояние Дамерау {{---}} Левенштейна между двумя строками по префиксу]]. Будем хранить матрицу <tex>SD[0..M + 1][0..N + 1]</tex> и , где <tex>TD[i + 1][j + 1]</tex>, длины которых равны соответственно {{---}} расстояние Дамерау-Левенштейна между префиксами строк <tex>mS</tex> и <tex>nT</tex>, затратив сравнительно небольшое количество вычислительных ресурсов. Сложность алгоритма: <tex>O\left (m \cdot n \cdot \max(m, n) \right )</tex>. Затраты памяти: длины префиксов {{---}} <tex>O\left (M \cdot N \right)i</tex>. Однако скорость работы алгоритма может быть улучшена до и <tex>O\left (M \cdot N \right)j</tex>соответственно.

==Наивный алгоритм==Простая модификация алгоритма поиска [[Задача о редакционном расстоянии, алгоритм Левенштейна| расстояния Левенштейна]] не приводит к целиДля учёта транспозиции потребуется хранение следующей информации. Рассмотрим псевдокод алгоритма, отличающегося от алгоритма поиска расстояния Левенштейна одной проверкойИнвариант:

'''int''' DamerauLevenshteinDistance('''char''' S[1..m], '''char''' T[1..n]) '''declare''' '''int''' d<tex>\mathtt{lastPosition}[0..m, 0..nx] '''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[itex> {{-1, j ] + 1, ''// удаление'' d[i , j-1] + 1, ''// вставка'' d[i-1, j-1] + cost ''}} индекс последнего вхождения <tex>x<// замена'' ) '''if'''(i tex> 1 '''and''' j в <tex> 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]tex>

КонтрпримерТогда если на очередной итерации внутреннего цикла положить: <tex>S =</tex> <tex>'CAi'</tex> и <tex>T =</tex> <tex>'ABC'</tex>. Расстояние Дамерау {\mathtt{---lastPosition}} Левенштейна между строками равно 2 (<tex>CA [T[j]],\rightarrow AC j' = \rightarrow ABC</tex>), однако функция приведённая выше возвратит 3. Дело в том, что использование этого упрощённого алгоритма накладывает ограничение: любая подстрока может быть редактирована не более одного раза. Поэтому переход <tex>AC \rightarrow ABCmathtt{last}</tex> невозможен, и последовательность действий такая: (<tex>CA \rightarrow A \rightarrow AB \rightarrow ABC</tex>).то

Ниже представлен более сложный алгоритм<tex>D(i, который корректно решает задачу поиска расстояния Дамерау {j) = \min{(A, D(i', j') + (i - i' -1) \cdot deleteCost + transposeCost + (j -j' -1) \cdot insertCost)}} Левенштейна.</tex> <tex>(*)</tex>

==Алгоритм==В основу алгоритма положена идея динамического программирования по префиксу. будем хранить матрицу <tex>D[m][n]</tex>, где <tex>D[i][j]</tex> {{---}} расстояние Дамерау {{---}} Левенштейна между префиксами строк <tex>S</tex> и <tex>T</tex>, длины префиксов {{---}} <tex>i</tex> и <tex>j</tex> соответственно. Будем редактировать элементы матрицы по формуле:

<tex>\rm{D}(i, j) A = \left\{\begin{array}{llcl}0&&;&\ i = 0,\ j = 0\\i&* deleteCost&;&\ j = 0,\ i > 0\\j&* insertCost&;&\ i = 0,\ j > 0\\D(i - 1, j - 1)&&;&S_1\ S[i] = S_2T[j]\\\rmmin{min(}(\\&\rmbegin{array}{llcl}&D}(i, j - 1) + insertCost\\&\rm{D}(i - 1, j) + deleteCost&;&j > 0,\ i > 0,\ S_1[i] \ne S_2[j]\\&\rm{D}(i - 1, j - 1) + replaceCost\\&\rmend{Darray}(&;\ j > 0,\ i - 2> 0, \ S[i] \ne T[j - 2) + transpositionCost]\\

В оригинальной задаче Доказательства требует лишь формула <tex>deleteCost = insertCost = 1;(*)</tex>, смысл которой {{---}} сравнение стоимости перехода без использования транспозиции <tex>(A)</tex>со стоимостью перехода, включающего в число операций транспозицию; остальные формулы обосновываются так же, как и в доказательстве [[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера|алгоритма Вагнера-Фишера]]. Но действительно, при редактировании подпоследовательности несколько раз всегда существует оптимальная последовательность операций одного из двух видов:*Переставить местами соседние символы, затем вставить некоторое количество символов между ними;*Удалить некоторое количество символов, а затем переставить местами символы, ставшие соседними.

Тогда если символ <tex>replaceCost = \begin{cases}S[i]</tex> встречался в <tex>T[1]..T[j]</tex> на позиции <tex>j'</tex>, & а символ <tex>T[j]</tex> встречался в <tex>S[1]..S[i] \neq </tex> на позиции <tex>i'</tex>; то <tex>T[1]..T[j]</tex> может быть получена из <tex>S[1]..S[i]</tex> удалением символов <tex>S[i' + 1]..S[i - 1]</tex>, \\ 0, & транспозицией ставших соседними <tex>S[i']</tex> и <tex>S[i] = </tex> и вставкой символов <tex>T[j' + 1]..T[j- 1]; </tex>. Суммарно на это будет затрачено <tex>D(i', j') + (i - i' - 1) \cdot deleteCost + transposeCost + (j - j' - 1) \end{cases}cdot insertCost</tex> операций, что описано в <tex>(*)</tex>. Поэтому мы выбирали оптимальную последовательность операций, рассмотрев случай с транспозицией и без неё.

Сложность алгоритма: <tex>transpositionCost = O\beginleft (M \cdot N \cdot \max{cases(M, N)}1, & S[i] = T[j - 1] \wedge S[i - 1] = T[j], right )</tex>. Затраты памяти: <tex>O\left (M \cdot N \ right)</tex>. Однако скорость работы алгоритма может быть улучшена до <tex>O\infty, & left (M \textnormal{иначе. }cdot N \end{cases}right)</tex>. Псевдокод алгоритма:

Псевдокод алгоритма: '''int''' DamerauLevenshteinDistance(S: '''char''' S[1..mM], '''char, T: ''' Tchar[1..nN]'''; deleteCost, insertCost, replaceCost, transposeCost: '''int'''): ''<font color=green>// Обработка крайних случаев</font>'' '''declareif''' (S == "") '''intif''' d[0..m, 0..n](T == "") '''declarereturn''' 0 '''intelse''' i, j, cost '''return'// База динамики''N '''forelse''' i '''fromif''' 0 (T == "") '''toreturn''' mM d D: '''int[0..M + 1][i, 0..N + 1] ''' ''<font color= igreen>// Динамика</font>'' INF = (M + N) * max(deleteCost, insertCost, replaceCost, transposeCost) ''<font color=green>// Большая константа</font>'' 'for'<font color=green>// База индукции</font>'' j D[0][0] = INF '''fromfor''' 1 i = 0 '''to''' тM D[i + 1][1] = i * deleteCost d D[i + 1][0, j] = jINF '''for''' i j = 0 '''fromto''' N D[1][j + 1] = j * insertCost D[0][j + 1 ] = INF lastPosition: '''toint[0..количество различных символов в S и T]''' m ''<font color=green>//для каждого элемента C алфавита задано значение lastPosition[C]</font>'for' '' j 'foreach''from'('' 1 'char''to'Letter '' n 'in'// Стоимость замены''(S + T)) lastPosition[Letter] = 0 '''iffor''' S[i] == T[j] 1 '''thento''' costChange M last = 0 '''elsefor''' costChange j = 1'''to''' N i' = lastPosition[T[j]] j' = last '''if''' S[i] == T[j - ] D[i + 1] и S[i - j + 1] = TD[i][j] '''then''' costTransposition last = 1j '''else''' costTransposition = inf ''// значение константы inf очень велико'' ''// costTransposition = inf, то использовать'' ''// транспозицию заведомо невыгодно'' dD[i, + 1][j+ 1] = minimummin( dD[i][j] + replaceCost, D[i-+ 1][j] + insertCost, D[i][j + 1] + 1, ''// удаление''deleteCost) d D[i , + 1][j-+ 1] = min(D[i + 1] [j + 1], D[i'][j'// вставка'] + (i - i' d[i-1, ) <tex>\cdot</tex> deleteCost + transposeCost + (j- j' -1] + costChange '') <tex>\cdot<// замена''tex> insertCost) d lastPosition[S[i-2, j-2] + costTransposition ''// транспозиция''] = i ) '''return''' dD[m, nM][N]

*[[Задача о редакционном расстояниинаибольшей общей подпоследовательности]]*[[Задача о выводе в контекстно-свободной грамматике, алгоритм ЛевенштейнаКока-Янгера-Касами]]*[[Динамическое программирование по профилю]]

==CсылкиИсточники информации==*[http://en.wikipedia.org/wiki/Damerau–Levenshtein_distance статья на английской ВикипедииWikipedia {{---}} Damerau-Levenshtein distance]*[http://ru.wikipedia.org/wiki/Расстояние_Дамерау_—_Левенштейна Википедия {{---}} Расстояние Дамерау-Левенштейна]*[http://habrahabr.ru/blogs/algorithm/114997/ Хабрахабр {{---}} Нечёткий поиск в тексте и словаре (Хабрахабр)]* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 3-е изд. — М.: «Вильямс», 2013. — с. 440. — ISBN 978-5-8459-1794-2