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

Question

有谁知道为什么这两个返回不同的比率。

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

Answer 1

这给出了一些关于匹配如何工作的想法。

>>> 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提供的答案增添一点情趣，因为它可以直观地显示正在发生的事情。

在我进入代码片段之前，让我引用文档

这个想法是找到不包含“垃圾”元素的最长连续匹配子序列；这些“垃圾”元素在某种意义上是无趣的，例如空行或空格。（处理垃圾是 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。该比率按照文档中给出的此处计算