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

我实现了（参见下面的代码）绝对最小的通用后缀树构建算法 . 我写了一个单元测试，它似乎按预期工作（在正确的位置找到正确的子串） . 但这棵树实在太大了 . Question: 我在某处犯了错误，或者这种基本形式的后缀树只能用于非常短的文本吗？

Statistics

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

当我构建40'000字符串2.5Mb后缀树（如果公司名称是一个列表），树需要400Mb . 我可以将其优化大约4倍，但即便如此，每个字符的原始文本也要超过40个字节 . 这是正常的吗？文献中的估计对我来说这很高 .

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

在进一步使用15MB文本的实验中，在我添加前10个'000 suffixes (long to short). There'几乎没有重复的子串之后，我耗尽了2Gb的内存，因此树不能重复使用 . 我完全可以看到后缀 array 实际上是多么有用，每个字符需要固定2-4个字节，并且在20Mb文本中每次搜索只需要24个字符串比较 . 对于具有所有唯一字符的字符串，我可以't possibly see how suffix tree with as many vertices as there are unique substrings in text can fit in memory. It'的O（n ^ 2）个节点，但对于英文文本它似乎仍然非常超线性 . 后缀树如何为大文本工作？我读过的论文和问题似乎暗示它应该是可用的，因此我的问题在这里 .

Questions

我在某个地方犯了一个错误，使树比它应该更大吗？

建造后缀树的方式应该与最终的树形状无关？这是正确的吗？

我的不是Ukkonen算法，而只是强力将所有后缀添加到树中以简化代码和数据结构（无后缀链接字段）并稍后将perf与Ukkonen进行比较 . 建造方法应该只影响建筑的速度，树的大小或形状 . 无论哪种方式，构建树都是递增的，因此比最终树更大's no intermediate result that' .

这是代码：

#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);
    }
};