相似度得分基于R中的字符串比较(编辑距离)

Question

我试图根据2个字符串之间的比较来指定相似度分数.在R中是否有相同的功能.我在SAS中通过SPEDIS的名称了解这样的功能.如果在R中有这样的功能,请告诉我.

Answer 1

函数adist计算两个字符串之间的Levenshtein编辑距离.这可以转换为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))))
}

仅供参考:如果你总是比较两个字符串而不是矢量,你可以创建一个新的版本,使用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在性能方面,虽然前者是优选的,如果你不希望添加软件包的依赖.如何将其转换为相似性度量确实会对性能产生一些影响.