此时我觉得有点厚.我花了几天时间试图完全用后缀树构建我的头,但由于我没有数学背景,因为他们开始过度使用数学符号系统时,许多解释都没有.最接近我发现的一个很好的解释是使用后缀树进行快速字符串搜索,但是他隐藏了各种点,并且算法的某些方面仍然不清楚.
在Stack Overflow中对此算法的逐步解释对于我以外的许多其他人来说都是非常宝贵的,我敢肯定.
作为参考,这里是Ukkonen关于该算法的论文:http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
到目前为止我的基本理解:
基本算法似乎是O(n 2),正如我们在大多数解释中所指出的那样,因为我们需要遍历所有前缀,然后我们需要逐步遍历每个前缀的每个后缀.由于他使用的后缀指针技术,Ukkonen的算法显然是独一无二的,尽管我认为这是我无法理解的.
我也很难理解:
这是完成的C#源代码.它不仅工作正常,而且支持自动规范化,并提供更好看的输出文本图形.源代码和示例输出位于:
更新2017-11-04
多年以后,我发现了后缀树的新用途,并在JavaScript中实现了该算法.要点如下.它应该没有错误.npm install chalk从同一位置将其转储到js文件中,然后使用node.js运行以查看一些彩色输出.在同一个Gist中有一个精简版本,没有任何调试代码.
https://gist.github.com/axefrog/c347bf0f5e0723cbd09b1aaed6ec6fc6