Как изменить / выровнять списки Python, используя функцию произвольного соответствия - PullRequest
Новая
       6

Как изменить / выровнять списки Python, используя функцию произвольного соответствия

7 голосов
/ 27 апреля 2010

Я бы хотел выровнять два списка аналогично тому, что сделал бы 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, я бы предпочел, чтобы алгоритм давал более интуитивные результаты типа Ратклифа-Обершельпа, а не чисто минимальное расстояние Левенштейна.

Ответы [ 2 ]

8 голосов
/ 27 апреля 2010

Я только что написал эту реализацию 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]
0 голосов
/ 27 апреля 2010

Недавно я столкнулся с обсуждением алгоритма под названием терпение diff , который звучит довольно просто. Вы можете попробовать реализовать это самостоятельно, и тогда, конечно, вы можете использовать любой алгоритм сравнения, который вам нравится.

...