Я знаю, что в стеке есть похожие ответы, а также в Интернете, но я чувствую, что что-то упускаю. Учитывая приведенный ниже код, нам нужно восстановить последовательность событий, которая привела к получению минимального расстояния редактирования. Для приведенного ниже кода нам нужно написать функцию, которая выводит:
Equal, L, L
Delete, E
Equal, A, A
Substitute, D, S
Insert, T
РЕДАКТИРОВАТЬ: КОД ОБНОВЛЕН С МОИМ (ЧАСТИЧНО ПРАВИЛЬНЫМ) РЕШЕНИЕМ
Вот код с моим частичным решением. Это работает, например, как мне дали ("ведущий" -> "последний"), но не работает для приведенного ниже примера ("подсказка" -> "не является"). Я подозреваю, что это потому, что первый символ равен, что отбрасывает мой код. Любые советы или указатели в правильном направлении были бы замечательными!
def printMatrix(M):
for row in M:
print row
print
def med(s, t):
k = len(s) + 1
l = len(t) + 1
M = [[0 for i in range(k)] for j in range(l)]
MTrace = [["" for i in range(k)] for j in range(l)]
M[0][0] = 0
for i in xrange(0, k):
M[i][0] = i
MTrace[i][0] = s[i-1]
for j in xrange(0, l):
M[0][j] = j
MTrace[0][j] = t[j-1]
MTrace[0][0] = "DONE"
for i in xrange(1, k):
for j in xrange(1, l):
sub = 1
sub_op = "sub"
if s[i-1] == t[j-1]:
# equality
sub = 0
sub_op = "eq"
# deletion
min_value = M[i-1][j] + 1
op = "del"
if min_value > M[i][j-1] + 1:
# insertion
min_value = M[i][j-1] + 1
op = "ins"
if min_value > M[i-1][j-1] + sub:
# substitution
min_value = M[i-1][j-1] + sub
op = sub_op
M[i][j] = min_value
MTrace[i][j] = op
print "final Matrix"
printMatrix(M)
printMatrix(MTrace)
############ MY PARTIAL SOLUTION
def array_append(array,x,y):
ops_string = MTrace[x][y]
if ops_string == 'ins':
array.append(("Insert",MTrace[0][y]))
elif ops_string == 'sub':
array.append(("Substitute",MTrace[x][0],MTrace[0][y]))
elif ops_string == 'eq':
array.append(("Equal",MTrace[x][0],MTrace[0][y]))
elif ops_string == 'del':
array.append(("Delete",MTrace[x][0]))
i = len(s)
j = len(t)
ops_array = []
base = M[i][j]
array_append(ops_array,i,j)
while MTrace[i][j] != "DONE":
base = M[i][j]
local_min = min(M[i][j-1],M[i-1][j],M[i-1][j-1])
if base == local_min:
i = i - 1
j = j - 1
array_append(ops_array,i,j)
elif M[i][j-1] < M[i-1][j]:
j = j -1
array_append(ops_array,i,j)
elif M[i-1][j] < M[i][j-1]:
i = i - 1
array_append(ops_array,i,j)
else:
i = i - 1
j = j - 1
array_append(ops_array,i,j)
print ops_array
#########
return M[k-1][l-1]
print med('lead', 'last')