高效字符串相似性分组

Question

场景：我有一个关于人的数据，包括他们父母的姓名，我想要找到兄弟姐妹（即父母姓名相同的人）。

Translated text:

场景：我有一个关于人的数据，包括他们父母的姓名，我想要找到兄弟姐妹（即父母姓名相同的人）。

 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，允许两个字符的差异。但如果其他变体例如“最长公共子串”运行更快，那么也可以使用。

对于较小的子样本，我在循环中使用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编码而不是拉丁字母（天城体）
• 预处理以删除未使用的字符等已完成

- sheß

---

你的for循环不起作用。此外，你应该提供在你正在工作的规模下的示例数据... - minem

我希望你能理解，出于保密原因，我无法提供实际数据。 - sheß

问题：检查pdata$parents_name[1:i]的距离不是更好吗？第一项始终是它自己的family_id（因为尚未分配其他family id）。然后，只需要将第二项与第一项进行比较，因为其他项都尚未分配family_id。 - Adam Sampson

如果这些示例足够接近您的实际情况，则您可能不需要计算所有成对距离，您可以考虑如果它们之间的距离小于4，则认为2个字符串具有相同的family_id，并且将family_id的第一个实例视为规范实例，如果您拥有相当数量的family_id实例，速度会更快。可以通过围绕“+”进行分割并放弃长度非常不同的配对（例如超过3个字符）来进行额外的距离筛选。 - moodymudskipper

Answer 1

有两个挑战：

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

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

为了让我的语言使用清晰明了，以下是我们的定义：

- 我们想要测量表达式之间的Levenstein距离。 - 每个表达式都有两个部分，父母A全名和父母B全名，它们由加号分隔。 - 部分（或全名）是一系列单词，由空格或破折号分隔，并对应于人的名字和姓氏。 - 我们假设每个部分中的单词数最多为6个（您的示例具有2或3个单词的部分，我假设我们最多可以有6个）部分中的单词顺序很重要（该部分始终是名字后跟姓氏，绝不是姓氏先，例如Jack John和John Jack是两个不同的人）。 - 有400万个表达式。 - 表达式仅包含英文字符。数字、空格、标点符号、破折号和任何非英文字符都可以忽略。 - 我们假设易匹配项已经完成（例如精确的表达式匹配），我们不需要搜索精确匹配项。

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

实际上，我们创建了两个列表，它们是最初的400万个表达式列表的精确副本。我们称之为左侧列表和右侧列表。在复制列表之前，每个表达式都被分配了一个表达式ID。

我们的目标是找到右侧列表中与左侧列表条目的Levenstein距离小于2的条目，但排除相同的条目（相同的表达式ID）。

我建议采用两步方法分别解决两个挑战。第一步将减少可能匹配表达式的列表，第二步将简化Levenstein距离测量，因为我们只查看非常接近的表达式。所使用的技术是任何传统的数据库服务器，因为我们需要为性能对数据集进行索引。 挑战A 挑战A是减少距离测量次数。我们从大约1600万亿(4百万的平方)开始，不应超过几千万或几百万。在这里使用的技术是在完整表达式中搜索至少一个相似单词。根据数据的分布情况，这将显著减少可能匹配的对数。或者，根据结果所需的准确度，我们也可以搜索具有至少两个相似单词或至少一半相似单词的对。

从技术上讲，我建议将表达式列表放在表中。添加标识列以创建每个表达式的唯一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个临时表中收集输出，并运行一个union查询以获得所有具有至少一个相同单词的潜在匹配表达式的缩短列表。这是我们挑战A的解决方案。现在我们拥有了最有可能匹配的几对的缩短列表。该列表将包含数百万条记录（左侧和右侧条目的对），但不会超过数十亿。

挑战B的目标是批处理简化的Levenstein距离（而不是在循环中运行它）。首先，我们应该就什么是简化的Levenstein距离达成一致。首先，我们同意两个表达式的Levenstein距离是它们具有相同索引的所有单词的Levenstein距离之和。我的意思是两个表达式的Levenstein距离是它们的前两个单词的距离，加上它们的第二个单词的距离等等。其次，我们需要发明一个简化的Levenstein距离。我建议使用n-gram方法，只使用2个字符的克，其索引绝对差小于2。例如：peter和pieter之间的距离如下计算：

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-gram或4-gram或允许大于2个gram序列差异。但是，这个想法是执行比传统的Levenstein算法更少的每对计算。

然后我们需要将其转换为技术解决方案。我之前做过的是：首先隔离单词：由于我们只需要测量单词之间的距离，然后按表达式累加这些距离，因此我们可以通过在单词列表上运行distinct select来进一步减少计算数量（我们已经在前一节中准备好了单词列表）。

这种方法需要一个映射表，用于跟踪表达式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 L.gram = R.gram 
AND ABS(L.gram_seq + R.gram_seq)< 2 
AND L.word_id <> R.word_id 

距离是两个单词中最长单词的长度减去匹配字节的数量。SQL非常快地进行这样的查询，我认为一台只有8GB内存的简单计算机可以在合理的时间范围内轻松处理数亿行。

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

