Изменить расстояние с помощью свопов

Question

Изменить расстояние определяет количество вложений, удалений или замещений, необходимых для одной строки в другую. Я хочу также включить свопы в этот алгоритм. Например, «apple» и «appel» должны дать расстояние редактирования 1.

Answer 1

См. Алгоритм здесь.

http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Dynamic/Edit/

Вы можете дать различные расходы на обмен, добавьте, делеции.

m[i,j] = min(m[i-1,j-1] 
     + if s1[i]=s2[j] then 0 else cost_swap fi, 
     m[i-1, j] + cost_insert, 
     m[i, j-1] + cost_delete), i=1..|s1|, j=1..|s2| 

Answer 2

Редактирование расстояние, которое вы определяете называется Damerau-Левенштейна. Вы можете найти возможные варианты реализации на Wikipedia page.