2

如果我有两个序列（例如，字符串）

//   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)

什么样的算法更适合这个问题？？？（我需要最佳结果，性能至关重要）。

谢谢。

4

2 回答 2

1

有趣的问题，您可以使用 Boyer-Moore ( http://en.wikipedia.org/wiki/Boyer –Moore_string_search_algorithm ) 或 KMP ( http: //en.wikipedia.org/wiki/Knuth –Morris–Pratt_algorithm ）算法或任何其他线性时间字符串搜索算法。

  • 对于每个 b[0..i] ty，在字符串 a 中（在 O(|a| + i) 中）找到它，直到你再也找不到它
  • 你知道你可以找到 b[0..i] 但不能找到 b[0..i+1]，所以你有一个匹配 b[0..i] 并且你继续 b[i+1..i+ 1],b[i+1..i+2]..
  • 最后 b 的每个部分都匹配或不匹配，如果匹配则尽可能大。

总复杂度最多为 sum( O(|a| + i) , i=0..|b|) = O(|a|.|b| + |b|^2) 但如果只有b 的小子串可以在 a 中找到。

编辑 ：

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

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

  • 对于 |b| 的每个 |b|^2 子串 确定它是否可以在 |a| 中找到，并只保留那些是这种情况的
  • 我们需要在这些字符串中找到它们的子集：
    • 它们中的任何两个之间没有重叠
    • 长度之和最大
    • 长度相等时，字符串的数量必须最少

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

因此，如果我们将 b 的大小为 1 的子字符串（甚至是不在 a 中的字母）添加到上面的匹配字符串集合中，我们需要找到 b 的最小集合覆盖，并且没有重叠。

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

我正在调查它。

确实，NP完全：http ://www.springerlink.com/content/n73561q050w54pn6/

您可能想寻找近似算法....

于 2010-10-08T13:09:18.817 回答
0

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

所以在你的例子中 AAACDDFFFEE1122VV1VAADD DDFFAA11221DHHVV1VAAFE LCS = VV1VAA

AAACDDFFFEE1122DD DDFFAA11221DHHFE

LCS = DDFF

AAACFEE1122DD AA11221DHHFE

生命周期 = 1122

AAACFEEDD AADHFE

等等

算法如下 1) 使用基于后缀树的标准 LCS 算法 1.1 构建连接的两个字符串的后缀树，并使用唯一的终止符 1.2 用 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 的书 Algorithms on String, Trees and Sequences，特别是 7.4 部分，如果您有问题，请告诉我。

于 2010-10-08T16:35:59.673 回答