Анонс #200. Расстояние Дамерау — Левенштейна

Справка

Дана текстовая строка. С ней можно выполнять следующие операции:

• Заменить один символ строки на другой символ.
• Удалить один произвольный символ.
• Вставить произвольный символ в произвольное место строки.
• Переставить два соседних символа местами. При этом между переставленными символами нельзя вставлять другие символы.

Например, дана строка "СОК" 

• при помощи 1й операции из исходной строки можно получить строку "СУК";
• при помощи 2й операции — строку "ОК";
• при помощи 3й операции — строку "СТОК";
• при помощи четвертой операции — строку "ОСК".

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

Задача

Попробуйте реализовать алгоритм определения расстояния Дамерау-Левенштейна для двух заданных строк.

Входные данные: str1, str2 - строки, длина которых не превосходит 1000 символов.

Вывод: расстояние Дамерау-Левенштейна для исходных строк.

Пример: 

str1 = "XABCDE";

str2 = "ACBYDF"

Output = 4

Пояснение к примеру:

Вторая строка может быть получена из первой при помощи четырех операций редактирования: удаления буквы X, перестановки букв B и C, вставки буквы Y и замены буквы E на букву F.

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

Расстояние Дамерау-Левенштейна является мерой "схожести" двух строк. Алгоритм его поиска находит применение в реализации нечёткого поиска, а также в биоинформатике (сравнение ДНК). 

Дамерау показал, что 80% человеческих ошибок при наборе текстов составляют перестановки соседних символов, пропуск символа, добавление нового символа, и ошибка в символе. Поэтому метрика Дамерау-Левенштейна часто используется в редакторских программах для проверки правописания.

Дополнительный материал

Алгоритм вычисления расстояния Дамерау-Левенштейна между 2мя строками тесно связан с алгоритмом нахождения наибольшей общей подпоследовательности.

• Статья "Наибольшая общая подпоследовательность"