如何修改Levenshteins编辑距离以将"相邻字母交换"计为1次编辑

Question

我正在玩Levenshteins编辑距离算法,我想扩展它来计算换位 - 即相邻字母的交换 - 作为1编辑.未修改的算法计算从另一个字符串到达​​某个字符串所需的插入,删除或替换.例如,从"KITTEN"到"SITTING"的编辑距离是3.这是维基百科的解释:

1. 小猫→坐着(用's'代替'k')
2. sitten→sittin(用'i'代替'e')
3. 坐着→坐着(在结尾插入'g').

按照相同的方法,从"CHIAR"到"CHAIR"的编辑距离为2:

1. CHIAR→CHAR(删除'我')
2. CHAR→CHAIR(插入'I')

我想把它算作"1编辑",因为我只交换两个相邻的字母.我该怎么做呢？

Answer 1

您需要在维基百科的算法中再添一个案例:

if s[i] = t[j] then 
  d[i, j] := d[i-1, j-1]
else if i > 0 and j > 0 and s[i] = t[j - 1] and s[i - 1] = t[j] then
  d[i, j] := minimum
             (
               d[i-2, j-2] + 1 // transpose
               d[i-1, j] + 1,  // deletion
               d[i, j-1] + 1,  // insertion
               d[i-1, j-1] + 1 // substitution
             )
else
  d[i, j] := minimum
             (
               d[i-1, j] + 1,  // deletion
               d[i, j-1] + 1,  // insertion
               d[i-1, j-1] + 1 // substitution
             )