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

Question

有没有人知道为什么这两个返回的比例不一样呢？

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

Answer 1

我最近在使用 difflib，虽然这个回答来得有点晚，但我觉得可以为 hughdbrown 提供的答案增添一些视觉上的解释。

在进入代码片段之前，我想引用一下 文档。

这个想法是找到最长的连续匹配子序列，这个子序列中不包含任何“垃圾”元素；这些“垃圾”元素是指在某种意义上不重要的元素，比如空行或空格。（处理垃圾元素是 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。这个比例的计算方法可以在 文档中找到。

Answer 2

这个链接提供了一些关于匹配是如何工作的想法。

>>> 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在右边仍然可以继续匹配，所以找到了两个匹配。

我觉得这个匹配算法在对已经排序的序列进行比较时是可以互换的。