标签: suffix-tree

此时我觉得有点厚.我花了几天时间试图完全用后缀树构建我的头,但由于我没有数学背景,因为他们开始过度使用数学符号系统时,许多解释都没有.最接近我发现的一个很好的解释是使用后缀树进行快速字符串搜索,但是他隐藏了各种点,并且算法的某些方面仍然不清楚.

在Stack Overflow中对此算法的逐步解释对于我以外的许多其他人来说都是非常宝贵的,我敢肯定.

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

到目前为止我的基本理解:

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

基本算法似乎是O(n ²),正如我们在大多数解释中所指出的那样,因为我们需要遍历所有前缀,然后我们需要逐步遍历每个前缀的每个后缀.由于他使用的后缀指针技术,Ukkonen的算法显然是独一无二的,尽管我认为这是我无法理解的.

我也很难理解:

• 确切地指定,使用和更改"活动点"的时间和方式
• 算法的典型化方面发生了什么
• 为什么我看到的实现需要"修复"他们正在使用的边界变量

这是完成的C#源代码.它不仅工作正常,而且支持自动规范化,并提供更好看的输出文本图形.源代码和示例输出位于:

https://gist.github.com/2373868

更新2017-11-04

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

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

我正在阅读Tries通常称为前缀树和Suffix Trees.
虽然我找到了代码,但Trie我找不到一个例子Suffix Tree.此外,我感觉构建a的代码与a的代码Trie相同,Suffix Tree唯一的区别是在前一种情况下我们存储前缀但在后面的后缀中.
这是真的？任何人都可以帮我解决这个问题吗？一个示例代码将是很好的帮助!

我试图在字符串中找到最长的回文.蛮力解决方案需要O(n ^ 3)时间.我读到有一个使用后缀树的线性时间算法.我熟悉后缀树,很舒服地建造它们.如何使用构建的后缀树找到最长的回文.

给定一系列操作:

A*B*A*B*A*A*B*A*B

有没有办法获得最佳细分以启用子串的重用.

制造

a*b*a*b*a*a*b*a*b => c*a*c,其中c = a*b*a*b

然后看到了

a*b*a*b => d*d,其中d = a*b

总而言之,将8个初始操作减少到这里描述的4个？

(c =(d = a*b)*d)*a*c

当然,目标是尽量减少操作次数

我正在考虑各种后缀.

我对线性时间启发式或解决方案特别感兴趣.'*'操作实际上是矩阵乘法.

要构建一个后缀树,在最坏的情况下,如果字符串的所有字母都不同,那么复杂性将是类似的

n + (n-1) + (n-2) ... 1 = n*(n+1)/2

这是O(n ^ 2).

但是根据http://en.wikipedia.org/wiki/Suffix_tree构建后缀树需要花费O(n)时间.我在这里错过了什么？

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

我已经学会了算法并对其进行了编码,但是我用作信息主要信息源的文章(链接波纹管)在某些部分有点令人困惑,因此对我来说,为什么算法是线性的并不是很清楚.

有帮助吗？谢谢.

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

谁能给我一个关于如何以及何时在后缀树中创建后缀链接的示例？

如果我的字符串是ABABABC,但如果更好,请使用不同的示例.

希望能给出一些图片来说明每一步.

非常感谢.

我试图将BioPython序列传递给Ilya Stepanov在iPython笔记本环境中实现Ukkonen的后缀树算法.我在argparse组件上遇到了绊脚石.

我之前从未直接与argparse打过交道.如何在不重写main()的情况下使用它？

通过这个,这个Ukkonen算法的写法非常棒.

我需要python库,它可以构造后缀树,特别是通用的后缀树.你能给我一些图书馆吗？谢谢.

对于上下文,我编写了这个算法来获取任何字符串的唯一子串的数量.它为计算其包含的节点的字符串构建后缀树,并将其作为答案返回.我想要解决的问题需要一个O(n)算法,所以这个问题只是关于这个代码的行为方式,而不是关于它的作用有多糟糕.

struct node{
    char value = ' ';
    vector<node*> children;
    ~node()
    {
        for (node* child: children)
        {
            delete child;
        }
    }
};

int numberOfUniqueSubstrings(string aString, node*& root)
{
    root = new node();
    int substrings = 0;
    for (int i = 0; i < aString.size(); ++i)
    {
        string tmp = aString.substr(i, aString.size());
        node* currentNode = root;
        char indexToNext = 0;
        for (int j = 0; j < currentNode->children.size(); ++j)
        {
            if (currentNode->children[j]->value == tmp[indexToNext])
            {
                currentNode = currentNode->children[j];
                j …