Как рассчитать расстояние Левенштейна в R (с примерами)

Редакция Кодкампа -

Расстояние Левенштейна между двумя строками — это минимальное количество односимвольных правок, необходимых для превращения одного слова в другое.

Слово «редактирование» включает замены, вставки и удаления.

Например, предположим, что у нас есть следующие два слова:

  • ПАРТИЯ
  • ПАРК

Расстояние Левенштейна между двумя словами (то есть количество правок, которые мы должны сделать, чтобы превратить одно слово в другое) будет равно 2 :

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

В этом руководстве объясняется, как вычислить расстояние Левенштейна между строками в R с помощью функции stringdist() из пакета stringdist в R.

Эта функция использует следующий базовый синтаксис:

#load stringdist package
library(stringdist)

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

Обратите внимание, что эта функция может вычислять множество различных показателей расстояния. Указав method = «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)

#define vectors
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

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

Дополнительные ресурсы

Как рассчитать расстояние Хэмминга в R
Как рассчитать евклидово расстояние в R
Как рассчитать манхэттенское расстояние в R