python - 在python中使用后缀树

我对python比较陌生，并且开始使用后缀树。我可以构建它们，但是当字符串变大时，我遇到了内存问题。我知道它们可以用于处理大小为4 ^ 10或4 ^ 12的DNA字符串，但是每当我尝试实现一种方法时，都会遇到内存问题。

这是我用于生成字符串和后缀树的代码。

import random

def get_string(length):
    string=""
    for i in range(length):
        string += random.choice("ATGC")
    return string

word=get_string(4**4)+"$"

def suffixtree(string):
    for i in xrange(len(string)):
        if tree.has_key(string[i]):
            tree[string[i]].append([string[i+1:]][0])
        else:
            tree[string[i]]=[string[i+1:]]
    return tree

tree={}
suffixtree(word)

当我达到4 ** 8左右时，我遇到了严重的内存问题。我对此很陌生，因此我确定存储这些东西会丢失一些东西。任何建议将不胜感激。

注意:我想进行字符串搜索以在非常大的字符串中查找匹配的字符串。搜索字符串匹配大小为16。因此，这将在大字符串中查找大小为16的字符串，然后移至下一个字符串并执行另一次搜索。由于我将进行大量搜索，因此建议使用后缀树。

非常感谢

最佳答案

正如其他人已经说过的那样，您正在构建的数据结构不是后缀树。但是，内存问题很大程度上是由于您的数据结构涉及许多显式字符串副本。 像这样的电话

string[i+1:]

创建一个实际的(深层)子字符串副本(从i+1开始)。

如果您仍然对构造原始数据结构感兴趣(无论其用途如何)，一个好的解决方案是使用缓冲区而不是字符串副本。您的算法将如下所示:

def suffixtree(string):
    N = len(string)
    for i in xrange(N):
        if tree.has_key(string[i]):
            tree[string[i]].append(buffer(string,i+1,N))
        else:
            tree[string[i]]=[buffer(string,i+1,N)]
    return tree

我尝试将其嵌入到您的其余代码中，并确认即使总长度为8 ^ 11个字符，它也需要少于1 GB的主内存。

请注意，即使您切换到实际的后缀树，这也可能很重要。 正确的后缀树实现将不会在树的边缘存储副本(甚至不存储缓冲区)。但是，在树的构造过程中，可能需要大量的字符串临时副本。为这些使用buffer类型是一个很好的主意，可以避免为所有不必要的显式字符串副本增加垃圾回收器的负担。