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

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

Приклад:

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

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

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

Алгоритм

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

$D_{0,0}=0$

$D_{i,j}=min{\begin{cases}D_{i-1,j-1}&+0\ {\rm {(equal,nochange)}}\\D_{i-1,j-1}&+1\ {\rm {(replace)}}\\D_{i-1,j}&+1\ {\rm {(insert)}}\\D_{i,j-1}&+1\ {\rm {(delete)}}\end{cases}}$

У псевдокоді алгоритм виглядає так:

int LevenshteinDistance(char str1[1..lenStr1], char str2[1..lenStr2])
   // d таблиця кількість рядків = lenStr1+1 та кількість стовпців = lenStr2+1
   declare int d[0..lenStr1, 0..lenStr2]
   // i та j використовуються для індексування позиції у str1 та у 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,     // вилучення
                                d[i  , j-1] + 1,     // вставка
                                d[i-1, j-1] + cost   // заміна або одинакові
                            )
 
   return d[lenStr1, lenStr2]

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

ε - т.зв. пусте слово, без літер

  ε К О Р А Б Е Л Ь
ε 0 1 2 3 4 5 6 7 8   /* тобто відстань між пустим словом і словом КОРАБЕЛЬ = 8 (довжина слова КОРАБЕЛЬ) */
Б 1 1 2 3 4 4 5 6 7   /* між Б і КОРАБЕЛЬ відстань = 7 (літера Б в обох словах і може бути використана) */
А 2 2 2 3 3 4 5 6 7   /* між БА і КОРАБЕЛЬ відстань = 7 (лише одну з літер Б або А можна використати) */
Л 3 3 3 3 4 4 5 5 6   /* між БАЛ і КОРАБЕЛЬ відстань = 6 (можна використати дві літери (Б або А) + Л) */

Як видно з прикладу існувє декілька еквівалентних шляхів і алгоритм вираховує усі шляхи, використовуючи у кожному наступному кроці інформацію здобуту у попередніх кроках (принцип динамічного програмування).

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

Межі

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

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

Подібні методи

• Відстань Гемінга (Hamming distance)
• Відстань Єнсена-Шенона (Jensen-Shannon distance)
• Soundex-метод
• Фонетичний пошук
• Pattern Matching
• Sequence alignment

Посилання

• Різні методи реалізіції
• Візуалізація алгоритму Левенштейна
• Розрахунок відстані між рядками - Левенштейн і Геммінг
• Ще одна візуалізація методу Левенштейна (швидка)