как к разности / выравнивают списки Python с помощью произвольной функции соответствия?
Я хотел бы выровнять два списка похожим способом к какой difflib.Differ сделал бы кроме, я хочу смочь определить функцию соответствия для сравнения объектов, не только используют строковое равенство и предпочтительно функцию соответствия, которая может возвратить число между 0,0 и 1.0, не только булевская переменная.
Так, например, скажите, что у меня было два списка:
L1 = [('A', 1), ('B', 3), ('C', 7)]
L2 = ['A', 'b', 'C']
и я хочу смочь записать функцию соответствия как это:
def match(item1, item2):
if item1[0] == item2:
return 1.0
elif item1[0].lower() == item2.lower():
return 0.5
else:
return 0.0
и затем сделайте:
d = Differ(match_func=match)
d.compare(L1, L2)
и имейте его разность с помощью функции соответствия. Как difflib, Я быть бы, алгоритм дал более интуитивные результаты типа Ratcliff-Obershelp, а не чисто минимальное расстояние Левенштейна.
2 ответа
Я только что написал эту реализацию Needleman-Wunsch и, кажется, делает то, что я хочу:
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]
Недавно я наткнулся на обсуждение алгоритма под названием Patience diff , которое звучит довольно просто. Вы можете попробовать реализовать это самостоятельно, а затем, конечно, вы можете использовать любой алгоритм сравнения, который вам нравится.