R - data.table быстрый поиск с регулярным выражением

Question

Таблица данных с двумя столбцами (3 грамма и их количеством), для которой установлен ключ в столбце ngrams. 3-граммы представляют собой односимвольный вектор из трех слов, разделенных пробелами.

set.seed(20182)

create.ngrams <- function(){
        w1 <- paste(sample(letters[1:5], 3, T), collapse = '')
        w2 <- paste(sample(letters[1:5], 3, T), collapse = '')
        w3 <- paste(sample(letters, 5, T), collapse = '')

        ngram <- paste(c(w1, w2, w3), collapse = " ")
        return(ngram)
}

dt <- data.table(ngrams = replicate(100000, create.ngrams()), N = sample.int(100, 100000, replace=T))

dt[ngrams %like% '^ada cab \\.*']

Что мне нужно получить, учитывая, что 2 грамма, сколько уникальных 3 граммов появятся в таблице 3 грамма с 2 граммами в качестве основы? До сих пор подход состоит в том, чтобы фильтровать 3-граммовые таблицы и получать количество строк, используя выражения регулярных выражений и функцию data.table %like%. К сожалению, в документации указано, что like не использует ключ таблицы.

Примечание. В текущей реализации не используются отсортированные ключи.

Это значительно замедляет фильтрацию:

dt[ngrams %like% '^ada cab \\.*']

          ngrams  N
1: ada cab jsfzb 33
2: ada cab rbkqz 43
3: ada cab oyohg 10
4: ada cab dahtd 87
5: ada cab qgmfb  8
6: ada cab ylyfl 13
7: ada cab izeje 83
8: ada cab fukov 12

microbenchmark(dt[ngrams %like% '^ada cab \\.*']))

Unit: milliseconds
                                expr     min      lq     mean  median       uq     max neval
 dt[ngrams %like% "^ada cab \\\\.*"] 22.4061 23.9792 25.89883 25.0981 26.88145 34.7454   100

В реальной таблице, с которой я работаю (nrow = 46856038), производительность слишком низкая для выполнения поставленной задачи:

Unit: seconds
                              expr      min       lq     mean   median       uq      max neval
 t[ngrams %like% "^on the \\\\.*"] 10.48471 10.57198 11.27199 10.77015 10.94827 17.42804   100

Что я могу сделать, чтобы улучшить производительность? Я попытался немного поработать с dplyr, но выигрыш не показался значительным.

Answer 1

Вы можете go с fixed= паттернами? Если вы добавляете пробел ко всем ngram с, это дает вам виртуальную «границу слова», позволяющую вам сделать гораздо более быстрый шаблон:

dt[, ngrams1 := paste0(" ", ngrams)]
dt
#                ngrams  N        ngrams1
#      1: dcd aee vxfba 99  dcd aee vxfba
#      2: cad bec alsmv 92  cad bec alsmv
#      3: ebe edd zbogd 90  ebe edd zbogd
#      4: aac ace miexa 26  aac ace miexa
#      5: aea cda ppyii 67  aea cda ppyii
#     ---                                
#  99996: cca bbc xaezc 58  cca bbc xaezc
#  99997: ebc cae ktacb 95  ebc cae ktacb
#  99998: bed abe dpjmc 92  bed abe dpjmc
#  99999: dde cdb frkfz 79  dde cdb frkfz
# 100000: bed bce ydawa 52  bed bce ydawa

dt[ngrams %like% '^ada cab \\.*']
#           ngrams  N        ngrams1
# 1: ada cab qbbiw 22  ada cab qbbiw
# 2: ada cab kpejz 16  ada cab kpejz
# 3: ada cab lighh  4  ada cab lighh
# 4: ada cab rxpmc 64  ada cab rxpmc

dt[grepl(' ada cab ', ngrams1, fixed = TRUE),]
#           ngrams  N        ngrams1
# 1: ada cab qbbiw 22  ada cab qbbiw
# 2: ada cab kpejz 16  ada cab kpejz
# 3: ada cab lighh  4  ada cab lighh
# 4: ada cab rxpmc 64  ada cab rxpmc

В тесте фиксированный шаблон равен 3 -4 раза быстрее:

microbenchmark::microbenchmark(
  a = dt[ngrams %like% '^ada cab \\.*'],
  b = dt[grepl('^ada cab', ngrams),],
  c = dt[ngrams1 %flike% ' ada cab ', ],
  d = dt[grepl(' ada cab ', ngrams1, fixed = TRUE),]
)
# Unit: milliseconds
#  expr       min        lq      mean    median        uq       max neval
#     a 20.299101 21.364401 22.088702 21.832000 22.444351 25.403801   100
#     b 20.605501 21.648101 22.656212 22.382001 23.384151 26.330201   100
#     c  4.337301  4.872151  5.265142  5.125251  5.500951  9.646201   100
#     d  4.301901  4.860501  5.221697  5.102000  5.465402  7.339400   100

Это не работает, если шаблон отклоняется от 3-3-5 (например, если у вас есть больше 3 с, где это может случайно совпадать, кроме первой пары 3 с) .