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)

当行数较少时，这种方法可以很好地工作。但在实际例子中，共有3350行，总共有93300个字符，其中字符串长度的中位数为25个字符，导致出现类似于此类错误：

Error in paste(unlist(sapply(seq(length(v1)), function(i) apply(combn(v1, : result would exceed 2^31-1 bytes

我尝试将函数中的utils::combn更改为RcppAlgos::comboGeneral，因为它显然更快速，但仍遇到了相同的问题。有没有解决这个问题的建议？

- rsylatian

---

这看起来像是一个非常大的数字，超过了大多数计算机可以处理的范围。粗略地说，即使你只允许最多10个单词组合，你已经有大约3,000 ^ 10个选项，或者约为10^44？那将需要约1 PB的空间才能列出这些数字，更不用说给它们分配字符串了。也许还有你没有提到的更多限制条件，可能会让这变得更容易？ - Jon Spring

这将是一个非常庞大的字符串。即使只有1,000个单词，也有大约2.7E299个500个单词的组合。包括所有长度的所有子集将会有大约1.07E301个组合。 - eipi10

我正在使用一台大型的EC2实例。 - rsylatian

只是出于好奇，你打算用这个包含所有可能组合的字符串做什么呢？如果你能提供更多上下文信息，我们或许可以想出比生成一个巨大的组合字符串更高效的解决方案。 - eipi10

它的目的是通过反向连接一个关键词集合中的部分匹配项与另一个关键词集合进行间隙分析。 - rsylatian

Answer 1

我们在quanteda中拥有一个非常高效的向量化skipgrams和ngrams函数。尝试使用此函数，它支持多线程以提高效率（您可以根据系统的最大线程数进行更改）：

Original Answer翻译成"最初的回答"

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"

- Ken Benoit

Answer 2

最初的回答

如果你有三个词

fruits <- "Apple Banana Cherry"

使用0或1表示每个单词的包含情况，可以表达出组合。这意味着在三个单词中，您有7种选项，排除空值：2^3-1。

最初的回答：

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（1.2E24）种不同的可能组合，这将需要比世界上所有硬盘驱动器更多的空间。

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

Translated:

我们可以把它看作是二进制计数。所有三个单词的组合都可以用三位表示，而且有2^3-1=7个选项。

存储每个组合的问题在于，随着每个额外的单词，这个列表的长度将翻倍。当你有80个单词时，每个可能的组合将需要80位来表示，但是会有2^80-1=大约1.2E24种不同的可能组合，这将需要比世界上所有硬盘驱动器更多的空间。

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

- Jon Spring

Answer 3

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

我也不知道这个名字叫做使用Skip-Gram进行令牌化。虽然最终仍然很慢，但这个解决方案避免了R内存错误，并且有足够的计算能力，可以完成任务：

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

- rsylatian