R の文字列比較に基づく類似度スコア (編集距離) 質問する

Question

関数アディスト計算するレーベンシュタイン編集距離2 つの文字列間の類似度。これは、1 - (レーベンシュタイン編集距離 / 長い方の文字列の長さ) として類似度メトリックに変換できます。

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: 興味深いことに、levenshteinDistRecordLinkageパッケージでははよりもわずかに速いように見えますがadist、levenshteinSimはどちらよりもかなり遅いです。ベンチマークパッケージ：

> 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))))
}

参考までに: 常にベクトルではなく 2 つの文字列を比較する場合は、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が、パッケージの依存関係を追加したくない場合は前者の方が適しています。これを類似性の尺度に変換する方法は、パフォーマンスに多少影響します。

Answer 1