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

Question

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

rstring-comparisonedit-distance

29

我正在尝试基于两个字符串之间的比较来分配相似性分数。在R中是否有这样的功能？我知道SAS中有一个名为SPEDIS的函数可以实现此功能。请告诉我在R中是否有类似的函数。

- Kunal Batra

你是否探索过 adist 和 agrep？我不熟悉 SPEDIS。 - A5C1D2H2I1M1N2O1R2T1

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David Robinson · Accepted Answer

函数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

更新：有趣的是，虽然RecordLinkage包中的levenshteinDist函数似乎比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之间几乎没有什么区别，但如果您不想添加软件包依赖，则前者更可取。如何将其转化为相似度测量会对性能产生一定影响。