2

我正在编写一个 Sublime Text 脚本来对齐几行代码。该脚本获取每一行，通过一组预定义的分隔符 ( ,;:=) 将其拆分，然后将其与填充到相同宽度的“列”中的每个段重新连接。当所有行都具有相同的定界符集时，这很有效，但有些行可能有额外的段、末尾的可选逗号等等。

我的想法是提出一个规范的分隔符列表。具体来说，给定几个定界符字符串，我想找到可以由任何给定字符串仅使用插入形成的最短字符串，并以某种合理的方式打破联系。经过一番研究，我了解到这是众所周知的全局多序列比对问题，除了没有错配，只有匹配和插入缺失。

不幸的是，动态编程方法在字符串数量上呈指数增长——至少在一般情况下是这样。当不允许不匹配时，是否有更快的解决方案的希望？

4

1 回答 1

1

我有点犹豫要不要笼统地声明没有这样的希望，即使不匹配是不允许的，但我很确定没有。这就是为什么。

进行序列比对时生成的动态规划表的大小约为（字符串长度）^（字符串数），因此需要指数级的运行时间/空间。为了让您了解它的来源，这是一个包含两个字符串的示例，ABC 和 ACB，每个长度为 3。这给了我们一个 3x3 表：

    A B C
  A 0 1 2
  C 1 1 1
  B 2 1 2

我们从左上角开始初始化这个表，然后从那里向下到右下角。到达表中任何位置的总成本由该位置的数字给出（为简单起见，我假设插入、删除和替换的成本都为 1）。用于到达给定位置的操作由您从前一个值移动的方向给出。向右移动意味着您从顶部字符串插入元素。向下移动从侧面的字符串中插入元素。对角线移动意味着您从顶部和底部对齐元素。如果这些元素不匹配，那么这代表了一种替代，并且您增加了到达那里的成本。

这就是问题所在。说不允许不匹配并不能排除导致表格长度和高度的操作（插入/删除）。更糟糕的是，不允许不匹配甚至不排除潜在的举动。有时，表格中的对角线移动仍然是可能的，只是当两个元素不匹配时就不行了。另外，你仍然需要检查元素是否匹配，所以你基本上还在考虑这个动作。因此，这应该无法改善您的最坏情况时间，并且似乎也不太可能对您的平均或最佳情况时间产生重大影响。

从好的方面来说，这是生物信息学中一个非常重要的问题，所以人们想出了一些解决方案。它们有缺陷，但可能对您的情况足够好（特别是因为您的字符串不是由四个字母组成的，与 DNA 相比，您似乎不太可能进行虚假对齐字母）。所以看看 Star Alignment 和 Neighbor Joining。

于 2015-02-25T05:53:08.400 回答