difflib restituisce rapporto differente secondo ordine delle sequenze

Question

Qualcuno sa perché questi due diversi rapporti di ritorno.

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

Answer 1

Questo dà alcune idee di come corrispondenti opere.

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

Sembra come se corrisponde a quanto si può sulla prima sequenza contro la seconda e continua dalle corrispondenze. In questo caso ( '01017', '14260'), la partita destra è sul 0, l'ultimo carattere, in modo che nessun ulteriore partite sulla destra sono possibili. In questo caso ( '14260', '01017'), i 1s Match e la 0 è ancora disponibile per abbinare a destra, quindi due sono riscontrate.

Credo che l'algoritmo di matching è contro commutativa allineati sequenze.

Answer 2

Stavo lavorando con difflib ultimamente, e anche se questa risposta è in ritardo, ho pensato che potrebbe aggiungere un po 'di pepe alla risposta fornita da hughdbrown come dimostra quello che sta accadendo visivamente.

Prima di andare al frammento di codice, vorrei citare il documentazione

L'idea è quella di trovare la più lunga sequenza corrispondente, che non contiene elementi "spazzatura"; questi elementi "spazzatura" sono quelli che sono non interessanti in un certo senso, come righe vuote o spazi. (Spazzatura Handling è un'estensione per il Ratcliff e Obershelp algoritmo.) La stessa idea viene quindi applicata in modo ricorsivo ai pezzi di le sequenze a sinistra ea destra della corrispondenza sotto sequenza. Questo non cede minimi modificare le sequenze, ma tende per le partite di rendimento che “look giusto” per le persone.

Credo che confrontando la prima stringa contro il secondo e poi trovare corrispondenze guarda a destra abbastanza per le persone. Questo è spiegato bene nella risposta da hughdbrown .

Ora provate ed eseguire questo frammento di codice:

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)

Output:

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

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

Le parti interne parentesi ({}) sono le parti corrispondenti. Ho appena usato SequenceMatcher.get_matching_blocks() di mettere i blocchi corrispondenti all'interno bretelle per una migliore visibilità. Si può vedere chiaramente la differenza quando l'ordine è invertito. Con il primo ordine, ci sono 4 partite, quindi il rapporto è 2*4/16=0.5. Ma quando l'ordine è invertito, ora ci sono 5 partite, in modo che il rapporto diventa 2*5/16=0.625. Il rapporto è calcolato come dato qui nella documentazione