Як розрахувати відстань левенштейна в python

Відстань Левенштейна між двома рядками — це мінімальна кількість змін одного символу, необхідних для перетворення одного слова в інше.

Слово «модифікації» включає заміни, вставки та видалення.

Наприклад, припустимо, що ми маємо такі два слова:

• НА ВЕЧІРКУ
• ПАРК

Відстань Левенштейна між двома словами (тобто кількість змін, які нам потрібно зробити, щоб перетворити одне слово в інше) буде 2 :

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

У цьому посібнику пояснюється, як обчислити відстань Левенштейна між рядками в Python за допомогою модуля python-Levenshtein.

Ви можете використовувати наступний синтаксис для встановлення цього модуля:

 pip install python-Levenshtein

Потім ви можете завантажити функцію для обчислення відстані Левенштейна:

 from Levenshtein import distance as lev

Наступні приклади показують, як використовувати цю функцію на практиці.

Приклад 1: Відстань Левенштейна між двома струнами

Наступний код показує, як обчислити відстань Левенштейна між двома рядками «party» і «park»:

 #calculate Levenshtein distance
lev(' party ', ' park ')

2

Відстань Левенштейна виявляється рівною 2 .

Приклад 2: Відстань Левенштейна між двома столами

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

 #define arrays
a = ['Mavs', 'Spurs', 'Lakers', 'Cavs']
b <- ['Rockets', 'Pacers', 'Warriors', 'Celtics']

#calculate Levenshtein distance between two arrays
for i,k in zip (a,b):
  print (lev(i, k))

6
4
5
5

Спосіб інтерпретації результату такий:

• Відстань Левенштейна між «Мавами» і «Ракетами» дорівнює 6 .
• Відстань Левенштейна між «Сперс» і «Пейсерс» дорівнює 4 .
• Відстань Левенштейна між «Лейкерс» і «Ворріорз» дорівнює 5 .
• Відстань Левенштейна між «Кавс» і «Селтікс» становить 5 .

Додаткові ресурси

Як обчислити відстань Хеммінга в Python
Як розрахувати евклідову відстань у Python
Як обчислити відстань Махаланобіса в Python