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

Question

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

fruits <- "Apple Banana Cherry"

要获得此输出：

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

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

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 个字符，导致类似于 this:

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

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

Answer 1

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

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

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

Answer 2

我们在 quanteda 中有一个非常有效的矢量化 skipgrams 和 ngrams 函数。试试这个，使用多线程提高效率（您可以将线程数更改为系统的最大值）：

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 3

如果你有三个字

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 (1.2E24) 种不同的可能组合，这将比所有的 space世界上的硬盘。

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

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

R: Memory-Efficient Method of Getting Every Word Permutation within a String

nlp

r

permutation

out-of-memory