74
правки
Изменения
м
Заготовка
{{Определение
|definition=
'''Расстояние Дамерау {{---}} Левенштейна''' между двумя строками, состоящими из конечного числа символов {{---}} это минимальное число операций вставки, удаления, замены одного символа и транспозиции двух соседних символов, необходимых для перевода одной строки в другую.}}
Является модификацией [[Задача о редакционном расстоянии, алгоритм Левенштейна| расстояния Левенштейна]], отличается от него добавлением операции перестановки.
Расстояние Дамерау {{---}} Левенштейна является метрикой.
==Практическое применение==
==Описание алгоритма==
Метод динамического программирования позволяет найти расстояние Дамерау {{---}} Левенштейна между двумя строками <tex>S</tex> и <tex>T</tex>, длины которых равны соответственно <tex>m</tex> и <tex>n</tex>, затратив сравнительно небольшое количество вычислительных ресурсов.
Простая модификация алгоритма поиска [[Задача о редакционном расстоянии, алгоритм Левенштейна| расстояния Левенштейна]] не приводит к цели:
Рассмотрим более сложный алгоритм, который корректно решает задачу поиска расстояния Дамерау {{---}} Левенштейна.
==Оценка сложности==
==См. также==
*[[Задача о редакционном расстоянии, алгоритм Левенштейна]]
==Cсылки==
*[http://en.wikipedia.org/wiki/Damerau–Levenshtein_distance статья на английской Википедии]
*[http://habrahabr.ru/blogs/algorithm/114997/ Нечёткий поиск в тексте и словаре (Хабрахабр)]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Динамическое программирование]]
|definition=
'''Расстояние Дамерау {{---}} Левенштейна''' между двумя строками, состоящими из конечного числа символов {{---}} это минимальное число операций вставки, удаления, замены одного символа и транспозиции двух соседних символов, необходимых для перевода одной строки в другую.}}
Является модификацией [[Задача о редакционном расстоянии, алгоритм Левенштейна| расстояния Левенштейна]], отличается от него добавлением операции перестановки.
Расстояние Дамерау {{---}} Левенштейна является метрикой.
==Практическое применение==
==Описание алгоритма==
Метод динамического программирования позволяет найти расстояние Дамерау {{---}} Левенштейна между двумя строками <tex>S</tex> и <tex>T</tex>, длины которых равны соответственно <tex>m</tex> и <tex>n</tex>, затратив сравнительно небольшое количество вычислительных ресурсов.
Простая модификация алгоритма поиска [[Задача о редакционном расстоянии, алгоритм Левенштейна| расстояния Левенштейна]] не приводит к цели:
Рассмотрим более сложный алгоритм, который корректно решает задачу поиска расстояния Дамерау {{---}} Левенштейна.
==Оценка сложности==
==См. также==
*[[Задача о редакционном расстоянии, алгоритм Левенштейна]]
==Cсылки==
*[http://en.wikipedia.org/wiki/Damerau–Levenshtein_distance статья на английской Википедии]
*[http://habrahabr.ru/blogs/algorithm/114997/ Нечёткий поиск в тексте и словаре (Хабрахабр)]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Динамическое программирование]]
