Расчет минимального расстояния редактирования для неравных строк Python ⇐ Python

[Anonymous]

Я пытаюсь реализовать минимальное расстояние редактирования с стоимостью замены 2. Ниже приведен код, который я до сих пор. Он хорошо работает для строк равной длины, но генерирует ошибку для неравных строк. Пожалуйста, поправьте меня, где я не ошибаюсь, < /p>

def med(source, target):
# if len(x) > len(y):
# print("insode if")
# source, target = y, x
print(len(source), len(target))
cost = [[0 for inner in range(len(source)+1)] for outer in
range(len(target)+1)]

global backtrace
backtrace = [[0 for inner in range(len(source)+1)] for outer in
range(len(target)+1)]
global SUB
global INS
global DEL

for i in range(0,len(target)+1):
cost[0] = i

for j in range(0,len(source)+1):
cost[0][j] = j

for i in range(1,len(target)+1):
for j in range(1,len(source)+1):
if source[i-1]==target[j-1]:
cost[j] = cost[i-1][j-1]
else:
deletion = cost[i-1][j]+1
insertion = cost[j-1]+1
substitution = cost[i-1][j-1]+2
cost[j] = min(insertion,deletion,substitution)

if cost[j] == substitution:
backtrace[j] = SUB
elif cost[j] == insertion:
backtrace[j] = INS
else:
backtrace[j] = DEL

return cost[j]

med("levenshtein","levels")
< /code>

Ошибка, которую я получаю: < /p>

---------------------------------------------------------------------------
IndexError Traceback (most recent call last)
in ()
49 return cost[i][j]
50
---> 51 med("levenshtein","levels")

in med(source, target)
31 for i in range(1,len(target)+1):
32 for j in range(1,len(source)+1):
---> 33 if source[i-1]==target[j-1]:
34 cost[i][j] = cost[i-1][j-1]
35 else:

IndexError: string index out of range


Подробнее здесь: https://stackoverflow.com/questions/530 ... ngs-python