算法书上没有的数据结构（一）-后缀树

前言

这个系列的文章将介绍一些在一般算法书上很少提到，但是在实际应用中却发挥着重要作用的数据结构。希望读者通过学习这些数据结构的原理与应用，为日后工作学习中的编程添加了更多选择。


后缀树

什么是后缀树

顾名思义，后缀树是基于树的一种数据结构，它表示了给定字符串的所有后缀，对字符串的许多重要操作能够提供快速的实现。后缀数在数据挖掘中被广泛的使用。它也是我本科毕业设计中的序列模式挖掘算法的核心数据结构。后缀树的定义如下：

  1. 对于一个m个字符长的字符串S, S对应的后缀树T有着m个叶子节点.
  2. 每个内节点（除了叶子节点和根节点以外的节点），都有至少有两个子节点，以及每条边都被S的非空子字符串所标记。
  3. 从根节点到叶子节点，将所有边的标记子字符串连接起来，必定是字符串S的一个后缀。

上面的定义过于抽象，让我们看一个实际的例子。对于字符串“BANANA”, 它的后缀树是：

我们通过上图来解释之前提到的后缀数的三个性质:
* 性质1：对于“BANANA”，该字符串的后缀有六个，而图中的树也有六个叶子节点。
* 性质2：对于图中的内节点（即圆形节点），都至少有两个子节点。而每条边上被子字符串所标记。
* 性质3：可以看到，从根节点到叶子节点1, 依次将边上标记的字符串连接起来，组成的是“ANANA”，是“BANANA”的一个后缀。实际上，从根节点到每个叶子节点的边的标记字符串的连接，都是“BANANA”的后缀。

细心的读者可能会发现，图中的字符串末尾有“$“符号。比如从根节点到叶子节点0的边上，标记的字符串是“BANANA$”，这个“$”有何用途呢？能否将它去掉呢？ “$”是为了解决一个问题而引入的方案。如果字符串S的后缀中，有后缀s1是后缀s2的前缀的话，那么在后缀树中，s1将不会以叶子节点结束。用“BANANA”的例子, 后缀“A”是后缀“ANANA”的前缀，没有“$”的话，那就没有叶子节点5, 那么“A”就只是一个内节点了，这违反了性质1，2。“$”是字符串的符号集以外的符号，将它添加到末尾后，就不会有后缀成为其他后缀的前缀了，那么性质1,2也就成立 了。理解这一点十分重要，希望读者想清楚这个问题。

如何构建后缀树

简单的算法

首先我们介绍一个简单的构建算法。对于一个长度为m的字符串S，定义S[i..j]是S从位置i到j的的子字符串。比如对于“BANANA”，S[4..6]是字串”ANA”。那么构建长度为m的字符串的后缀树的简单算法如下：

  1. 将一条边S[1..m]作为后缀树T的初始形状。
  2. 对于i = 2…m, 依次将S[i..m]插入到T中。

下图是以上述算法构建“BANANA”的后缀树的过程：

上图从左到右依次将后缀“BANANA”, “ANANA” …“A” 插入到后缀树中。对于长度为m的字符串，这个算法的时间复杂度是O(m2 )。在数据挖掘的应用中，对于大规模的数据集，这个算法的效率是不能满足需求的。

Ukkonen’s算法

Ukkonen’s算法是一个线性算法，该算法是E. Ukkonen在论文 《On-line construction of suffix trees》中提出的。我们先忽略一些细节，从高层次来描述该算法，让读者对算法的思想有大致的掌握。
首先，我们有以下的定义：

Ti 是字符串S的子串S[1..i]的后缀树。

Ukkonen’s算法分成m个步骤（m是字符串S长度），在步骤i+1中，我们将在后缀树Ti的基础上，构建后缀树Ti+1。而对于步骤i+1, 有i+1个操作。在第j个操作中，首先找到S[j..i]的叶子节点，然后将字符S[i+1]添加到叶子节点上。以“BANANA”为例子，一共有6个步骤。在第4步中，基于“BAN”的后缀树T3已经存在了，我们要在以T3为基础构建T4，即“BANA”的后缀树。在这一步中，将有4个操作，就是将字符“A”添加到T3的各个叶子节点中。要注意的是，这样描述的算法的时间复杂度是O( m3 )，比之前介绍的算法更慢！ 这是因为我们忽略了一些重要的优化手段。从高层次理解了算法的思路后，接着将介绍算法中如何使用优化手段将时间复杂度降为O(m)。

1. 后缀链接

后缀链接的定义如下：

