algorithm - Levenshtein 分割的子串太多

Question

我已经实现了 Levenshtein 距离来进行信号对齐。在某些情况下，Levenshtein 找不到我想要的解决方案，尽管它是最佳的。例如，我有字符串：

  aaabaa
abaaabaaa

该算法应该认识到它需要删除前两个和最后一个字符以匹配字符串：

abaaabaaa
x      xx

相反，它发现：

abaaabaaa
 x  x   x

因此，它将字符串划分为比它需要的更多的子字符串。Levenshtein 距离是否有扩展，它将字符串分成最少的子字符串？

Answer 1

您可以引入比 Levenshtein distance 使用的更复杂的编辑成本函数。您可以使 n 次连续删除（或 n 次连续插入）比 n 次单独删除（或插入）便宜。

这将使您想要的解决方案比 Levenshtein 距离找到的解决方案更便宜。

应满足您需求的编辑成本函数示例：

cost of replace: 2
cost of fist insert: 2
cost of consecutive insert: 1
cost of fist delete: 2
cost of consecutive delete: 1

比

abaaabaaa
x      xx

将有编辑成本：5

和

abaaabaaa
 x  x   x

将有编辑成本：6

所以找到的解决方案将是您想要的编辑距离：5