# Optimal algorithm for finding all ngrams from a pre-defined set in a text

I'm thinking about the optimal algorithm for the following problem:

Input data:

• a text, say it's an article about 5-50 pages.
• a set of ngrams (ngram strings, n>2), of arbitrary length, could be more than 20k n-grams.

The algorithm should output the following:

• a dictionary of all ngrams that were found in the text with the corresponding quantities, it should also take into account that ngrams could partially intersect or consist of each other (like 'probability density', 'probability density function', 'probability density distribution')

So the question is what would be the most time-efficient algorithm to compute this?

Both all words in a text and all words in ngrams are reduced to the canonical forms.

-

What you want to solve is a string matching problem. Wikipedia (and any textbook on the matter) contains a rich list of algorithms with their respective runtimes.

Be aware that they give worst-case runtimes. Different algorithms behave differently on natural text; some perform better because of the large alphabet and some worst because of its repetitive nature. Therefore, you should benchmark the respective algorithms with data similar to which you expect to get.

-

You could construct a DFA that recognizes the given set of ngrams. Some of the states signify that a certain ngram has just been read, so if you keep track of all the states the DFA is in, you know all occurrences of the ngrams in the text.

-
Thanks a lot, do you know what will be the running time for such algorithm? I guess it will depend on the size of the ngram set, –  dragoon Jan 16 '13 at 20:27
I'm not sure what is the fastest way to construct such a DFA, but you could Google it. –  Yuval Filmus Jan 16 '13 at 20:44
For finite sets of patterns, even the minimal DFA can be huge (i.e. exponential size). There are algorithms better suited to the task. –  Raphael Jan 16 '13 at 21:15
@dragoon, the running time is linear in the text; but the building-the-DFA phase can take a long time. Something like the KMP algorithm would have to be invented (KMP searches for a single string). Or perhaps the algorithm behind fgrep(1) (the original one) is near what you are looking for? –  vonbrand Jan 27 '13 at 0:57
@Raphael, in the worst case the minimal DFA will have one state for each symbol in the patterns, not exponential. –  vonbrand Jan 27 '13 at 0:58
show 1 more comment

Following up on Yuval, I would build a tree structure so that you can find the $n$-grams. Store the number of matches of each $n$-gram in the corresponding leaf. (It is similar to a DFA, but does not store links for 'missing' letters.)

In general my method for looking at multiple strings with overlap would be Aho-Corasick. It has "failure links" that tell where to continue when the next letter read from the input is not in the tree. It also handles the fact that if you reach a leaf (found an $n$-gram) then the maximal overlap with possible next match is known.

A problem with storing trees is the alphabet size. In the lower level of the trees a node will have many children, in upper levels the children are sparse. Done in the wrong way this leads to a waste of space.

-