5

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

非常感谢

4

4 回答 4

4

这在我看来不像一棵树。看起来您正在生成所有可能的后缀，并将它们存储在哈希表中。

如果您使用实际的树，您可能会获得更小的内存性能。我建议使用库实现。

于 2012-04-10T11:00:12.917 回答
3

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

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

于 2012-04-12T02:34:59.147 回答
2

如果您的记忆问题在于创建后缀树，您确定需要一个吗？您可以在一个字符串中找到所有匹配项，如下所示：

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

def matcher(word, match_string):
    positions = [-1]
    while 1:
        positions.append(word.find(match_string, positions[-1] + 1))
        if positions[-1] == -1:
            return positions[1:-1]

print matcher(word,'AAAAAAAAAAAA')
[13331731, 13331732, 13331733]
print matcher('AACTATAAATTTACCA','AT')
[4, 8]

我的机器很旧，运行时间为 30 秒，字符串为 4^12。我使用了一个 12 位的目标，所以会有一些匹配。此解决方案还将找到重叠的结果 - 如果有的话。

这是您可以尝试的后缀树模块，如下所示：

import suffixtree
stree = suffixtree.SuffixTree(word)
print stree.find_substring("AAAAAAAAAAAA")

不幸的是，我的机器太慢了，无法用长字符串正确测试它。但是大概一旦构建了后缀树，搜索将非常快，因此对于大量搜索，它应该是一个很好的调用。进一步find_substring只返回第一个匹配项（不知道这是否是一个问题，我相信你可以轻松适应它）。

更新：将字符串拆分成更小的后缀树，从而避免内存问题

因此，如果您需要对 4^12 长度的字符串进行 1000 万次搜索，我们显然不想等待 9.5 年（标准的简单搜索，我首先建议，在我的慢速机器上......）。但是，我们仍然可以使用后缀树（因此要快得多），并避免内存问题。将大字符串拆分为可管理的块（我们知道机器内存可以处理）并将一个块变成后缀树，搜索 1000 万次，然后丢弃该块并移动到下一个块。我们还需要记住搜索每个块之间的重叠。我写了一些代码来做到这一点（它假设要搜索的大字符串word是我们最大可管理字符串长度的倍数max_length，你必须调整代码以检查最后的余数，如果这不是案子）：

def split_find(word,search_words,max_length):
    number_sub_trees = len(word)/max_length
    matches = {}
    for i in xrange(0,number_sub_trees):
        stree = suffixtree.SuffixTree(word[max_length*i:max_length*(i+1)])
        for search in search_words:
            if search not in matches:
                match = stree.find_substring(search)
                if match > -1:
                    matches[search] = match + max_length*i,i
            if i < number_sub_trees:
                match = word[max_length*(i+1) - len(search):max_length*(i+1) + len(search)].find(search)
                if match > -1:
                    matches[search] = match + max_length*i,i
    return matches

word=get_string(4**12)
search_words = ['AAAAAAAAAAAAAAAA'] #list of all words to find matches for
max_length = 4**10 #as large as your machine can cope with (multiple of word)
print split_find(word,search_words,max_length)

在此示例中，我将最大后缀树长度限制为长度 4^10，大约需要 700MB。使用此代码，对于一个 4^12 长度的字符串，1000 万次搜索大约需要 13 个小时（完整搜索，零匹配，所以如果有匹配会更快）。但是，作为其中的一部分，我们需要构建 100 棵后缀树，这大约需要..100*41sec= 1 小时。

所以运行的总时间大约是 14 小时，没有内存问题……比 9.5 年有了很大的改进。请注意，我在具有 1GB RAM 的 1.6GHz CPU 上运行它，所以你应该能够做得比这更好！

于 2012-04-10T11:38:54.213 回答
2

您遇到内存问题的原因是'banana'您正在生成的输入{'b': ['anana$'], 'a': ['nana$', 'na$', '$'], 'n': ['ana$', 'a$']}。那不是树形结构。您可以在其中一个列表中创建并存储输入的所有可能后缀。这需要 O(n^2) 存储空间。此外，为了使后缀树正常工作，您希望叶节点为您提供索引位置。

你想要得到的结果是{'banana$': 0, 'a': {'$': 5, 'na': {'$': 3, 'na$': 1}}, 'na': {'$': 4, 'na$': 2}}. （这是一种优化的表示；一种更简单的方法将我们限制为单字符标签。）

于 2012-04-10T13:07:56.267 回答