问题标签 [suffix-tree]

根据维基百科关于后缀树的文章，如果允许一定数量的错误，后缀树可用于定位字符串的子字符串。

给定字符串的后缀树，我怎样才能找到它的给定子字符串的所有实例，而每个实例最多允许一个错误？

（“错误”是指替换一个字符。）

1973 年 Weiner 给出了后缀树的第一个线性时间构造。该算法于 1976 年由 McCreight 和 1995 年由 Ukkonen 简化。尽管如此，我发现 Ukkonen 的算法在概念上相对复杂。

自 1995 年以来，Ukkonen 的算法是否有过简化？

我需要可以构建后缀树，尤其是通用后缀树的 python 库。你能给我推荐一些图书馆吗？谢谢。

后缀数组将索引给定字符串列表的所有后缀，但是如果您尝试索引所有可能的唯一子字符串怎么办？我对此有点陌生，所以这是我的意思的一个例子：

给定字符串

后缀数组索引（至少在我的理解中）

我想索引（所有子字符串）

我正在寻找后缀数组吗？如果是这样，我该怎么做才能索引所有子字符串？如果没有，我应该在哪里寻找？另外我会用谷歌来对比“所有子字符串”与“后缀子字符串”吗？

这个时候我觉得有点厚。我花了几天时间试图完全理解后缀树的构造，但由于我没有数学背景，许多解释都让我无法理解，因为他们开始过度使用数学符号。我找到的最接近好的解释是Fast String Searching With Suffix Trees，但他掩盖了各个点，算法的某些方面仍不清楚。

我敢肯定，在 Stack Overflow 上一步一步地解释这个算法对于除我之外的许多其他人来说都是无价的。

作为参考，这里是 Ukkonen 关于算法的论文：http ://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

到目前为止，我的基本理解：

• 我需要遍历给定字符串 T 的每个前缀 P
• 我需要遍历前缀 P 中的每个后缀 S 并将其添加到树
• 要将后缀 S 添加到树中，我需要遍历 S 中的每个字符，迭代包括沿着以 S 中的相同字符集 C 开始的现有分支走下去，并可能在我将一条边拆分为后代节点时到达后缀中的不同字符，或者如果没有匹配的边缘可以向下走。当没有找到匹配的边缘向下走 C 时，为 C 创建一个新的叶边缘。

正如大多数解释中所指出的，基本算法似乎是 O(n ^{2 )，因为我们需要遍历所有前缀，然后我们需要遍历每个前缀的每个后缀。}Ukkonen 的算法显然是独一无二的，因为他使用了后缀指针技术，尽管我认为这是我无法理解的。

我也很难理解：

• 究竟何时以及如何分配、使用和更改“活动点”
• 算法的规范化方面发生了什么
• 为什么我看到的实现需要“修复”他们正在使用的边界变量

这是完整的C#源代码。它不仅可以正常工作，而且支持自动规范化并呈现更好看的输出文本图。源代码和示例输出位于：

https://gist.github.com/2373868

2017-11-04 更新

多年后，我发现了后缀树的新用途，并在JavaScript中实现了该算法。要点如下。它应该没有错误。将其从同一位置转储到 js 文件中，npm install chalk然后使用 node.js 运行以查看一些彩色输出。在同一个 Gist 中有一个精简版本，没有任何调试代码。

https://gist.github.com/axefrog/c347bf0f5e0723cbd09b1aaed6ec6fc6

我一直在寻找有关后缀树的教程很长一段时间。在 SO 中，我发现了 2 篇关于理解后缀树的帖子：1、2。

但我不能说我了解如何构建一个，哎呀。在 Skiena 的《算法设计手册》一书中，他说：

由于线性时间后缀树构造算法很重要，我建议使用现有的实现。

那么，后缀树的在线构造算法有那么难吗？任何人都可以让我朝着正确的方向理解它吗？

无论如何，切入正题，除了构造之外，关于后缀树还有一件事我不明白。因为后缀树中的边只是一对整数（对吗？）指定子字符串的开始和结束位置，那么如果我想x在这个后缀树中搜索一个字符串，我应该怎么做呢？取消引用后缀树中的那些整数，然后将它们与x? 不可能是这样的。

我正在搜索后缀树库（具有线性时间构造），我发现的只是 PATL，但 PATL 没有文档，我无法找出任何示例。那么是否有一个具有不错文档的 c++ 后缀树库？

PATL 主页： http ://code.google.com/p/patl/

编辑：
动机：我需要处理大量字符串并找到频繁的公共子字符串，并报告是否在 t 秒内发生了 n 次以上的任何子字符串。我实现了一个树（在节点中有计数器，实际上它不是一个计数器，而是一个访问时间的 std::vector，因为就像我说我需要时间一样），但它非常慢。所以我想到了增加（在字符串之间连接一些随机的东西，这样子字符串不会跨越一个以上的字符串）一定数量的消息（比如说 30 秒的数据），然后在那个字符串上构建一个后缀树.

我将为给定的字符串实现后缀树，我认为它应该像这样删除

//这里我要构建所有出现的子字符串和字符的树，但不知道如何使用左右部分，这棵树是按照严格的字符顺序排序和排列的，比如二叉搜索树吗？或者？请帮助我，我不知道想在网上使用一些代码，我需要自己实现，所以请给我一些提示，一些小代码

我在网上找到了后缀树的以下代码

这段代码几乎一切都清楚了，因为我之前已经读过很多次关于后缀树的内容，但我不明白这个片段：

这段代码有什么作用？

又是什么for()？还是j_start？

这是此代码的链接。

我构建了一个后缀树，一棵包含字符串所有后缀的树，其中每个节点只包含一个字符，每个路径的末尾都有一个 SuffixNode，其中包含字符串中后缀的位置。

假设我的 trie 包含单词“Cat”、“Car”和“Can”，我想搜索“Ca”，结果应该返回 3 个后缀节点，因为搜索字符串在 3 个不同的地方找到。我设法在树中搜索“Ca”，但一旦我到达那个点，我不知道如何继续遍历“a”节点的子节点以找到所有后缀节点。

我正在考虑使用某种集合将后缀节点添加到然后返回集合。这种方法有意义吗，还是有更好的解决方案？

我已经解决了下面的搜索问题。它没有返回任何节点的原因与树的创建和节点之间的差异有关：

节点：