大家好。
数据结构与算法这次一讲的内容是第十二章高级数据结构中的
那我们在前面介绍的这样的BST的索引结构中呢它如果是输入 一个随机的这么数据集，那我们会得到一个log n的树高
是一个比较好的性能。
但是如果我输入的时候呢是一个顺序的这样的输入的数据那它就会退化
当然我们有一些平衡的方法
但是如果我输入的时候呢是一个顺序的这样的输入的数据那它就会退化
比如说像红黑树，还有AVL树、splay树 但是我们想一想能不能够
那如果这些数据在整个空间里面它的分布是比较随机的也就是比较均衡的，那我们得到的这么一个树结构呢也许就是比较好的结构。
这个idea呢它主要是来自于我们信息检索领域
也就是说我主要是希望能得到一个非常好的检索性能
因此我们取了这个retrieval这个单词中间的几个字母作为这个trie树的这么一个名称
那对于英文单词来说呢它很明显的就是由26个字母组成了这么一个空间的划分
那对于我们一般的情况因为计算机里面所有的信息它都是用二进制的0、1来表达的，因此我们可以用二叉Trie来进行一个构造。
那首先我们来看一下26叉Trie。那对于这么一个单词集
那我们把用a字母开头的这些字符串呢在这个a字母的这么一个子树里面来出现
那么在它的第二级那我们就根据它的第二个字母再进行这个空间的划分
但是注意在这一个字符树里面呢，这些单词它们是等长的
也就是说我任何一个单词不可能是别人的前缀。
如果是有某一个单词是别人的前缀的 情况呢我们就需要特别的区分
在某一个位置它是要称出来
成为一个独立的单词,比如说像这边an
那它是另外两个单词的前缀，那我们就是要在
这边呢有一个星号要拉出来，拉出一个独立的单词
那我们为了统一呢对其他的这样的字符串 呢也都是用这个星号来表示结尾。
那在这个树里面呢我们其实可以进行一下压缩特别是靠近叶的方向.
那我们把那些没有分支的这样的子结构呢我给它都收起来
那为什么我们不在靠近根的方向给它压缩呢？
因为我这个字符树的构建过程它是从一个空树不断的去扩展的过程。
那在前面的扩展的过程中呢它将来这些字符筑的分支呢它可能会分裂，慢慢慢慢的成长
那我们就没有必要在这个前面这几级呢去给它进行太多的这一种压缩
那我就让它是该分支就分支只压缩这样的靠近叶的这一级
而且我们所有的信息呢都是存在这个叶节点上头。
那如果对应于一个字典的话那就是对于这个单词的一些解释都是在叶节点上存放
我们的中间节点只起到一个索引的这么一个过渡的作用。
那我们再来看二叉Trie如果对这样的一个6个位表达的这样的关键码那也就是在0到63之间，
那我们在划分的时候呢我根据它们在整个这个空间里面是在前一半还是后一半，
那我们去两两的划分 那我们得到这么一个二叉Trie
那其实这一个二叉Trie呢我们对应到它的二进制的编码
就是在最高位就是根这个地方呢我们来判断这个字符串或者是说这个对应的一个整数那它的高位是0还是1
然后呢0就在左分支里面继续划分，1在右分支里面
那这个结构我们看到呢2它其实是只有一个单分支
那在这种情况下我们可以对它进行一个压缩，
那压缩完了以后呢我们这个二叉Trie它的存储结构更加紧凑
而且在检索的时候它的效率呢其实也是更高的。
那我们这么一个二叉Trie它的检索的最长的长度呢就是你的这样的一个表达这个关键码它的这样的位数有多少位那我们最多是检索这样的层次
那我们再来看Trie结构的一个非常好的应用，就是后缀树。
那对于这么一个字符串，我们把它的所有的这些非空的子串呢我们把它找出来
那这些子串它其实也构成了一个字符串的集合，
我们对这么一个字符串我把它的非空的后缀子串都拿出来，那就得到了这么一个字符串的集合。
我把这个字符串集合呢也用刚才的这样的26叉Trie的形式来组织 那我们就得到了这么一个Trie结构。
那中间这些灰色的节点我们可以看到它并没有其他的分支
因此呢它也是可以压缩的。
那压缩完以后呢我们就得到了这样的一个树，这叫做后缀树。
后缀树呢我们是能够在一个O(n)的时间内构造的，
那这个构造的算法呢是Ukkonen他所设计的。
那是一个非常巧妙的算法。那这个后缀树它是有很好的索引性能的。
那我们再来看跟后缀树相关的一个数据结构就是后缀数组。
那对于这样一个字符串 那我们把它的所有的这些后缀串呢我们都给它拿出来，而且我对它进行一个排序
而且呢我记录这个子串在原来的母串里面出现了这样的下标的位置，也就是说 我把它这个信息呢记录在这么一个叫做后缀数组或者叫SA数组里面
那同时我们还记录这相邻的两个后缀串它们最大的共同的一个前缀长度
那这两个数组记录了以后我们就有很好的这样的索引的一个信息了
那我们来看开始为下标5的这个子串和开始为下标1的这两个子串
那它们的共同的前缀长度呢就是3，那就是ALA
那我们得到这两个子的数组它们对原来这个字符串呢共同组织了一个非常有效的索引结构
那我们再来看这个后缀数组跟后缀树的一个对应关系
那我们首先得到了这么一个后缀数组以后呢那我们看怎么来构建这个后缀树。
那首先在字典序里面排列在最前面的这个子串我们拿出来在根节点下面呢建立了这么一个节点。
然后呢第二个子串它跟这个第一个子串共同前缀长呢是3
那我在 这个3这个位子呢我切分一下
然后我把我这个第二个子串加进去，
第三个子串呢?跟这第二个子串它共用是一个字母。
那我们再切分，
那我不断的去构建这样的一个后缀树。
那我们根据刚才的这个后缀数组它的两组信息
一组呢就是所谓这个SA数组，也有人称为Rank数组
那它表达的就是我们排序以后的这个后缀串它在原来这个母串里面出现的起始的下标位置。
然后还有lcp数组，那也有人称为height数组，
它表达的呢是我们相邻的两个后缀子串它们拥有的最长的这个公共前缀的长度
那在这两个数组的帮助下呢我们就构建出了这样的相应的后缀树。
那从这个过程我们也可以了解到后缀树和后缀数组 它们是完全等价的。
它们的不同只是在构建后缀树或者是构建后缀数组的时候
可以采用不同的算法。那构建后缀数组的算法主要是像倍增算法还有DC3算法。
那构建后缀树呢主要是UKK算法
它们这些构建的算法呢最好的就是DC3和UKK算法，
都是能够在你的原来这个字符串长度n相关的一个c塔n也就是线性的时间内完成构造。
而后缀树和后缀数组它们有非常好的应用。
那我们给大家留一下思考题。
首先呢就是对于中文的情况是不是适合我们前面英文的那种26叉Trie的构建？
大家想一下中文的这个字符串那是由中文的这个字来组成的
这个字的一个后选集非常非常大
那如果还用这个26叉Trie显然是不适合的。
其实我们有Trie结构的一种变种，也就是三数组Trie，
还有双数组Trie能够很好的组织中文的字符树。
其实我们有Trie结构的一种变种，也就是三数组Trie，
另外呢大家查阅一下后缀树、后缀数组的构建的一些相关论文以及它的应用的相关论文，
那它们在这些平凡模式挖掘啊、聚类啊基因的比对啊等等很多的场景里面都有丰富的应用
可以说后缀数组呢它写起来更加方便，
那我们在一些比较简单的应用里面呢我们可以使用后缀数组。
而后缀树呢它在实现的时候是比较麻烦一些的。
但是呢一旦构建了以后我们对后缀树
的一个操作其实是能够更加的方便.
那大家可以去看一下一些相关的应用。谢谢大家。