r - 高效的字符串相似度分组

Question

设置 :
我有关于人及其 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 倍。但这太少了。任何减少计算时间的建议表示赞赏。

备注 :

字符串实际上是 unicode 而不是拉丁字母 (Devnagari)

删除未使用字符等的预处理完成

Answer 1

有两个挑战:

A. Levenstein 距离的并行执行——而不是顺序循环

B.比较次数:如果我们的源列表有400万个条目，理论上我们应该运行16万亿个Levenstein距离度量，这是不现实的，即使我们解决了第一个挑战。

为了使我的语言使用清晰，这里是我们的定义

我们想要测量表达式之间的 Levenstein 距离。

每个表达式都有两部分，父 A 全名和父 B 全名，用加号分隔

部分的顺序很重要(即，如果表达式 1 的父 A = 表达式 2 的父 A 和父 B 或表达式 1= 表达式 2 的父 B，则两个表达式 (1, 2) 相同。如果父表达式 1 的 A = 表达式 2 的父 B 和表达式 1 的父 B = 表达式 2) 的父 A

部分(或全名)是一系列单词，由空格或破折号分隔，对应于人的名字和姓氏

我们假设一个部分中的最大单词数为 6(您的示例有 2 或 3 个单词的部分，我假设我们最多可以有 6 个)
部分中的单词顺序很重要(该部分总是名字后跟姓氏，而不是姓氏在前，例如 jack 约翰和约翰 jack 是两个不同的人)。

有400万个表情

假定表达式仅包含英文字符。数字、空格、标点符号、破折号和任何非英文字符都可以忽略

我们假设简单匹配已经完成(如精确表达式匹配)并且我们不必搜索精确匹配

从技术上讲，目标是在 400 万个表达式列表中找到一系列匹配的表达式。如果两个表达式的 Levenstein 距离小于 2，则认为它们是匹配表达式。

实际上，我们创建了两个列表，它们是最初 400 万个表达式列表的精确副本。然后我们称之为左列表和右列表。在复制列表之前，每个表达式都被分配了一个表达式 id。
我们的目标是在 Right 列表中找到与 Left 列表的条目的 Levenstein 距离小于 2 的条目，不包括相同的条目(相同的表达式 id)。

我建议采用两步法来分别解决这两个挑战。第一步将减少可能匹配表达式的列表，第二步将简化 Levenstein 距离测量，因为我们只查看非常接近的表达式。使用的技术是任何传统的数据库服务器，因为我们需要索引数据集以提高性能。

挑战A

挑战 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 的解决方案。我们现在有一个最可能匹配对的简短列表。该列表将包含数百万条记录(成对的 Left 和 Right 条目)，但不会包含数十亿条记录。

挑战 B

挑战 B 的目标是批量处理简化的 Levenstein 距离(而不是循环运行)。
首先，我们应该同意什么是简化的 Levenstein 距离。
首先我们同意两个表达式的 levenstein 距离是两个表达式中具有相同索引的所有单词的 levenstein 距离之和。我的意思是两个表达式的 Levenstein 距离是它们两个第一个词的距离，加上它们两个第二个词的距离，等等。
其次，我们需要发明一个简化的 Levenstein 距离。我建议使用 n-gram 方法，只使用 2 个字符的克数，这些字符的索引绝对差异小于 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 和 Pieter 有 4 个共同的 2-gram，索引绝对差小于 2 'et','te','er','r_'。两个单词中最大的有 6 个可能的 2-gram，距离为 6-4 = 2 - Levenstein 距离也为 2，因为有一个 'eter' 移动和一个字母插入 'i'。

这是一个近似值，不适用于所有情况，但我认为在我们的情况下它会很好地工作。如果我们对结果的质量不满意，我们可以尝试使用 3 克或 4 克或允许大于 2 克的序列差异。但是这个想法是每对执行的计算比传统的 Levenstein 算法少得多。

然后我们需要将其转换为技术解决方案。我之前所做的是以下内容:
首先隔离单词:由于我们只需要测量单词之间的距离，然后将每个表达式的这些距离相加，我们可以通过在单词列表上运行一个不同的选择来进一步减少计算次数(我们已经准备好了列表上一节中的词)。

这种方法需要一个映射表来记录表达id、段id、词id和词的词序列号，以便在过程结束时计算原始表达距离。

然后我们有一个更短的新列表，它包含所有与 2-gram 距离度量相关的单词的交叉连接。
然后我们要批量处理这个 2-gram 距离测量，我建议在 SQL join 中进行。这需要一个预处理步骤，包括创建一个新的临时表，将每 2-gram 存储在单独的行中 - 并跟踪单词 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 列上创建索引，距离可以通过左右 gram 列表的连接来计算，其中 ON 看起来像

ON L.gram = R.gram 
AND ABS(L.gram_seq + R.gram_seq)< 2 
AND L.word_id <> R.word_id 

距离是两个词中最长的词的长度减去匹配的克数。 SQL 进行此类查询的速度非常快，我认为一台具有 8 gig 内存的简单计算机可以在合理的时间范围内轻松完成几亿行。

然后只需加入映射表计算每个表达式中单词到单词距离的总和，即可得到总表达式到表达式距离。