python - 如何使用任意匹配函数来区分/对齐 Python 列表？

Question

我想以与 difflib.Differ 类似的方式对齐两个列表，除了我希望能够定义用于比较项目的匹配函数，而不仅仅是使用字符串相等性，最好是一个匹配函数，它可以返回 0.0 到 1.0 之间的数字，而不仅仅是一个 bool 值。

例如，假设我有两个列表:

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)

并使用 match 函数进行比较。与 difflib 一样，我宁愿该算法给出更直观的 Ratcliff-Obershelp 类型结果，而不是纯粹的最小 Levenshtein 距离。

Answer 1

我刚刚写了这个 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]