- JeromeE

---

顺便提一下，如果这个速度还是太慢，有一个解决方案可以提高性能：用数字替换2元组-在侧面构建一个包含所有可能的2元组的映射表。由于可能的2元组数量很少（假设我们只处理2元组），使用SMALLINT而不是CHAR（2）将大大提高JOIN查询性能。我们只需要计算匹配的2元组数量，不需要知道它们最初由哪些字母组成。 - JeromeE

值得一提的是，4^2 = 16百万（而不是兆级）两两比较并不正确。正确的数量应该是4（4-1）/2 = 6百万次比较。4（4-1）因为不需要进行自我比较，并且除以二，因为比较是（应该是）无序的。仍然有很多工作要做，但远远少于16。 - Brooks Ambrose

Answer 2

您正在使用stringdist包，那么stringdist::phonetic()是否符合您的需求？它为每个字符串计算soundex代码，例如：

phonetic(pdata$parents_name)
[1] "P361" "P361" "A655" "J225"

Soundex是一种经过实践考验的方法（已有近100年历史），用于哈希姓名，这意味着您不需要比较每一对观测值。

您可能希望进一步分别对父亲和母亲的名字进行Soundex编码。

- Neal Fultz

---

好主意，但我的名字是用天城文/尼泊尔语写的，我认为soundex处理不太好。 - sheß

这个通用的想法应该是可行的，你只需要自己指定元音和辅音即可。 - Neal Fultz

或者您可以尝试先将数据转换为英文，例如使用https://github.com/prabhasp/Nepali-Language-Tools/blob/master/transliterate_ne2en.py作为预处理步骤。 - Neal Fultz

Answer 3

我的建议是使用数据科学方法，仅识别相似（同一簇）的名称，并使用stringdist进行比较。

我已经对生成“parents_name”的代码进行了一些修改，在接近现实情况的场景中增加了更多的名字变量。

num<-4e6
#Random length
random_l<-round(runif(num,min = 5, max=15),0)
#Random strings in the first and second name
parent_rand_first<-stringi::stri_rand_strings(num, random_l)
order<-sample(1:num, num, replace=F)
parent_rand_second<-parent_rand_first[order]
#Paste first and second name
parents_name<-paste(parent_rand_first," + ",parent_rand_second)
parents_name[1:10]

现在开始进行真正的分析，首先从名称中提取特征，例如全局长度、第一个名称的长度、第二个名称的长度、两个名称中元音和辅音的数量（以及其他有趣的内容）。

之后将所有这些特征绑定起来，并将数据框聚类到高数量的簇中（例如1000个）。

features<-cbind(nchars,nchars_first,nchars_second,nvowels_first,nvowels_second,nconsonants_first,nconsonants_second)
n_clusters<-1000
clusters<-kmeans(features,centers = n_clusters)

仅在每个包含相似名称对的聚类内部应用stringdistmatrix

dist_matrix<-NULL
for(i in 1:n_clusters)
{
  cluster_i<-clusters$cluster==i

  parents_name<-as.character(parents_name[cluster_i])

  dist_matrix[[i]]<-stringdistmatrix(parents_name,parents_name,"lv")
}

在dist_matrix中，您可以获得每个聚类元素之间的距离，并且可以使用此距离分配family_id。

为了计算每个聚类中的距离（在此示例中），代码需要大约1秒钟（取决于聚类的维度），在15分钟内计算出所有距离。

警告：dist_matrix增长非常快，在您的代码中最好在di循环内部分析它，提取famyli_id，然后可以将其丢弃。

- Terru_theTerror

Answer 4

你可以通过不对所有行进行比较来提高效率。 相反，创建一个新变量，用于决定是否值得进行比较。

例如，创建一个名为“score”的新变量，其中包含父母姓名中使用的字母的有序列表（例如，“peter pan + marta steward”则得分为“ademnprstw”），并仅在得分匹配的行之间计算距离。

当然，你可以找到更适合你需求的评分，并稍微改进以便在不共用全部字母时也能进行比较。

- MrSmithGoesToWashington

---

我喜欢这种方法，但是我缺乏一个能够捕捉最常见差异的好分数。正如我所说，我已经使用了整体长度的差异，并且我开始额外使用第一个辅音（因为差异在很大程度上源于元音的替代拼写）。但这有点太过严格了。你有更多建议吗？ - sheß

也许可以分别对辅音和元音打分（使用相同的原则），并在至少有一个匹配时进行比较。也许，只需针对您语言中最常用的字母执行此操作（请参阅维基百科中的字母频率）。 - MrSmithGoesToWashington

在聚类阶段，您可以为每个字母添加一个功能，计算名字中每个字母的数量。 - Terru_theTerror

