Jak obliczyć odległość levenshteina w r (z przykładami)

Odległość Levenshteina między dwoma ciągami znaków to minimalna liczba zmian pojedynczych znaków wymagana do przekształcenia jednego słowa w drugie.

Słowo „modyfikacje” obejmuje podstawienia, insercje i skreślenia.

Załóżmy na przykład, że mamy następujące dwa słowa:

• IMPREZOWAĆ
• PARK

Odległość Levenshteina między dwoma słowami (tj. liczba zmian, które musimy wprowadzić, aby przekształcić jedno słowo w drugie) wyniosłaby 2 :

W praktyce odległość Levenshteina jest wykorzystywana w wielu różnych zastosowaniach, w tym w dopasowywaniu ciągów rozmytych, sprawdzaniu pisowni i przetwarzaniu języka naturalnego.

W tym samouczku wyjaśniono, jak obliczyć odległość Levenshteina między ciągami w języku R przy użyciu funkcji stringdist() pakietu stringdist w języku R.

Ta funkcja wykorzystuje następującą podstawową składnię:

 #load stringdist package
library(stringdist)

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

Należy pamiętać, że ta funkcja może obliczać wiele różnych pomiarów odległości. Podając metodę = „lv”, nakazujemy funkcji obliczenie odległości Levenshteina.

Przykład 1: Odległość Levenshteina pomiędzy dwiema strunami

Poniższy kod pokazuje, jak obliczyć odległość Levenshteina między dwoma ciągami „impreza” i „park” za pomocą funkcji stringdist() :

 #load stringdist package
library(stringdist)

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

[1] 2

Okazuje się, że odległość Levenshteina wynosi 2 .

Przykład 2: Odległość Levenshteina między dwoma wektorami

Poniższy kod pokazuje, jak obliczyć odległość Levenshteina pomiędzy każdą kombinacją parami ciągów w dwóch różnych wektorach:

 #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

Sposób interpretacji wyniku jest następujący:

• Odległość Levenshteina pomiędzy „Mavami” i „Rakietami” wynosi 6 .
• Odległość Levenshteina pomiędzy „Spurs” i „Pacers” wynosi 4 .
• Odległość Levenshteina pomiędzy „Lakerami” i „Wojownikami” wynosi 5 .
• Odległość Levenshteina pomiędzy „Cavs” i „Celtics” wynosi 5 .

Przykład 3: Odległość Levenshteina pomiędzy kolumnami ramki danych

Poniższy kod pokazuje, jak obliczyć odległość Levenshteina pomiędzy każdą parą kombinacji ciągów w dwóch różnych kolumnach ramki danych:

 #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

Gdybyśmy chcieli, moglibyśmy następnie dodać odległość Levenshteina jako nową kolumnę w ramce danych:

 #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

Dodatkowe zasoby

Jak obliczyć odległość Hamminga w R
Jak obliczyć odległość euklidesową w R
Jak obliczyć odległość od Manhattanu w R