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

非常感谢！

- doggysaywhat

---

我对后缀树并不是特别熟悉，而且你的实现也没有给我提供它应该如何工作的线索。我建议你使用一个库，例如pytst。 - MattH

提示：树形结构将涉及嵌套字典。 - Karl Knechtel

Answer 1

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

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

- Marcin

Answer 2

正如其他人已经说过的那样，您正在构建的数据结构不是后缀树。然而，内存问题主要源于您的数据结构涉及大量显式字符串复制。像这样的调用

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。 请注意，即使您切换到实际后缀树，这也可能是相关的。正确的后缀树实现不会在树边缘中存储副本（甚至不是缓冲区），但是在构建树期间，您可能需要许多字符串的临时副本。对于这些，使用缓冲区类型是一个非常好的想法，以避免为所有不必要的显式字符串副本增加垃圾收集器的重负。

- jogojapan

---

谢谢提供的信息。我需要更详细地了解缓冲函数。 - doggysaywhat

Answer 3

如果您在创建后缀树时遇到了内存问题，您确定需要创建一个后缀树吗？您可以通过以下方式在单个字符串中查找所有匹配项：

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]

我的机器比较老，使用4^12个字符串运行需要30秒。我使用了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*41秒=1小时。

因此，总运行时间约为14小时，没有内存问题......比9.5年的时间有了很大的改进。请注意，我在1.6GHz CPU和1GB RAM上运行此代码，所以您应该能够做得比这更好！

- fraxel

---

谢谢您的帮助，我正在进行实验。然而，我发现当字符串大小达到4^11时，仍然会出现内存问题。 - doggysaywhat

@doggysaywhat - 从一个4^11的字符串构建后缀树需要大约3GB的空间。而对于4^12的字符串，需要大约12GB的空间。你需要搜索多少个字符串？以及需要进行多少次搜索？你最好先使用我描述的方法，并耐心等待！ - fraxel

你好Fraxel，很抱歉回复晚了。我遇到了家庭问题。当我的搜索量达到100万到1000万时，慢速方法会遇到问题。这个想法是为了在原始字符串中找到所有大小为16的重复元素。所以从M[0:16]开始，然后是M[1:17]等，一直到原始字符串的末尾，并在字符串中搜索它们的副本。它基本上给出了重复的数量。我正在尝试使用Burrows-Wheeler算法进行精确匹配来处理大型数据。 - doggysaywhat

@doggysaywhat - 我没意识到你在做这么多的搜索。我已经编辑了我的答案，使用一个解决方法来解决这个问题，希望能对你有所帮助 :) - fraxel

Answer 4

你出现记忆问题的原因是，对于输入的字符串'banana'，你生成了{'b': ['anana$'], 'a': ['nana$', 'na$', '$'], 'n': ['ana$', 'a$']}。这不是一棵树形结构。你已经创建并存储了输入的每个可能后缀，并将它们存储在其中一个列表中。这需要O(n^2)的存储空间。此外，为了使后缀树正常工作，你需要叶节点提供索引位置。

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

- Karl Knechtel