String similarity metrics in Python

user_121793 0
Viewed 51909

I want to find string similarity between two strings. en.wikipedia has examples of some of them. code.google has a Python implementation of Levenshtein distance.
Is there a better algorithm, (and hopefully a Python library), under these constraints:

  1. I want to do fuzzy matches between strings. eg matches('Hello, All you people', 'hello, all You peopl') should return True
  2. False negatives are acceptable, False positives, except in extremely rare cases are not.
  3. This is done in a non realtime setting, so speed is not (much) of concern.
  4. [Edit] I am comparing multi word strings.

Would something other than Levenshtein distance(or Levenshtein ratio) be a better algorithm for my case?

levenshtein-distance edit-distance algorithm python string
7 Answers

To avoid false positives, the method nratio() from the library ngramratio may help.

>>> pip install ngramratio

>>> from ngramratio import ngramratio
>>> SequenceMatcherExtended = ngramratio.SequenceMatcherExtended

>>> a = 'Hi there'
>>> b = 'Hit here'

>>> seq=SequenceMatcherExtended(a=a.lower(), b=b.lower())

>>> seq.ratio()
>>> 0.875
>>> seq.nratio(1) #this replicates `seq.ratio`.
>>> 0.875

>>> seq.nratio(2)
>>> 0.75

>>> seq.nratio(3)
>>> 0.5

nratio(n) only matches n-grams of length >= n.

You can pick a value for n, say n = 2, and create a boolean similarity function as Nadia did in a previous reply.

def similar(seq1, seq2):
    return SequenceMatcherExtended(a=seq1.lower(), b=seq2.lower()).nratio(2) > 0.8

>>> similar(a, b)
False
>>> similar('Hi there', 'Hi ther')
True
user_191399550
Related