2

我在列表中存储了 300K 个字符串，每个字符串的长度在 10 到 400 之间。我想删除其他字符串的子字符串（长度较短的字符串更有可能成为其他字符串的子字符串）。

目前，我首先根据长度对这 300K 字符串进行排序，然后使用下面的方法。

sorted_string = sorted(string_list, key=length, reverse=True)
for item in sorted_string
    for next_item in sorted_string[sorted_string.index(item)+1:]
        if next_item in item:
            del sorted_string[sorted_string.index(next_item)]

该方法的运行时间为 O(n^2)。由于我有 300K 字符串，我对这种方法并不满意。

我试图将这些排序的字符串分成不同的块，并使用多处理来计算每个块。我的第一个想法是将前 10K 放到第一个块中，然后将接下来的 10K 放到第二个块中，依此类推。但是这样，每个块中的字符串具有相似的长度，并且它们可能不会成为同一块中其他字符串的子字符串。所以这不是一个好的划分策略。

有什么好主意吗？

编辑：这些字符串代表 DNA 序列，仅包含“g”、“c”、“t”和“a”

更新：

我尝试使用https://github.com/kvh/Python-Suffix-Tree中的代码构建后缀树。该程序基于Ukkonen 算法构建后缀树。

连接字符串的总长度约为 90,000,000。这是一个很大的数字。该程序已运行半小时，仅处理了约 3,000,000 (1/30) 个字符。我对这个程序不满意。

有没有其他可以处理这个大字符串的后缀树构建算法？

4

2 回答 2

2

您可以使用后缀树。它会让你达到 O(mn)，其中 m 是字符串的长度。它仍然是二次的，但由于 m << n 在您的情况下，它将提供显着的改进。

这些讲义提供了一个很好的可视化解释，说明如何使用后缀树来查找子字符串。

于 2013-08-08T22:32:02.407 回答
0

这是一个非常酷且非常有趣的问题。我研究了子集种子算法，并且已经有很多。

你听说过 BLAST 算法吗？http://blastalgorithm.com/ 图形用户界面： http: //blast.ncbi.nlm.nih.gov/

于 2013-08-08T23:55:54.410 回答