come diff/allineare gli elenchi Python usando la funzione di corrispondenza arbitraria?

Question

Vorrei allineare due elenchi in un modo simile a quello che farebbe difflib.Differ tranne che voglio essere in grado di definire una funzione di corrispondenza per confrontare gli elementi, non solo usare l'uguaglianza delle stringhe e preferibilmente una funzione di corrispondenza che può restituire un numero tra 0.0 e 1.0, non solo un booleano.

Così, per esempio, dire che ho avuto le due liste:

L1 = [('A', 1), ('B', 3), ('C', 7)] 
L2 = ['A', 'b', 'C'] 

e voglio essere in grado di scrivere una funzione partita come questa:

def match(item1, item2): 
    if item1[0] == item2: 
     return 1.0 
    elif item1[0].lower() == item2.lower(): 
     return 0.5 
    else: 
     return 0.0 

e poi fare:

d = Differ(match_func=match) 
d.compare(L1, L2) 

e avere diff con la funzione di corrispondenza. Come difflib, preferirei che l'algoritmo fornisse risultati di tipo Ratcliff-Obershelp più intuitivi piuttosto che una distanza puramente minima di Levenshtein.

Answer 1

che ho appena scritto questa implementazione di Needleman-Wunsch e sembra fare quello che voglio:

def nw_align(a, b, replace_func, insert, delete): 

    ZERO, LEFT, UP, DIAGONAL = 0, 1, 2, 3 

    len_a = len(a) 
    len_b = len(b) 

    matrix = [[(0, ZERO) for x in range(len_b + 1)] for y in range(len_a + 1)] 

    for i in range(len_a + 1): 
     matrix[i][0] = (insert * i, UP) 

    for j in range(len_b + 1): 
     matrix[0][j] = (delete * j, LEFT) 

    for i in range(1, len_a + 1): 
     for j in range(1, len_b + 1): 
      replace = replace_func(a[i - 1], b[j - 1]) 
      matrix[i][j] = max([ 
       (matrix[i - 1][j - 1][0] + replace, DIAGONAL), 
       (matrix[i][j - 1][0] + insert, LEFT), 
       (matrix[i - 1][j][0] + delete, UP) 
      ]) 

    i, j = len_a, len_b 
    align_a = "" 
    align_b = "" 

    while (i, j) != (0, 0): 
     if matrix[i][j][1] == DIAGONAL: 
      align_a += a[i - 1] 
      align_b += b[j - 1] 
      i -= 1 
      j -= 1 
     elif matrix[i][j][1] == LEFT: 
      align_a += "-" 
      align_b += b[j - 1] 
      j -= 1 
     else: # UP 
      align_a += a[i - 1] 
      align_b += "-" 
      i -= 1 

    return align_a[::-1], align_b[::-1] 

Answer 2

Recentemente ho trovato una discussione su un algoritmo chiamato patience diff che sembra piuttosto semplice. Potresti provare a implementarlo tu stesso, e poi ovviamente puoi usare qualsiasi algoritmo di confronto che ti piace.