所以我之前试着问过这个问题，但我想我对我要找的东西还不够清楚。我正在制作最佳字符串对齐算法，it's really just a dynamic programming problem .所以我决定递归地写它。该程序由两部分组成:
- 找出两个词之间的“编辑距离”，根据相关成本最大限度地减少对齐。例如，对齐相同字母的成本为 0，对齐两个元音字母的成本为 0.5，但对齐一个有间隙的字母成本为 1。
- 可视化对齐方式:即将字符串以字符和间隙的最佳对齐方式堆叠在一起。
我认为我的编辑距离有效。我得到了与同龄人相同的值(value)观，而且似乎没有直接的问题。但是，我很难弄清楚如何恢复匹配、插入和删除的顺序以可视化对齐。我的问题来自于我有一个递归函数，它至少需要三个递归调用。因此，我最终得到了一个比必要的更长的序列，因为每个递归调用都会附加一个“移动”(匹配、插入、删除)，但可能不会被使用，因为它不是成本最低的。
这是我的代码:
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
请您参考如下方法:
1) 通过递归函数将堆栈(或其他集合)作为参数传递。
3) 当你从 2) 的调用返回时，出栈并重复 2)。
4) 当您有解决方案时，您可以存储与其结果/分数关联的堆栈。
