2

I am trying to find all the possible longest common subsequence from the same position of multiple fixed length strings (there are 700 strings in total, each string have 25 alphabets ). The longest common subsequence must contain at least 3 alphabets and belong to at least 3 strings. So if I have:

String test1 = "abcdeug";
String test2 = "abxdopq";
String test3 = "abydnpq";
String test4 = "hzsdwpq";

I need the answer to be:

String[] Answer = ["abd", "dpq"];

My one problem is this needs to be as fast as possible. I am trying to find the answer with suffix tree, but the solution of suffix tree method is ["ab","pq"].Suffix tree can only find continuous substring from multiple strings.The common longest common subsequence algorithm cannot solve this problem. Does anyone have any idea on how to solve this with low time cost? Thanks

4

2 回答 2

1

我建议您在尝试使用任何听起来可能会执行您想要的操作的算法之前，将其转换为一个众所周知的计算问题。

这是我的建议：将其转换为图形问题。对于字符串中的每个位置，您创建一组节点（一个用于集合中所有字符串中该位置的每个唯一字母......所以如果所有 700 个字符串在同一位置不同，则为 700 个节点）。一旦您为字符串中的每个位置创建了所有节点，您将通过您的字符串集查看两个位置共享超过 3 个相等连接的频率。在您的示例中，我们将首先查看位置 1 和 2，并看到三个字符串在位置 1 中包含“a”，在位置 2 中包含“b”，因此我们在第一组节点中的节点“a”之间添加有向边第二组节点中的图形和“b”（继续对所有位置对和这两个位置中的所有字母组合执行此操作）。

一旦你有了最终的图表，你必须寻找最长的路径；我建议在这里查看维基百科文章：最长路径。在我们的例子中，我们将有一个有向无环图，您可以在线性时间内解决它！预处理应该是字符串位置数量的二次方，因为我想你的字母表是固定大小的。

PS：你给我发了一封关于我正在研究的双聚类算法的电子邮件；它尚未发布，但将在今年某个时候发布（祈祷）。不过感谢您的兴趣:)

于 2013-05-22T11:14:19.020 回答
0

您可以尝试使用散列。
每个字符串最多有 25 个字符。这意味着它有 2^25 个子序列。你取每个字符串，计算所有 2^25 个哈希值。然后你加入所有字符串的所有哈希并计算其中至少包含 3 次。为了获得这些子序列的长度，您不仅需要存储散列，还需要存储<hash, subsequence_pointer>确定subsequence_pointer该散列的子序列的对（最简单的方法是枚举所有字符串的所有散列并存储散列号）。
根据算法，最坏情况下的程序（700 个字符串，每个 25 个字符）将运行几分钟。

于 2013-05-22T03:52:26.430 回答