Левенштейн можно вычислить итеративно с помощью двух рядов таким образом:Итерационная версии Damerau-Левенштейн расстояние
https://en.wikipedia.org/wiki/Levenshtein_distance#Iterative_with_two_matrix_rows
я наткнулся на Optimal String alignment distance, что принимает во внимание транспозиции. Википедия говорит, что она может быть вычислена с помощью простого расширения регулярного алгоритма Левенштейна:
if i > 1 and j > 1 and a[i-1] = b[j-2] and a[i-2] = b[j-1] then
d[i, j] := minimum(d[i, j],
d[i-2, j-2] + cost) // transposition
Однако, я не в состоянии порта расширения алгоритма псевдокода на этой странице, чтобы код итеративной версии. Любая помощь приветствуется.