问题标签 [suffix-tree]

我正在浏览The Algorithm Design Manual中的数据结构章节，并遇到了 Suffix Trees。

该示例指出：

输入：

输出：

我无法理解该树是如何从给定的输入字符串生成的。后缀树用于在给定字符串中查找给定子字符串，但给定树如何帮助实现这一点？我确实理解下面显示的另一个给定的 trie 示例，但是如果下面的 trie 被压缩为后缀树，那么它会是什么样子？

我正在构建一个数据结构来帮助索引总长度为 n 的 S 个文档的集合，以便它支持以下查询：给定两个单词 P1 和 P2，计算包含 P1 但不包含 P2 的所有文档。我希望答案是完整的（不要错过结果）。

我已经建立了一个通用的后缀树并选择每个 sqrt(n)-th 叶及其祖先（并删除每个单子节点）。对于每个内部节点 v，我预先计算针对节点 u 的查询的答案。

但是有了这个，如果查询包含出现在节点 v 和 u 中的树中的单词，我可以在 O(1) 中得到答案，但是当单词不在我们选择的节点之一时我该怎么办？

我可以通过使用预处理保持 O(n ² ) 数据结构并为 O(1) 时间检索准备好所有可能的答案来轻松做到这一点，但目标是在 O(n) 空间中构建此数据结构和使查询尽可能高效。

我只想知道，什么时候后缀树优于增强的后缀数组。

在阅读了用增强的后缀数组替换后缀树之后，我看不到使用后缀树的理由了。有些方法可能会变得复杂，但是您可以使用后缀数组来做所有事情，您可以使用后缀树来做任何事情，并且您需要相同的时间复杂度但更少的内存。

一项调查甚至表明，后缀数组更快，因为它们对缓存更友好，并且不会产生尽可能多的缓存未命中，然后是后缀树（因此缓存可以更好地预测数组使用情况，然后是递归树结构）。

那么，有谁知道选择后缀树而不是后缀数组的原因？

编辑 好的，如果您知道更多，请告诉我，到目前为止：

• 后缀数组不允许在线构建
• 一些模式匹配算法在后缀树上运行得更快
• （补充）由于在线构建，您可以将其保存在 hd a 并扩大现有的后缀树。如果您使用 SSD，它也应该很快安静。

我在一些代码上遇到了一些麻烦。请记住，我是一个糟糕的程序员，所以我的解决方案可能不是很有说服力（这可能是我内存不足的原因 - 我有 4 GB 并且脚本会慢慢填充它）。

这就是问题所在。我在一个目录中有大约 3,500 个文件。每个文件由一行组成，该行可以包含相对较少或许多没有空格的字符（最小的文件为 200 字节，而最大的文件为 1.3 兆字节）。我想要做的是在设定长度的两个文件之间找到一个公共子字符串（在下面的代码中它是 13 个字符）。我一次做两个，因为我不是在所有这些中寻找一个共同的子字符串，而是在比较所有文件之前两个的组合。即，文件之间设置长度的任何公共子字符串，而不是所有文件共有的子字符串。

我使用了一个包装了 C 实现的后缀树模块（在这里）。首先，我列出目录中的所有文件，然后查找两个文件的组合以覆盖所有组合，一次将两个文件传递给后缀树，然后查找作为公共子字符串的序列。

但是，我真的不知道为什么它会慢慢耗尽内存。我希望我们可以对代码进行修改，以便它以某种方式清除未使用内容的内存？显然，处理 3,500 个文件需要很长时间，但我希望无需增量填充 4 GB 内存就可以做到。任何帮助将不胜感激！这是我到目前为止的代码：

更新#1

这是更新的代码。我添加了 Pyrce 提出的建议。然而，在 jogojapan 发现 C 代码中的内存泄漏之后，鉴于这超出了我的专业知识范围，我最终采用了一种慢得多的方法。如果有人在这方面知识渊博，我真的很想知道如何修改 C 代码以修复内存泄漏或释放函数，因为我认为 Python 的 C 后缀树绑定非常有价值。在没有后缀树的情况下通过这个脚本运行数据可能需要几天时间，所以我绝对愿意看看是否有人有创造性的修复！

我有大约 3,500 个由单行字符串组成的文件。这些文件的大小各不相同（从大约 200b 到 1mb）。我正在尝试将每个文件与其他文件进行比较，并在两个文件之间找到一个长度为 20 个字符的公共子序列。请注意，每次比较期间，子序列仅在两个文件之间通用，而不是在所有文件中通用。

我在这个问题上遇到了一些困难，由于我不是专家，所以我最终得到了一些临时解决方案。我使用 itertools.combinations 在 Python 中构建一个列表，最终得到大约 6,239,278 个组合。然后，我一次将两个文件传递给一个 Perl 脚本，该脚本充当一个用 C 编写的名为libstree的后缀树库的包装器。我试图避免这种类型的解决方案，但 Python 中唯一可比较的 C 后缀树包装器存在内存泄漏。

