后缀树

后缀树

内容提要

本章主要介绍了后缀树的来源以及后缀树的应用背景，给出了后缀树的定义、性质、特征以及构造方法等理论基础，通过最长回文的查找、子串的查找等实例进一步说明了后缀树的特征及用途。

引言

在计算机科学中，后缀树（也叫做PAT树，早期的形式是位置树）是一种数据结构，在某种程度上，它可以显示出一个给定字符串的后缀，且对于很多的字符串操作它能够非常快的实现。

字符串S的后缀树是这样一棵树，它的所有边都是用字符串来标示的，这样字符串S的每一后缀都恰好的对应一条从根到叶子节点的路径。这是以字符串S为后缀的基数树，更具体地说，这是一颗帕特里夏树。

为字符串S构造一颗这样的树耗费的时间和空间与字符串的长度呈线性关系。这样的树一旦构造完成，几个操作能够被很快的执行，例如，在字符串S中定位一个字串，在允许一定数量的错误前提下定位一个字串，为一个标准表达式模式定位匹配的问题等等。后缀树也为最大公共字串问题提供了一个第一线性时间的解决方案。这种速度的提升带来了一定的开销：存储一个字符串的后缀树比存储字符串本身需要更大的空间。

历史

在1973年，后缀树的概念是以位置树的形式被weiner首先提出来，随后Donald Knuth称它为1973年的年度算法。分别在1976年和1995年，McCreight和Ukkonen对它的结构进行了很大程度的简化。Ukkonen提供了后缀树的第一个网络建设，即现在熟知的Ukkonen算法，它是运行时间是最快的算法。对于恒定大小的字母表来说，这些算法的运行时间都是线性的，并且一般情况下，它们的最坏的运行时间是O(n long n)。

在1997年Farach给出了第一个后缀树构造算法，对于所有的字母表，它都是最佳的。特别的，对来自于一个多项式范围内的一个整数的字母表的字符串，这是第一个线性时间算法。Farach算法成为了构造后缀树和后缀树组的新算法的基础，例如，在外部存储器中，它是压缩的和简洁的。

定义

字符串S的后缀树的长度被定义为这样：

1． 2． 3．

对于字符串S的每一后缀，从根节点到叶节点都有一个一一对应关系的路径。 边表示非空字符串。

除了根节点外，所有的内节点至少有两个子节点。

由于对所有的字符串，并不都存在这样的树，所以，字符串S的末端要填补一个原字符串中并不存在的符号，这个符号通常是﹩。 这就确保了没有后缀是另一个后缀的前缀，并且将会有n个叶节点，每个叶节点都对应字符串S的n个后缀中的一个。由于所有的内部节点都有分支，所以这样的节点最多有n-1个且公有n+(n-1)+1=2n个节点，其中，一个根节点，n-1个内部节点，n个叶节点。

后缀树的构造

? 基本思路：先往树中插入最长的后缀，即字符串本身。然后插入次长的后缀，再然

后插入第三长的后缀，如此反复一直到空后缀被插入为止。这个过程也可以这样描述：

1．插入S本身

2．若上一个插入的后缀为S，令S=aw（这里a表示S的第一个字符，w表示S去掉a以后所得到的后缀）。往树中插入w。重复本操作直到S=$ 例如，字符串“ababa$”的构造过程如下：

对于字符串 \的后缀树构造如下。内部节点用圆来表示，叶子用矩形来表示,该例子中有六个叶子，被标号为1到6。 终止字符在图中被省略掉了。

尽管大部分基于Farach算法的新算法省却了后缀链接，但后缀链接仍是一些旧线性时间构造算法的关键特征。在一个完全后缀树中，所有的非跟内部节点与其他的非跟内部节点之间都有一个后缀链接。如果从根节点到一个节点的路径标识是??，其中?是一个单个字符，?可能是一个空字符，它就有一个到内部节点?的后缀链接。

广义后缀树

广义后缀树是这样一棵树，它的字符串是一个单词集而不是一个单词。它代表这个单词集的所有后缀。每一个单词必须以一个终止符或者单词结束。

函数性

如果字符串的字符来自于多项式范围内的整型字母表，一个长度为n的字符串的后缀树能够在O(n)时间内建立起来，，特别的，对于恒定大小的字母表更是如此。对于大的字母表来说，它的运行时间依赖于第一次将字符按大小化成区间所用的时间，一般情况下耗费的时间是O(n log n)，下面的耗费是在恒定字母表的假设下给出的。 假设长度为n的字符串S的后缀树已经构造完成，或者长度为为n=|n1|+|n2|+…|nk|的字符串集D={s1,s2,…sk}的广义后缀树以构造完成。你可以： 一． 查找字符串

1. 在O(m)时间内检查是否存在一个长度为m的字串P。

2. 在O(m)时间内找出字符串集P1，…Pq中第一个出现的总长度为m的字串。

3. 在时间O(m+z)时间内找出字符串集P1，…Pq中所有z出现的总长度为m的字串。 4. 在期望的亚线性时间n内寻找一个正则表达式P。

