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

Матеріал з Вікіпедії — вільної енциклопедії.

Відстань Левенштейна (також функція Левенштейна, алгоритм Левенштейна або відстань редагування) у теорії інформації і комп'ютерній лінгвістиці міра відмінності двох послідовностей символів (рядків). Обчислюється як мінімальна кількість операцій вставки, видалення і заміни, необхідних для перетворення одної послідовності в іншу. Метод розроблений у 1965 році радянським математиком Володимиром Йосиповичем Левенштейном і названий його іменем.

Приклад:

Щоб перетворити слово небо на слово треба необхідно зробити дві заміни та одну вставку, відповідно дистанція Левенштейна становить 3:

небо -> неба (замінюємо о на а)
неба -> реба (замінюємо н на р)
реба -> треба (вставляємо т)

На практиці дистанція Левенштейна використовується для визначення подібності послідовностей символів, наприклад для корекції орфографії або для пошуку дублікатів.

[ред.] Алгоритм

Для розрахунку відстані Левенштейна найчастіше використовують простий алгоритм, в якому використовується матриця розміром (n + 1) * (m + 1), де n і m - довжини порівнюваних рядків. На псевдокоді алгоритм виглядає так:

int LevenshteinDistance(char str1[1..lenStr1], char str2[1..lenStr2])
   // d is a table with lenStr1+1 rows and lenStr2+1 columns
   declare int d[0..lenStr1, 0..lenStr2]
   // i and j are used to iterate over str1 and str2
   declare int i, j, cost
 
   for i from 0 to lenStr1
       d[i, 0] := i
   for j from 0 to lenStr2
       d[0, j] := j
 
   for i from 1 to lenStr1
       for j from 1 to lenStr2
           if str1[i] = str2[j] then cost := 0
                                else cost := 1
           d[i, j] := minimum(
                                d[i-1, j  ] + 1,     // deletion
                                d[i  , j-1] + 1,     // insertion
                                d[i-1, j-1] + cost   // substitution
                            )
 
   return d[lenStr1, lenStr2]

Цей алгоритм легко реалізовується також вручну у вигляді таблиці.

Мовою програмування PHP цей алгоритм реалізований як функція levenshteіn.

[ред.] Межі

Для відстані Левенштейна існують такі верхня і нижня межі:

Дистанція Левенштейна не менша за різницю довжини рядків, що порівнюються
Вона не може бути більшою довжини найдовшого рядка
Вона дорівнює 0 тільки тоді і тільки тоді, коли рядки однакові
Якщо обидва рядки мають однакову довжину, то відстань Гемінга є верхньою межею
Якщо довжина рядків різна, то верхньою межею є відстань Гемінга плюс різниця довжини рядків