对于无序序列匹配问题，哪种算法更好？

Question

如果我有两个序列(例如，字符串)

//   01234567890123456789012  
a = "AAACDDFFFEE1122VV1VAADD"

//   0123456789012345678901
b = "DDFFAA11221DHHVV1VAAFE"

我想知道从b到a的最佳子字符串匹配(无序)，例如：

optimal (6 matched parts, 19 characters of a matched)
b         a
DDFF   -> DDFF     (4,7)
AA     -> AA       (0,1)
1122   -> 1122     (11,14)
1     
D      -> D        (21)
HH
VV1VAA -> VV1VAA   (15,20)
FE     -> FE       (8,9)

还有另一种解决方案，但不是最优的：

not optimal (8 parts matched, 19 characters of a matched)
b        a
DDFF  -> DDFF  (4,7)
AA    -> AA    (0,1)
1122  -> 1122  (11,14)
1     -> 1     (17)
D     -> D     (21)
HH
VV    -> VV    (15,16)
1     
VAA   -> VAA   (18,20)
FE    -> FE    (8,9)

哪种算法更适合这个问题？(我需要最优的结果，性能至关重要)。

谢谢。

Answer 1

有趣的问题，您可以使用Boyer-Moore (http://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm)或KMP (http://en.wikipedia.org/wiki/Knuth-Morris-Pratt_ algorithm )算法或任何其他线性时间字符串搜索算法在O(|a|.|b| + |b|^2)中解决它。

对于每个b0，我都要在字符串a(在O(|a| + i)中)中找到它，直到你再也找不到它为止。你知道你可以找到b0..i，但不能找到b0..i+1，所以你有一个b0的匹配项。.i，你继续bi+1..i+1，bi+1..i+2..

• 在最后b的每个部分是否都匹配了，如果它已经匹配了，如果它尽可能大的话。

总复杂度至多为sum( O(| a | + i)，i=0..|b|) = O(|a|.|b| + |b|^2)，但如果在a中只能找到b的较小子串，则复杂度可以小得多。

编辑:

上面的方法是贪婪的，不会最小化部件的数量，但我认为它会最大化匹配的字符总数。

关于最佳解决方案的思考：

​

对于|b|的每个|b|^2子字符串，确定它是否可以在|a|中找到，并仅保留我们需要在这些字符串中找到它们的子集的那些：

of length is maximum<>H121如果长度相等，字符串数必须为minimum

​

总和很容易计算，因为一个非常简单的解决方案是只匹配大小为1的子串:那么length就是a和b之间常见字母的数量。

因此，如果我们将大小为1的子串(即使是不在a中的字母)添加到上面的匹配字符串集合中，我们需要找到一个没有重叠的b的最小集合覆盖。

一般的集合覆盖是NP-完全的，但是这里有无重叠的约束，它有帮助吗？

我正在调查。

事实上，NP-complete：http://www.springerlink.com/content/n73561q050w54pn6/

你可能想要寻找近似算法...

Answer 2

如果我理解您的问题，您希望找到两个给定字符串的一组不重叠的公共子字符串，它们要么最大化公共子字符串的总长度，要么最小化公共子字符串的数量。我将提出以下启发式:找到两个字符串中最长的公共子字符串(LCS)，删除它，重复。我不能证明这是最优的，但我有一个非常有效的算法

因此，在您的示例中，AAACDDFFFEE1122VV1VAADD DDFFAA11221DHHVV1VAAFE LCS = VV1VAA

AAACDDFFFEE1122DD DDFFAA11221DHHFE

LCS = DDFF

AAACFEE1122DD AA11221DHHFE

LCS = 1122

AAACFEEDD AADHHFE

以此类推

该算法如下:1)使用基于后缀树的标准LCS算法1.1建立连接的两个字符串的后缀树，并使用唯一的终止符1.2根据根在那里的子树是否具有来自任意一个或两个字符串的叶子来标记每个节点1.3计算每个节点的字符串深度1.4找到标记为1和2的字符串最深的节点2)移除以该节点为根的子树，并更新其上节点的标签3)从1.4开始重复

当树没有标记为1和2的节点时，该算法终止。1.1可以在时间上与两个字符串的长度之和成比例地完成。1.2、1.3和1.4比树遍历多2。如果树被正确地实现并且更新受LCS的长度的限制，则移除应该是恒定的时间3再次是树遍历，但是是较小树的遍历

这是一个优化，为了避免重复遍历树，让我们添加步骤1.35:按字符串深度对具有两个标签的内部节点进行排序(在单独的数据结构中，树仍然存在)。现在，您可以扫描已排序的节点列表，执行2)并重复。有了这种优化，如果你可以使用基数排序，它看起来算法是线性时间，并且你不能在渐近意义上击败它。

我希望这是正确的和足够清楚的，我相信你需要熟悉一下后缀树的文献，然后它听起来很明显。我推荐Dan Gusfield的关于字符串、树和序列的算法一书，特别是7.4一节让我知道如果你有问题。