大文本（10Mb）的后缀树占用过多的内存

2018-06-14 02:02:33

我实现了（见下面的代码）绝对最小的通用后缀树构建算法。我写了一个单元测试，它似乎按预期工作（在正确的位置找到正确的子字符串）。但这棵树不切实际地大。 问题：我在某个地方犯了什么错误，或者这种基本形式的后缀树只能用于很短的文本吗？

统计

我想用它来搜索大量的文本：多个15-20Mb的文本文件，或者例如40'000个字符串〜每个60个字符。

当我建立40'000字符串2.5Mb后缀树（这是一个名单，如果公司名称），树需要400Mb。我大概可以优化它大约4倍，但即使如此，每个字符的原始文本也会超过40个字节。这是正常的吗？文献中的估计表明这是很高的。

查看树的每个级别的平均分支因子，它们是：80 40 8 3 2 1 1 1 ...即只有树的前3-5个级别实际分支。我建立3-5个关卡并保留长文本后缀节点要好得多。低于5级的东西基本上是链接的字符列表。这是预期的表现吗？这很直观，公司名称之间共享的字符串不多。

在进一步的15MB文本实验中，我添加了前10'000个后缀（从长到短），耗尽2Gb的内存。几乎没有重复的子串，所以树不能重复使用。我完全可以看到后缀数组实际上是多么有用，每个字符需要固定的2-4个字节，并且在20Mb的文本中每个搜索只需要24个字符串比较。我不可能看到具有尽可能多的顶点的后缀树与文本中的唯一子字符串如何适合内存。对于具有所有独特字符的字符串而言，它是O（n ^ 2）个节点，但对于英文文本而言它似乎仍然非常超线性。后缀树如何适用于大型文本？我读过的论文和问题似乎暗示它应该是可用的，因此我的问题在这里。

问题

我是否在某个地方犯了一个错误，让树变得比它应该大？

建立后缀树的方式应该与最终的树形无关吗？

我不是Ukkonen算法，只是蛮力将所有后缀添加到树中以简化代码和数据结构（无后缀链接字段），并稍后将perf与Ukkonen进行比较。建筑的方法只应该影响施工的速度， 而不是树的大小或形状。无论哪种方式，构建树都是渐进的，所以没有比最终树更大的中间结果。

代码如下：

#include <vector>
#include <assert.h>
class Node 
{public:
    char c; // 0 is terminator. terminators have no children
    Node(char _c) { c = _c; }
};

class Terminator 
{
public:
    Terminator(int i, int p ) { id = i; pos = p; }
    bool operator == (const Terminator &that)const { return id == that.id && pos == that.pos; }
    int id; // id of the string
    int pos; //position of this substring in the string
};


class Vertex : public Node 
{
public:
    static size_t s_nCount;
    std::vector< Vertex* > children; // interior tree nodes; char != 0
    std::vector< Terminator >terminators;
    Vertex(char c) :Node(c) { s_nCount++; }
    ~Vertex() { for (Vertex*v : children) delete v; }
    //void* operator new  (size_t count) { return g_GstAlloc.Alloc(count); }
    //void operator delete(void *p) { g_GstAlloc.Free(p); }
    void getDepthCounts(std::vector<unsigned> &depth, size_t nLevel = 0)const
    {
        if (depth.size() <= nLevel)
            depth.resize(nLevel + 1);
        depth[nLevel]++;
        for (Vertex*v : children)
            v->getDepthCounts(depth,nLevel + 1);
    }
    Vertex *getOrCreateChildVertex(char c )
    {
        Vertex *out = getChild(c);
        if (!out)
        {
            out = new Vertex(c);
            children.push_back(out);
        }
        return out;
    }

    void getTerminators(std::vector<Terminator> &out, size_t limit )
    {
        if (out.size() >= limit)
            return;
        out.insert(out.end(), terminators.begin(), terminators.end());;
        for (Vertex* c: children) {
            c->getTerminators(out, limit);
            if (out.size() >= limit)
                break;
        }
    }
    Vertex *getChild(char c) 
    {
        for (Vertex *p : children)
            if (p->c == c)
                return p;
        return nullptr;
    }
    size_t memSize()const
    {
        size_t out = sizeof(*this) + terminators.size() * sizeof(terminators[0]);
        for (Vertex*v : children)
            out += sizeof(v) + v->memSize();
        return out;
    }
};

class Root : public Vertex 
{
public:
    Root():Vertex(0) {  }
    void appendString(const char *str, int id )
    {
        for (volatile size_t len = strlen(str), suffix = len; suffix-- > 0;)
        {
            Vertex* parent = this;
            for (size_t pos = suffix; pos < len; pos++)
            {
                parent = parent->getOrCreateChildVertex(str[pos]);
            }
            parent->terminators.push_back(Terminator(id, (int)suffix));
        }
    }

    void findSubstr(std::vector<Terminator> &out, const char *substr, size_t limit )
    {
        Vertex *parent = this;
        for (size_t len = strlen( substr ), i = 0; i < len; i++)
        {
            parent = parent->getChild(substr[i]);
            if (!parent)
                return;
        }
        parent->getTerminators(out, limit);
    }
};

Bo Persson的评论提示，我重新阅读了后缀树上的维基百科文章，并最终点击了它。我仍然可能会误解后缀树，但是这种特殊的内存爆炸是由我在每个节点上用单个字符构建扩展树（我们称之为字符树）引起的。这是一个不正确的格式。

Ukkonen的算法以及所有其他后缀树构建算法在O（n）时间内构建树，其中包含提示。一个字符串ABCD .... XYZ将有O（n ^ 2）个节点的字符树，这显然不可能在O（n）时间内建立。

正确的后缀树必须包含具有唯一子字符串的节点（在wiki页面中，BANANA $是一个节点而不是6个节点加终止符）。它需要固定内存（例如，第一个字符和长度的索引）。

Ukkonen的算法洞察力正在优化AAAAAA ... AAAAA字符串的情况。这样的字符串具有O（n）个后缀树节点（还有O（n）个“字符树”节点），而且耐用的构建需要O（n ^ 2）个时间，因为您必须跟踪每一步中越来越多的节点串。但是，通过Ukkonen的后缀链接添加每个后缀需要O（1）次操作（它只是在末尾添加一个节点，并且在后续链接后再停止）。

在ABCD ... XYZ字符串的情况下，正确的后缀树仍然会有O（n）个节点。例如，后缀FGH ... XYZ将只有一个节点。

在我的代码中，该后缀将生成21个单独的节点。这就是创建O（n ^ 2）内存消耗的原因，基本上我误解后缀树节点是一个子串而不是一个字符。

链接地址: http://www.djcxy.com/p/40105.html

上一篇: Suffix tree of large (10Mb) text taking excessive memory

下一篇: What are the differences between suffix links and failure links?