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

Определение:

Расстояние Дамерау — Левенштейна между двумя строками, состоящими из конечного числа символов — это минимальное число операций вставки, удаления, замены одного символа и транспозиции двух соседних символов, необходимых для перевода одной строки в другую.

Является модификацией расстояния Левенштейна, отличается от него добавлением операции перестановки.

Расстояние Дамерау — Левенштейна является метрикой.

Описание алгоритма

Метод динамического программирования позволяет найти расстояние Дамерау — Левенштейна между двумя строками [math]S[/math] и [math]T[/math], длины которых равны соответственно [math]m[/math] и [math]n[/math], затратив сравнительно небольшое количество вычислительных ресурсов.

Простая модификация алгоритма поиска расстояния Левенштейна не приводит к цели:

Рассмотрим более сложный алгоритм, который корректно решает задачу поиска расстояния Дамерау — Левенштейна.

См. также

• Задача о редакционном расстоянии, алгоритм Левенштейна

Cсылки

• статья на английской Википедии
• Нечёткий поиск в тексте и словаре (Хабрахабр)