-1

私はこのプログラムをほぼ完成させましたが、ここの最後の部分で少し立ち往生しています。プログラムを実行すると、2 つの文字列が要求されます。次に、これらを比較して最小編集距離を確認します。削除と挿入のコストは 1 で、置換 (削除と挿入) のコストは 2 です。

IE quick and quicker の距離は 4 です。これは、最後の 2 文字を別の文字に置き換える必要があるためです。

私が問題を抱えているのは、配置を示すことです。次のように表示したい：

q u i c k l y
          s s
q u i c k e r

2 つの置換とそれらがどこにあるかを示します。これは、削除と挿入にも当てはまります。

ここまでです：

#!/usr/bin/env python
import sys
from sys import stdout

def  Edit_Distance(target, source):


n = len(target)
m = len(source)

distance = [[0 for i in range(m+1)] for j in range(n+1)]

for i in range(1,n+1):
    distance[i][0] = distance[i-1][0] + insertCost(target[i-1])

for j in range(1,m+1):
    distance[0][j] = distance[0][j-1] + deleteCost(source[j-1])

for i in range(1,n+1):
    for j in range(1,m+1):
       distance[i][j] = min(distance[i-1][j]+1,
                            distance[i][j-1]+1,
                            distance[i-1][j-1]+substCost(source[j-1],target[i-1]))
return distance[n][m]

def substCost(x,y):
    if x == y:
        return 0
    else:
        return 2

def insertCost(x):
    return 1

def deleteCost(x):
    return 1


# User inputs the strings for comparison
word1 = raw_input("Enter A Word: ")
word2 = raw_input("Enter The Second Word: ")

# Simple conditional that will set the length of the range loop below based on the longest string
if (word2 >= word1):
    x = len(word2)
else:
        x = len(word1)

# x is then the longest string length so that we have the perfect length range loop
# stdout.write allows us to print multiple things on the same line, instead of tabbing down a line each time
print ("The minimum edit distance between S1 and S2 is: ", Edit_Distance(word1,word2))

print list(word1)
for i in range(x):
    if(word1[i] != word2[i]):
        print("D")

print list(word2)
4

1 に答える 1

0

あなたの質問が「D」を揃えて印刷する方法だけである場合は、

http://docs.python.org/2/library/stdtypes.html#string-formatting-operations

ここでは、文字列をフォーマットする方法を見つけることができます（私が理解している場合、これはあなたが求めているものです）。

ところで、整列して印刷する方法のヒント (コードがうまく機能することを前提): リストを使用して "D" をループに格納しないのはなぜですか?

于 2012-12-10T23:32:08.957 に答える