Расстояние Левенштейна между двумя строками — это минимальное количество односимвольных правок, необходимых для превращения одного слова в другое.
Слово «редактирование» включает замены, вставки и удаления.
Например, предположим, что у нас есть следующие два слова:
- ПАРТИЯ
- ПАРК
Расстояние Левенштейна между двумя словами (то есть количество правок, которые мы должны сделать, чтобы превратить одно слово в другое) будет равно 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