Изменения

Перейти к: навигация, поиск

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

100 байт убрано, 17:56, 16 декабря 2014
Нет описания правки
{{Определение
|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>). Рекуррентное соотношение имеет вид:
j&&;&i = 0,\ j > 0\\
D(i - 1, j - 1)&&;&S[i] = T[j]\\
\min{\left(\begin{array}{llcl}\\&D(i, j - 1) + insertCost\\&D(i - 1, j) + deleteCost\\D(i - 1, j - 1) + replaceCost\\\end{array}\right)}&&;&j > 0,\ i > 0,\ S[i] \ne T[j]\\&D(i - 1, j - 1) + replaceCost\\)
\end{array}\right.
</tex>
Псевдокод алгоритма:
'''int''' DamerauLevenshteinDistance('''char''' S[1..M], T[1..N]: '''char''' T[1..N]) , deleteCost, insertCost, replaceCost, transposeCost: '''int''' ): d[0..M, ][0..N] : '''int''' i, j, cost, deleteCost = 1, insertCost = 1, replaceCost = 1, transposeCost = 1 ''<font color=green>// База динамики</font>'' '''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 ''<font color=green>// Стоимость замены</font>'' '''if''' S[i] == T[j] '''then''' replaceCost d[i][j] = 0d[i - 1][j - 1] '''else''' replaceCost d[i][j] = d[i - 1][j - 1] + replaceCost d[i, ][j] = minimummin( d[i - 1, ][j ] + deleteCost, ''<font color=green>// удалениезамена</font>'' d[i , j - 1][j ] + insertCostdeleteCost, ''<font color=green>// вставкаудаление</font>'' d[i - 1, ][j - 1] + replaceCost insertCost, ''<font color=green>// заменавставка</font>'' ) '''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] + transposeCost ''<font color=green>// транспозиция</font>'' ) '''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>S =</tex> <tex>\mathtt{DLD}('CA'</tex> и <tex>T =</tex> <tex>,\ 'ABCAC'</tex>. Расстояние Дамерау )\ + \mathtt{{---DLD}} Левенштейна между строками равно 2 (<tex>CA \rightarrow 'AC ',\rightarrow 'ABC</tex>'), однако функция приведённая выше возвратит 3. Дело в том, что использование этого упрощённого алгоритма накладывает ограничение: любая подстрока может быть редактирована не более одного раза. Поэтому переход <tex>AC \rightarrow ABC</tex> невозможен, и последовательность действий такая: ngeqslant \mathtt{DLD}(<tex>'CA ',\rightarrow A \rightarrow AB \rightarrow 'ABC')</tex>).
Условие многих практических задач не предполагает многократного редактирования подстрок, поэтому часто достаточно упрощённого алгоритма. Ниже представлен более сложный алгоритм, который корректно решает задачу поиска расстояния Дамерау {{---}} Левенштейна.
==Корректный алгоритм==
В интересах краткости положим <tex>insertCost = deleteCost = replaceCost = transposeCost = 1</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> соответственно. Будем заполнять матрицу следующим образом, используя рекуррентное соотношение, описанное ниже:  '''for''' i '''from''' 0 '''to''' M '''for''' j '''from''' 0 '''to''' N вычислить D(i + 1, j + 1); '''return''' D(m + 1, n + 1);
Для учёта транспозиции потребуется хранение следующей информации. Инвариант:
<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 + 1 transposeCost + (j - j' - 1)\cdot insertCost)}</tex><tex>(*)</tex>
, где
j&&;&i = 0,\ j > 0\\
D(i - 1, j - 1)&&;&S[i] = T[j]\\
\min{\left(\begin{array}{llcl}\\&D(i, j - 1) + insertCost\\D(i - 1, j) + deleteCost\\&D(i - 1, j- 1) + 1replaceCost\\\end{array}\right)}&&;&j > 0,\ i > 0,\ S[i] \ne T[j]\\&D(i - 1, j - 1) + 1\\)
\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 + 1 transposeCost + (j - j' - 1)\cdot insertCost</tex> операций, что описано в <tex>(*)</tex>. Поэтому мы выбирали оптимальную последовательность операций, рассматрев рассмотрев случай с транспозицией и без неё. Корректный алгоритм Дамерау-Левенштейна будет являться метрикой: <tex>\mathtt{DLD}(S,\ V)\ + \mathtt{DLD}(V,\ T) \geqslant \mathtt{DLD}(S,\ T)</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('''char''' S[1..M], T[1..N]: '''char''' T[1..N]), deleteCost, insertCost, replaceCost, transposeCost: '''int'''): ''<font color=green>// Обработка крайних случаев</font>'' '''if''' (S == "") '''then''' '''if''' (T == "") '''then''' '''return''' 0 '''else''' '''return''' N '''else''' '''if''' (T == "") '''then''' '''return''' M '''int''' D[0..M + 1, ][0..N + 1] : '''int''' ''<font color=green>// Динамика</font>'' INF = M + N: '''int''' INF = M + N ''<font color=green>// Большая константа</font>''
''<font color=green>// База индукции</font>'' D[0, ][0] = INF; '''for''' i '''from''' = 0 '''to''' M D[i + 1, ][1] = i D[i + 1, ][0] = INF '''for''' j '''from''' = 0 '''to''' N D[1, ][j + 1] = j D[0, ][j + 1] = INF
'''int''' lastPosition[0..количество различных символов в S и T]: '''int''' ''<font color=green>//для каждого элемента C алфавита задано значение lastPosition[C]</font>''
'''foreach''' ('''char''' Letter '''in''' (S + T)) '''if''' Letter не содержится в lastPosition добавить Letter в lastPosition lastPosition[Letter] = 0
'''for''' i '''from''' = 1 '''to''' M last = 0: '''int''' last = 0 '''for''' j '''from''' = 1 '''to''' N '''int''' i' = lastPosition[T[j]] : '''int''' j' = last: '''int''' '''if''' S[i] == T[j] '''then''' D[i + 1, ][j + 1] = D[i, ][j] last = j '''else''' D[i + 1, ][j + 1] = minimum(D[i, ][j]+ replaceCost, D[i + 1, ][j]+ insertCost, D[i, ][j + 1]+ deleteCost) + 1 D[i + 1, ][j + 1] = minimum(D[i + 1, ][j + 1], D[i', ][j'] + (i - i' - 1) <tex>\cdot</tex> deleteCost + 1 transposeCost + (j - j' - 1)<tex>\cdot</tex> insertCost) lastPosition[S[i]] = i
'''return''' D[M + 1, ][N + 1]
==См. также==
*[[Задача о редакционном расстояниинаибольшей общей подпоследовательности]]*[[Задача о выводе в контекстно-свободной грамматике, алгоритм ВагнераКока-Янгера-ФишераКасами]]*[[Динамическое программирование по профилю]]
==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
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Динамическое программирование]]
63
правки

Навигация