Расстояние Левенштейна

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

Попробуем посчитать расстояние Левенштейна между словами «карета» и «ракета». 

Чтобы превратить карету в ракету, нужно:

1. поменять первую букву — «к» на «р», после этой операции штраф  равен 1 и  у нас есть слово «какета»
2. поменять третью букву — «р» на «к», после этой операции штраф равен  2 и мы получили нужное слово «ракета».

Расстояние Левенштейна между словами  «карета» и «ракета» равно двум.

Усложняем задачу. У нас есть строка «с крипкол иса» и мы хотим понять, на что она больше похожа, на «скрип колеса», «скрипка леса» или «скрипка лиса». Посчитаем расстояние Левенштейна.

Удалим пробел после «с» → вставим пробел после «п» → удалим пробел после «л» → заменим вторую «и» на «е».
ИТОГО: 4 операции = 4 балла штрафа, т.е. расстояние Левенштейна между «с крипкол иса» и «скрип колеса» равно четырем. 

Удалим пробел после «с» →  вставим пробел после «а» → удалить пробел после «л».
ИТОГО: 3 операции = 3 балла штрафа, т.е. расстояние Левенштейна между «с крипкол иса» в  «скрипка лиса» равно трем.

Вы можете попробовать посчитать расстояние Левенштейна для строк «с крипкол иса» и  «скрипка леса» и убедиться, что оно будет равно четырем. 

Получается, что «с крипкол иса» ближе всего к «скрипка лиса». 

Какие еще бывают Левенштейны?

1. Пословное расстояние Левенштейна.
   При таком подходе за единицу принимается не один символ, а одно слово. Измерим близость между предложениями «Я люблю лингвистику» и «Я люблю компьютерную лингвистику».  Используя пословное расстояние Левенштейна, мы можем превратить первую строку во вторую за одну операцию – вставка слова «компьютерную»,  получив всего 1 балл штрафа,  а не 14 баллов, как было бы в случае посимвольных операций (по одному баллу за вставку каждой буквы в слове «компьютерную» + 2 балла штрафа за вставку пробелов).

2. Взвешенное расстояние Левенштейна.
   Мы можем давать разный штраф за разные операции. Например, решить, что мы очень не любим замены символов и давать за них не 1, а 2 балла штрафа. В этом случае говорят, что операции имеют разный вес.

3. Расстояние Дамерау–Левенштейна.
   В этом случае к добавляется еще одна операция: перестановка соседних символов (транспозиция).