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

我正在尝试根据两个字符串之间的比较来分配相似度分数。 R 中是否有相同的函数。我知道 SAS 中有一个名为 SPEDIS 的函数。如果R中有这样的函数，请告诉我。

功能adist http://stat.ethz.ch/R-manual/R-patched/library/utils/html/adist.html计算编辑距离 http://en.wikipedia.org/wiki/Levenshtein_distance两根弦之间。这可以转换为相似性度量，即 1 -（Levenshtein 编辑距离/较长的字符串长度）。

The levenshteinSim函数在记录联动 http://cran.r-project.org/web/packages/RecordLinkage/index.html包也直接执行此操作，并且可能比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

预计到达时间：有趣的是，虽然levenshteinDistRecordLinkage 包中的速度似乎比adist, levenshteinSim比任何一个都慢得多。使用基准测试 http://cran.r-project.org/web/packages/rbenchmark/index.html包裹：

> 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 and levenshteinDist就性能而言，如果您不想添加包依赖项，则前者更可取。如何将其转变为相似性度量确实会对性能产生一些影响。