可能是这样的：parents_name <- c("彼得潘+玛塔斯图尔特", "皮特潘+玛塔斯图尔特", "阿明·多尔格纳+简·约翰娜·道", "杰克·杰克逊+其他人") alphagrep <- function (x) { res <- NULL for (i in letters) {res <- c(res, grepl(i, x))} res }sum(alphagrep(parents_name[1]) + alphagrep(parents_name[2]) == 1) sum(alphagrep(parents_name[1]) + alphagrep(parents_name[3]) == 1) sum(alphagrep(parents_name[1]) + alphagrep(parents_name[4]) == 1)根据您的需要，可以比较总和是否小于1、2等。 - MrSmithGoesToWashington

Answer 5

我几年前也遇到了同样的性能问题。我需要基于人们输入的名字匹配重复项。我的数据集有20万个名称，矩阵方法不起作用了。经过几天的搜索，我找到了一个更好的方法，在几分钟内完成了工作：

library(stringdist)

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

person_id <- 1:length(parents_name)

family_id <- vector("integer", length(parents_name))


#Looping through unassigned family ids
while(sum(family_id == 0) > 0){

  ids <- person_id[family_id == 0]

  dists <- stringdist(parents_name[family_id == 0][1], 
                      parents_name[family_id == 0], 
                      method = "lv")

  matches <- ids[dists <= 3]

  family_id[matches] <- max(family_id) + 1
}

result <- data.frame(person_id, parents_name, family_id)

这样，每次迭代时while会比较更少的匹配项。从此，您可以实现不同的性能提升器，例如在比较之前过滤具有相同首字母的名称等。

- Anderson Neisse

Answer 6

在非传递关系上制作等价组没有意义。如果A像B，B像C，但A不像C，那么你如何从中建立家族关系呢？使用类似 Soundex 这样的东西（这是 Neal Fultz 的想法，而不是我的）似乎是唯一有意义的选择，并且它还解决了性能问题。

- Antonín Lejsek

---

传递性确实是一个问题。然而，从对数据的首次检查中看来，名称差异已足够大，所以如果A=B和B=C，则将A~=C视为可行。这可以在单个简单的后处理步骤中处理。 - sheß

Answer 7

我用来减少这种名称匹配中所涉及的排列组合的方法是创建一个函数，该函数计算涉及的名字(姓氏)中的音节数。然后将其作为预处理值存储在数据库中。这就成为了一个音节哈希函数。

然后您可以选择将具有相同音节数的单词分组在一起。(虽然我使用允许1或2个音节差异的算法，这可能被视为合法的拼写/打字错误...但我的研究发现95%的拼写错误都具有相同数量的音节)

在这种情况下，Peter和Pieter将具有相同的音节数(2)，但Jones和Smith则没有(它们只有1个)。(例如)

如果您的函数未能为Jones获取1个音节，则可能需要增加您的容忍度，以允许在您使用的音节哈希函数分组中至少有1个音节差异。(为了解决不正确的音节函数结果，并捕获正确匹配姓氏的分组)

我的音节计数函数可能不完全适用 - 因为您可能需要处理非英文字母集...(所以我没有粘贴代码...它是用C编写的) 请注意 - 音节计数函数不必在真实音节数方面准确; 它只需要作为可靠的哈希函数即可 - 而它确实做到了。比依赖第一个字母准确的SoundEx要好得多。

试一试吧，通过实现音节哈希函数，您可能会惊讶地发现有多少改进。您可能需要向SO寻求帮助，将该函数转换成您的语言。

- Grantly

Answer 8

它会复制您的输出，我猜您将不得不决定部分匹配的标准，我保留了默认的 agrep 标准。

pdata$parents_name<-as.character(pdata$parents_name)
x00<-unique(lapply(pdata$parents_name,function(x) agrep(x,pdata$parents_name)))
x=c()
for (i in 1:length(x00)){
  x=c(x,rep(i,length(x00[[i]])))
}
pdata$person_id=seq(1:nrow(pdata))
pdata$family_id=x

- Antonios

Answer 9

如果我理解正确，您想将每个父母对（即父母名称数据框中的每一行）与所有其他对（行）进行比较，并保留Levenstein距离小于或等于2的行。

我已经为此编写了以下代码：

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

fuzzy_match <- list()
system.time(for (i in 1:nrow(pdata)){
  fuzzy_match[[i]] <- cbind(pdata, parents_name_2 = pdata[i,"parents_name"],
                            dist = as.integer(stringdist(pdata[i,"parents_name"], pdata$parents_name)))
  fuzzy_match[[i]] <- fuzzy_match[[i]][fuzzy_match[[i]]$dist <= 2,]
})
fuzzy_final <- do.call(rbind, fuzzy_match)

它返回了你想要的结果吗？

- Mislav

---

它确实可以（除了不符合我问题中指定的格式，但无妨）。然而，你的解决方案并不高效，一旦使用了几百万条观察数据，它就会崩溃。 - sheß

可以使用并行计算（foreach循环）使其更快。什么意思是它崩溃了？ - Mislav

我所说的“分解”是指需要100000年才能完成，您可以使用我在问题中提供的第二个代码来获取更大的数据集，然后您会发现您的代码表现非常糟糕。 - sheß