2
$\begingroup$

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.

Improve this question
$\endgroup$
5
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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, $\endgroup$
    – dragoon
    Jan 16 '13 at 20:27
  • $\begingroup$ I'm not sure what is the fastest way to construct such a DFA, but you could Google it. $\endgroup$
    – Yuval Filmus
    Jan 16 '13 at 20:44
  • $\begingroup$ For finite sets of patterns, even the minimal DFA can be huge (i.e. exponential size). There are algorithms better suited to the task. $\endgroup$
    – Raphael ♦
    Jan 16 '13 at 21:15
  • $\begingroup$ @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? $\endgroup$
    – vonbrand
    Jan 27 '13 at 0:57
  • $\begingroup$ @Raphael, in the worst case the minimal DFA will have one state for each symbol in the patterns, not exponential. $\endgroup$
    – vonbrand
    Jan 27 '13 at 0:58
2
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

The standard answer to this was given by Bentley in "Programming Pearls": Sort this way [horizontal hand wave] then this way [vertical wave].

In more detail:

  • For each word in your dictionary, set up a signature computed by sorting its letters
  • Sort the dictionary by signatures

The set of anagrams are those with the same signature, it is now a simple matter to collect them.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks, but I still don't understand how finding anagrams (original problem) can help me in finding ngrams with the corresponding quantities. $\endgroup$
    – dragoon
    Feb 3 '13 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.