具有许多字符串的字符串中每个元素的最佳匹配

Question

输入数据：

a <- c("coca cola","hot coffee","Running Shoes","Table cloth",
       ”mobile phones under 5000”,”Amazon kindle”)
b <- c("running shoes","plastic cup","pizza","Let’s go to hill","motor van",
       "coffee table","drinking coffee on a rainy day",”Best mobile phones under 10000”,
       ”kindle e-books”,”Coffee Cup”)

将向量（此处为向量a）的每个句子的每个单词与单独的向量（此处为向量b）中的所有字符串逐字匹配，并获得最佳匹配。

逻辑：矢量“a”的所有句子必须逐字地与矢量“b”的所有句子匹配，并且必须计算百分比。每个句子的矢量“a”只能有一个最佳匹配。

示例1：向量“a”中的“跑鞋”与向量“b”中的“跑鞋”完美匹配，percentage_match为100％（因为两个单词匹配）

示例2：“热咖啡”的最佳匹配可能是“在下雨天喝咖啡”或“咖啡桌”或“咖啡杯”，百分比匹配为50％（因为只有“咖啡”，与“热咖啡”相匹配） “在所有情况下）。在这种情况下，如果有多个竞争者具有相同的最大percentage_match，我们将选择具有最低字符串长度的最佳匹配，即“咖啡桌”和“咖啡杯”优先于“在下雨天喝咖啡”。即使在这样做之后，也有一个平局，我们可以自由选择任何东西（即“咖啡桌”或“咖啡杯”，可以是“热咖啡”的最佳搭配。

代码尝试：

as <- strsplit(a, " ")
bs <- strsplit(b, " ")

matchFun <- function(x, y) length(intersect(x, y)) / length(x) * 100
mx <- outer(as, bs, Vectorize(matchFun))

m <- apply(mx, 1, which.max)  # the maximum column of each row

z <- unlist(apply(mx, 1, function(x) x[which.max(x)]))  # maximum percentage
z[z == 0] <- NA  # this gives you the NA if you want it

data.frame(a, Matching_String=b[m], match_perc=z)

面临的问题：由于我的实际数据非常大（超过200万条记录与1条Mn记录相匹配），因此该代码将永远存在。

Answer 1

这是使用stringdistmatrix包中的stringdist实现此目的的一种方法。基本上，我们正在计算a和b中字符串之间的距离。然后我们保持最小的距离。即使距离很大，总会有匹配。您可以做的一件事是建立最小距离，否则建立NA。

library(stringdist)
m <- stringdistmatrix(tolower(a), tolower(b), method = "qgram")
b[apply(m, 1, which.min)]

#[1] "plastic cup"                    "coffee table"                   "running shoes"                 
#[4] "coffee table"                   "best mobile phones under 10000" "kindle e-books"