double arrow

Вычисление дистанции Левенштейна

4

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

Впервые такой способ вычисления дистанции (меры различия) между двумя двоичными последовательностями предложил советский ученый-математик В. И. Левенштейн (род. 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 раза, а это в каждом случае приводит к повторному вычислению дистанций между «с» и «спор», «со» и «спо», «с» и «спо» и т. д.

Следует отметить, что в информатике часто используется дистанция Дамерау – Левенштейна, которая является модификацией дистанции Левенштейна и отличается применением еще одной операции преобразования – перестановки соседних символов.


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  


4

Сейчас читают про: