2

所以我以前试过问这个，但我想我对我要找的东西还不够清楚。我正在制作一个最佳的字符串对齐算法，它实际上只是一个动态编程问题。所以我决定递归地写它。该计划由两部分组成：

  • 找到两个单词之间的“编辑距离”，您可以根据一些相关成本最小化对齐。例如，对齐同一个字母的成本为 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，因为我尝试通过删除递归调用期间发生的所有附加来重置它。如何设置一种方法来记录构成与此递归算法的最佳对齐的“移动”序列？

编辑：这是我的 memoize 装饰器功能：

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
4

1 回答 1

1

1）通过您的递归函数将堆栈（或其他集合）作为参数传递。

2）当您递归调用自己时，还将您正在采取的步骤推入堆栈（例如，使用步骤类型和整数/字符/字符串/指示它正在做什么的枚举）。

3) 当您从 2) 中的调用返回时，弹出堆栈并重复 2)。

4）当您有解决方案时，您可以存储与其结果/分数相关联的堆栈。

于 2013-03-03T23:42:47.797 回答