Difflib devuelve una relación diferente dependiendo del orden de las secuencias

Question

¿Alguien sabe por qué estos dos devuelven diferentes proporciones?

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

Answer 1

Este Da algunas ideas sobre cómo funciona el emparejamiento.

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

Parece que coincide tanto como puede en la primera secuencia contra la segunda y continúa desde los partidos. En este caso ('01017', '14260'), el partido derecho está en el 0, el último carácter, por lo que no son posibles más coincidencias a la derecha. En este caso ('14260', '01017'), la coincidencia de 1S y el 0 todavía están disponibles para que coincidan a la derecha, por lo que se encuentran dos coincidencias.

Creo que el algoritmo coincidente es conmutativo contra secuencias ordenadas.

Answer 2

Estaba trabajando con difflib Últimamente, y aunque esta respuesta es tarde, pensé que podría agregar un poco de especia a la respuesta proporcionada por hughdbrown Como muestra lo que está sucediendo visualmente.

Antes de ir al fragmento del código, déjame citar el documentación

La idea es encontrar la posterior posterior de coincidencia contigua que no contenga elementos "basura"; Estos elementos "basura" son poco interesantes en algún sentido, como líneas en blanco o espacios en blanco. (El manejo de la basura es una extensión del algoritmo de Ratcliff y Obershelp.) La misma idea se aplica de manera recursiva a las piezas de las secuencias a la izquierda y a la derecha de la posterior posterior. Esto no produce secuencias de edición mínima, pero tiende a producir coincidencias que "parecen bien" a las personas.

Creo que comparar la primera cadena contra el segundo y luego encontrar partidos se ve bien suficiente A la gente. Esto se explica muy bien en la respuesta por hughdbrown.

Ahora intente ejecutar este fragmento de código:

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)

Producción:

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

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

Las partes dentro de los aparatos ({}) son las partes coincidentes. Acabo de usar SequenceMatcher.get_matching_blocks() Poner los bloques coincidentes dentro de los aparatos ortopédicos para una mejor visibilidad. Puede ver claramente la diferencia cuando el pedido se invierte. Con el primer orden, hay 4 partidos, por lo que la relación es 2*4/16=0.5. Pero cuando el pedido se invierte, ahora hay 5 coincidencias, por lo que la relación se vuelve 2*5/16=0.625. La relación se calcula como se da aquí en la documentación