通过递归调用找到路径：最优字符串对齐

Question

我之前尝试问过这个问题，但我想我没有把我想要的表达得很清楚。我正在制作一个最优字符串对齐算法，这其实就是一个动态规划的问题。所以我决定用递归来写。这个程序分为两个部分：

计算两个单词之间的“编辑距离”，也就是根据一些相关的成本来最小化对齐的代价。例如，对齐相同的字母成本是0，对齐两个元音字母成本是0.5，但对齐一个字母和一个空格的成本是1。
可视化对齐：也就是把字符串叠在一起，显示字符和空格的最佳对齐方式。

我觉得我的编辑距离算法是有效的。我得到的值和我的同学们是一样的，似乎没有明显的问题。然而，我在找出如何恢复匹配、插入和删除的序列以可视化对齐时遇到了困难。我的问题在于我有一个递归函数，它需要从三个递归调用中选择最小值。因此，我最终得到的序列比必要的要长，因为每个递归调用都会添加一个“移动”（匹配、插入、删除），但这个移动可能并不是成本最低的。

这是我的代码：

newseq = []
@memoize
def opt(a, b):
    global newseq # Visual Alignment 'move' sequence
    gap = 1 # Gap cost
    if not a: 
        return len(b)
    if not b: 
        return len(a)

    if a and b:
        p1 = a[0] in v   # First letters vowells?
        p2 = b[0] in v   
        if a[0] == b[0]: # First letters equal each other?
            alpha = 0
        elif p1 ^ p2:    # Vowel and Consonant?
            alpha = 1.2
        elif p1 and p2:  # Vowel and Vowel?
            alpha = 0.5
        else:            # Consonant and Consonant?
            alpha = 0.6

    r1 = opt(a[1:], b[1:]) + alpha
    r2 = opt(a[1:], b) + gap
    r3 = opt(a, b[1:]) + gap
    # Reset newseq
    newseq = newseq[:-3]

    # Takes min of recursive calls, and gives associated 'move'
    res = min((r1, 'Match'),      # Match
              (r2, 'Insertion'),  # Insertion
              (r3, 'Deletion'),   # Deletion
              key = lambda x: x[0])

    newseq.append(res[1])
    return res[0]

所以，是的，我知道我现在的代码是有问题的。我的全局变量 newseq 目前的长度是1，因为我试图通过移除在递归调用中发生的所有添加来重置它。我该如何设置一个方法来记录构成最优对齐的“移动”序列呢？

编辑：这是我的备忘录装饰器函数：

def memoize(f):
    cache = {}
    def decorated_function(*args):
        if args in cache:
            return cache[args]
        else:
            cache[args] = f(*args)
            return cache[args]
    return decorated_function

递归动态规划成本计算编辑距离最优算法递归调用字符串对齐可视化对齐

通过递归调用找到路径：最优字符串对齐

1 个回答

撰写回答