algorithm - 如何修改编辑编辑距离以将 "adjacent letter exchanges"计为 1 次编辑

Question

我正在玩弄 Levenshteins Edit Distance algorithm ，我想扩展它以计算换位——即相邻字母的交换——作为 1 次编辑。未修改的算法计算从另一个字符串到达​​某个字符串所需的插入、删除或替换。例如，从“KITTEN”到“SITTING”的编辑距离为 3。这是来自维基百科的解释:

1. kitten → sitten(将“k”替换为“s”)
2. sitten → sittin(将“e”替换为“i”)
3. sittin → sitting(在末尾插入“g”)。

同理，“CHIAR”到“CHAIR”的编辑距离为2:

1. CHIAR → CHAR(删除“我”)
2. CHAR → CHAIR(插入“我”)

我想将此计为“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
             )