В R - самый быстрый путь, попарно сравнивающий символьные строки по подобию

Question

Я ищу способ ускорить следующий подход. Любые указатели очень приветствуются. Где узкие места?

Скажем, у меня есть следующий data.frame:

df <- data.frame(names=c("A ADAM", "S BEAN", "A APPLE", "J BOND", "J BOND"), 
         v1=c("Test_a", "Test_b", "Test_a", "Test_b", "Test_b"), 
         v2=c("Test_c", "Test_c", "Test_d", "Test_d", "Test_d")) 

Я хочу, чтобы сравнить каждую пару строк в df на их JaroWinkler сходства.

С некоторой помощью других (see this post), я был в состоянии построить этот код:

#columns to compare 
testCols <- c("names", "v1", "v2") 

#compare pairs 
RowCompare= function(x){ 
comp <- NULL 
pairs <- t(combn(nrow(x),2)) 
for(i in 1:nrow(pairs)){ 
    row_a <- pairs[i,1] 
    row_b <- pairs[i,2] 
    a_tests <- x[row_a,testCols] 
    b_tests <- x[row_b,testCols] 
comp <- rbind(comp, c(row_a, row_b, TestsCompare(a_tests, b_tests))) 
} 

colnames(comp) <- c("row_a","row_b","names_j","v1_j","v2_j") 
return(comp) 
} 

#define TestsCompare 
TestsCompare=function(x,y){ 
names_j <- stringdist(x$names, y$names, method = "jw") 
v1_j <-stringdist(x$v1, y$v1, method = "jw") 
v2_j <-stringdist(x$v2, y$v2, method = "jw") 
c(names_j,v1_j, v2_j) 
} 

Это генерирует правильный вывод:

output = as.data.frame(RowCompare(df)) 

> output 
    row_a row_b names_j  v1_j  v2_j 
1  1  2 0.4444444 0.1111111 0.0000000 
2  1  3 0.3571429 0.0000000 0.1111111 
3  1  4 0.4444444 0.1111111 0.1111111 
4  1  5 0.4444444 0.1111111 0.1111111 
5  2  3 0.4603175 0.1111111 0.1111111 
6  2  4 0.3333333 0.0000000 0.1111111 
7  2  5 0.3333333 0.0000000 0.1111111 
8  3  4 0.5634921 0.1111111 0.0000000 
9  3  5 0.5634921 0.1111111 0.0000000 
10  4  5 0.0000000 0.0000000 0.0000000 

Однако, мой реальный data.frame имеет 8 миллионов наблюдений, и я делаю 17 сравнений. Для того, чтобы запустить этот код занимает дни ...

Я ищу способы, чтобы ускорить этот процесс:

• Должен ли я использовать матрицы вместо data.frames?
• Как распараллелить этот процесс?
• Векторизация?

Answer 1

Если вы перебираете переменные, которые хотите проверить, вы можете сделать матрицу расстояний для каждого с stringdist::stringdistmatrix. Используя форму lapply или purrr::map, мы вернем список матриц расстояний (по одному для каждого столбца), которые вы можете, в свою очередь, перебрать на cal broom::tidy, что превратит их в хорошо отформатированные данные. Если вы используете purrr::map_df и используете его параметр .id, результаты будут принудительно введены в один большой файл data.frame, и имя каждого элемента списка будет добавлено в виде нового столбца, чтобы вы могли держать их прямо. Результирующий файл data.frame будет длинным, поэтому, если вы хотите, чтобы он соответствовал результатам выше, измените форму на tidyr::spread.

Если, как вы упомянули в комментариях, вы хотите использовать разные методы для разных переменных, выполните итерацию параллельно с map2 или Map.

Всего

library(tidyverse) 

map2(df, c('soundex', 'jw', 'jw'), ~stringdist::stringdistmatrix(.x, method = .y)) %>% 
    map_df(broom::tidy, .id = 'var') %>% 
    spread(var, distance) 

## item1 item2 names  v1  v2 
## 1  2  1  1 0.1111111 0.0000000 
## 2  3  1  1 0.0000000 0.1111111 
## 3  3  2  1 0.1111111 0.1111111 
## 4  4  1  1 0.1111111 0.1111111 
## 5  4  2  1 0.0000000 0.1111111 
## 6  4  3  1 0.1111111 0.0000000 
## 7  5  1  1 0.1111111 0.1111111 
## 8  5  2  1 0.0000000 0.1111111 
## 9  5  3  1 0.1111111 0.0000000 
## 10  5  4  0 0.0000000 0.0000000 

Обратите внимание, что в то время как choose(5, 2) возвращает 10 наблюдений, choose(8000000, 2) возвращает 3.2E + 13 (32 000 млрд) наблюдений, так и для практических целей, даже если это будет работать гораздо быстрее, чем ваш существующий код (и stringdistmatrix выполняет некоторую распараллеливание, когда это возможно), данные станут непомерно большими, если только вы не работаете только с подмножествами.