基於R（編輯距離）中字符串比較的相似性分數

Question

我想根據2個字符串之間的比較來分配相似性分數。在R中是否有相同的函數？我知道SAS中的這種函數的名稱爲SPEDIS。請讓我知道R中是否有這樣的功能。

Answer 1

函數adist計算兩個字符串之間的Levenshtein edit distance。這可以轉化爲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)))) 
} 

FYI：如果你總是比較兩個字符串，而不是矢量，您可以創建使用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之間幾乎沒有什麼區別，但如果您不想添加軟件包依賴關係，前者更可取。如何將其轉化爲相似性度量對性能有一定影響。