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

Question

我有一组 40.000 行 x 4 列，我需要将每一列与其自身进行比较，以便找到最接近的结果或最小编辑距离。这个想法是为每一行获得“几乎重复”。我已经用“adist”计算过，但似乎太慢了。例如，对于仅一列（5.000 行）而言，与所有列数据集（40.000 行）相比，需要近 2 小时。对于 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

Answer 1

你可以尝试

stringsdist

-package。

它是用 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

Answer 2

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

以下是我如何使用该包来加入这些数据框：

install.packages("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 观察值的数据框。