5. 在时间O(m)内找每一个这样的样本P，它与前缀P{i,…m}和在字符串集D中的子

串最长匹配。这叫做样本P的匹配统计。

二．找出字符串的属性

1.在时间O(ni+nj)内找出字符串Si与Sj的最长公共子串。

2.在时间O(n+z)时间内找出最大的对，最大的重复或者超级重复。 3.在时间O(n)内找出Lempel-Ziv分解。 4.在时间O(n)内找出最长重复的子串。

5.在时间O(n)内找出最短的且出现频率最高的子串。

6.如果存在不属于字符串集D的字符串z,在时间O(n+z)时间内找出它。 7.在时间O(n)内找出最短且只出现一次的字符串。

8.对于每一个i,在时间O(n)内找出最短的且在字符串集D中只唯一出现一次的字符串Si。

后缀树的应用环境

在文本编辑、自由文本搜索、计算生物学以及其他应用领域中，字符串可以用于解决大量字符串的问题，主要应用包括：

1. 在时间O(m)内查找长度为m的子字串，并要求在最初的时间O(n)内建立字符串的后缀

树

2. 寻找最长的重复子串 3. 寻找最长的公共子串 4. 寻找的最长的回文子串

后缀树通常应用于生物信息学的应用程序、在DNA中的模式查询或者可以被视为长字符串字符的蛋白质序列。搜索字符串不匹配的效率被认为是后缀树的最大优势。后缀树也经常应用于数据压缩；他们可以用来找到重复的数据。后缀树也经常应用于后缀树聚类，在一些搜索引擎里面用到数据聚类算法。

后缀树应用举例

例1.在字符串中，找出给定字符串XMADAMYX里面的最长回文

这里考察回文的半径，而不是回文本身。所谓半径，就是回文对折后的字串。比如回文MADAM 的半径为MAD，半径长度为3，半径的中心是字母D。显然，最长回文必有最长半径，且两条半径相等。还是以MADAM为例，以D为中心往左，我们得到半径 DAM；以D为中心向右，我们得到半径DAM。二者肯定相等。因为MADAM已经是单词XMADAMYX里的最长回文，我们可以肯定从D往左数的字串 DAMX与从D往右数的子串DAMYX共享最长前缀DAM。而这，正是解决回文问题的关键。现在我们有后缀树，怎么把从D向左数的字串DAMX变成后缀呢？到这个地步，答案应该明显：把单词XMADAMYX翻转就行了。于是我们把寻找回文的问题转换成了寻找后缀的LCA（Lowest Common Ancestor)的问题。当然，我们还需要知道到底查询哪些后缀间的LCA。这也简单，给定字符串S，如果最长回文的中心在i，那从位置i向右数的后缀刚好是S(i)，而向左数的字符串刚好是翻转S后 得到的字符串S的后缀S'(n-i+1)。这里的n是字符串S的长度。 时间复杂度：

预处理后缀树，使得查询LCA的复杂度为O(1)。这步的开销是O(N)，N是单词S的长度 对单词的每一位置i(也就是从0到N-1)，获取LCA(S(i), S(N-i+1)) 以及LCA(S(i+1), S(n-i+1))。查找两次的原因是我们需要考虑奇数回文和偶数回文的情况。这步要考察每个i，所以复杂度是O(N) 找到最大的LCA，我们也就得到了回文的中心i以及回文的半径长度，自然也就得到了最长回文。总的复杂度O(n)。

例2.子串的查询

如果在后缀树T中查找子串P，我们需要这样的过程：

(1) 从根结点root出发，遍历所有的根的孩子结点：N1,N2,N3....

(2) 如果所有孩子结点中的关键字的第一个字符都和P的第一个字符不匹配，则没有这个子串，查找结束。

(3) 假如N3结点的关键字K3第一个字符与P的相同，则匹配K3和P。

若 K3.length>=P.length 并且K3.subString(0,P.length-1)=P，则匹配成功，否则匹配失败。

若K3.length<=P.length 并且K3=P.subString(0,K3.length-1)，则将子串P1=P.subString(K3.length, P.length); 即取出P中排除K3之后的子串。然后P1以N3为根结点继续重复(1)~(3)的步骤。直到匹配完P1的所有字符，则匹配成功。否则匹配失败。 查询效率：很显然，在上面的算法中。匹配成功正好比较了P.length次字符。而定位结点的孩子指针，和Trie情况类似，假如字母表数量为d。则查询效率为O(d*m)，实际上，d是固定常数，如果使用Hash表直接定位，则d=1.

因此，后缀树查询子串P的时间复杂度为O(m)，其中m为P的长度。

本章小结

虽然后缀树的概念独立于T rie，但是理解了Trie后能更好理解后缀树，某种意义上后缀树就像是Trie的压缩版，这里注意，有时候可能会丢失某些后缀。后缀树最大的优势在于它能高效的解决涉及大量字符串的编程问题，并且，在实际应用中，后缀树也是一种应用广泛的数据结构。

本文来源：https://www.bwwdw.com/article/z1xr.html