R: эффективный для памяти метод получения каждой перестановки слов в строке - PullRequest
Новая
       34

R: эффективный для памяти метод получения каждой перестановки слов в строке

4 голосов
/ 03 апреля 2019

У меня есть строка со списком слов, и я хочу получить из нее все возможные словосочетания.

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)

Это прекрасно работаеткогда строк относительно мало, но в реальном примере в общей сложности содержится 33 300 символов в 3350 строках со средней длиной строки 25 символов, что приводит к ошибке, аналогичной this:

Ошибка в вставке (unlist (sapply (seq (length (v1))), function (i) apply (combn (v1,: результат превысил бы 2 ^ 31-1 байт)

Я пытался изменитьutils::combn до RcppAlgos::comboGeneral внутри функции, потому что она, по-видимому, * на 1022 * быстрее , но все же столкнулась с той же проблемой.

Ответы [ 3 ]

2 голосов
/ 04 апреля 2019

У нас есть довольно эффективная функция для векторизованных скипграмм и нграмм в quanteda . Попробуйте это, с многопоточностью для эффективности (вы можете изменить потоки на максимум вашей системы): 

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"
2 голосов
/ 04 апреля 2019

Если у вас есть три слова 

fruits <- "Apple Banana Cherry"

, комбинации могут быть выражены с помощью 0 или 1 для обозначения включения каждого слова.Это будет означать, что с тремя словами у вас есть 2 ^ 3 - 1 = 7 опций, исключая нуль: 

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) различных возможных комбинаций, что займет больше места, чем все жесткие диски вмир.

Я не имею в виду, что это неразрешимая проблема, и моя область опыта не состоит в том, чтобы судить, будут ли другие ответы эффективно выполнять то, что вы хотите, но я просто хотелзаметить, что будут физические ограничения, делающие нецелесообразным предварительный расчет и сохранение всех возможных комбинаций так, как предлагает вопрос.

1 голос
/ 04 апреля 2019

Чтобы не усложнять вопрос, я пропустил, что в конечном итоге я хотел создать список этих комбинаций.

Я также не знал, как называется токенизация с Skip-Gram . Несмотря на то, что в конечном итоге он все еще медленный, это решение позволяет избежать ошибки памяти R и, обладая достаточной вычислительной мощностью, делает свое дело: 

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