问题标签 [suffix-tree]

后缀树中的最大和最小边数是多少？我知道最大值是 2m-1，但我不明白为什么会这样。

我必须从大型 PDF 文档中构建某种“字符串目录”，以便更快地搜索字符串/子字符串。

该机制应该像这样工作：PDF 扫描仪扫描 PDF 文档中的字符串，并在我的目录中调用回调方法来索引该字符串。

现在，应该使用什么技术来构建这样的目录？我听说过： - 后缀树 - 广义后缀树 - 后缀数组

我主要倾向于广义后缀树。那我是对还是错？我猜“普通”后缀树只适用于索引单个字符串。

但是后缀数组呢？那里有通用的后缀数组吗？

我在 C/C++ 中发现了很多用于从字符串构建后缀树的代码，但没有用于构建通用后缀树的代码！

我正在寻找一种有效的数据结构来对一组非常庞大的字符串进行字符串/模式匹配。我发现了尝试、后缀树和后缀数组。但是到目前为止，我在 C/C++ 中找不到一个现成的实现（而且我自己实现它似乎很困难并且容易出错）。但我仍然不确定 Suffix-Arrays 是否真的是我正在寻找的东西......我已经尝试过 libdivsufsort 和 esaxx，但无法找到如何使用它们来满足我的需求：

我想使用一组预定义的字符串，带有通配符（甚至是正则表达式）来匹配用户输入。我有一大堆预定义的字符串，即

“什么是 *？” “什么是 XYZ？” “多少 *？” ...

现在我想找到最匹配的字符串（如果有的话，那就完全匹配了）。即用户输入：>什么是XYZ？应该找到“什么是 XYZ？” 而不是“什么是*？”，而是“什么是什么？” 应该找到“什么是*？” （假设 * 是任何字符数的通配符）。

构建结构不是时间紧迫的（并且结构不必非常节省空间），但搜索不应该花费太长时间。怎么能轻易做到呢？欢迎任何框架/库或代码示例

谢谢

后缀树中的最大和最小节点数是多少？我该如何证明呢？

我们可以使用带有后缀树的圆形字符串吗？所以最后一个字符后面是列表中的第一个字符。

如果是这样，这个后缀树的表示与普通的后缀树有什么不同？

为什么我们在实现后缀树时需要将“$”附加到原始字符串？

我正在寻找具有模仿 python 字典的友好 API 的后缀树实现：

我从这个网站上举了这个例子：Python 中的后缀树 你可能会问：“你为什么不使用网站上的实现？” 好吧，显然它在 python 绑定中有一些内存泄漏，所以我不能将它与我的大型（120 万个字符串，大约 200 MB）数据集一起使用。

我什至会对使用以下 API 的 C++ 实现（我可以自己编写 python 绑定）感到满意：

有什么提示吗？

根据维基百科，实现后缀树时的一个重要选择是节点之间的父子关系。最常见的一种是使用称为兄弟列表的链表。

这在 Java 中是如何工作的？

我已经实现了一个算法来构造一个后缀树。现在，我正在尝试实现一个方法计数，该方法返回查询发生的次数作为参考序列的子列表/子间隔。最好的方法是什么？

例子：

序列的后缀树

询问

结果

来自编程珍珠的第 15.2 节

C代码可以在这里查看：http ://www.cs.bell-labs.com/cm/cs/pearls/longdup.c

当我使用后缀数组在 Python 中实现它时：

我发现这idx.sort一步很慢。我认为这很慢，因为 Python 需要按值而不是按指针传递子字符串（如上面的 C 代码）。

测试文件可以从这里下载

C 代码只需 0.3 秒即可完成。

但是对于 Python 代码，它永远不会在我的计算机上结束（我等了 10 分钟并杀死了它）

有谁知道如何使代码高效？（例如，少于 10 秒）