algorithm - Levenshtein 分成太多的子串

Question

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

  aaabaa
abaaabaaa

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

abaaabaaa
x      xx

相反，它发现:

abaaabaaa
 x  x   x

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

Answer 1

您可以引入比 Levenshtein 距离使用的函数更复杂的编辑成本函数。您可以使 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