Fuzzy string matching algorithm in Python

Question

Hi guys,

I'm trying to find some sort of a good, fuzzy string matching algorithm. Direct matching doesn't work for me — this isn't too good because unless my strings are a 100% similar, the match fails. The Levenshtein method doesn't work too well for strings as it works on a character level. I was looking for something along the lines of word level matching e.g.

String A: The quick brown fox.

String B: The quick brown fox jumped over the lazy dog.

These should match as all words in string A are in string B.

Now, this is an oversimplified example but would anyone know a good, fuzzy string matching algorithm that works on a word level.

Thanks in advance.

Answer 1

If all you want to do is to test whether or not all the words in a string match another string, that's a one liner:

if not [word for word in b.split(' ') if word not in a.split(' ')]:
    print 'Match!'

If you want to score them instead of a binary test, why not just do something like:

((# of matching words) / (# of words in bigger string)) * ((# of words in smaller string) / (# of words in bigger string))

?

If you wanted to, you could get fancier and do fuzzy match on each string.

Answer 2

I like Drew's answer.

You can use difflib to find the longest match:

>>> a = 'The quick brown fox.'
>>> b = 'The quick brown fox jumped over the lazy dog.'
>>> import difflib
>>> s = difflib.SequenceMatcher(None, a, b)
>>> s.find_longest_match(0,len(a),0,len(b))
Match(a=0, b=0, size=19) # returns NamedTuple (new in v2.6)

Or pick some minimum matching threshold. Example:

>>> difflib.SequenceMatcher(None, a, b).ratio()
0.61538461538461542

Answer 3

You could modify the Levenshtein algorithm to compare words rather than characters. It's not a very complex algorithm and the source is available in many languages online.

Levenshtein works by comparing two arrays of chars. There is no reason that the same logic could not be applied against two arrays of strings.

Answer 4

I did this some time ago with C#, my previous question is here. There is starter algorith for your interest, you can easily transform it to python.

Ideas you should use writing your own algorithm is something like this:

• Have a list with original "titles" (words/sentences you want to match with).
• Each title item should have minimal match score on word/sentence, ignore title as well.
• You also should have global minimal match percentage of final result.
• You should calculate each word - word Levenshtein distance.
• You should increase total match weight if words are going in the same order (quick brown vs quick brown, should have definitively higher weight than quick brown vs. brown quick.)