设置:
我有关于人及其 parent 姓名的数据，并且我想找到 sibling (具有相同 parent 姓名的人)。
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
当前方法:
对于距离指标，我很灵活。目前，我使用Levenshtein的编辑距离来匹配obs，从而允许两个字符的差异。但是其他变体，例如“最大的公共(public)子字符串”，如果运行得更快，则可以。
对于较小的子样本，我在循环中使用
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倍。但这远远太少了。减少计算时间的任何建议均受到赞赏。
备注:
最佳答案
有两个挑战:
A. Levenstein距离的并行执行-而不是顺序循环
B.比较次数:如果我们的来源列表中有400万个条目，那么即使我们解决了第一个挑战，从理论上讲我们也应该运行16万亿个Levenstein距离度量，这是不现实的。
为了使我的语言更清楚，这是我们的定义
小节中的单词顺序很重要(小节始终是名字，后跟姓氏，永远不要姓，例如， jack ·约翰和约翰· jack 是两个不同的人)。
从技术上讲，目标是在400万个表达式列表中找到一系列匹配表达式。如果两个表达式的Levenstein距离小于2，则认为它们是匹配表达式。
实际上，我们创建了两个列表，它们是最初的400万个表达式列表的精确副本。然后我们称为“左”列表和“右”列表。在复制列表之前，会为每个表达式分配一个表达式ID。
我们的目标是在“右”列表中找到距左列表的Levenstein距离小于2的条目，但不包括相同的条目(相同的表达式ID)。
我建议采用两步法分别解决两个挑战。第一步将减少可能匹配表达式的列表，第二步将简化Levenstein距离测量，因为我们仅查看非常接近的表达式。使用的技术是任何传统的数据库服务器，因为我们需要为数据集建立索引以提高性能。
挑战
挑战A包括减少距离测量的次数。我们从最大值开始。 16万亿(400万乘以2的幂)，我们不应超过几千万或几亿。
此处使用的技术包括在完整表达式中搜索至少一个相似的单词。根据数据的分布方式，这将大大减少可能的匹配对的数量。或者，根据结果的要求准确性，我们也可以搜索至少两个相似词或至少一半相似词的对。
从技术上讲，我建议将表达式列表放在一个表中。添加一个标识列以为每个表达式创建唯一的ID，并创建12个字符列。然后解析表达式并将每个部分的每个单词放在单独的列中。这看起来像(我没有代表全部12列，但是下面的想法):
|id | expression | sect_a_w_1 | sect_a_w_2 | sect_b_w_1 |sect_b_w_2 |
|1 | peter pan + marta steward | peter | pan | marta |steward |
有空列(因为很少有12个单词的表达式)，但这并不重要。
然后，我们复制表并在每个Sect ...列上创建一个索引。
我们进行了12次连接，试图找到相似的单词，例如
SELECT L.id, R.id
FROM left table L JOIN right table T
ON L.sect_a_w_1 = R.sect_a_w_1
AND L.id <> R.id
我们收集12个临时表中的输出，并对12个表进行联合查询，以获取所有表达式的简短列表，这些表达式具有可能的匹配表达式，且至少具有一个相同的单词。这是对我们挑战A的解决方案。我们现在列出了最可能匹配的对。此列表将包含数百万条记录(成对的左右记录)，但不包含数十亿条记录。
挑战B
挑战B的目标是批量处理简化的Levenstein距离(而不是循环运行)。
首先，我们应该就简化的Levenstein距离达成一致。
首先，我们同意两个表达式的Levenstein距离是两个具有相同索引的表达式的所有单词的Levenstein距离的总和。我的意思是两个表达式的Levenstein距离是他们两个第一个单词的距离，再加上他们两个第二个单词的距离，依此类推。
其次，我们需要发明简化的Levenstein距离。我建议只对2个字符的克使用n-gram方法，它们的索引绝对差小于2。
例如彼得和彼得之间的距离计算如下
Peter
1 = pe
2 = et
3 = te
4 = er
5 = r_
Pieter
1 = pi
2 = ie
3 = et
4 = te
5 = er
6 = r_
彼得和皮特(Peter and Pieter)有4个普通的2克，其索引绝对差小于2个“et”，“te”，“er”，“r_”。两个单词中的最大单词有6个可能的2克，则距离为6-4 = 2-Levenstein距离也将为2，因为有一个移动“eter”和一个字母插入“i”。
这是一个近似值，并非在所有情况下都有效，但我认为在我们的情况下，它将非常有效。如果我们对结果的质量不满意，可以尝试使用3克或4克或允许大于2克的序列差异。但是，这种想法是每对计算要比传统的Levenstein算法执行的计算少得多。
然后，我们需要将其转换为技术解决方案。我之前做过的事情如下:
首先隔离单词:由于我们只需要测量单词之间的距离，然后将每个表达式的距离求和，我们可以通过在单词列表上运行不同的选择来进一步减少计算量(我们已经准备好了上一节中的单词)。
这种方法需要一个映射表，该表跟踪表达式id，部分id，单词id和单词的单词序列号，以便可以在处理结束时计算出原始表达距离。
然后，我们有了一个新的列表，该列表要短得多，并且包含与2克距离度量相关的所有单词的交叉连接。
然后，我们要批处理此2克距离的测量，我建议在SQL连接中进行。这需要一个预处理步骤，该步骤包括创建一个新的临时表，该表将每2克存储在单独的行中-并跟踪单词ID，单词序列和节类型
从技术上讲，这是通过使用一系列(或一个循环)子串选择将单词列表切成薄片来完成的，就像这样(假设单词列表表-有两个副本，一个左和一个右-包含2列word_id和word):
INSERT INTO left_gram_table (word_id, gram_seq, gram)
SELECT word_id, 1 AS gram_seq, SUBSTRING(word,1,2) AS gram
FROM left_word_table
然后
INSERT INTO left_gram_table (word_id, gram_seq, gram)
SELECT word_id, 2 AS gram_seq, SUBSTRING(word,2,2) AS gram
FROM left_word_table
等等。
使“管家”看起来像这样的东西(假设单词id为152)
| pk | word_id | gram_seq | gram |
| 1 | 152 | 1 | st |
| 2 | 152 | 2 | te |
| 3 | 152 | 3 | ew |
| 4 | 152 | 4 | wa |
| 5 | 152 | 5 | ar |
| 6 | 152 | 6 | rd |
| 7 | 152 | 7 | d_ |
不要忘记在word_id，gram和gram_seq列上创建索引，并且可以通过左右克列表的连接来计算距离，其中ON看起来像
ON L.gram = R.gram
AND ABS(L.gram_seq + R.gram_seq)< 2
AND L.word_id <> R.word_id
距离是两个单词中最长的一个的长度减去匹配的克数。 SQL进行这样的查询的速度非常快，我认为一台具有8 GB RAM的简单计算机很容易在合理的时间内完成几亿行。
然后，只需连接映射表即可计算每个表达式中单词到单词的距离之和，以得到整个表达式到表达式的距离。
关于r - 高效的字符串相似性分组，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/48058104/