Configuração: Tenho dados sobre pessoas e o nome dos pais e quero encontrar irmãos (pessoas com nomes idênticos).

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

A saída esperada aqui seria uma coluna indicando que as duas primeiras observações pertencem à família X, enquanto a terceira e a quarta colunas estão cada uma em uma família separada. Por exemplo:

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

Abordagem atual: Sou flexível em relação à métrica de distância. Atualmente, eu uso a distância de edição de Levenshtein para combinar com obs, permitindo diferenças de dois caracteres. Mas outras variantes, como a "maior sub-cadeia comum", seriam boas se executadas mais rapidamente.

Para subamostras menores, eu usostringdist::stringdist em um loop oustringdist::stringdistmatrix, mas isso está se tornando cada vez mais ineficiente à medida que o tamanho da amostra aumenta.

A versão da matriz explode quando um determinado tamanho de amostra é usado. Minha tentativa terrivelmente ineficiente de loop está aqui:

#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]
}

Minha pergunta: Deve haver ganhos substanciais de eficiência, por exemplo porque eu poderia parar de comparar seqüências de caracteres uma vez que as encontrasse suficientemente diferentes em algo mais fácil de avaliar, por exemplo. comprimento da string ou primeira palavra. A variante do comprimento da string já funciona e reduz a complexidade em um fator ~ 3. Mas isso é muito pouco. Todas as sugestões para reduzir o tempo de computação são apreciadas.

Observações:

As strings são realmente em unicode e não no alfabeto latino (Devnagari)O pré-processamento para descartar caracteres não utilizados etc. é feito