algorithm - 如何计算最长公共子序列的数量

Question

我正在尝试计算两个字符串之间存在的最长可能子序列的数量。

例如字符串 X = "efgefg"; 字符串 Y = "efegf";

输出：最长公共序列的数量为：3（即：efeg, efef, efgf - 这个不需要算法计算，这里只是为了演示）

我已经设法在 O(|X|*|Y|) 中使用基于这里的一般思想的动态编程来做到这一点：最便宜的路径算法。

任何人都可以想出一种方法来有效地进行更好的运行时间计算吗？

——针对 Jason 的评论进行了编辑。

score 1 · Accepted Answer

最长公共子序列问题是一个经过充分研究的 CS 问题。

score 0 · Accepted Answer

我不知道，但这里有一些大声思考的尝试：

我能够构建的最坏情况有一个指数 - 2**(0.5 |X|) - 最长公共子序列的数量：

X = "aAbBcCdD..."
Y = "AaBbCcDd..."

其中最长的公共子序列恰好包括 {A, a} 中的一个，恰好是 {B, b} 中的一个等等......（挑剔：如果你的字母限制为 256 个字符，这最终会分解 - 但是 2** 128已经很大了。）

但是，您不一定必须生成所有子序列来计算它们。如果你有 O(|X| * |Y|)，那么你已经比这更好了！我们从中学到的是，任何比你更好的算法都不能尝试生成实际的子序列。

score 0 · Accepted Answer

首先，我们确实知道，除非强指数时间假设失败，否则无法在 O(n ^{2-ε ) 时间内找到长度为 n 的两个序列的任何最长公共子序列，请参阅：}https ://arxiv.org/abs /1412.0348

这几乎意味着您无法计算如何在 O(n ^2-ε ) 时间内将公共子序列与输入序列对齐的方法数量。另一方面，可以在 O(n ² ) 时间内计算这种对齐方式的数量。也可以在 O(n ² /log(n)) 时间内用所谓的四俄罗斯人加速来计算它们。

现在真正的问题是你是否真的打算计算这个或者你想找到不同子序列的数量？恐怕后者是一个#P-complete 计数问题。至少，我们确实知道计算常规文法可以生成的给定长度的序列数是#P-complete：

S. Kannan、Z. Sweedyk 和 SR Mahaney。计数和随机生成常规语言中的字符串。在 ACM-SIAM 离散算法 (SODA) 研讨会上，第 551-557 页，1995

从某种意义上说，这是一个类似的问题，计算常规语法可以生成给定长度序列的方式数量是一种简单的动态规划算法。但是，如果您不想区分产生相同序列的世代，那么问题就会从简单变为极其困难。我的自然猜想是序列比对问题也应该是这种情况（最长公共子序列、编辑距离、最短公共超串等）。

因此，如果您想计算两个序列的不同子序列的数量，那么您当前的算法很可能是错误的，并且任何算法都无法在多项式时间内计算它，除非 P = NP（以及更多......）。

score 0 · Accepted Answer

0

我发现的最佳解释（带代码）：

于 2017-07-03T16:56:37.123 回答

4 回答 4