Оценки подобия, основанные на сравнении строк в R (расстояние редактирования)

Ответ 1

Функция adist вычисляет расстояние редактирования Левенштейна между двумя строками. Это можно преобразовать в метрику подобия как 1 - (длина редактирования Левенштейна/длинная длина строки).

Функция levenshteinSim в пакете RecordLinkage также делает это напрямую и может быть быстрее, чем 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 отличается от производительности, хотя первая предпочтительнее, если вы не хотите добавлять зависимости пакетов. Как вы превращаете его в меру подобия, это немного влияет на производительность.