3

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

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

2 に答える 2

3

これにより、マッチングがどのように機能するかについてのアイデアが得られます。

>>> 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'）、1が一致し、0は引き続き右側で一致するため、2つの一致が見つかります。

マッチングアルゴリズムは、ソートされたシーケンスに対して可換であると思います。

于 2012-02-17T02:35:58.593 に答える
1

私は最近一緒に仕事をしていて、この答えは遅いですが、視覚的に何が起こっているのかを示しているので、 hughdbrowndifflibによって提供された答えに少しスパイスを加えるかもしれないと思いました。

コードスニペットに進む前に、ドキュメントを引用させてください

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

最初の文字列を2番目の文字列と比較してから、一致するものを見つけることは、人々にとって十分に正しい と思います。これは、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ます。比率は、ドキュメントに記載されているように計算されます

于 2016-01-23T13:56:28.660 に答える