大家好。
数据结构与算法这一讲的内容是第5章，二叉树。
最后一讲，Huffman树及其在编码中的运用。那我们来看一下等长编码。在计算机中，
我们常用的二进制码有ASCII这样的
单字节的编码，以及中文编码这样的双字节编码。
在等长编码的情况下呢，我们其实是假设所有的这些 字符它们的使用频率是相同的。
那它们的编码长度也一样，对n个不同的字符，我们需要log(2n)位，
来进行编码。那如果是些字符它的使用频率是
不一样的情况下，那就会带来空间效率的一个浪费。
那我们看这样的一组
字符。那这个字符呢，有8个，其中
其中像E这样的元音字母，它的使用的频率是比较大的。而Z呢，它的使用频率是比较小的。
那如果用等长编码，显然是不太划算的。
那我们希望呢，经常出现的字符，它的
编码呢，是比较短，这样它总体的这个编码长度会短。
不经常出现呢，稍微长点没关系。我们这样的一个不等长的编码呢，它使得
这个数据的总体的存储量是变小，那
我们的数据经常是存在外存里面，或者是在网络上要进行传输。如果我们的长度
变小的话呢，那我们访外的这样的次数是会小很多。因为我们知道，
访外的，它的效率是比访内呢，
是要低很多的。那一般来说，我们访问一个字节，
就是在外存里面读，我们是内存里面的100万倍左右。
那这个外存的时空权衡原则跟内存是不一样的。我们要尽量减少
往外次数。那前提就是说，我们在同样的，这样的信息表达的情况下，
我们希望我们的编码是越短越好，那我们在外存里面所存储的数据呢，就会越少。
那我们对于不等长的编码，
首先就是希望它有前缀的一个特性。那我们看，等长编码里面它是，已经是满足了
这样的前缀特性，因为他们的单码长度都是一样。
因此任何一个编码不可能是别人的一个前缀。
在不等长的情况下呢，我们一定要满足这个特性。
那， 我们看一下这样的一个编码。
那它呢，因为是根据这个，
二叉数里面的左分支，右分支来编的，我们所有的这个码呢都是落在叶结点。
那因此呢，我们可以看到，叶结点它都不是其它叶结点的前缀，
就能得到一个这样的前缀编码。那我们得到的这样的编码的一个表是这样的，
那我们可以看到呢，如果对于这样一个“000110”这样的二进制串，
对应这个编码表，我们可以翻译出唯一的字符串。
那如果我们换一组编码。
这个编码看起来好像比我们前面的前缀编码显得要短，
但是它是不合法的，我们不能用它
来很好的解释这样的二进制串。
那例如，我们对于这样的一个“000110”的串，
那我们能得出各种可能，这是因为像C(0)这样的一个编码.
这个0呢，它既出现在Z中，也出现在K还有E当中，
因此，我们在译码的时候呢，就不知道在什么时候应该停止，
所以是非法的。我们 前面已经看到了这样的一个
二叉树，如果我们左分支设为0，右分支设为1，
那我们可以在叶结点上很好的编码。
那Huffman编码树呢，它是一个特殊的树，那我们考虑了权重，我们是
能够通过一个构造呢，我们使得这样的代码呢，它的编码
的外部路径的总长度呢，是最小，而且呢，它是对应于
不等长编码的情况。那我们来看
这个建立Huffman编码树的一个思想。
那我们对于n个字符，
它们的使用频率呢，分别是W0到 Wn-1.
那我们给出它的一个最优的编码方案的话呢，
其实对应到我们刚才的这样的一个二叉树，它实际上是
在叶结点上的这样的一个扩充的外部路径，
那我们带上权以后，就是所有这个
叶结点它所对应的这么一个外部路径
加权的一个长度的一个最小。那也是说，我们这是具有最小的
带权外部路径长度总和的这么一个树，就是我们的最佳的一个编码树。
那我们可以显然发现呢，就是权越大，离根呢，越近，
那它的编码越短。权越小呢，就是它离根越远，它的编码是越长。
总体来说呢，这么一个加权的外部路径长度总和呢，是最小。
那我们要建立这么一个树呢，实际上采用的是贪心的思想。
那我们首先呢，按照权把这些字符呢，给它排起来。
然后呢，我们拿走这具有最小的这个权重的两个字符，
然后我们组合出一个新的一个结点。那这个结点呢，具有这两个
字符所带权的这个和，然后我们把它再放回到
那样的待处理的这些字符里面去。
我们一直重复这个贪心的过程，直到所有的字符都被处理完毕为止。
那我们看一下这个构建的过程。那首先我们把2和3最小的取出来，然后构建出一个
具有权5的结点。这个5呢其实应该放回去。但是我们这里呢，就摆在这，作为一个子树。
那其它的这些结点，其实它们逻辑上来说，也是一个子的
Huffman树，我们不断地去合并这些Huffman树。
那我们现在呢，又找出权最小的这两个，就是
5和5，然后我们构成一个权为10的结点，接着再找。
那就是10和7，那构成一个新结点。
那11和13，又构成一个新的子树。那我们一直重复这个过程，
直到所有的这个结点呢，都被处理完了。然后我们所有的这些
待编码的这些字符呢，都在叶的位置。然后我们构建出一个整体的Huffman树为止。
那我们怎么样对它进行编码呢？其实我们可以规定，
左分支呢，都是0，然后右分支呢，都是1。当然你也可以用另外一些
方式，比如说，你反过来，左为1，右为0，这是习惯的问题。
那我们把这个编码呢，我们就存在一个编码表里面。
那我们在将来对这个
字符进行编码处理的时候呢，我们就是直接查表，
然后就可以得到这样相应的二进制字符串。
那这就是我们的编码表。然后呢，
我们将来要对一个字符序列进行
编码的时候，比如说我们给d0，d5，d11，那我们就是d0这个码，
直接加上，然后再缀上这个d5，再缀上d11就把它编出了
这样的二进制码。那
解码的过程，它实际上刚才的一个逆过程一样的。
那我们呢。对这么一个0，1的二进制串，
我们从左到右逐位的判断这个代码串， 然后呢，一直到确定一个字符。
那我们每次在解码时候都是从根开始，
然后呢如果是0呢，我们就下降到左分支，1呢下降到右分支。然后降到某一个叶结点，
那就得到了一个对应的一个字符，然后
接着我们又对下面的呢，从根开始，继续处理。
那一直到整个这个二进制串处理完毕。如果是从我们原来的这个编码树，
得到的一个合理的编码，那我们一定是最后处理到所有的，
这样的二进制字符都被处理完为止。那我们来看一个例子。
那假设我们待译码的二进制串是这么一个串，
我们从根开始，然后走111，是对应出是d12是它对应的字符。
然后呢，下面又接着回到根开始，走
10110，那我们对应到
d2这个字符。那我们对这样的二进制串呢，
就完成了译码。那如果你是合法的，那一定是
到这里就结束，不会有一些剩余的不能够解释的这种 字符。
那我们看一下Huffman树的实现，最主要的呢就是合并两个子树的
这样的操作，因为我们实际上最开始的时候，只有n个独立的Huffman树。
然后呢，我们每次呢是找出具有最小权重的那两个子树合并，
成为一个新的树。那么我们子树的数目呢是逐步的要减少。
那每次减少1，一直到减少为最后只有一个子树为止，那就是整体的Huffman树。
那我们看一下它的构造。首先那我们就是
把这n个子树，
我们都把它加到这样的一个最小堆里面，这个堆它的权值呢，就是我们的
这样的字符它的出现频率的这个权值。
我们在完成了刚才的一个 初步建立堆的这个过程以后，那我们
整个这个堆里面呢，其实是有n棵Huffman树。
然后呢我们是操作n减1次，每一次操作呢，
是从堆里面删除具有最小权值的这两个结点。
然后呢，我们把它合并。这个合并出来的这个新树呢，是具有刚才这两个子树的
这样的权重和。然后，我们又把这个新树的权重
加回到刚才的这么一个堆里面去，
因此呢，我们这个堆呢，是删除了2个，加入了1个，那它的规模缩小了1.
那经过这样的n减1次的这样的
删除，合并和加到原来的堆里面这么一个过程，
那其实呢，我们最后呢就是得到了一个整个的Huffman树。那这就是我们所要锝的这个编码树。
那我们再来证明下Huffman树的正确性。
那首先就是要说明它是不是前缀编码，也就是说，
它的编码里面呢，任何一个结点所代表的这个
字符，它的编码，是不是另外一个结点的前缀。
那显然它不是的，因为我们每一个编码都落在叶结点。叶结点呢，
它不可能是别人的前缀，因此我们是满足前缀编码特性的。
另外呢，我们要证明它的整个构造呢，是得到最优解。
那首先呢我们就是要证明它的一个贪心性质。也就是说，我们在构建的每一步，
这个权最小的两个子树，
被结合成新子树的时候，这是不是正确的，是不是得到了
最优的，也就是说，具有最优子结构子的这样一个性质。
然后我们在这个性质之上呢，我们再来看，它全局的，是不是得到最优解。
那我们看这么一个引理。
也就是说，具有两个结点以上的Huffman树，
字符使用频率最小的这两个字符呢，它是兄弟结点，
而且它的深度呢，是不比这个树里面的其它的
叶结点呢，要浅。也就是说，它应该是在最深的那层。
同一层可能也有其它的这个结点，但是不可能有比它再深了。
那我们来看，假设y1，y2，它们是
具有最小权重的这两个字符。
那它们的父节点就是y，y的权重是它们的和。那如果有那么一个结点
x，它是由具有权重x1，x2的
这样的子结点组成的，那么必然呢，就是x这个权重啊，是要大于等于y的。
那我们在v构造的过程中，那
那它一定会是去选择y，而不是选择x，因为y是
会小于这个x的。
那因此呢，这种情况呢，就是不可能发生的，就是说，如果x比
y还要深，那这个情况是不可能存在的，因为它必然是，这个x它是会大于等于这个y的，它不可能比它深。
那我们再来看，这样的一个最优的性质。
也就是说，对于给定的这一组字符，Huffman树呢，它能够实现这样的一个具有
最小的外部路径权重和这样的一个结构。那我们采用归纳法来进行证明。
在初始情况，也就是n等于2的时候，
我们一定是得到一个最小的外部路径权重，因为这种
情况下，只可能是成对称的这两种树，也就是
w1在左边，w0在右边，或者是w0在左边，w1在右边。
那这两种情况下呢，它们的这个加权的路径长度和都是一样的。那
如果对n减1个叶结点，我们能够
有Huffman树来产生具有最小外部权重的一个
子结构。那么我们对于这样的一个n
个节点的情况呢，我们就可以用归纳法来证明了。那
假设这n个结点呢，它的权重分别是
w0到wn减1，而且我们排序，w0和w1是最小的
那两个。那我们采用Huffman编码树的方法，那它的
这两个最小的权重的结点呢，会被首先选出来。
那么是形成一个更大一点的子树是v。那v是它们的父节点。
那根据引理呢，这个v呢，就是
树里面最深的那个父结点。
当然这相应w0，w1呢，也是最深的那两个叶结点。
那我们把V呢，换成一个叶结点。
V‘，这个V’它的权重呢，是w0加w1.
那我们可以得到另外一棵子树T‘。那T’呢它只有n减1个结点。
那根据我们的归纳假设呢,它是具有最小的外部路径长度.
那这个时候我们把这个V‘展开成为
V，也就是把w0加w1呢，我把它还回去，把它扩展。
那显然呢就把这个T’就还原为T。
那T呢，它也是应该具有最小的外部路径长度的，
因此根据归纳原理，我们的定理就是成立的，也就是说Huffman树能得到最优解。
那我们再来看一下Huffman树的编码效率。
主要就是估计这个Huffman树，它编码所节省的空间。
假设在整个这个字符集里面呢，我们
每一个字符的长度是Ci，它对应的频率是Pi，
那它的平均的代码长度呢， 就会是ΣCiPi，
那我们当然也可以用这个出现的总次数，
以及每一个字符出现的次数，这样的形式来表达，它是等价的。
那对于这么一个编码树，我们可以算出呢，它的平均代码长度是3.38，
因为它是由13个字符组成的这么一个字符集。
那如果是等长编码，它显然是
Log以2为底，13的对数然后取上整，那需要4位，那Huffman树呢只需要3.38位。
那这样的话呢，我们Huffman树的编码，它预计呢，
只需要原来这个等长编码的84%的空间。
我们空间节省的同时，实际上在运算的效率上，我们是得到提升的，
因为这些代码呢，这些编码的字符呢，它很多时候是存在外存里面，或者是
要在网上传输的。因此，如果你所花的这个存储的
这些信息呢更多的话，那我们的运算的时间也要更多。
Huffman树，它适合于字符频率不等，而且差别比较大的
情况。那广泛的用于这种数据通讯啊，文件压缩啊，
还有像我们规定的外排序里面，也都有一些应用。那我们常见的这种zip的文件
压缩包，那它里面呢，就用到了Huffman和其它的这种压缩算法的结合。
那我们最后给大家留下思考。二叉数呢可以扩展为b叉树。
那b叉树呢，我们不一定是说都能构成满b叉树，
因此呢，其实我们是需要构造一些虚的结点，
来构造满的b叉树，那这个虚结点其实就是权重为0的结点。
这种情况下，显然我们是要加几个0的这种结点，使得它能构造满的b叉树。
给它放进去。那我们推导一下，需要加多少个
这样的虚结点。把这个过程来推导和证明一下。
那当然我们这个虚结点，因为它是具有权值为0的，因此它其实应该是加在
这个最深的那一层，这个叶层。
另外我们可以调研一下，在这种常用的压缩软件里面，Huffman树是怎样应用的。
谢谢大家。