基于R（编辑距离）中字符串比较的相似性分数

Question

我想根据2个字符串之间的比较来分配相似性分数。在R中是否有相同的函数？我知道SAS中的这种函数的名称为SPEDIS。请让我知道R中是否有这样的功能。

Answer 1

函数adist计算两个字符串之间的Levenshtein edit distance。这可以转化为1 - （Levenshtein编辑距离/更长的字符串长度）的相似性度量。

RecordLinkage包中的levenshteinSim函数也直接执行此操作，并且可能会比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：有趣的是，levenshteinDist在RecordLinkage包似乎是略快于adist，levenshteinSim比任一慢得多。使用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 

这个开销是由于单纯为levenshteinSim的代码，这仅仅是一个围绕levenshteinDist包装：

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

FYI：如果你总是比较两个字符串，而不是矢量，您可以创建使用max代替pmax新版本和刮胡子〜25％的运行时间：

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 

长话短说 - 在性能方面，adist和levenshteinDist之间几乎没有什么区别，但如果您不想添加软件包依赖关系，前者更可取。如何将其转化为相似性度量对性能有一定影响。