声明

欢迎提出反例来证明代码有bug, 虽然我自己测试了一段时间，但毕竟测试不能证明一段代码没有bug👻

前言

最近项目中的一个关键算法使用了后缀树(Suffix Tree)来优化匹配速度，所以花时间去研究了一下。
后缀树是一种数据结构，能够帮助我们快速解决很多关于字符串的问题。后缀树的概念最早由Weiner在1973年提出，后来 McCreight 和Ukkonen又对其做了改进和完善，本文的主角就是Ukkonen在论文On–line construction of suffix trees中提出的后缀树构造算法。

什么是后缀树

先给你们看一幅恐怖的后缀树表示图：

参考的一篇论文中对后缀树的介绍

是不是顿时感觉很头疼👀？
其实还没到头疼的地方。

笔者理解后缀树的过程是: 字典树(Trie) ->后缀字典树(Suffix Trie) -> 压缩之后的后缀字典树，即后缀树。

什么是字典树(Trie)

Trie常用于词频统计及大量字符串的排序，核心思想是空间换时间。
Trie长这样：
插入ABABA, ABABC

从根节点到叶节点就能表示一个唯一的字符串

再插入ABBAC

分叉之前的部分表示字符串的公共前缀

Trie的基本性质可以归纳为：

1. 根节点不包含字符，除根节点意外每个节点只包含一个字符。
2. 从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
3. 每个节点的所有子节点包含的字符串不相同。

Trie的结构就是这么简单直接。如果我们在节点的实现类上加一个计数属性，然后
在每次新字符串插入完成时将所在节点的计数加一，我们就可以实现词频统计了。

什么是后缀字典树(Suffix Trie)

把一个字符串的所有后缀都插入到Trie中，就得到了Suffix Trie。

Suffix Trie

压缩我们的Suffix Trie

通过观察上图，我们可以发现一个问题。
（树太长了一屏都放不下？逃。。。。。
树确实太长了，对于那些没有分叉的一连串节点，完全可以压缩成一个单独的节点。
像这样：

Suffix Tree

abab的后缀有：
abab, bab, ab, b.
其中ab, b都被隐式的包含了，所以在图中要好好找一找才能找到。
我们还发现图中有两条虚线箭头，这玩意叫Suffix Link, 是后缀树中一个很重要的概念，下文会详述。
现在我们对后缀树已经有了一个直观感受了，对其的一些应用想必也很容易理解。比如模式匹配。在KMP算法中，我们对模式串进行处理，这种方式在模式串数量巨大而文本有限时就会显得低效。这个时候对文本进行处理的后缀树的优势就体现出来了。
在使用Ukkonen的算法进行后缀树的构造时，设文本长度是n, 则时间和空间复杂度都是O(n), 匹配某个特定长度为k的模式时，时间复杂度是O(k)。

Ukkonen's Algorithm的流程

接下来我们以aaaabbbbaaaabbbb这个字符串为例，描述一遍这个算法的流程。
我们最后构造出来的后缀树长这样：

字符串aaaabbbbaaaabbbb$的后缀树

联系上文我们知道有一部分后缀因为重复的原因被隐式的包含了，而我们在实践中并不希望这样的情况出现，所以我们用一个唯一的标识符$来表示字符串的结尾，这样每一个后缀都有一个唯一的结尾标识符，就只能被显示的分叉出来👀。

Let's begin

代码实现的上下文：

程序的输入是需要构建后缀树的字符串text。

1. Index指针，指向字符串中具体的某一个字符。
2. ActivePoint(active_node, active_edg, active_length), 它是一个三元组，里面记录了当前活动节点，活动边，及活动长度。对于这个概念先不要慌，看下去就能明白是干什么的，初始值是(root, null, -1)。
3. remainder, 表示我们还需要插入多少个后缀，初始值是0。

4. 节点：在这里使用节点来保存信息，保存的信息有该节点中保存的字符串在text中的开始和结束位置，它的子节点们，以及它的SuffixLink链接的节点。
   初始化我们的后缀树，让它有一个根节点

   
   空的后缀树

