Слишком сложно? Тогда запросите консультацию специалиста!
Наша компания занимается тем, что помогает студентам выполнять различные учебные работы на заказ. Вы можете ознакомиться с перечнем выполняемых работ, а так же с их стоимостью на странице с ценами.
Дистанция Левенштейна (расстояние Левенштейна, редакционное расстояние, дистанция редактирования) определяется между двумя строками и равна минимальному количеству операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую.
Впервые такой способ вычисления дистанции (меры различия) между двумя двоичными последовательностями предложил советский ученый-математик В. И. Левенштейн (род. 1935). Впоследствии способ распространился на последовательности произвольного алфавита.
Расстояние Левенштейна активно применяется для исправления ошибок в поисковых системах, в текстовых редакторах, а также в биоинформатике.
Пусть 
и 
– две символьные строки, тогда для вычисления дистанции Левенштейна 
между ними может быть использовано следующее рекуррентное соотношение:
В предыдущем выражении используются символы 
и 
Разъясним их смысл:
– количество символов в заданной строке. Например, 
– заданная строка без последнего символа. Например, 
– последний символ заданной строки. Например, 
Поясним принцип применения этого рекуррентного соотношения на следующем примере.
Пусть необходимо вычислить 
Тогда имеем следующую последовательность шагов:
1. 
2. 
3. 
4. 
5. 
6. 
7. 
8. 
9. 
10. 
11. 
12. 
13. 
14. 
15. 
16. 
17. 
18. 
19. 
20. 
21. 
22. 
23. 
24. 
25. 
26. 
27. 
28. 
Шаги вычисления с 1 по 14 соответствуют рекурсивному погружению, а шаги с 15 по 28 – восходящему вычислению. Нетрудно убедиться, что для превращения слова «сор» в слово «спорт» достаточно удалить (или вставить) две буквы.
На рис. 17 и 18 представлена рекурсивная функция levenshtein_r, вычисляющая дистанцию Левенштейна для двух строк, а на рис. 19 и 20 – пример программы, вызывающей эту функцию и результат ее выполнения соответственно.
Рис. 17. Прототип функции levenshtein_r, вычисляющей дистанцию Левенштейна между двумя строками
Рис. 18. Реализация рекурсивной функцииlevenshtein_r
Рис. 19. Пример программы, вызывающей функцию levenshtein_r
Рис. 20. Результат выполнения программы, представленной на рис. 19
Функция levenshtein_rимеет четыре параметра: lx(длина первой строки), x(массив символов размерностью lx, содержащий символы первой строки), ly(длина второй строки), y(массив символов размерностью ly, содержащий символы второй строки). Фунция возвращает дистанцию Левенштейна между двуми заданными строками.
Реализация функции (рис. 17) практически повторяет рекуррентное соотношение, приведенное выше, поэтому не нуждается в дополнительном пояснении.
В программе, приведенной на рис. 18, вызывается функция levenshtein_rдля вычисления дистанции Левенштейна между строками «сор» и «спорт».
Результат выполнения программы (рис. 17) совпадает с результатом, полученным ранее вручную. Следует лишь обратить внимание, что в отличие от ручного просчета при выполнении функции levenshtein_rнекоторыеподзадачи решаются по несколько раз. Например, дистанция между строками «со» и «спор» вычисляется 3 раза, а это в каждом случае приводит к повторному вычислению дистанций между «с» и «спор», «со» и «спо», «с» и «спо» и т. д.
Следует отметить, что в информатике часто используется дистанция Дамерау – Левенштейна, которая является модификацией дистанции Левенштейна и отличается применением еще одной операции преобразования – перестановки соседних символов.
