ойкаУ меня есть данные о людях и именах их родителей, и я хочу найти братьев и сестер (людей с одинаковыми именами родителей).

 pdata<-data.frame(parents_name=c("peter pan + marta steward",
                                 "pieter pan + marta steward",
                                 "armin dolgner + jane johanna dough",
                                 "jack jackson + sombody else"))

Ожидаемый результат здесь будет столбцом, указывающим, что первые два наблюдения принадлежат семейству X, в то время как третий и четвертый столбцы находятся в отдельном семействе. Например:

person_id    parents_name                           family_id
1            "peter pan + marta steward",           1
2            "pieter pan + marta steward",          1
3            "armin dolgner + jane johanna dough",  2
4            "jack jackson + sombody else"          3

Текущий подход: Я гибок в отношении метрики расстояния. В настоящее время я использую расстояние редактирования Левенштейна для сопоставления с obs, учитывая разницу в два символа. Но другие варианты, такие как «самая большая общая подстрока», подойдут быстрее.

Для меньших подвыборок я используюstringdist::stringdist в цикле илиstringdist::stringdistmatrix, но это становится все более неэффективным с увеличением размера выборки.

Версия матрицы взрывается при использовании определенного размера выборки. Моя ужасно неэффективная попытка зацикливания здесь:

#create data of the same complexity using random last-names
#(4mio obs and ~1-3 kids per parents) 
pdata<-data.frame(parents_name=paste0(rep(c("peter pan + marta ",
                                "pieter pan + marta ",
                                "armin dolgner + jane johanna ",
                                "jack jackson + sombody "),1e6),stringi::stri_rand_strings(4e6, 5)))

for (i in 1:nrow(pdata)) {
  similar_fatersname0<-stringdist::stringdist(pdata$parents_name[i],pdata$parents_name[i:nrow(pdata)],nthread=4)<2
  #[create grouping indicator]
}

Мой вопрос: Должно быть значительное повышение эффективности, например, потому что я могу перестать сравнивать строки, как только найду их достаточно разными в чем-то, что легче оценить, например. длина строки или первое слово. Вариант длины строки уже работает и уменьшает сложность в ~ 3 раза. Но это слишком мало. Любые предложения по сокращению времени вычислений приветствуются.

замечания:

Строки на самом деле в Unicode, а не в латинском алфавите (Devnagari)Предварительная обработка для удаления неиспользуемых символов и т. Д. Выполнена