How to predict in advance a kwic search that will take a very long time?

[kbenoit]

What would be reasonable limits on what we allow a user to ask for the pattern matching functions? It appears to be an issue mainly in the number of patterns. Below, the number of patterns in stopwords("en") is 175, so 160/8.5 = 18.8 is not bad, but it's till 2.5 minutes of frozen console.

Maybe we could issue a warning and ask to proceed if the user tries to fit more than a vector of 10 patterns? We could set this limit and the prompt with warning as global options.

library(quanteda)
## Package version: 1.9.9007

data_corpus_guardian <- as.corpus(quanteda.corpora::download("data_corpus_guardian"))

# ndoc = 6000
system.time(
  kw1 <- kwic(data_corpus_guardian, "the")
)
##    user  system elapsed 
##   8.473   0.445   8.615

# compare with longer documents
data_corpus_guardiansents <- corpus_reshape(data_corpus_guardian, to = "sentences")
system.time(
  kw3 <- kwic(data_corpus_guardiansents, "the")
)
##    user  system elapsed 
##  12.248   0.388  11.803

# with shorter documents
data_corpus_guardianonebig <-
  corpus(texts(data_corpus_guardian, groups = rep(1, ndoc(data_corpus_guardian))))
system.time(
  kw4 <- kwic(data_corpus_guardianonebig, "the")
)
##    user  system elapsed 
##   6.233   0.377   6.653

# not really ok
system.time(
  kw2 <- kwic(data_corpus_guardian, stopwords("en"))
)
##    user  system elapsed 
## 160.170   5.907 125.154

[koheiw]

It takes a lot of time to construct data.frame actually. When it is too large for human inspection, isn't it nice to add something like pagination?

[kbenoit]

The view of the data.frame using DT already does this, e.g. View.kwic(). Did you have something else in mind?

[koheiw]

DT has pagination, but it is still a large kwic data.frame with all rows. My idea is to qatd_cpp_kwic() to return from i to i + n rows of the data.frame. Here len is the total number of rows in the data.frame. The following section (from L101) is data.frame construction, which takes looooong time.

quanteda/src/kwic_mt.cpp

Lines 86 to 99 in fca7399

	#if QUANTEDA_USE_TBB
	kwic_mt kwic_mt(texts, temp, spans, set_words);
	parallelFor(0, texts.size(), kwic_mt);
	#else
	for (std::size_t h = 0; h < texts.size(); h++) {
	temp[h] = kwic(texts[h], spans, set_words);
	}
	#endif
	// Get total number of matches
	std::size_t len = 0;
	for (std::size_t h = 0; h < temp.size(); h++) {
	len += temp[h].size();
	}

We can even split below and above L101 into different functions that pass intermediate kwic objects.

[koheiw]

The best solution would be to change KWIC object from data.frame to tokens with locations of keywords saved in the object meta field as data.frame (the same as the first three columns of current kwic) using the technique explored in #1912. With the new kwic object, print.kwic will generate the concordance view per users request with max_ndoc. KWIC cache is reset every time tokens is updated.

[kbenoit]

😱The slippery slope of being able to modify objects without assignment!!

Seriously though if we attached kwic to tokens, then we would not be able to have multiple and distinct kwics as objects, without copying the entire tokens object.

Also the issue here is knowing in advance how long a search will take. How would that search differ if we pass tokens by value to kwic() versus searching a tokens object directly before attaching the kwic results to the tokens object? It's the search time, not the passing of the object, that consumes the time I thought.

[koheiw]

KWIC's search in not always the slowest part. Conversion from tokens to string can be the slowest. This is what we can slash dramatically by making a intermediate object.

> quanteda_options(threads = 8)
> corp <- as.corpus(quanteda.corpora::download("data_corpus_guardian"))
> toks <- tokens(corp)
> kw <- kwic(toks, "th*")
'Search keywords'    2070.99 millsec
'Create strings'     4364.16 millsec
'Create data.frame'  1.91384 millsec

[kbenoit]

Wow, ok. How about making a copy of the tokens then and storing the kwic as a (sub)set of the tokens along with positions in the original? Is that possible?

[koheiw]

Unlike summary, we can return tokens with special class ("kwic2"?) with keyword positions in the object meta. This is straight forward.

However, this is really slow because of a different reason.

system.time(
  kw2 <- kwic(data_corpus_guardian, stopwords("en"))
)
##    user  system elapsed 
## 160.170   5.907 125.154

I noticed that C++ function is called length(stopwords("en")) times in a for loop...

[kbenoit]

Yikes. Something to work on then.

[koheiw]

Then, we are ready to make more fundamental changes.