Задача о расстоянии Дамерау-Левенштейна

2020-11-03T14:54:55Z

193.34.232.21: /* Корректный алгоритм */

{{Определение
|definition=
'''Расстояние Дамерау-Левенштейна''' (англ. ''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]'''

''// База динамики''
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
''// Стоимость замены''
'''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], ''// замена''
d[i - 1][j ] + deleteCost, ''// удаление''
d[i ][j - 1] + insertCost ''// вставка''
)
'''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 ''// транспозиция''
)
'''return''' d[M][N]

Контрпример: <tex>S =</tex> <tex>'CA'</tex> и <tex>T =</tex> <tex>'ABC'</tex>. Расстояние Дамерау-Левенштейна между строками равно <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>.

Условие многих практических задач не предполагает многократного редактирования подстрок, поэтому часто достаточно упрощённого алгоритма. Ниже представлен более сложный алгоритм, который корректно решает задачу поиска расстояния Дамерау-Левенштейна.

==Корректный алгоритм==
В основу алгоритма положена идея [[Динамическое программирование#.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][0..N + 1]</tex>, где <tex>D[i + 1][j + 1]</tex> {{---}} расстояние Дамерау-Левенштейна между префиксами строк <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>i' = \mathtt{lastPosition}[T[j]],\ j' = \mathtt{last}</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>
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>(*)</tex>, смысл которой {{---}} сравнение стоимости перехода без использования транспозиции <tex>(A)</tex> со стоимостью перехода, включающего в число операций транспозицию; остальные формулы обосновываются так же, как и в доказательстве [[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера|алгоритма Вагнера-Фишера]]. Но действительно, при редактировании подпоследовательности несколько раз всегда существует оптимальная последовательность операций одного из двух видов:
*Переставить местами соседние символы, затем вставить некоторое количество символов между ними;
*Удалить некоторое количество символов, а затем переставить местами символы, ставшие соседними.

Тогда если символ <tex>S[i]</tex> встречался в <tex>T[1]..T[j]</tex> на позиции <tex>j'</tex>, а символ <tex>T[j]</tex> встречался в <tex>S[1]..S[i]</tex> на позиции <tex>i'</tex>; то <tex>T[1]..T[j]</tex> может быть получена из <tex>S[1]..S[i]</tex> удалением символов <tex>S[i' + 1]..S[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' - 1) \cdot insertCost</tex> операций, что описано в <tex>(*)</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>.

Псевдокод алгоритма:

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

''// База индукции''
D[0][0] = INF
'''for''' i = 0 '''to''' M
D[i + 1][1] = i * deleteCost
D[i + 1][0] = INF
'''for''' j = 0 '''to''' N
D[1][j + 1] = j * insertCost
D[0][j + 1] = INF

lastPosition: '''int[0..количество различных символов в S и T]'''
''//для каждого элемента C алфавита задано значение lastPosition[C]''

'''foreach''' ('''char''' Letter '''in''' (S + T))
lastPosition[Letter] = 0

'''for''' i = 1 '''to''' M
last = 0
'''for''' j = 1 '''to''' N
i' = lastPosition[T[j]]
j' = last
'''if''' S[i] == T[j]
D[i + 1][j + 1] = D[i][j]
last = j
'''else'''
D[i + 1][j + 1] = min(D[i][j] + replaceCost, D[i + 1][j] + insertCost, D[i][j + 1] + deleteCost)
D[i + 1][j + 1] = min(D[i + 1][j + 1], D[i'][j'] + (i - i' - 1) <tex>\cdot</tex> deleteCost + transposeCost + (j - j' - 1) <tex>\cdot</tex> insertCost)
lastPosition[S[i]] = i

'''return''' D[M][N]

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

==Источники информации==
*[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

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Динамическое программирование]]

Викиконспекты - Вклад участника [ru]

Задача о расстоянии Дамерау-Левенштейна