Відстань Левенштейна

Коротко: Відстань Левенштейна рахує мінімальну кількість вставок, видалень і замін окремих символів, потрібних, щоб перетворити одне слово на інше.

Докладніше: «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-грам, а не порівнюють кожне слово.

Див. також: алгоритми пошуку тексту