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

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

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

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

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

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

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

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

results matching ""

    No results matching ""