difflib根据序列的顺序返回不同的比率

Question

有人知道为什么这两个返回不同的比率吗？

>>> import difflib
>>> difflib.SequenceMatcher(None, '10101789', '11426089').ratio()
0.5
>>> difflib.SequenceMatcher(None, '11426089', '10101789').ratio()
0.625

Answer 1

This给出了匹配是如何工作的一些想法。

>>> import difflib
>>> 
>>> def print_matches(a, b):
...     s =  difflib.SequenceMatcher(None, a, b)
...     for block in s.get_matching_blocks():
...         print "a[%d] and b[%d] match for %d elements" % block
...     print s.ratio()
... 
>>> print_matches('01017', '14260')
a[0] and b[4] match for 1 elements
a[5] and b[5] match for 0 elements
0.2
>>> print_matches('14260', '01017')
a[0] and b[1] match for 1 elements
a[4] and b[2] match for 1 elements
a[5] and b[5] match for 0 elements
0.4

它看起来似乎在第一个序列上与第二个序列尽可能多地匹配，并从匹配中继续。在这种情况下('01017'，'14260')，右边的匹配是在0上，也就是最后一个字符上，所以右边不可能有更多的匹配。在这种情况下('14260'，'01017')，1匹配，0仍然可以在右边匹配，所以找到了两个匹配。

我认为匹配算法对排序序列是可交换的。

Answer 2

我最近在使用difflib，虽然这个答案太晚了，但我认为它可能会给hughdbrown提供的答案增加一点趣味，因为它直观地显示了正在发生的事情。

在我进入代码片段之前，让我引用一下documentation

的想法是找到不包含“垃圾”元素的最长的连续匹配子序列；这些“垃圾”元素是在某种意义上没有意义的元素，例如空行或空格。(处理垃圾是Ratcliff和Obershelp算法的扩展。)然后，将相同的思想递归地应用于匹配子序列左侧和右侧的序列片段。这不会产生最小的编辑序列，但确实倾向于产生对人们来说“看起来正确”的匹配。

我认为将第一个字符串与第二个字符串进行比较，然后找到匹配的，对人们来说，是正确的。hughdbrown在答案中很好地解释了这一点。

现在尝试运行以下代码片段：

def show_matching_blocks(a, b):
    s = SequenceMatcher(None, a, b)
    m = s.get_matching_blocks()
    seqs = [a, b]

    new_seqs = []
    for select, seq in enumerate(seqs):
        i, n = 0, 0
        new_seq = ''
        while i < len(seq):
            if i == m[n][select]:
                new_seq += '{' + seq[m[n][select]:m[n][select] + m[n].size] + '}'
                i += m[n].size
                n += 1
            elif i < m[n][select]:
                new_seq += seq[i:m[n][select]]
                i = m[n][select]
        new_seqs.append(new_seq)
    for seq, n in zip(seqs, new_seqs):
        print('{} --> {}'.format(seq, n))
    print('')

a, b = '10101789', '11426089'
show_matching_blocks(a, b)
show_matching_blocks(b, a)

输出：

10101789 --> {1}{0}1017{89}
11426089 --> {1}1426{0}{89}

11426089 --> {1}{1}426{0}{89}
10101789 --> {1}0{1}{0}17{89}

大括号内的部分({})是匹配的部分。我只是使用SequenceMatcher.get_matching_blocks()将匹配的块放在大括号中，以获得更好的可见性。当顺序颠倒时，您可以清楚地看到不同之处。对于第一个订单，有4个匹配，因此比率为2*4/16=0.5。但当顺序颠倒时，现在有5个匹配项，因此比率变为2*5/16=0.625。该比率按给定的here in the documentation计算