所以这是我的问题。我已经计时了，在我的机器上，该解决方案在 25 秒内处理了大约 500 次比较。这意味着，完成任务需要大约 3 天的连续处理时间。然后我必须再次查看 25 个字符而不是 20 个字符。请注意，我已经超出了我的舒适区并且不是一个非常好的程序员，所以我确信有一个更优雅的方式去做这个。我想我会在这里问它并生成我的代码，看看是否有人对我如何更快地完成这项任务有任何建议。

Python代码：

Perl代码：

我想在未安装的 Perl 脚本中包含一个本地模块。下面的代码似乎适用于此目的。但是，我要包含的模块是 C 库的包装器。我这样做如下：

Perl 模块称为Tree::Suffix并充当libstree的包装器。我的问题是，我如何在本地也引用 C 库（假设它没有安装）。

我认为这与 Perl 模块的内部工作有关？如果这是一个业余问题，我深表歉意。谢谢！

我们可以使用带有后缀链接的因子-oracle（此处为论文）来计算多个字符串的最长公共子字符串吗？这里，子字符串表示原始字符串的任何部分。例如“abc”是“ffabcgg”的子字符串，而“abg”不是。

我找到了一种方法来计算两个字符串的最大长度公共子字符串s1和s2. 它通过使用不在其中的字符连接两个字符串来工作，例如'$'。s然后对于长度为 的连接字符串的每个前缀i >= |s1| + 2，我们计算其 LRS（最长重复后缀）长度lrs[i]和sp[i]（其 LRS 第一次出现的结束位置）。最后，答案是

我已经编写了一个使用这种方法的 C++ 程序，它可以在我的笔记本电脑上|s1|+|s2| <= 200000使用因子 oracle 在 200 毫秒内解决问题。

我知道使用 suffix-array 和 suffix-tree 可以高效地解决这两个问题，但是我想知道是否有使用因子 oracle 的方法来解决它。我对此感兴趣是因为因子 oracle 很容易构造（用 30 行 C++，suffix-array 需要大约 60，而 suffix-tree 需要 150），并且它比 suffix-array 和 suffix-tree 运行得更快。

您可以在此 OnlineJudge中测试您的第一个问题的方法，并在此处测试第二个问题。

假设我有文本“abcabx”。我想知道有一个重复的模式“ab”，它出现的所有位置，以及这些重复的上下文如何与它的其他出现相关。我还希望数据结构具有区分和隔离的独特模式“c”和“x”。我已经设置了一个后缀树来尝试这样做，它看起来像这样（来自this SO answer）：

这确实告诉我模式“ab”出现了两次，一次带有后缀“cabx”，另一次带有“x”。但是，根处的“ab”仅指向模式的第一次出现。它的叶子“cabx”中还嵌入了另一个“ab”，当我希望那个“ab”（在“cabx”中）以某种方式被确认为数据结构中的重复时。我知道根“ab”的“x”叶代表它，但我需要知道，在“ab”的“cabx”叶中，那里有一个“ab”。另外，两个独特的图案“c”和“x”是该边缘的一部分。加上它们在那个边缘的位置，以及它们的“主要定义”（根边缘？）之间的交叉引用。

更简单地说，数据结构需要清楚地说明“这是所有独特的模式”，“这是所有重复的模式以及它们发生的每个地方”，以及“这是关联所有这些事物的上下文” .

所以我想我正在为后缀树寻找一个类似图形的元素，它将划分出已知的模式并将它们明确地关联起来。在此过程中，将记录独特的模式。但是我还是想要后缀树的上下文特征，比如说“c”（不是“cabx”，而是“c”）和“x”都在“ab”之后，“abx”在“abc”之后，什么跟在他们之后（在更大的情况下）等等。是否有后缀树的改编可以做到这一点，或者可能是另一种算法？

我需要在字符串中找到最长的非重叠重复子字符串。我有可用的字符串的后缀树和后缀数组。

当允许重叠时，答案很简单（后缀树中最深的父节点）。

例如对于 String = "acaca"

如果允许重叠，则答案为“aca”，但不允许重叠时，答案为“ac”或“ca”。

我只需要算法或高级想法。

PS：我试过了，但在网上找不到明确的答案。

S对于给定的长度字符串n-

• S查找不能小于的所有唯一子串的最佳算法O(n^2)。所以，最好的算法会给我们带来O(n^2). 根据我所阅读的内容，这可以通过为S.

S的后缀树可以及时创建O(n)。现在，我的问题是——

我们如何使用 S 的后缀树来获取Sin的所有唯一子字符串O(n^2)？