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

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

Метод розроблений у 1965 році радянським математиком Володимиром Йосиповичем Левенштейном і названий його іменем.

Приклад:

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

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

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

Алгоритм

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

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

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]. Як видно з прикладу існує декілька еквівалентних шляхів, і алгоритм знаходить не тільки мінімальну відстань, але й усі шляхи. На кожному наступному кроці застосовується інформація, здобута на попередньому кроці (принцип динамічного програмування).

Межі

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

  • Дистанція Левенштейна не є меншою за різницю довжини рядків, що порівнюються
  • Вона не є більшою довжини найдовшого рядка
  • Вона дорівнює 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]

В Python алгоритм реалізовано в бібілотеці python-Levenshtein[1][2].

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

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

Примітки

  1. ↑ python-Levenshtein: Python extension for computing string edit distances and similarities., процитовано 7 жовтня 2024
  2. ↑ Welcome to Levenshtein’s documentation! — Levenshtein 0.23.0 documentation. rapidfuzz.github.io. Процитовано 7 жовтня 2024.
  3. ↑ levenshtein — Calculate Levenshtein distance between two strings. PHP Manual. The PHP Group. Архів оригіналу за 16 грудня 2017. Процитовано 19 грудня 2017. (англ.)

Посилання