占用过多内存的大型(10 of )文本的后缀树
我实现了绝对最小广义后缀树构建算法(见下面的代码)。我编写了一个单元测试，它似乎像预期的那样工作(在正确的位置找到正确的子字符串)。但这棵树实在是太大了。问题：，我在什么地方犯了一个错误，还是这种基本形式的后缀树只适用于非常短的文本？
统计
我想用这个搜索大量的文本:多个15-20Mb文本文件，或者像40,000个字符串~60个字符。
当我构建40'000字符串2.5Mb后缀树(如果是一个名称为公司名称的列表)时，该树需要400 if。我可能会优化它大约4倍，但即使这样，它将是超过40个字节的每个字符的原始文本。这正常吗？文献中的估计数字对我来说是很高的。
每株树的平均分枝因子为: 80 40 8 3 2 1 1.也就是说，只有树的前3-5层实际上是树枝。我更好地构建3-5层和保持长文本后缀节点。5级以下的所有内容基本上都是链接的字符列表。这是预期的表现吗？这很直观，公司名称之间共享的6+字符子串不多。
在对15 10文本的进一步实验中，在添加前10,000个后缀(长到短)后，我耗尽了2Gb的内存。几乎没有重复的子字符串，所以树不能重用太多。我完全可以看到后缀数组是如何实际有用的，它需要固定的每个字符2-4字节，并且在20 of的文本中每次搜索只需要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);
}
};回答 1
Stack Overflow用户
发布于 2018-01-13 03:08:28
在博·佩尔松评论的推动下，我重新阅读了维基百科的后缀树文章，终于点击了.我可能仍然误解了后缀树，但是这种特殊的内存爆炸是由于我在每个节点上构建一个扩展树(我们称之为字符树)而造成的。这是不正确的格式。
Ukkonen的算法以及所有其他后缀树构建算法都是在O(n)时间内构建的，其中包含了一个提示。字符串ABCD....XYZ将具有O(n^2)节点的字符树，这显然不可能在O(n)时间内构建。
适当的后缀树必须有具有唯一子字符串的节点(在wiki页面中，香蕉$是一个节点，而不是6个节点加上一个终止符)。它使用固定内存(例如，第一个字符和长度的索引)。
Ukkonen的算法洞察力在于优化AAAAAA...AAAAA字符串的情况。这样的字符串具有O(n)后缀树节点(以及O(n)“字符树”节点)，而天真的构建需要O(n^2)时间，因为您必须在每一步中跟踪不断增长的节点字符串。但是，对于Ukkonen的后缀链接，添加每个后缀需要O(1)操作(它只是在末尾添加一个节点，在后缀链接之后，它就停止了)。
对于ABCD...XYZ字符串，适当的后缀树仍然有O(n)节点。例如，后缀FGH...XYZ将只有一个节点。
在我的代码中，这个后缀将生成21个独立的节点。这就是造成O(n^2)内存消耗的原因，基本上我对后缀树节点是一个子字符串而不是一个字符的误解。
https://stackoverflow.com/questions/48236299
复制相似问题
腾讯云开发者
