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

Question

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

Answer 1

Расстояние редактирования, которое вы определяете, называется Расстояние Дамерау – Левенштейна . Вы можете найти возможные реализации на странице Википедии .

Answer 2

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

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|