如何使用任意匹配函数对比/对齐Python列表？

Question

我想把两个列表对齐，类似于 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 类型的结果，而不是仅仅计算最小的 Levenshtein 距离。

Answer 1

我最近看到一个关于一种叫做 patience diff 的算法的讨论，这个算法听起来挺简单的。你可以试着自己实现一下这个算法，当然你也可以选择任何你喜欢的比较算法来使用。

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