Index = 0，ActivePoint(root, null, -1), remainder = 0

我们需要插入到位置0为止该字符串的所有后缀，即：a。

屏幕快照 2018-04-04 下午3.10.20 (2).png

Index = 1, ActivePoint(root, aa, 0), remainder = 1

屏幕快照 2018-04-04 下午3.19.34 (2).png

神奇的事情出现了。因为我们是使用左右指针来代表节点中保存的字符串，所以有一件事情我们要注意----所有的叶节点的右指针跟Index指针保持一致。
当Index变成1的时候，我们需要插入的后缀是：aa, a。
节点一的右指针随着Index自动加一，所以aa已经在里面了,我们还需要插入a。
这个时候我们发现a已经被隐式的包含了。
就这么算了？
当然不，我们必须保证所有的后缀都被表示出来，所以我们需要remainder来记录我们还需要插入多少个后缀，并用ActivePoint这个标记，用来表示被隐式包含的后缀在哪。所以现在，remainder变成了1， ActivePoint变成了：root的一个叫aa的子节点的0位置。即a。

Index = 2, ActivePoint(root, aaa, 1), remainder = 2

屏幕快照 2018-04-04 下午3.30.23 (2).png

现在remainder变成2了，因为aa, a被隐式包含了。

Index = 3, ActivePoint(root, aaaa, 2), remainder = 3

屏幕快照 2018-04-04 下午3.32.28 (2).png

Index = 4, ActivePoint(root, aaa, 1), remainder = 3;

屏幕快照 2018-04-04 下午3.34.16 (2).png

这一步发生了什么：
我们前进到位置4时，新的字符b出现了，现在待插入的后缀是aaab, aab, ab, b。
如果我们在ActivePoint继续往下走，我们会发现下一个是a, 跟b不一样，当前节点是aaaab, 所以aaab并没有被隐式包含。所以树要分叉了。在 aaaab中插一个节点进来，把aaaab分裂成aaa和ab, 这样我们就插入了aaab。
现在还剩下aab, ab, b。

这个分叉给我们带来了一个问题，在active_node是根节点的时候，分叉发生之后，我们怎么更新ActivePoint?

我们前面说过，ActivePoint是用来表示被隐式包含的待插入后缀的，所以，当前位置的隐式包含后缀被插入了，当然是当前插入的后缀aaab往前进一个位置，删掉第一个字符成aab，即active_length - 1。

由于后缀树的特性，当更长aaa的后缀都被隐式包含的时候，短一个字符的后缀aaa肯定也被包含了，而且既然前一个是从root节点的子节点，那后一个肯定也一样，这个特性很容易验证，所以active_node依然是root。

那active_edg又怎么更新呢？我们此时就要开始寻找active_node的子节点中以新后缀的开头开头的子节点了，这个时候还是以a开头的，所以不变(如果不是以a开头的，就需要更换active_edg了)，此时ActivePoint变成了(root, aaa, 1)。

aab被隐式包含了吗？没有，所以我们继续分叉

屏幕快照 2018-04-04 下午3.47.08 (2).png

