# A fuzzy string matching algorithm for finding all occurrences from a set of strings in a large string

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.

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.