在python中使用后缀树

Question

我是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的字符串,然后移动到下一个字符串并执行另一个搜索.由于我将进行大量搜索,因此建议使用后缀树.

非常感谢

Answer 1

正如其他人已经说过的，您正在构建的数据结构不是后缀树。然而，内存问题很大程度上源于这样一个事实：您的数据结构涉及大量显式字符串副本。像这样的电话

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这些类型是一个非常好的主意，可以避免给垃圾收集器带来所有不必要的显式字符串副本的沉重负担。