3

3 種類の操作のみを使用して、1 つの文字列 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 です。

これを行うために次のコードを使用していますが、正しい結果が得られません。使用されるアルゴリズムはレーベンシュタインです。

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

レーベンシュタイン距離アルゴリズムを使用できます

于 2013-04-23T07:02:59.037 に答える
1

動的計画法を使用してこの問題を解決します。positionから始まる最初の文字列の接尾辞を から始まる 2 番目の文字列の接尾辞に変換する最小コストを格納する 2 次元配列を使用mem[n1][n2]します。mem[i][j]ij

あなたのアプローチは貪欲に思えますし、大きな例では非常に遅くなると思います。

于 2013-04-23T08:18:42.610 に答える