相关疑难解决方法(0)

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

在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

我一直在寻找关于后缀树的教程很长一段时间.在SO,我发现了2个职位大概了解后缀树:1,2.

但我不能说我理解如何建立一个,哎呀.在Skiena的书"算法设计手册"中,他说:

由于线性时间后缀树构造算法非常重要,我建议使用现有的实现.

那么,后缀树的在线构造算法是如此难以实现吗？任何人都可以让我朝着正确的方向去理解它吗？

无论如何,切入追逐,除了建设之外,还有一件我对后缀树不了解的事情.因为后缀树中的边只是一对整数(右？),指定了子串的起始和结束位置,那么如果我想x在这个后缀树中搜索一个字符串,我应该怎么做呢？在后缀树中取消引用那些整数,然后逐个比较它们x？不可能这样.

我正在阅读"算法设计手册"中的数据结构章节,并遇到了后缀树.

该示例说明:

输入:

XYZXYZ$
 YZXYZ$
  ZXYZ$
   XYZ$
    YZ$
     Z$
      $

输出:

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