Як розрахувати відстань левенштейна в r (з прикладами)

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

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

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

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

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

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

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

Ця функція використовує такий базовий синтаксис:

 #load stringdist package
library(stringdist)

#calculate Levenshtein distance between two strings
stringdist(" string1 ", " string2 ", method = " lv ")

Зауважте, що ця функція може обчислювати багато різних вимірювань відстані. Вказавши метод = “lv”, ми наказуємо функції обчислити відстань Левенштейна.

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

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

 #load stringdist package
library(stringdist)

#calculate Levenshtein distance between two strings
stringdist(' party ', ' park ', method = ' lv ')

[1] 2

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

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

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

 #load stringdist package
library(stringdist)

#definevectors
a <- c('Mavs', 'Spurs', 'Lakers', 'Cavs')
b <- c('Rockets', 'Pacers', 'Warriors', 'Celtics')

#calculate Levenshtein distance between two vectors
stringdist(a, b, method=' lv ')

[1] 6 4 5 5

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

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

Приклад 3: Відстань Левенштейна між стовпцями кадру даних

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

 #load stringdist package
library(stringdist)

#define data
data <- data.frame(a = c('Mavs', 'Spurs', 'Lakers', 'Cavs'),
                   b = c('Rockets', 'Pacers', 'Warriors', 'Celtics'))

#calculate Levenshtein distance
stringdist(data$a, data$b, method=' lv ')

[1] 6 4 5 5

Тоді ми можемо додати відстань Левенштейна як новий стовпець у кадрі даних, якщо захочемо:

 #save Levenshtein distance as vector
lev <- stringdist(data$a, data$b, method=' lv ')

#append Levenshtein distance as new column
data$lev <- lev

#view data frame
data

       ab lev
1 Mavs Rockets 6
2 Spurs Pacers 4
3 Lakers Warriors 5
4 Cavs Celtics 5

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

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