在R中进行非常快速的字符串模糊匹配

Question

我有一组 40,000 行 x 4 列的数据，需要将每一列与自己进行比较，以找到最接近的结果或最小的莱文斯坦距离。目的是为每一行获取一个“几乎相同”的副本。我用“adist”计算了一下，但速度似乎太慢。例如，对于只有一列的情况，将 5,000 行与整个数据集的 40,000 行进行比较，需要近两个小时的时间。对于 4 列来说，则需要 8 小时，对于整个数据集，则需要 32 小时。有没有更快的方法实现同样的效果？如果可能的话，我希望在 1 或 2 小时内完成。以下是我迄今为止所做的示例：

    #vector example
    a<-as.character(c("hello","allo","hola"))
    b<-as.character(c("hello","allo","hola"))
    
    #execution time
    start_time <- Sys.time()
    
    #Matrix with distance
    dist.name<-adist(a,b, partial = TRUE, ignore.case = TRUE)
    
    #time elapsed
    end_time <- Sys.time()
    end_time - start_time
    
    Output:
    Time difference of 5.873202 secs
    
    #result
    dist.name
          [,1] [,2] [,3]
    [1,]    0    4    5
    [2,]    2    0    2
    [3,]    5    4    0

期望输出（每行的最小距离，但同一行除外），但我需要更快的速度。

[1,] 4
[2,] 2
[3,] 4

- ecp

---

不知道是否适用于您的情况，但如果您知道有一些精确匹配项，我建议您首先通过执行 which(a%in%b) 来将其清除，然后再对剩余部分运行 Levenshtein 距离的代码。 - boski

值得一提的是，可以尝试使用 fuzzyjoin：通过使用 fuzzyjoin::stringdist_inner_join(df, df)，您可以基于一个或多个列将df中的每一行与其最接近的邻居进行匹配。它使用 stringdist 进行实际的距离计算，因此 Humpelstielzchen 的答案绝对是开始的地方。 - Marius

如果有多个距离相同的结果会发生什么？ - ecp

它将首先匹配具有两个邻居的行，您需要想出一种策略来过滤每行仅匹配1次。 - Marius

我会试一下，这可能会改善我需要的性能。fuzzyjoin是否有任何参数可用于过滤结果必须最少但<0，以避免相同的结果？ - ecp

Answer 1

你可以尝试使用stringsdist包。

该包使用C语言编写，采用并行处理技术，并提供各种距离度量标准，包括莱文斯坦距离。

library(stringdist)

a<-as.character(c("hello","allo","hola"))
b<-as.character(c("hello","allo","hola"))

start_time <- Sys.time()
res <- stringdistmatrix(a,b, method = "lv")
end_time <- Sys.time()

> end_time - start_time
Time difference of 0.006981134 secs
> res
     [,1] [,2] [,3]
[1,]    0    2    3
[2,]    2    0    3
[3,]    3    3    0


diag(res) <- NA
apply(res, 1, FUN = min, na.rm = T)
[1] 2 2 3

- Humpelstielzchen

---

这真的可以提高性能。我如何选择每行的最小结果及其关联字符串，但排除相同的值？ - ecp

太棒了——我本来想建议原帖作者编写一个Rcpp块，但这样做可以为他节省很多工作。 - Carl Witthoft

一旦我得到矩阵，我该如何对每行或每列进行排序？我的数据框有134781个观测值和176个变量，而且colnames()和rownames()的形式为V**。 - marine8115

为什么要对距离矩阵进行排序？ - Humpelstielzchen

Answer 2

我编写了一个R包zoomerjoin，它允许您模糊地连接大型数据集，而无需比较两个数据框之间的所有行对。这意味着您可以在现代数据科学笔记本电脑上在几秒钟或几分钟内合并中等大小（数百万行）的数据框，而不会耗尽内存。

以下是我如何使用该软件包来连接这些数据框：

devtools::install_github("beniaminogreen/zoomerjoin")
library(zoomerjoin)

a<-data.frame(string = c("hello","allo","hola"), id_1 = 1:3)
b<-data.frame(string = c("hello","allo","hola"), id_2 = 1:3)

jaccard_inner_join(a,b)
#   string.x id_1 string.y id_2
# 1     allo    2     allo    2
# 2     hola    3     hola    3
# 3    hello    1    hello    1

这将为您提供一组接近的数据框，然后您可以使用stringdist来找到每个最接近的匹配项，如果我正确理解了您的问题。

我曾经使用此软件包模糊连接具有数百万行的数据集，在几分钟内完成，所以它应该能够快速处理具有40k观测值的数据框。

- beniaminogreen