63
правки
Изменения
Нет описания правки
Псевдокод алгоритма:
'''int''' DamerauLevenshteinDistance(S[1..M], T[1..N]: '''char''', ; deleteCost, insertCost, replaceCost, transposeCost: '''int'''):
d[0..M][0..N]: '''int'''
d[i][j], ''<font color=green>// замена</font>''
d[i - 1][j ] + deleteCost, ''<font color=green>// удаление</font>''
d[i ][j - 1] + insertCost, ''<font color=green>// вставка</font>''
)
'''if'''(i > 1 '''and''' j > 1 '''and''' S[i] == T[j - 1] '''and''' S[i - 1] == T[j])
d[i][j] = minimummin( d[i][j], d[i - 2][j - 2] + transposeCost ''<font color=green>// транспозиция</font>'' )
'''return''' d[M][N]
Псевдокод алгоритма:
'''int''' DamerauLevenshteinDistance(S[1..M], T[1..N]: '''char''', ; deleteCost, insertCost, replaceCost, transposeCost: '''int'''):
''<font color=green>// Обработка крайних случаев</font>''
'''if''' (S == "")
last = j
'''else'''
D[i + 1][j + 1] = minimummin(D[i][j] + replaceCost, D[i + 1][j] + insertCost, D[i][j + 1] + deleteCost) D[i + 1][j + 1] = minimummin(D[i + 1][j + 1], D[i'][j'] + (i - i' - 1) <tex>\cdot</tex> deleteCost + transposeCost + (j - j' - 1) <tex>\cdot</tex> insertCost)
lastPosition[S[i]] = i
