R:获取字符串中每个单词排列的内存高效方法

Question

我有一个带有单词列表的字符串，我想从中获取所有可能的单词组合。

fruits <- "Apple Banana Cherry"

要获取此输出，请执行以下操作：

"Apple, Banana, Cherry, Apple Banana, Apple Cherry, Banana Cherry, Apple Banana Cherry"

使用此处定义的函数，稍作修改：

f1 <- function(str1){
v1 <- strsplit(str1, ' ')[[1]]
paste(unlist(sapply(seq(length(v1)), function(i)
apply(combn(v1, i), 2, paste, collapse=" "))), collapse= ', ')
}
f1(fruits)

当行相对较少时，这工作正常，但实际示例在 3,350 行中总共有 93,300 个字符，字符串长度中位数为 25 个字符，导致类似于以下内容的错误：

粘贴中的错误(unlist(sapply(seq(length(v1))， function(i) apply(combn(v1， ： 结果将超过 2^31-1 字节

我尝试在函数中将utils::combn更改为RcppAlgos::comboGeneral，因为它显然更快，但仍然遇到同样的问题。有什么解决方法吗？

Answer 1

我们有一个非常有效的函数，用于量化中的矢量化跳跃图和 ngram。 试试这个，使用多线程提高效率(您可以将线程更改为系统的最大值)：

library("quanteda")
## Package version: 1.4.3
## Parallel computing: 2 of 12 threads used.
## See https://quanteda.io for tutorials and examples.
## 
## Attaching package: 'quanteda'
## The following object is masked from 'package:utils':
## 
##     View
quanteda_options(threads = 4)
fruits <- "Apple Banana Cherry"
tokens(fruits) %>%
tokens_skipgrams(., n = seq_len(ntoken(.)), skip = 0:ntoken(.), concatenator = " ") %>%
as.character() %>%
paste(collapse = ", ")
## [1] "Apple, Banana, Cherry, Apple Banana, Apple Cherry, Banana Cherry, Apple Banana Cherry"

Answer 2

如果你有三个单词

fruits <- "Apple Banana Cherry"

这些组合可以通过使用 0 或 1 来表示包含每个单词。 这意味着使用三个单词，您有 2^3 - 1 = 7 个选项，不包括 null：

001 Cherry
010 Banana
011 Banana, Cherry
100 Apple
101 Apple, Cherry
110 Apple, Banana
111 Apple, Banana, Cherry

因此，我们可以将其视为二进制计数。所有三个单词的组合都可以用三个位表示，并且有 2^3 - 1 = 7 个选项。

存储每个组合的问题在于，此列表的长度将随着每个额外的单词而增加一倍。当你有 80 个单词时，表达每个可能的组合需要 80 位，但会有 2^80 - 1 = 大约 1,200,000,000,000,000,000,000,000,000 (1.2E24) 不同的可能组合，这将比世界上所有的硬盘驱动器占用更多的空间。

我并不是要暗示这是一个无法解决的问题，判断其他答案是否会以有效的方式做你想要的事情也不是我的经验领域，但我只是想观察一下，会有物理限制，使得以问题提出的方式预先计算和存储所有可能的组合是不切实际的。

Answer 3

为了简单起见，我省略了我最终想要做的是创建这些组合的列表。

我也不知道这个名字是用Skip-Gram标记化。虽然最终仍然很慢，但此解决方案避免了 R 内存错误，并且具有足够的计算能力，它可以解决问题：

library(tokenizers)
unlist(tokenize_skip_ngrams(fruits, n = 3, n_min = 1, k = 3))