r - R での文字列比較に基づく類似度スコア (編集距離)

Question

2 つの文字列の比較に基づいて類似性スコアを割り当てようとしています。Rにも同じ機能がありますか.SPEDISの名前でSASにそのような機能があることを知っています. Rにそのような機能があるかどうか教えてください。

Answer 1

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

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: 興味深いことに、 RecordLinkage パッケージでは はlevenshteinDistよりわずかに速いように見えますが、どちらよりもかなり遅いです。rbenchmarkパッケージの使用:adistlevenshteinSim

> 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ありませんが、パッケージの依存関係を追加したくない場合は前者の方が望ましいです。それをどのように類似性尺度に変換するかは、パフォーマンスに少し影響します。