Comment calculer la distance de Levenshtein en Python

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 tutoriel explique comment calculer la distance de Levenshtein entre les chaînes en Python à l’aide du module python-Levenshtein.

Vous pouvez utiliser la syntaxe suivante pour installer ce module :

pip install python-Levenshtein

Vous pouvez ensuite charger la fonction pour calculer la distance de Levenshtein :

from Levenshtein import distance as lev

Les exemples suivants montrent comment utiliser cette fonction dans la pratique.

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 » :

#calculate Levenshtein distance
lev('party', 'park')

2

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

Exemple 2 : distance de Levenshtein entre deux tableaux

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

#define arrays
a = ['Mavs', 'Spurs', 'Lakers', 'Cavs']
b <- ['Rockets', 'Pacers', 'Warriors', 'Celtics']

#calculate Levenshtein distance between two arrays
for i,k in zip(a, b):
  print(lev(i, k))

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 .

Ressources additionnelles

Comment calculer la distance de Hamming en Python
Comment calculer la distance euclidienne en Python
Comment calculer la distance de Mahalanobis en Python