tree - 修改广义后缀树以保存节点在文本字符串中出现的次数

Question

如何修改Ukkonen 论文中的过程以保存一个单词在文本中出现的次数的值。是否有任何这样的实现也可以提供字符串频率？

我想要的修改就像一个字符串“hehe”，所有“h”、“e”、“he”的频率计数在树中应该是 2。其余节点的默认值为 1。

我发现了一些迄今为止最好的库和一些以前的问题。

但是他们都没有描述我的问题的足够好的解决方案。我还必须处理一个非常大的字典文件（大约十亿字）。然后算法需要非常快。我准备在空间上妥协一点。

Answer 1

答案可以在这里找到：计算子串的数量

基本上，构建后缀树，从根开始匹配子字符串并计算该点以下的叶节点。这是单词在文本中出现的次数。