并更新ActivePoint为(root, aa, 0); remainder减去1变成2。
此时我们注意到a和aa被一个虚线箭头链接了起来，这个箭头叫SuffixLink, 意义在于比如当我们的ActivePoint指向Node1的位置0时， 即隐式包含了aaaa时，我们遇到新的字符串$，于是通过分叉把aaaa$插进去，接下来插需要插aaa$，我们只需要跟着suffixLink走就能确定新的ActivePoint的Active_node的位置，而活动长度只需要保持不变。(那我们怎么确认是active_node跟哪个个子节点的边是active_edg的呢？不好意思，我们只能遍历一下找一找，看看哪个子节点是a开头的）。关于SuffixLink的使用后面会有体现。
如果看不懂前面的描述，只需要先记住：

在一次插入剩余后缀的流程中后面分裂的节点都应该被前面分裂的节点用SuffixLink链接起来。

接下来我们再度分叉插入ab

屏幕快照 2018-04-04 下午4.06.18 (2).png

b没有被隐式包含，此时ActivePoint是(root, null, -1);
直接插入b

屏幕快照 2018-04-04 下午4.07.53 (2).png

因为隐式包含的原因，往前走了三步

Index = 7, ActivePoint(root, bbbb, 2), remainder = 3;

屏幕快照 2018-04-04 下午4.16.26 (2).png

Index = 8, ActivePoint(root, null, -1), remainder = 1

重复上面的分叉流程

插入了bbba, bba, ba

屏幕快照 2018-04-04 下午4.19.46 (2).png

新的问题出现了，a这个后缀被隐式包含了，所以我们退出这次插入，把活动点改成(root, a, 0)。但我们发现，这个时候我们的活动点指向了Node6的结尾，所以我们需要将ActivePoint更新位(6, null, -1)。这样我们才能继续隐式包含的查找。

Index = 8, ActivePoint(6, null, -1), remainder = 1

屏幕快照 2018-04-04 下午4.24.42 (2).png

通过观察图像我们可以预料到，接下来的aaabbbb全是已经在树中的，所以我们会得到：

Index = 15, ActivePoint(2, abbbbaaaabbbb, 4), remainder = 8

屏幕快照 2018-04-04 下午4.28.20 (2).png

接下来就是我们的$大显神威的时候了，它会把所有的隐式包含后缀都变成显式的。
而且现在我们面临了新的情况，active_node不是根节点，所以我们会探讨这个时候发生节点分裂后怎么更新active_node。
我们也发现了图中有大量的SuffixLink, 所以我们也会探讨SuffixLink的使用。
我们现在的情况，简单一点来说，就是在Index指向$时，插入aaaabbbb$的所有后缀。

Index = 16, ActivePoint(2, bbbbaaaabbbb$, 3), remainder = 8

屏幕快照 2018-04-04 下午5.00.34 (2).png

这一步发生了什么？
首先，我们照例分裂了activePoint指定的节点，插入$, 完成了aaaabbbb$的插入。

然后发现，这里没有SuffixLink, 但是，既然aaaabbbb都被包含了，那么aaabbbb一定也已经被包含了，所以我们把active_node设置成了root。

由于接下来需要插入aaabbbb$, 所以active_length是6(注意对长度的计数为了实现的方便也从0开始)。

从root开始，我们顺着aaabbbb在树中的路径一路前进，就能发现aaabbbb在树中的结尾在2的子节点bbbbaaaabbbb$的位置3，于是，新的ActivePoint就被确定了：

（2，bbbbaaaabbbb$, 3)。

这是比较繁琐的一步，有了suffixLink的话会简单很多。

Index = 16, ActivePoint(4, bbbbaaaabbbb$, 3), remainder = 7

屏幕快照 2018-04-04 下午5.11.16 (2).png

观察：SuffixLink的妙用：

我们通过分裂节点3（bbbbaaaabbbb$）可以完成aaabbbb$的插入。
然后跟着SuffixLink把active_node设置成节点4，active_length不变，active_edg也不变。
我们可以验证，通过suffixLink来更新 activePoint和通过把active_node设置为root然后一步一步往前走得到的结果是一样的。

当我们分裂了一个节点需要更新active_node的时候，如果当前的active_node有suffixLink, 我们直接把active_node更新成被指向的节点，activePoint的其他数据不变。

于是我们按照上述流程继续分裂或插入后缀，就能得到我们的最终结果。
再放一遍图：

屏幕快照 2018-04-04 下午5.20.59 (2).png

以上是对整个算法流程的描述，如果觉得笔者没有讲清楚，可以到Visualization of Ukkonen's Algorithm上跟一遍完整的流程。喜欢英文资料的童鞋们也可以到stackoveflow上看一下外国某大佬的解释😼。不过最好的学习方式当然还是自己实现一遍啦👀。

Java实现

当前还只是尝试性的实现，并没有翻译成项目用的语言并加入到项目中，有兴趣的同学可以读一读测一测，如果能帮忙找出Bug那就真是太感谢了（毕竟整合进项目要改就比较爆炸😓）
GitHub