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

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

Пусть u и v – две строки над некоторым алфавитом.

Расстоянием Левенштейна d(u, v) между строками u и v называется наименьшее количество операций редактирования, необходимое, чтобы перевести u в v. Из соображений обратимости операций редактирования, имеем d(u, v) = d(v, u).

Метод разработан в 1965 году советским математиком Владимиром Иосифовичем Левенштейном и назван его именем.