r - 基于 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性能方面几乎没有区别，但如果您不想添加包依赖项，则前者更可取。如何将其转换为相似性度量确实会对性能产生一些影响。