R Optimizing double loop that uses stri_extract

Question

I have been working on some text scraping/analysis. One thing I did was pull out the top words from documents to compare and learn about different metrics. This was fast and easy. There became an issue with defining what separators to use though and pulling out individual words rather than phrases removed information from the analysis. For example .Net Developer becomes net and developer after the transformation. I already had a list of set phrases/words from an old project someone else gave up on. The next step was pulling out specific keywords from multiple rows for multiple documents.

I have been looking into several techniques including vectorization, parallel processing, using C++ code within R and others. Moving forward I will experiment with all of these techniques and try and speed up my process as well as give me these tools for future projects. In the mean time (without experimentation) I'm wondering what adjustments are obvious which will significantly decrease the time taken e.g. moving parts of the code outside the loop, using better packages etc I also have a progress bar, but I can remove it if its slowing down my loop significantly.

Here is my code:

words <- read.csv("keyphrases.csv")
df <- data.frame(x=(list.files("sec/new/")))
total = length(df$x)
pb <- txtProgressBar(title = "Progress Bar", min = 0, max =total , width = 300, style=3)

for (i in df$x){
          s <- read.csv(paste0("sec/new/",i))
          u <- do.call(rbind, pblapply(words$words, function(x){
              t <- data.frame(ref= s[,2], words = stri_extract(s[,3], coll=x))
              t<-na.omit(t)
          }))
          write.csv(u,paste0("sec/new_results/new/",i), row.names = F)
          setTxtProgressBar(pb, i, title=paste( round(which(df$x== i)/total*100, 2),"% done"))
      }

So words has 60,000 rows of words/short phrases - no more than 30 characters each. Length i is around 4000 where each i has between 100 and 5000 rows with each row having between 1 and 5000 characters. Any random characters/strings can be used if my question needs to be reproducible.

I only used lapply because combining it with rbind and do.call worked really well, having a loop within a loop may be slowing down the process significantly too.

So off the bat there are somethings I can do right? Swapping data.frame to data.table or using vectors instead. Do the reading and writing outside the loop somehow? Perhaps write it such that one of the loops isnt nested?

Thanks in advance

EDIT

The key element that needs speeding up is the extract. Whether I use lapply above or cut it down to:

for(x in words$words){t<-data.table(words=stri_extract(s[,3], coll=x))}

This still takes the most time for a long way. skills and t are data tables in this case.

EDIT2

Attempting to create reproducible data:

set.seed(42)    
words <- data.frame(words=rnorm(1:60000))
    words$wwords <- as.String(words$words)

set.seed(42)
     file1 <- data.frame(x=rnorm(1:5000))
     file1$x<-as.String(file1$x)

     pblapply(words$words, function(x){
         t <- data.frame(words = stri_extract(file1$x, coll=x))
     })

Answer 1

First things first. Yes, I would definitely switch from data.frame to data.table. Not only is it faster and easier to use, when you start merging data sets data.table will do reasonable things when data.frame will give you unexpected and unintended results.

Secondly, is there an advantage to using R to take care of your separators? You mentioned a number of different techniques you are considering using. If separators are just noise for the purposes of your analysis, why not split the work into two tools and use a tool that is much better at handling separators and continuation lines and so on? For me, Python is a natural choice to do things like parsing a bunch of text into keywords--including stripping off separators and other "noise" words you do not care about in your analysis. Feed the results of the Python parsing into R, and use R for its strengths.

There are a few different ways to get the output of Python into R. I would suggest starting off with something simple: CSV files. They are what you are starting with, they are easy to read and write in Python and easy to read in R. Later you can deal with a direct pipe between Python and R, but it does not give you much advantage until you have a working prototype and it is a lot more work at first. Make Python read in your raw data and turn out a CSV file that R can drop straight into a data.table without further processing.

As for stri_extract, it is really not the tool you need this time. You certainly can match on a bunch of different words, but it is not really what it is optimized for. I agree with @Chris that using merge() on data.tables is a much more efficient--and faster--way to search for a number of key words.

Answer 2

Single Word Version

When you have single words in each lookup, this is easily accomplished with merging:

library(data.table)

#Word List
set.seed(42)
WordList <- data.table(ID = 1:60000, words = sapply(1:60000, function(x) paste(sample(letters, 5), collapse = '')))

#A list of dictionaries
set.seed(42)
Dicts <- list(
  Dict1 = sapply(1:15000, function(x) {
    paste(sample(letters, 5), collapse = '')
  }),
  Dict2 = sapply(1:15000, function(x) {
    paste(sample(letters, 5), collapse = '')
  }),
  Dict3 = sapply(1:15000, function(x) {
    paste(sample(letters, 5), collapse = '')
  })
)

