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

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

Подробнее: «kitten» → «sitting» имеет расстояние 3 (k→s, e→i, добавить g). Оно лежит в основе проверки орфографии, «вы имели в виду …?» и нечёткого поиска.

Подробности

• Метод: Динамическое программирование с таблицей d[i][j] для расстояния между первыми i символами A и первыми j символами B.
• Рекуррентное соотношение: d[i][j] = min(d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1] + (a[i]≠b[j])).
• Затраты: Время O(m·n), при хранении лишь двух строк память O(min(m, n)).
• Варианты: Дамерау — Левенштейн считает и перестановку соседних символов. Расстояние Хэмминга применимо только к словам равной длины.
• На практике: Для больших словарей используют индексы вроде BK-деревьев или n-грамм, а не сравнивают каждое слово.

См. также: алгоритмы поиска текста