1
$\begingroup$

I have thousands of documents, and a term list with thousands of entries. The entries in the term list range in length from an acronym of two characters to a 14-word phrase with 96 characters. I would like to find every occurrence of any term in the term list in each document in the order that they appear.

I have created two test implementations so far: one using the Aho-Corasick algorithm and the other using n-gram matching. I tested them both on a medium-sized document (8 MB). The Aho-Corasick algorithm came up with over 8700 matches in 24 seconds. This would be great, except that I would like to use a fuzzy matching algorithm, and Aho-Corasick only finds exact matches. N-gram matching found 9600 matches, since some of them are approximate, but it took 885 seconds!

As such, I would like suggestions on an efficient fuzzy matching algorithm for finding matches from a set of strings. Is there any way to modify the current code I have for the Aho-Corasick algorithm so that it can take into account Levenshtein distance? I have found some other questions on this site that are related, but I didn't feel like they solved my problem. Thanks.

$\endgroup$

1 Answer 1

1
$\begingroup$

One approach: Build a BK tree containing the terms in your term list. Given any word $w$, this lets you efficiently find the term that is closest to $w$ in Levenshtein edit distance.

Now the problem becomes easy. Do a linear scan over the document. For each word, look it up in the BK tree to find the closest match in your term list, and if it is close enough, output it.

Alternatively, you could read Peter Norvig's tutorial on spell checking, and the references he lists there, and try using that. They might be especially effective if your fuzzy matching only considers very small Levenshtein edit distance (e.g., distance 1 or 2).

$\endgroup$
3
  • $\begingroup$ I found an implementation of the BK tree and tested it out a bit. I feel like it would work well if all the terms in my term list were just one word. The BK tree can certainly hold multi-word phrases, but how, when scanning the document, would I determine whether to look up a single word in it or a group of words? $\endgroup$ Commented Jun 22, 2018 at 13:51
  • 1
    $\begingroup$ @MikeBorkland, oh, good point, I missed that on the first read. Two ideas: (1) insert just the first word of the phrase in the BK-tree; if it matches a query word, check against the whole phrase; (2) build one BK-tree for phrases of length 1, one BK-tree for phrases of length 2, one for phrases of length 3, etc.; then at each position in the document, check all lengths of phrases against the corresponding BK-tree. $\endgroup$
    – D.W.
    Commented Jun 22, 2018 at 16:06
  • $\begingroup$ I tried the first idea in your comment, and I believe it may work. I'm sill adjusting some of the parameters, but it is much faster than the n-gram matching. It is still quite a bit slower than the Aho-Corasick algorithm, but I guess that is to be expected for any fuzzy matching algorithm. $\endgroup$ Commented Jun 26, 2018 at 16:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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