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

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

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

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

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

Межі

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

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

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

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

Реалізація

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

def levenstein(s1,s2):
    n = range(0,len(s1)+1)
    for y in range(1,len(s2)+1):
        l,n = n,[y]
        for x in range(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]

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

• Відстань Геммінга
• Подібність Джаро — Вінклера
• Відстань Єнсена-Шенона (Jensen-Shannon distance)
• Soundex-метод
• Фонетичний пошук
• Зіставляння зі взірцем
• Вирівнювання послідовностей

Посилання

• Різні методи реалізіції [Архівовано 28 червня 2006 у Wayback Machine.]
• Візуалізація алгоритму Левенштейна [Архівовано 25 липня 2008 у Wayback Machine.]
• Розрахунок відстані між рядками - Левенштейн і Геммінг [Архівовано 31 жовтня 2007 у Wayback Machine.]
• Ще одна візуалізація методу Левенштейна (швидка) [Архівовано 9 лютого 2008 у Wayback Machine.]