Large, approximate string matching algorithm
February 12, 2010 11:41 AM Subscribe
I have two large (10k-100k) sets of strings. I want to match the items in the sets up in pairs based on similarity. Levenshtein looks promising but costly.
posted by chairface to technology (15 answers total) 4 users marked this as a favorite
I have a set of strings. Say:
And another (possibly of different length):
I want to pair them up based on similarity:
kitten55 - smitten45
buicks - bucks
aspire - aspirin
ice cream -
The Levenshtein distance algorithm seems like a good approach but is O(NM) on string lengths in run time, and would need to run across every possible pairing (well, not exactly but still essentailly O(N^2)). This seems awful, given the 10K-100K size of my input sets.
Is there a better way? Can I compile a string into a DFA of some sort suitable for approximate match scoring that I can reuse, rather than trying to evaluate each possible pairing? I'm open to other solutions as well.