difflib retourne rapport différent en fonction de l'ordre des séquences

Question

Quelqu'un sait pourquoi ces deux différents rapports retour.

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

Answer 1

Cette donne quelques idées sur la façon dont les travaux correspondant.

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

Il semble que si elle correspond à autant que possible sur la première séquence contre la seconde et continue des matchs. Dans ce cas ( « 01017 », « 14260 »), le match est sur la droite 0, le dernier caractère, donc pas d'autres matchs à droite sont possibles. Dans ce cas ( « 14260 », « 01017 »), les 1 match et le 0 est toujours disponible pour correspondre à droite, donc deux matches se trouvent.

Je pense que l'algorithme d'adaptation est commutatif contre des séquences triés.

Answer 2

Je travaillais avec difflib ces derniers temps, et bien que cette réponse est en retard, je pensais qu'il pourrait ajouter un peu de piquant à la réponse fournie par hughdbrown car il montre ce qui se passe visuellement.

Avant de passer à l'extrait de code, permettez-moi de citer le documentation

L'idée est de trouver la plus longue séquence de correspondance contiguë ne contient pas d'éléments « junk »; ces éléments « indésirables » sont ceux qui sont sans intérêt dans un certain sens, comme des lignes vides ou des espaces. (Indésirable de manutention est une extension de la Ratcliff et Obershelp algorithme.) La même idée est ensuite appliquée de manière récursive aux morceaux de les séquences à gauche et à droite de l'appariement séquence. Cela ne donne pas des séquences d'édition minimum, mais tend aux matches de rendement qui « droit de regard » aux gens.

Je pense que l'on compare la première chaîne contre la seconde puis trouver des correspondances regarde à droite assez aux gens. Ceci est expliqué bien dans la réponse par hughdbrown .

Maintenant, essayez et exécuter cet extrait de code:

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)

Sortie:

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

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

Les pièces à l'intérieur des accolades ({}) sont les parties correspondant. Je viens d'utiliser SequenceMatcher.get_matching_blocks() pour mettre les blocs correspondants dans les accolades pour une meilleure visibilité. Vous pouvez clairement voir la différence quand l'ordre est inversé. Avec le premier ordre, il y a 4 matches, de sorte que le ratio est 2*4/16=0.5. Mais quand l'ordre est inversé, il y a maintenant 5 matches, de sorte que le rapport devient 2*5/16=0.625. Le ratio est calculé comme indiqué ici dans la documentation