Изменения

'''Расстояние Дамерау {{---}} Левенштейна''' (англ. ''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>. Псевдокод алгоритма:

Контрпример: <tex>S =</tex> <tex>'CA'</tex> и <tex>T =Практическое применение==</tex> <tex>'ABC'</tex>. Расстояние Дамерау {{---}} Левенштейнамежду строками равно <tex>2\ (CA \rightarrow AC \rightarrow ABC)</tex>, как и метрика [http:однако функция приведённая выше возвратит <tex>3<//rutex>.wikipediaДело в том, что использование этого упрощённого алгоритма накладывает ограничение: любая подстрока может быть редактирована не более одного раза.orgПоэтому переход <tex>AC \rightarrow ABC</wikitex> невозможен, и последовательность действий такая: <tex>(CA \rightarrow A \rightarrow AB \rightarrow ABC)</Левенштейн,_Владимир,_Иосифович tex>. Упрощенный алгоритм Дамерау-Левенштейна], не является мерой "схожести" двух строк. Алгоритм его поиска находит применение в реализации нечёткого поискаметрикой, а также в биоинформатике так как не выполняется правило треугольника: <tex>\mathtt{DLD}(сравнение ДНК'CA',\ 'AC')+ \mathtt{DLD}('AC', несмотря на то\ 'ABC') \ngeqslant \mathtt{DLD}('CA',\ 'ABC')</tex>. Условие многих практических задач не предполагает многократного редактирования подстрок, что изначально поэтому часто достаточно упрощённого алгоритма. Ниже представлен более сложный алгоритм разрабатывался для сравнения текстов, набранных человеком (который корректно решает задачу поиска расстояния Дамерау-Левенштейна. ==Корректный алгоритм==В основу алгоритма положена идея [[Динамическое программирование#.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>D[0..M + 1][http://en0.wikipedia.orgN + 1]</wikitex>, где <tex>D[i + 1][j + 1]</Frederick_J._Damerau tex> {{---}} расстояние Дамерау] показал, что 80% человеческих ошибок при наборе текстов составляют перестановки соседних символов, пропуск символа, добавление нового символа-Левенштейна между префиксами строк <tex>S</tex> и <tex>T</tex>, длины префиксов {{---}} <tex>i</tex> и ошибка в символе<tex>j</tex> соответственно. Для учёта транспозиции потребуется хранение следующей информации. Поэтому метрика Дамерау Инвариант: <tex>\mathtt{lastPosition}[x]</tex> {{---}} Левенштейна часто используется индекс последнего вхождения <tex>x</tex> в редакторских программах для проверки правописания). <tex>S</tex> <tex>\mathtt{last}</tex> {{---}} на <tex>i</tex>-й итерации внешнего цикла индекс последнего символа <tex>T: T[\mathtt{last}] = S[i]</tex>

==Описание алгоритма==Метод динамического программирования позволяет найти расстояние Дамерау {{---}} Левенштейна между двумя строками <tex>S</tex> и <tex>T</tex>, длины которых равны соответственно <tex>m</tex> и <tex>n</tex>, затратив сравнительно небольшое количество вычислительных ресурсов. Сложность алгоритмаТогда если на очередной итерации внутреннего цикла положить: <tex>Oi' = \left (m \cdot n \cdot \max(mmathtt{lastPosition}[T[j]], n) \right )</tex>. Затраты памяти: <tex>Oj' = \left (M \cdot N \right)mathtt{last}</tex>. Однако скорость работы алгоритма может быть улучшена до <tex>O\left (M \cdot N \right)</tex>., то

<tex>D(i, j) ==Наивный алгоритм==Простая модификация алгоритма поиска [[Задача о редакционном расстоянии\min{(A, алгоритм Левенштейна| расстояния Левенштейна]] не приводит к цели. Рассмотрим псевдокод алгоритмаD(i', отличающегося от алгоритма поиска расстояния Левенштейна одной проверкой:j') + (i - i' - 1) \cdot deleteCost + transposeCost + (j - j' - 1) \cdot insertCost)}</tex> <tex>(*)</tex>

'''int''' DamerauLevenshteinDistance('''char''' S[1..m], '''char''' T[1..n]) '''declare''' '''int''' d[0..m, 0..n] '''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[i-1, j ] + 1, ''// удаление'' d[i , j-1] + 1, ''// вставка'' d[i-1, j-1] + cost ''// замена'' ) '''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] + costTransposition ''// транспозиция'' ) '''return''' d[m, n]где

Контрпример: <tex>S A = \left\{\begin{array}{llcl}0&;\ i = 0,\ j = 0\\i * deleteCost&;\ j =</tex0,\ i > <tex>'CA'</tex> и <tex0\\j * insertCost&;\ i = 0,\ j >0\\D(i - 1, j - 1)&;\ S[i] = T =</tex> <tex>'ABC'</tex>. Расстояние Дамерау [j]\\\min{(}\\\begin{---array}{llcl} Левенштейна между строками равно 2 &D(<tex>CA i, j - 1) + insertCost\rightarrow AC \rightarrow ABC</tex>&D(i - 1, j)+ deleteCost&&\\&D(i - 1, однако функция приведённая выше возвратит 3. Дело в томj - 1) + replaceCost\\\end{array}&;\ j > 0, что использование этого упрощённого алгоритма накладывает ограничение: любая подстрока может быть редактирована не более одного раза. Поэтому переход <tex>AC \rightarrow ABC</texi > невозможен0, и последовательность действий такая: (<tex>CA \rightarrow A S[i] \ne T[j]\\)\rightarrow AB end{array}\rightarrow ABCright.</tex>).

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

==Алгоритм==В основу алгоритма положена идея динамического программирования по префиксуТогда если символ <tex>S[i]</tex> встречался в <tex>T[1]. будем хранить матрицу .T[j]</tex> на позиции <tex>Dj'</tex>, а символ <tex>T[j]</tex> встречался в <tex>S[01]..m + S[i]</tex> на позиции <tex>i'</tex>; то <tex>T[1]..T[j]</tex> может быть получена из <tex>S[01]..n + 1S[i]</tex>, где удалением символов <tex>DS[i ' + 1]..S[j + i - 1]</tex> {{---}} расстояние Дамерау {{---}} Левенштейна между префиксами строк , транспозицией ставших соседними <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' -}} <tex>i1) \cdot insertCost</tex> и операций, что описано в <tex>j(*)</tex> соответственно. Поэтому мы выбирали оптимальную последовательность операций, рассмотрев случай с транспозицией и без неё.

'''int''' DamerauLevenshteinDistance(S: '''char''' S[1..mM], '''char, T: ''' Tchar[1..nN])'''; deleteCost, insertCost, replaceCost, transposeCost: '''int'''): ''<font color=green>// Обработка крайних случаев</font>'' '''if''' (S == "") '''then''' '''if''' (T == "") '''then''' '''return''' 0 '''else''' '''return''' nN '''else''' '''if''' (T == "") '''then''' '''return''' mM '''declare''' D: '''int''' D[0..m M + 1, ][0..n N + 1] ''' ''<font color=green>// Динамика</font>'' '''declare''' '''int''' INF = m (M + n N) * max(deleteCost, insertCost, replaceCost, transposeCost) ''<font color=green>// Большая константа</font>''

''<font color=green>// База индукции</font>'' D[0, ][0] = INF; '''for''' i '''from''' = 0 '''to''' mM D[i + 1, ][1] = i* deleteCost D[i + 1, ][0] = INF '''for''' j '''from''' = 0 '''to''' nN D[1, ][j + 1] = j* insertCost D[0, ][j + 1] = INF

lastPosition: '''declare''' sdint[0..количество различных символов в S и T] {{---}} отсортированный алфавит''' ''<font color=green>//для каждого элемента C алфавита задано значение sdlastPosition[C]</font>''

'''foreach''' ('''char''' Letter '''in''' (S + T)) '''if''' Letter не содержится в sd добавить Letter в sd sd lastPosition[Letter] = 0

'''for''' i '''from''' = 1 '''to''' mM '''declare''' '''int''' DB last = 0 '''for''' j '''from''' = 1 '''to''' nN i'''declare''' '''int''' i1 = sdlastPosition[targetT[j - 1]] '''declare''' '''int' j'' j1 = DBlast '''if''' sourceS[i - 1] == targetT[j - 1] '''then''' D[i + 1, ][j + 1] = D[i, ][j] DB last = j '''else''' D[i + 1, ][j + 1] = minimummin(D[i, ][j]+ replaceCost, D[i + 1, ][j]+ insertCost, D[i, ][j + 1]+ deleteCost) + 1 D[i + 1, ][j + 1] = minimummin(D[i + 1, ][j + 1], D[i1, j1i'][j'] + (i - i1 i' - 1) <tex>\cdot</tex> deleteCost + 1 transposeCost + (j - j1 j' - 1)<tex>\cdot</tex> insertCost) sd lastPosition[S[i - 1]] = i

'''return''' D[m + 1, n + 1M][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