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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Заготовка)
(нет различий)

Версия 08:47, 2 декабря 2011

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

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

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


Практическое применение

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

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

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

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

Оценка сложности

См. также

Cсылки