Расстояние Левенштейна (Levenshtein’s distance)

Синонимы: Редакционное расстояние, Дистанция редактирования

Разделы: Метрики

Loginom: Калькулятор (обработчик)

Расстояние Левенштейна определяет, сколько раз необходимо добавить/удалить/заменить символ, чтобы одну строку превратить в другую.

Впервые задачу упомянул в 1965 году советский математик Владимир Иосифович Левенштейн при изучении последовательностей. Впоследствии более общую задачу для произвольного алфавита связали с его именем. Позже большой вклад в изучение вопроса внес Дэн Гасфилд.

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

Например, необходимо преобразовать слово «Текст» в слово «Торт», используя операции удаления, добавления и замены:

1. Текст — Токст (замена)
2. Токст — Тост (удаление)
3. Тост — Торт (замена)

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