问题标签 [suffix-tree]

我已经对一个研究项目进行了基本搜索。我试图通过构建后缀树来提高搜索效率。我对Ukkonen算法的 C# 实现感兴趣。如果存在这样的实现，我不想浪费时间自己动手。

我正在寻找具有以下功能的通用后缀树 (GST) 的 Java 实现：

在从 1000 个字符串创建 GST 之后，我想知道这 1000 个字符串中有多少包含其他字符串“s”。

搜索必须快速安静，因为我需要对大约 100'000 个平均长度为 10 的候选字符串进行搜索。

我正在使用 Ukkonen 的算法来构建后缀树，但我不理解作者对其线性时间复杂度的解释的某些部分。

我已经学习了算法并对其进行了编码，但是我用作主要信息来源的论文（链接如下）在某些部分有点令人困惑，所以我不清楚为什么算法是线性的。

有什么帮助吗？谢谢。

链接到 Ukkonen 的论文：http ://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

有人可以指出关于“令牌后缀树”的教程。

我正在寻找一种简短、简单的 Java 后缀树构建/使用算法。到目前为止，我发现的最好的是 Semantic Discovery Toolkit，但它的实现有几千行长并且跨越了几个类。理想情况下，实现应该尽可能短，并且不超过几百行。

有没有人有这样的实现？

我正在尝试在 C++ 中构建一个后缀树，作为基因测序任务的一部分

chooseBranch()是一个函数来选择 4 个孩子中的哪一个，我正在尝试检查这个节点是否已经存在。我的节点类是：

这个 if 语句给了我一个段错误，我使用 gdb 回溯到：

这种形式的 NULL 检查有什么问题/我还能如何检查节点是否没有数据？

给定一个单词字典和一个初始字符。通过连续添加一个字符来找到字典中可能最长的单词。在任何给定的情况下，该词都应该是字典中的有效词。

例如：a -> at -> cat -> cart -> chart ....

我有两个非常大的字符串，我正在尝试找出它们的Longest Common Substring。

一种方法是使用后缀树（假设具有非常好的复杂性，尽管实现复杂），另一种是动态编程方法（以上链接的维基百科页面都提到了这两种方法）。

使用动态规划

问题是动态规划方法的运行时间很长（复杂度是O(n*m), wheren和m是两个字符串的长度）。

我想知道的（在开始实现后缀树之前）：如果我只想知道公共子字符串的长度（而不是公共子字符串本身），是否可以加快算法速度？

上周我进行了一次实习面试，我收到了一个关于在大型数据库中搜索特定字符串的问题。面试的时候我完全不知道，虽然我只是回复了“多级哈希”，因为这是我知道的唯一一个时间效率最高的hin，经过一番谷歌搜索后，我认为他期望的答案是后缀树。现在，在我的搜索过程中，我找到了构建后缀树的算法，甚至还有关于如何构建后缀树的研究论文！！那么真的有可能实现字符串匹配算法的后缀树，尤其是在面试期间吗？

如果有人可以照亮它，那就太好了。

提前致谢

在过去的几天里，我对此进行了广泛的研究，我读了很多东西，以至于我现在比以往任何时候都更加困惑。如何在大型数据集中找到最长的公共子字符串？这个想法是从这个数据集中删除重复的内容（长度不同，所以算法需要连续运行）。大型数据集是指大约 100mb 的文本。

后缀树？后缀数组？拉宾-卡普？最好的方法是什么？那里有可以帮助我的图书馆吗？

真的希望得到一个好的回应，我的头很痛。谢谢！:-)