DIFFLIB gibt je nach Reihenfolge der Sequenzen ein anderes Verhältnis zurück

Question

Weiß jemand, warum diese beiden unterschiedlichen Verhältnisse zurückgeben?

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

Answer 1

Dies gibt einige Ideen, wie passend funktioniert.

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

Es sieht so aus, als ob es in der ersten Sequenz gegen die zweite so viel wie möglich übereinstimmt und von den Spielen fortgesetzt wird. In diesem Fall ('01017', '14260') liegt das rechte Match auf der 0, dem letzten Charakter, sodass keine weiteren Übereinstimmungen auf der rechten Seite möglich sind. In diesem Fall ('14260', '01017') ist das 1S -Match und die 0 noch verfügbar, sodass zwei Spiele gefunden werden.

Ich denke, der passende Algorithmus ist gegen sortierte Sequenzen kommutativ.

Answer 2

Ich arbeitete mit difflib In letzter Zeit, und obwohl diese Antwort zu spät ist, dachte ich, sie könnte der Antwort ein wenig Gewürz hinzufügen Hughdbrown wie es zeigt, was visuell passiert.

Bevor ich zum Code -Snippet gehe, lassen Sie mich das zitieren Dokumentation

Die Idee ist, die am längsten zusammenhängende passende Subsequenz zu finden, die keine "Junk" -Elemente enthält. Diese "Junk" -Elemente sind solche, die in gewissem Sinne uninteressant sind, wie leere Zeilen oder Whitespace. (Der Handling -Junk ist eine Erweiterung des Algorithmus Ratcliff und Overshelp.) Die gleiche Idee wird dann rekursiv auf die Teile der Sequenzen links und rechts von der passenden Subsequenz angewendet. Dies liefert keine minimalen Bearbeitungssequenzen, sondern neigt dazu, Übereinstimmungen zu ergeben, die den Menschen „richtig aussehen“.

Ich denke, den ersten Zeichenfolge zu vergleichen gegen der zweite und dann Spiele finden Sieht richtig aus genügend zu Menschen. Dies wird gut in der Antwort von erklärt von Hughdbrown.

Versuchen Sie nun, diesen Code -Snippet auszuführen:

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)

Ausgabe:

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

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

Die Teile in Klammern ({}) sind die passenden Teile. Ich habe gerade verwendet SequenceMatcher.get_matching_blocks() Um die passenden Blöcke in Zahnspangen zu bringen, um eine bessere Sichtbarkeit zu erhalten. Sie können den Unterschied deutlich erkennen, wenn die Reihenfolge umgekehrt ist. Mit der ersten Bestellung gibt es 4 Übereinstimmungen, so dass das Verhältnis ist 2*4/16=0.5. Aber wenn die Bestellung umgekehrt ist, gibt es jetzt 5 Übereinstimmungen, so dass das Verhältnis wird 2*5/16=0.625. Das Verhältnis wird als angegeben berechnet Hier in der Dokumentation