在R语言中实现快速字符串匹配

Question

我正在尝试在一个庞大的数据集中进行单词匹配。我想知道是否有一种方法可以加速工作流程中最慢的操作。

我的目标是找到单词字典和单词向量列表之间的匹配位置。

words <- c("cat", "dog", "snake", "cow")
scores <- c(1.5, 0.7, 3.5, 4.6)
dic <- data.frame(words, scores)

wordList <- list(c("jiraffe", "dog"), c("cat", "elephant"), c("snake", "cow"))

到目前为止，我发现最快的方法是这样做：

matches <- function(wordList) {
    subD <- which(dic$words %in% wordList)
}

我期望的输出是：

matches(wordList):
list(c(2), c(1), c(3, 4))

我之后可以通过执行以下操作来获取每个wordList单元格的平均分数

averageScore <- sapply(matches, function(x) {mean(dic[x, "scores"]})

在函数中，有比我现在使用的字符串匹配方法更快的方法吗？

subD <- which(dic$words %in% wordList)

我尝试了dplyr的方法，认为它可能更快，使用“filter”首先获取“dic”的子集并在其上应用“colMeans”，但速度似乎慢了两倍。

此外，将我的匹配函数在循环中运行与对其使用“lapply”一样慢。

我错过了什么吗？有没有一种比两者都更快的方法？

- alexvicegrab

---

有一些用于快速匹配的包，例如 fastmatch；以及 data.table 包中的 chmatch 函数。很可能，这些包的性能要优于我们在基本 R 中编写的几行代码。 - Frank

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - Forrest R. Stevens

为了扩展Forrest的评论，你可以先用列表（适合输入组），然后转换为mydf <- data.frame(w=unlist(wordList),g=rep(1:length(wordList),sapply(wordList,length)))以进行更快速的分析。 - Frank

交替地，ww <- setNames(wordList,1:length(wordList)); stack(ww)。最好一开始就为列表中的组分配合理的名称，这样第一步就不是必需的。 - Frank

如果你的数据实际上很大（无法放入内存），那么你不应该使用R。而且，如果你要进行多次匹配，那么你应该使用btree。 - user1133275

Answer 1

这里有一个选项：

library(data.table)
nn <- lengths(wordList)  ## Or, for < R-3.2.0, `nn <- sapply(wordList, length)` 
dt <- data.table(grp=rep(seq_along(nn), times=nn), X = unlist(wordList), key="grp")
dt[,Score:=scores[chmatch(X,words)]]
dt[!is.na(Score), list(avgScore=mean(Score)), by="grp"]
#    grp avgScore
# 1:   1     0.70
# 2:   2     1.50
# 3:   3     4.05

- Josh O'Brien

---

谢谢Josh，这个解决方案非常优雅，比我原来的快多了！ - alexvicegrab