-1

我几乎完成了这个程序我只是有点卡在最后一部分。运行时程序会要求输入两个字符串。然后将它们进行比较以查看最小编辑距离。删除和插入的成本为 1，替换（删除和插入）的成本为 2。

IE 越来越快的距离为 4，因为需要替换最后两个字母才能从一个字母替换到另一个字母。

我遇到的问题是显示对齐方式。我想显示如下：

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

显示两个替换以及它们的位置。这也适用于删除和插入。

到目前为止：

#!/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

python文档的页面，您可以在其中找到如何格式化字符串（如果我理解，这就是您所要求的）。

顺便说一句，只是关于如何打印对齐的提示（鉴于代码运行良好）：为什么不使用列表将“D”存储在循环中？

于 2012-12-10T23:32:08.957 回答