Difflibは、シーケンスの順序に応じて異なる比率を返します

Question

なぜこれら2つが異なる比率を返す理由を知っていますか。

>>> 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

2番目に対する最初のシーケンスでできる限り一致し、試合から続くように見えます。この場合（ '01017'、 '14260'）、右側の一致は0で最後の文字であるため、右側のそれ以上の一致は不可能です。この場合（ '14260'、 '01017'）、1Sの一致と0は右側で一致する可能性があるため、2つの一致が見つかります。

一致するアルゴリズムは、ソートされたシーケンスに対して通勤していると思います。

Answer 2

私は一緒に働いていました difflib 最近、この答えは遅れていますが、私はそれが提供された答えに少しスパイスを加えるかもしれないと思いました ヒュードブラウン 視覚的に何が起こっているかを示しているので。

コードスニペットに行く前に、引用させてください ドキュメンテーション

アイデアは、「ジャンク」要素が含まれていない最長の連続的なマッチングサブシーケンスを見つけることです。これらの「ジャンク」要素は、空白の線や空白など、何らかの意味で面白くない要素です。 （ハンドリングジャンクは、RatcliffおよびOberShelpアルゴリズムの拡張です。）同じアイデアが、一致するサブセクセンスの左と右側のシーケンスの断片に再帰的に適用されます。 これは最小限の編集シーケンスを生成するものではありませんが、人々に「正しい」一致をもたらす傾向があります。

最初の文字列を比較すると思います に対して 2番目のものとその後、一致を見つけます 正しく見えます 足りる 人々に。これは、答えでうまく説明されています ヒュードブラウン.

今、このコードスニペットを試してみてください：

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. 。比率は、与えられたとおりに計算されます ここのドキュメントで