Huffman编码的证明过程与反思

看到http://mindhacks.cn/2011/07/10/the-importance-of-knowing-why-part3/这篇文章后,突然想起自己学习败者树的经历。当时确实认为自己已经掌握了败者树的构建原理与方法。可是没有过几天,再次给别人讲解时又忘得像没有学过一样。如作者所说,我们真的没有掌握其证明过程,而只是记住结论了。

下面尝试着看完博文后,自己也证明一下。

首先需要确认Huffman编码要解决的问题:一套字符在网络中传输时,其实都是事先已经对应好的0与1组成的编码。比如ascii码表中:字符a的编码就为01000001。对于任何一套字符,其中每个字符被使用的频率是不同的,如英文字母中e出现的频率就比z出现的高。这样一来,(好像这需要信息论的知识来解释其中的原理)完全可以用不同长度的0与1组合来表示不同出现频率的字符而且还能满足信息的充分表达,这样一来,便可以节约传输带宽。这就需要我们设计一套编码算法来解决这个问题(其中还需要满足前缀不匹配原则:任何一个字符的编码都不是任何一个字符编码的前缀,这样可以方便解码,这与此证明没有关系)。

Huffman编码最终转化成数学问题就是寻找一棵二叉树,使得 Σ freq(i) * depth(i)最小。接下来我们就是要证明,为什么按照Huffman算法来构造出来的二叉树就是最优值(以下称cost值最小)。

按照从上面博文学来的的分析方法,首先需要分析这个问题的解空间。对于指定的字符集而言,那么就是可以转化为:叶子数目一定的情况下,二叉树的所有可能形状数(真正解空间数还要少)。根据以前的知识,我们知道这个数量是可以计算出来的,所以解空间就是有限的。现在我们就要想办法从这个有限空间找出最优解,当然把所有的解列出来,算出cost值,那么最小的解就是最优解。但这种方法虽然美其名曰‘穷举’,但我们一般不会使用的。那就需要找分析问题的特殊性,或者说分析解空间的特殊性,来加快寻找最优解的速度。

使用从上面博文学来的分析方法:

如果你要搜寻的元素是某个满足特定条件的元素(例如寻找最优解的时候,“最优”的定义就是这个“特定条件”),那么可以“倒过来推”(数学证明常用手法,结论当条件使),即假设你已经找到了你要找的元素,那么能得出哪些结论,每一个结论都是最优解的一个必要条件,而每一个必要条件都能够帮助你避免不必要的搜寻,因为你只要发现某个候选解不满足某个必要条件,就可以立即将其丢弃,前面提到的寻找出现次数大于n/2的例子是一个极端情况,我们得出的必要条件导致我们可以直接丢弃除中点元素之外的一切其他元素,再例如如果有人叫你寻找有序数组中最小元素,你会毫不犹豫地把该数组头尾元素中较小的那个给他,因为你知道“如果那个最小元素存在,那么它必然位于头尾”——这个必要条件直接允许你丢弃掉n-2个候选解

我们假设最优解已经找到。最优解是什么,在这个问题中,就是比所有其它任何解的cost值都小的解。换句话说,就是比它相邻的解的cost值都要小的解。

这让我想起了有道笔试中的那道最终可转化为某个维度中一点x到所有其它点的‘距离’(|x-x0|)和最小的题,其解决思路是假设x点已经位于最优位置,然后移动这个点分析距离和的变化情况:发现这个点的位置与其左右点的数量分布有关,假设左边有a个点,右边有b个点,那么x向左移动一个单位增加的距离为b-a,因此只有当x不管是向左还是向右移动都是>=0时才是最优位置,即b-a>=0且a-b>=0。因此得出x位于中位点时是最优解。

同样,我们也需要分析最优解与其相邻解之间的关系,从而得出最优解的‘准确位置’。假设最优解中两点叶子的频率与深度为:f1,f2与d1,d2。那么交换两个叶子的位置同时保持其它结点不变后,即cost值变成C+f1*d2+f2*d1。这样根据最优解定义可知:

C+f1*d1+f2*d2 <= C+f1*d2+f2*d1

经过运算可知:f1(d1-d2) >= f2(d1-d2),

  • 如果f1>=f2,那么d1<=d2;
  • 如果f1=<f2,那么d1=>d2。

转换成自然语言,就是如果频率越高则必须满足其深度越低或者可以说频率越低则必须满足。那么Huffman树构造算法中的先选取频率最低的结点来开始构造便得到证明了。

好了,现有已经对Huffman算法的起步正确性进行了证明,剩下的就是证明算法中递归处理过程的正确性了:即将选取的两个频率最低的结点构成一棵树,让带有前两者频率和的父结点继续参与接下来的选择过程。

tree

 

从上图我们可以看出,其中数字表示频率值。上面已经证明了频率值为1,2结点为什么必须在一开始就选取。接下来,我们看看第三小结点怎么处理,通过上图我们具体来分析一下:如果将1,2结合成树生成的父结点与4交换位置后,发现cost值总体减少了一个单位。这就引导我们去再思考  C+f1*d1+f2*d2 <= C+f1*d2+f2*d1 这个公式中交结点的范围是否可以扩展,即不只是叶子结点交换,是否表示生成的内部结点交换也满足这个条件。我们进一步发现,如果生成的内部结点的“频率值”为其直接孩子的结点的频率值和。那么在移动一棵树时,那么整棵树中内部叶子节点(也就编码节点)的频率和就是此树的根的频率值。只不过公式展开可能是:

C+(f1+f2)*d1+f3*d2 <= C+f3*d1+(f1+f2)*d2  或更准确点

C+(F1+F2)*d1+F3*d2 <= C+F3*d1+(F1+F2)*d2

其中F1与F2为所有结点的cost值的递归表示函数

这样就印证了上面思考的正确性,即当内部结点移动时(携带其子树),同样满足这个公式。这样就证明了huffman算法的递归过程:将编码结点中最小的两个结点组合成一棵树后,让其根继续参与下次选取过程。(上面的思考过程与证明过程说明了为什么让根继续参与下次递归选取过程)。

发表评论