Punteggi di similarità basati sul confronto di stringhe in R (modifica distanza)

Question

Sto provando ad assegnare un punteggio di somiglianza basato sul confronto tra 2 stringhe. Esiste una funzione per lo stesso in R. Sono consapevole di tale funzione in SAS con il nome di SPEDIS. Per favore fatemi sapere se c'è una tale funzione in R.

Answer 1

La funzione adist calcola lo Levenshtein edit distance tra due stringhe. Questo può essere trasformato in una metrica di similarità come 1 - (Levenshtein modifica distanza/lunghezza stringa più lunga).

La funzione levenshteinSim nel pacchetto RecordLinkage lo fa anche direttamente e potrebbe essere più veloce di adist.

library(RecordLinkage) 
> levenshteinSim("apple", "apple") 
[1] 1 
> levenshteinSim("apple", "aaple") 
[1] 0.8 
> levenshteinSim("apple", "appled") 
[1] 0.8333333 
> levenshteinSim("appl", "apple") 
[1] 0.8 

ETA: È interessante notare che, mentre levenshteinDist nel pacchetto RecordLinkage sembra essere leggermente più veloce di adist, levenshteinSim è notevolmente più lento di entrambi. Utilizzando il pacchetto rbenchmark:

> benchmark(levenshteinDist("applesauce", "aaplesauce"), replications=100000) 
             test replications elapsed relative 
1 levenshteinDist("applesauce", "aaplesauce")  100000 4.012  1 
    user.self sys.self user.child sys.child 
1  3.583 0.452   0   0 
> benchmark(adist("applesauce", "aaplesauce"), replications=100000) 
           test replications elapsed relative user.self 
1 adist("applesauce", "aaplesauce")  100000 4.277  1  3.707 
    sys.self user.child sys.child 
1 0.461   0   0 
> benchmark(levenshteinSim("applesauce", "aaplesauce"), replications=100000) 
             test replications elapsed relative 
1 levenshteinSim("applesauce", "aaplesauce")  100000 7.206  1 
    user.self sys.self user.child sys.child 
1  6.49 0.743   0   0 

Questo sovraccarico è dovuto semplicemente al codice per levenshteinSim, che è solo un wrapper levenshteinDist:

> levenshteinSim 
function (str1, str2) 
{ 
    return(1 - (levenshteinDist(str1, str2)/pmax(nchar(str1), 
     nchar(str2)))) 
} 

FYI: se si sta sempre confrontano due stringhe piuttosto che vettori , è possibile creare una nuova versione che utilizza max invece di pmax e la barba ~ 25% il tempo di esecuzione:

mylevsim = function (str1, str2) 
{ 
    return(1 - (levenshteinDist(str1, str2)/max(nchar(str1), 
     nchar(str2)))) 
} 
> benchmark(mylevsim("applesauce", "aaplesauce"), replications=100000) 
            test replications elapsed relative user.self 
1 mylevsim("applesauce", "aaplesauce")  100000 5.608  1  4.987 
    sys.self user.child sys.child 
1 0.627   0   0 

Per farla breve, c'è poca differenza tra adist e levenshteinDist in termini di prestazioni, sebbene il primo sia preferibile se non si desidera aggiungere dipendenze del pacchetto. Il modo in cui lo trasformi in una misura di somiglianza ha un po 'di effetto sulle prestazioni.