Puntuaciones de similitud basadas en la comparación de cadenas en R (distancia de edición)

Question

Estoy tratando de asignar una puntuación de similitud basada en la comparación entre 2 cadenas. ¿Existe una función para el mismo en R. Soy consciente de tal función en SAS con el nombre de SPEDIS. Por favor, hágamelo saber si existe tal función en R.

Answer 1

La función adist calcula el Levenshtein edit distance entre dos cadenas. Esto se puede transformar en una métrica de similitud como 1 - (distancia de edición de Levenshtein/longitud de cuerda más larga).

La función levenshteinSim en el paquete RecordLinkage también lo hace directamente, y puede ser más rápido que 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: Curiosamente, mientras levenshteinDist en el paquete RecordLinkage parece ser ligeramente más rápido que adist, levenshteinSim es considerablemente más lento que tampoco. Utilizando el rbenchmark paquete:

> 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 

Esta sobrecarga se debe simplemente al código para levenshteinSim, que es sólo una envoltura alrededor de levenshteinDist:

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

FYI: si siempre está comparando dos cadenas en lugar de vectores , puede crear una nueva versión que utiliza max lugar de pmax y afeitar ~ 25% de descuento en el tiempo de ejecución:

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 

Resumen breve: hay poca diferencia entre adist y levenshteinDist en términos de rendimiento, aunque la primera es preferible si no desea agregar dependencias de paquete. Cómo convertirlo en una medida de similitud tiene un poco de efecto en el rendimiento.