Очень быстрое нечеткое совпадение строк в R - PullRequest
Новая
       37

Очень быстрое нечеткое совпадение строк в R

1 голос
/ 10 мая 2019

У меня есть набор из 40 000 строк x 4 столбцов, и мне нужно сравнить каждый столбец с самим собой, чтобы найти наиболее близкий результат или минимальное расстояние Левенштейна. Идея состоит в том, чтобы получить «почти дубликат» для каждого ряда. Я рассчитал с "adist", но, кажется, слишком медленно. Например, только для одного столбца, 5000 строк по сравнению со всем набором данных столбцов (40 000 строк), требуется почти 2 часа. Это для 4 столбцов 8 часов и для всего набора данных 32 часа. Есть ли более быстрый способ добиться того же? Мне нужно, чтобы это было через 1 или 2 часа, если это возможно. Это пример того, что я сделал до сих пор: 


    #vector example
    a<-as.character(c("hello","allo","hola"))
    b<-as.character(c("hello","allo","hola"))

    #execution time
    start_time <- Sys.time()

    #Matrix with distance
    dist.name<-adist(a,b, partial = TRUE, ignore.case = TRUE)

    #time elapsed
    end_time <- Sys.time()
    end_time - start_time

    Output:
    Time difference of 5.873202 secs

    #result
    dist.name
          [,1] [,2] [,3]
    [1,]    0    4    5
    [2,]    2    0    2
    [3,]    5    4    0

желаемый результат (минимальное расстояние для каждой строки, но нет для той же строки), но мне это нужно быстрее. 

[1,] 4
[2,] 2
[3,] 4

1 Ответ

3 голосов
/ 10 мая 2019

Вы можете попробовать stringsdist -пакет.

Он написан на C, использует параллельную обработку и предлагает различные метрики расстояния, включая levenshtein-distance. 

library(stringdist)

a<-as.character(c("hello","allo","hola"))
b<-as.character(c("hello","allo","hola"))

start_time <- Sys.time()
res <- stringdistmatrix(a,b, method = "lv")
end_time <- Sys.time()

> end_time - start_time
Time difference of 0.006981134 secs
> res
     [,1] [,2] [,3]
[1,]    0    2    3
[2,]    2    0    3
[3,]    3    3    0


diag(res) <- NA
apply(res, 1, FUN = min, na.rm = T)
[1] 2 2 3
...