Come calcolare la distanza di levenshtein in python

La distanza di Levenshtein tra due stringhe è il numero minimo di modifiche di un singolo carattere necessarie per trasformare una parola in un’altra.

La parola “modifiche” comprende sostituzioni, inserimenti e cancellazioni.

Ad esempio, supponiamo di avere le seguenti due parole:

• FESTEGGIARE
• PARCO

La distanza di Levenshtein tra le due parole (ovvero il numero di cambiamenti che dobbiamo fare per trasformare una parola nell’altra) sarebbe 2 :

In pratica, la distanza di Levenshtein viene utilizzata in molte applicazioni diverse, tra cui la corrispondenza fuzzy di stringhe, il controllo ortografico e l’elaborazione del linguaggio naturale.

Questo tutorial spiega come calcolare la distanza Levenshtein tra le stringhe in Python utilizzando il modulo python-Levenshtein.

È possibile utilizzare la seguente sintassi per installare questo modulo:

 pip install python-Levenshtein

È quindi possibile caricare la funzione per calcolare la distanza di Levenshtein:

 from Levenshtein import distance as lev

I seguenti esempi mostrano come utilizzare questa funzione nella pratica.

Esempio 1: distanza di Levenshtein tra due corde

Il codice seguente mostra come calcolare la distanza di Levenshtein tra le due stringhe “party” e “park”:

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

2

La distanza di Levenshtein risulta essere 2 .

Esempio 2: distanza di Levenshtein tra due tavoli

Il codice seguente mostra come calcolare la distanza di Levenshtein tra ciascuna combinazione di stringhe a coppie in due array diversi:

 #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

Il modo di interpretare il risultato è il seguente:

• La distanza di Levenshtein tra “Mavs” e “Rockets” è 6 .
• La distanza di Levenshtein tra gli “Spurs” e i “Pacers” è 4 .
• La distanza di Levenshtein tra i “Lakers” e i “Warriors” è 5 .
• La distanza di Levenshtein tra “Cavs” e “Celtics” è 5 .

Risorse addizionali

Come calcolare la distanza di Hamming in Python
Come calcolare la distanza euclidea in Python
Come calcolare la distanza di Mahalanobis in Python