#Create Dictionary Data.table and add Identifier
Dicts <- rbindlist(lapply(Dicts, function(x){data.table(ref = x)}), use.names = T, idcol = T)

# set key for joining
setkey(WordList, "words")
setkey(Dicts, "ref")

Now we have a data.table with all dictionary words, and a data.table with all words in our word list. Now we can just merge:

merge(WordList, Dicts, by.x = "words", by.y = "ref", all.x = T, allow.cartesian = T)
       words    ID   .id
    1: abcli 30174 Dict3
    2: abcrg 26210 Dict2
    3: abcsj  8487 Dict1
    4: abczg 24311 Dict2
    5: abdgl  1326 Dict1
   ---                  
60260: zyxeb 52194    NA
60261: zyxfg 57359    NA
60262: zyxjw 19337 Dict2
60263: zyxoq  5771 Dict1
60264: zyxqa 24544 Dict2

So we can see abcli appears in Dict3, while zyxeb does not appear in any of the dictionaries. There look to be 264 duplicates (words that appear in >1 dictionary), as the resultant data.table is larger than our word list (60264 > 60000). This is shown as follows:

merge(WordList, Dicts, by.x = "words", by.y = "ref", all.x = T, allow.cartesian = T)[words == "ahlpk"]
   words    ID   .id
1: ahlpk  7344 Dict1
2: ahlpk  7344 Dict2
3: ahlpk 28487 Dict1
4: ahlpk 28487 Dict2

We also see here that duplicated words in our word list are going to create multiple resultant rows.

This is very very quick to run

Phrases + Sentences

In the case where you are searching for phrases within sentences, you will need to perform a string match instead. However, you will still need to make n(Phrases) * n(Sentences) comparisons, which will quick hit memory limits in most R data structures. Fortunately, this is an embarrassingly parallel operation:

Same setup:

library(data.table)
library(foreach)
library(doParallel)


# Sentence List
set.seed(42)
Sentences <- data.table(ID = 1:60000, Sentence = sapply(1:60000, function(x) paste(sample(letters, 10), collapse = '')))

# A list of phrases
set.seed(42)
Phrases <- list(
  Phrases1 = sapply(1:15000, function(x) {
    paste(sample(letters, 5), collapse = '')
  }),
  Phrases2 = sapply(1:15000, function(x) {
    paste(sample(letters, 5), collapse = '')
  }),
  Phrases3 = sapply(1:15000, function(x) {
    paste(sample(letters, 5), collapse = '')
  })
)

# Create Dictionary Data.table and add Identifier
Phrases <- rbindlist(lapply(Phrases, function(x){data.table(Phrase = x)}), use.names = T, idcol = T)

# Full Outer Join
Sentences[, JA := 1]
Phrases[, JA := 1]

# set key for joining
setkey(Sentences, "JA")
setkey(Phrases, "JA")

We now want to break up our Phrases table into manageable batches

cl<-makeCluster(4)
registerDoParallel(cl)

nPhrases <- as.numeric(nrow(Phrases))
nSentences <- as.numeric(nrow(Sentences))

batch_size <- ceiling(nPhrases*nSentences / 2^30) #Max data.table allocation is 2^31. Lower this if you are hitting memory allocation limits
seq_s <- seq(1,nrow(Phrases), by = floor(nrow(Phrases)/batch_size))
ln_s <- length(seq_s)
if(ln_s > 1){
  str_seq <- paste0(seq_s,":",c(seq_s[2:ln_s],nrow(Phrases) + 1) - 1)
} else {
  str_seq <- paste0(seq_s,":",nrow(Phrases))
}
  

We are now ready to send our job out. The grepl line below is doing the work - testing which phrases match each sentence. We then filter out any non-matches.

ls<-foreach(i = 1:ln_s) %dopar% {
  
  library(data.table)
  TEMP_DT <- merge(Sentences,Phrases[eval(parse(text = str_seq[1]))], by = "JA", allow.cartesian = T)
  TEMP_DT <- TEMP_DT[, match_test := grepl(Phrase,Sentence), by = .(Phrase,Sentence)][match_test == 1]
  return(TEMP_DT)
  
}

stopCluster(cl)


DT_OUT <- unique(do.call(rbind,ls))

DT_OUT now summarizes the sentences that match, along with the Phrase + Phrase list that it is found in.

This still will take some time (as there is a lot of processing that is necessary) , but nowhere near a year.