Comment calculer la distance de Levenshtein dans R (avec exemples)

La distance de Levenshtein entre deux chaînes est le nombre minimum de modifications d’un seul caractère requises pour transformer un mot en un autre.

Le mot « modifications » inclut les substitutions, les insertions et les suppressions.

Par exemple, supposons que nous ayons les deux mots suivants :

• FAIRE LA FÊTE
• PARC

La distance de Levenshtein entre les deux mots (c’est-à-dire le nombre de modifications que nous devons effectuer pour transformer un mot en l’autre) serait de 2 :

En pratique, la distance de Levenshtein est utilisée dans de nombreuses applications différentes, notamment la correspondance approximative de chaînes, la vérification orthographique et le traitement du langage naturel.

Ce didacticiel explique comment calculer la distance de Levenshtein entre les chaînes dans R en utilisant la fonction stringdist() du package stringdist dans R.

Cette fonction utilise la syntaxe de base suivante :

#load stringdist package
library(stringdist)

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

Notez que cette fonction peut calculer de nombreuses mesures de distance différentes. En spécifiant method = « lv », nous disons à la fonction de calculer la distance de Levenshtein.

Exemple 1 : Distance de Levenshtein entre deux cordes

Le code suivant montre comment calculer la distance de Levenshtein entre les deux chaînes « party » et « park » à l’aide de la fonction stringdist() :

#load stringdist package
library(stringdist)

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

[1] 2

La distance de Levenshtein s’avère être 2 .

Exemple 2 : Distance de Levenshtein entre deux vecteurs

Le code suivant montre comment calculer la distance de Levenshtein entre chaque combinaison par paire de chaînes dans deux vecteurs différents :

#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

La façon d’interpréter le résultat est la suivante :

• La distance de Levenshtein entre «Mavs» et «Rockets» est de 6 .
• La distance de Levenshtein entre les « Spurs » et les « Pacers » est de 4 .
• La distance de Levenshtein entre les « Lakers » et les « Warriors » est de 5 .
• La distance de Levenshtein entre « Cavs » et « Celtics » est de 5 .

Exemple 3 : Distance de Levenshtein entre les colonnes du bloc de données

Le code suivant montre comment calculer la distance de Levenshtein entre chaque combinaison par paire de chaînes dans deux colonnes différentes d’un bloc de données :

#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

Nous pourrions ensuite ajouter la distance de Levenshtein en tant que nouvelle colonne dans le bloc de données si nous le souhaitons :

#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

Ressources additionnelles

Comment calculer la distance de Hamming en R
Comment calculer la distance euclidienne dans R
Comment calculer la distance de Manhattan en R