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