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

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

Метод розроблений у 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, no change)} \\ 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 (можна використати дві літери (Б або А) + Л) */

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

У PHP цей алгоритм реалізований функцією levenshtein.

Межі

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

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

Між відстанню Левенштайна та відстанню Гемінга існують такі взаємозв'язки:

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

Реалізація

Реалізація оптимізованого алгоритму пошуку відстані Левенштейна на мові Python 2.x:

def levenstein(s1,s2):
    n = range(0,len(s1)+1)
    for y in xrange(1,len(s2)+1):
        l,n = n,[y]
        for x in xrange(1,len(s1)+1):
            n.append(min(l[x]+1,n[-1]+1,l[x-1]+((s2[y-1]!=s1[x-1]) and 1 or 0)))
    return n[-1]

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

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

Посилання

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