You forgot the first parameter to SequenceMatcher.
>>> import difflib
>>>
>>> a='abcd'
>>> b='ab123'
>>> seq=difflib.SequenceMatcher(None, a,b)
>>> d=seq.ratio()*100
>>> print d
44.4444444444
http://docs.python.org/library/difflib.html
Answer from Lennart Regebro on Stack OverflowYou forgot the first parameter to SequenceMatcher.
>>> import difflib
>>>
>>> a='abcd'
>>> b='ab123'
>>> seq=difflib.SequenceMatcher(None, a,b)
>>> d=seq.ratio()*100
>>> print d
44.4444444444
http://docs.python.org/library/difflib.html
From the docs:
The SequenceMatcher class has this constructor:
class difflib.SequenceMatcher(isjunk=None, a='', b='', autojunk=True)
The problem in your code is that by doing
seq=difflib.SequenceMatcher(a,b)
you are passing a as value for isjunk and b as value for a, leaving the default '' value for b. This results in a ratio of 0.0.
One way to overcome this (already mentioned by Lennart) is to explicitly pass None as extra first parameter so all the keyword arguments get assigned the correct values.
However I just found, and wanted to mention another solution, that doesn't touch the isjunk argument but uses the set_seqs() method to specify the different sequences.
>>> import difflib
>>> a = 'abcd'
>>> b = 'ab123'
>>> seq = difflib.SequenceMatcher()
>>> seq.set_seqs(a.lower(), b.lower())
>>> d = seq.ratio()*100
>>> print d
44.44444444444444
Videos
SequenceMatcher.ratio internally uses SequenceMatcher.get_matching_blocks to calculate the ratio, I will walk you through the steps to see how that happens:
SequenceMatcher.get_matching_blocksReturn list of triples describing matching subsequences. Each triple is of the form
(i, j, n), and means thata[i:i+n] == b[j:j+n]. The triples are monotonically increasing iniandj.The last triple is a dummy, and has the value
(len(a), len(b), 0). It is the only triple withn == 0.If (i, j, n)and(i', j', n')are adjacent triples in the list, and the second is not the last triple in the list, theni+n != i'orj+n != j'; in other words, adjacent triples always describe non-adjacent equal blocks.
ratio internally uses SequenceMatcher.get_matching_blocks 's results, and sums the sizes of all matched sequences returned bySequenceMatcher.get_matching_blocks. This is the exact source code from difflib.py:
matches = sum(triple[-1] for triple in self.get_matching_blocks())
The above line is critical, because the result of the above expression is used to compute the ratio. We'll see that shortly and how it impacts the calculation of the ratio.
>>> m1 = SequenceMatcher(None, "Ebojfm Mzpm", "Ebfo ef Mfpo")
>>> m2 = SequenceMatcher(None, "Ebfo ef Mfpo", "Ebojfm Mzpm")
>>> matches1 = sum(triple[-1] for triple in m1.get_matching_blocks())
>>> matches1
7
>>> matches2 = sum(triple[-1] for triple in m2.get_matching_blocks())
>>> matches2
6
As you can see, we have 7 and 6. These are simply the sums of the matched subsequences as returned by get_matching_blocks. Why does this matter? Here's why, the ratio is computed in the following way, (this is from difflib source code):
def _calculate_ratio(matches, length):
if length:
return 2.0 * matches / length
return 1.0
length is len(a) + len(b) where a is the first sequence and b being the second sequence.
Okay, enough talk, we need actions:
>>> length = len("Ebojfm Mzpm") + len("Ebfo ef Mfpo")
>>> m1.ratio()
0.6086956521739131
>>> (2.0 * matches1 / length) == m1.ratio()
True
Similarly for m2:
>>> 2.0 * matches2 / length
0.5217391304347826
>>> (2.0 * matches2 / length) == m2.ratio()
True
Note: Not all SequenceMatcher(None a,b).ratio() == SequenceMatcher(None b,a).ratio() are False, sometimes they can be True:
>>> s1 = SequenceMatcher(None, "abcd", "bcde").ratio()
>>> s2 = SequenceMatcher(None, "bcde", "abcd").ratio()
>>> s1 == s2
True
In case you're wondering why, this is because
sum(triple[-1] for triple in self.get_matching_blocks())
is the same for both SequenceMatcher(None, "abcd", "bcde") and SequenceMatcher(None, "bcde", "abcd") which is 3.
My answer does not provide exact details of the observed problem, but contains a general explanation of why such things may happen with loosely defined diffing methods.
Essentially everything boils down to the fact that, in the general case,
more than one common subsequences of the same length can be extracted from a given pair of strings, and
longer common subsequences may appear less natural to a human expert than a shorter one.
Since you are puzzled by this particular case let's analyze common subsequence identification on the following pair of strings:
my stackoverflow mysteriesmystery
To me, the natural match is "MYSTER", as follows:
my stackoverflow MYSTERies
.................MYSTERy..
However, the longest match fully covers the shorter of the two strings as follows:
MY STackovERflow mYsteries
MY.ST.....ER......Y.......
The drawback of such a match is that it introduces multiple matching sub-blocks whereas the (shorter) natural match is contiguous.
Therefore, diffing algorithms are tweaked so that their outputs are more pleasing to the final user. As a result, they are not 100% mathematically elegant and therefore don't possess properties that you would expect from a purely academic (rather than practical) tool.
The documentation of SequenceMatcher contains a corresponding note:
class difflib.SequenceMatcherThis is a flexible class for comparing pairs of sequences of any type, so long as the sequence elements are hashable. The basic algorithm predates, and is a little fancier than, an algorithm published in the late 1980’s by Ratcliff and Obershelp under the hyperbolic name “gestalt pattern matching.” The idea is to find the longest contiguous matching subsequence that contains no “junk” elements (the Ratcliff and Obershelp algorithm doesn’t address junk). The same idea is then applied recursively to the pieces of the sequences to the left and to the right of the matching subsequence. This does not yield minimal edit sequences, but does tend to yield matches that “look right” to people.