What is a simple fuzzy string matching algorithm in Python?
Question: 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](http://en.wikipedia.org/wiki/Levenshtein_distance) 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.


Answer: I like [Drew's answer](http://stackoverflow.com/questions/2923420/fuzzy-
string-matching-algorithm-in-python/2923488#2923488).

You can use [difflib](http://docs.python.org/library/difflib.html) 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
    

