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

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

Впервые такой способ вычисления дистанции (меры различия) между двумя двоичными последовательностями предложил советский ученый-математик В.И. Левенштейн (род. 1935). Впоследствииспособ распространился на последовательностипроизвольного алфавита.

Расстояние Левенштейна активно применяется для исправления ошибок в поисковых системах, в текстовых редакторах, а также в биоинформатике.

Пусть и – две символьные строки, тогда для вычисления дистанции Левенштейна между ними может быть использовано следующеерекуррентное соотношение:

В предыдущем выражении используются символы и Разъясним их смысл:

–количество символов в заданной строке. Например,

–заданная строка без последнего символа. Например,

– последний символ заданной строки. Например,

Поясним принцип применения этого рекуррентного соотношения на следующем примере.

Пусть необходимо вычислить Тогда имеем следующую последовательность шагов:

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 раза, а это в каждом случае приводит к повторному вычислению дистанций между «с» и «спор», «со» и «спо», «с» и «спо» и т. д.

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