Изменения

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

==Практическое применение==Расстояние Дамерау {{---}} Левенштейна , как и метрика Левенштейна, является метрикоймерой "схожести" двух строк. Алгоритм его поиска находит применение в реализации нечёткого поиска, а также в биоинформатике (Предполагаемсравнение ДНК), несмотря на то, что цены операций таковыизначально алгоритм разрабатывался для сравнения текстов, набранных человеком (Дамерау показал, что выполнено правило треугольника: если две последовательные операции можно заменить одной80% человеческих ошибок при наборе текстов составляют перестановки соседних символов, то это не ухудшает общую ценупропуск символа, добавление нового символа, и ошибка в символе.Поэтому метрика Дамерау-Левенштейна часто используется в редакторских программах для проверки правописания).  ==Упрощённый алгоритм==Не решает задачу корректно, но бывает полезен на практике.

==Практическое применение==Расстояние Дамерау {{---}} Рассмотрим алгоритм, отличающийся от алгоритма поиска расстояния Левенштейна, как и метрика [http://ru.wikipedia.orgодной проверкой (храним матрицу <tex>D</wiki/Левенштейнtex>,_Владимиргде <tex>D(i,_Иосифович Левенштейна], является мерой "схожести" двух j)</tex> — расстояние между префиксами строк. Алгоритм его поиска находит применение в реализации нечёткого поиска, а также в биоинформатике (сравнение ДНК), несмотря на то, что изначально алгоритм разрабатывался для сравнения текстов, набранных человеком ([http:первыми <tex>i</tex> символами строки <tex>S</en.wikipedia.orgtex> и первыми <tex>j</wikitex> символами строки <tex>T</Frederick_J._Damerau Дамерау] показал, что 80% человеческих ошибок при наборе текстов составляют перестановки соседних символов, пропуск символа, добавление нового символа, и ошибка в символе. Поэтому метрика Дамерау {{---}} Левенштейна часто используется в редакторских программах для проверки правописанияtex>). Рекуррентное соотношение имеет вид:

==Упрощённый алгоритм==Рассмотрим алгоритм, отличающийся от алгоритма поиска расстояния Левенштейна одной проверкой (храним матрицу <tex>D</tex>, где Ответ на задачу {{---}} <tex>D(iM, jN)</tex> — расстояние между префиксами строк: первыми i символами строки <tex>S</tex> и первыми j символами строки <tex>T</tex>). Рекуррентное соотношение имеет вид:, где

<tex> D(Si, Tj) = \left\{\begin{array}{lllc}\min{(A, D(Mi - 2,Nj - 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]\\\rmmin{min(}(\\\begin{array}{llcl}

&D(i - 1, j) + deleteCost&;&j > 0,\ i > 0,\ S[i] \ne T[j]\\

Таким образом для получения ответа необходимо заполнить матрицу <tex>D</tex>, пользуясь рекуррентным соотношением.Сложность алгоритма: <tex>O\left (m M \cdot n N \right )</tex>. Затраты памяти: <tex>O\left (M \cdot N \right)</tex>.

'''int''' DamerauLevenshteinDistance(S: '''char''' S[1..mM], '''char, T: ''' Tchar[1..nN]) '''declare; deleteCost, insertCost, replaceCost, transposeCost: ''' int'''int): d: ''' dint[0..m, M][0..nN] '''declare''' '''int''' i, j, cost ''<font color=green>// База динамики</font>'' '''for''' i '''from''' 0 '''to''' m d[i, 0] = i '''for''' j '''from''' 1 '''to''' n d[0, j] = j0 '''for''' i '''from''' = 1 '''to''' mM '''for''' j '''from''' 1 '''to''' n ''// Стоимость замены'' '''if''' S d[i] == T[j] '''then''' cost = 0 '''else''' cost = 1 d[i, j] = minimum( d[i-1, j ] + 1, ''// удаление'' d[i , j-10] + 1, ''// вставка''deleteCost d[i-1, j-1] + cost ''// замена'' ) '''if'''(i > 1 '''andfor''' j > = 1 '''andto''' S[i] == T[j-1] N '''and''' S d[i-10] == T[j]) '''then''' d[i, j] = minimum( d[i, j0], d[i-2, j-21] + costTransposition ''// транспозиция'' )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, nM][N]

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

Условие многих практических задач Упрощенный алгоритм Дамерау-Левенштейна не предполагает многократного редактирования подстрокявляется метрикой, поэтому часто достаточно упрощённого алгоритма. Ниже представлен более сложный алгоритмтак как не выполняется правило треугольника: <tex>\mathtt{DLD}('CA', который корректно решает задачу поиска расстояния Дамерау \ 'AC') + \mathtt{DLD}('AC',\ 'ABC') \ngeqslant \mathtt{---DLD}} Левенштейна('CA',\ '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>который корректно решает задачу поиска расстояния Дамерау-Левенштейна.

==Корректный алгоритм==В основу алгоритма положена идея [[Динамическое программирование#.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 M + 1][0..n N + 1]</tex>, где <tex>D[i + 1][j + 1]</tex> {{---}} расстояние Дамерау {{---}} Левенштейна между префиксами строк <tex>S</tex> и <tex>T</tex>, длины префиксов {{---}} <tex>i</tex> и <tex>j</tex> соответственно. Будем заполнять матрицу следующим образом, используя рекуррентное соотношение, описанное ниже:  '''for''' i '''from''' 0 '''to''' m '''for''' j '''from''' 0 '''to''' n вычислить D(i, j); '''return''' D(m, n);

<tex>sd\mathtt{lastPosition}[x]</tex> {{---}} индекс последнего вхождения <tex>x</tex> в <tex>S</tex>

<tex>DB\mathtt{last}</tex> {{---}} на <tex>i</tex>-й итерации внешнего цикла индекс последнего символа <tex>T: T[DB\mathtt{last}] = S[i]</tex>

Тогда если на очередной итерации внутреннего цикла положить: <tex>i1 i' = sd\mathtt{lastPosition}[T[j]],\ j1 j' = DB\mathtt{last}</tex>, то

<tex>D(i, j) = \min{(A, D(i1i', j1j') + (i - i1 i' - 1) \cdot deleteCost + 1 transposeCost + (j - j1 j' - 1)\cdot insertCost) }</tex> <tex>(*)</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]\\\rmmin{min(}(\\\begin{array}{llcl}

&D(i - 1, j) + deleteCost&;&j > 0,\ i > 0,\ S[i] \ne T[j]\\

Доказательства требует лишь утверждение формула <tex>(*)</tex>, так как смысл которой {{---}} сравнение стоимости перехода без использования транспозиции <tex>(A)</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[T[j]] '' j'declare''' '''int''' j1 = DBlast '''if''' S[i] == T[j] '''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]] = 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