3

假设我们只想使用 3 种类型的操作将一个字符串 S1 转换为另一个字符串 S2：

-Insert(pos,char) (costs 8)
-Delete(pos) (costs 6)
-Replace(pos,char) (costs 8)

找出将 S1 转换为 S2 的步骤序列，使得将 S1 转换为 S2 的成本最小。例如。'calculate' 到 'late' - 可能的操作是

Delete(0)
Delete(1)
Delete(2)
Delete(3)
Delete(4)

上面的操作顺序花费 30。

我正在使用以下代码来执行此操作，但它没有给出正确的结果。使用的算法是 Levenshtein。

tuples=[]
ops=[]
s1=''
s2=''
def levenshtein(a,b):
    global s1,s2
    n, m = len(a), len(b)
    if n > m:
        a,b = b,a
        n,m = m,n
    s1,s2=a,b
    current = range(n+1)
    for i in range(0,len(current)):
        current[i]=current[i]*8
    tuples.append(current)
    for i in range(1,m+1):
        previous, current = current, [i*8]+[0]*n
        for j in range(1,n+1):
            add, delete = previous[j]+6, current[j-1]+8
            change = previous[j-1]
            if a[j-1] != b[i-1]:
                change=change+8
            current[j] = min(add, delete, change)
        tuples.append(current)
    return current[n]
print levenshtein('calculate','late')
4

2 回答 2

5

您可以使用Levenshtein 距离算法

于 2013-04-23T07:02:59.037 回答
1

我会使用动态编程来解决这个问题。使用一个二维数组mem[n1][n2]，其中mem[i][j]存储从 position 开始的第一个字符串的后缀转换为从 开始i的第二个字符串的后缀的最小成本j。

你的方法似乎很贪婪，而且我认为对于更大的例子来说它会非常慢。

于 2013-04-23T08:18:42.610 回答