xs表示任意字符串，其中x表示单个字符，而s表示字符串。对于后缀树中的节点v, 对应边上的标识字符串是xs。如果存在另外一个节点s(v), 其对应边上的标识字符串是s，那么从v到s(v)的链接就是后缀链接。

在第一幅图中，虚线表示的就是后缀链接。对于图中后缀树深度为1的两个内节点，右边的节点的对应边的标识字符串是”NA”，而左边节点的对应边的标识字符串是“A”, 因此从右边节点有一虚线指向左边节点。

了解了后缀链接的概念后，我们接下来看算法如何使用它来优化。在第i+1步骤的第j个操作中，我们已经将字符S[i+1]添加到S[j..i]的叶子节点。那么在第j+1个操作中，我们想要将S[i+1]添加到S[j+1..i]的叶子节点时，我们遵循以下规定：
1.完成第j个操作后，我们从S[j..i+1]的叶子节点往上前进，要么前进一步到了根节点，要么前进直到找到一个拥有后缀链接的节点v， 其中路径上的标识字符串是s。
2.如果找到v，那么沿着后缀链接走到s(v)。
3.从s(v)往下走，根据s选择路径，找到S[j+1..i]的叶子节点。

通过后缀链接，我们避免了每次操作都从根节点开始寻找需要改变的叶节点。以“BANANA“为例子，在第4步以T3(“BAN”)为基础构建T4(“BANA”), 完成了第一个操作，将“A”添加到“BAN”对应的叶节点。下一个操作，我们需要将“A”添加到”AN“, 注意根据定义从“BAN”的叶节点会有后缀链接到”AN“的叶节点，那么我们直接根据后缀链接就可以快速找到”AN“的叶节点了。当然这个例子比较简单，更加通用的例子可以根据下图来帮助理解：

2. 跳跃比较

第二个加速的技巧叫做跳跃比较。当从节点s(v)往下走时，我们不需要路径上标识字符串的每一个字符，只需要比较第一个字符串就可以了。这是因为根据后缀链接和后缀树的定义，如果v到从S[j..i+1]的叶子节点的路径标识字符串是a，那么从s(v)到S[j+1..i]的叶子节点的路径标识字符串叶也必定是a, 那么我们就可以放心只比较第一个字符就可以了，不必比较每一个字符，如下图所示：

3. 更多技巧

还有两个重要的加速的技巧是：
1.如果在第i+1个步骤，在第j个操作要将S(i+i)添加到S[j..i]时，发现S[j..i+1]已经存在了，那么我们可以结束这个步骤。因为S[k..i+1] (j< k < i)也必定已经存在于树中，没有必要做后面的的操作了。
2.一个叶子节点，在构建的过程中将一直叶子节点，只不过它对应的路径的标识字符串不断增长。那么在第i+1个步骤中，如果我们第一次创建一个叶子节点，它的路径标识字符串应该是S[j..i+1], 我们可以用S[j..m]来标识它。因为在后面的操作中，S[j..i+1]将逐渐被拓展成S[j..m]。那么我们不如一次就完成。

使用了上面的技巧后，构建后缀树的时间复杂度减少到O(m)。 虽然感觉不可思议，但是确实是如此。而上面提到的技巧都不大直观，不利于理解。下面我将以”BANANA“为例，讲解使用上面技巧构建后缀树的过程，希望能够帮助到理解。

4. 实例讲解

TBD

后缀树的应用

后缀树在数据挖掘的应用中有着广泛的用途。它对字符串的各种操作提供了性能优秀的实现。下面简单介绍一下它的各种应用。
1. 将两个字符串构建同一个后缀树。使用后缀树，我们可以迅速找到两个字符串间的公共子字符串。只要遍历后缀树，找到两个字符串共享的叶子节点即可。
2. 将多个字符串构建一个后缀树，我们可以找到这些字符串的公共子字符串，以及某个子串出现的频率等数据。这些数据和操作在模式挖掘和模式匹配中发挥着重要作用。

总结

后缀树的概念虽然不难理解，但是线性时间的Ukkonen’s算法却十分晦涩。这是因为它使用了众多基于后缀数的特性的优化技巧，这些技巧都不大直观，必须十分了解后缀树的特性后，才能理解这些技巧的原理。在我学习的过程中，只看书或者讲解也是半知半解，最后通过调试代码，重现整个构建过程，才最终理解了算法的原理。后缀树的代码在我的github的suffix-tree repos中有提供。希望这篇文章以及代码能够帮助你深入理解后缀树和Ukkonen’s算法。

参考资料

  1. Gusfield, Dan (1999) [1997]. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press. ISBN 0-521-58519-8.
  2. http://en.wikipedia.org/wiki/Suffix_tree