返回首页
当前位置: 主页 > 互联网技术 > 网络安全 >

zip 的压缩原理与实现(4)

时间:2014-12-01 13:19来源:电脑教程学习网 www.etwiki.cn 编辑:admin

1.按照霍夫曼树的建立过程,新增的两个节点是当前节点序列中最小的两个,其他的任何两个节点的父节点都大于(或等于)这两个节点的父节点,只要前一步是最优二叉树,其他的任何两个节点的父节点就一定都处在它们的父节点的上层或同层,所以这两个节点一定处在当前二叉树的最低一层。
2.这两个新增的节点是最小的,所以无法和其他上层节点对换。符合我们前面说的最优二叉树的第一个条件。
3.只要前一步是最优二叉树,由于这两个新增的节点是最小的,即使同层有其他节点,也无法和同层其他节点重新结合,产生比它们的父节点更小的上层节点来和同层的其他节点对换。它们的父节点小于其他节点的父节点,它们又小于其他所有节点,只要前一步符合最优二叉树的第二个条件,到这一步仍将符合。

这样一步步逆推下去,在这个过程中霍夫曼树每一步都始终保持着是一棵最优二叉树。

由于每一步都从节点序列中删除两个节点,新增一个节点,霍夫曼树的建立过程共需 (原始节点数 - 1) 步,所以霍夫曼算法不失为一种精巧的编码式压缩算法。


附:对于 huffman 树,《计算机程序设计艺术》中有完全不同的证明,大意是这样的:
1.二叉编码树的内部节点(非叶子节点)数等于外部节点(叶子节点)数减1。
2.二叉编码树的外部节点的加权路径长度(值乘以路径长度)之和,等于所有内部节点值之和。(这两条都可以通过对节点数运用数学归纳法来证明,留给大家做练习。)
3.对 huffman 树的建立过程运用逆推,当只有一个内部节点时,肯定是一棵最优二叉树。
4.往前步进,新增两个最小的外部节点,它们结合在一起产生一个新的内部节点,当且仅当原先的内部节点集合是极小化的,加入这个新的内部节点后仍是极小化的。(因为最小的两个节点结合在一起,并处于最低层,相对于它们分别和其他同层或上层节点结合在一起,至少不会增加加权路径长度。)
5.随着内部节点数逐个增加,内部节点集合总维持极小化。

 


2.实现部分
  如果世界上从没有一个压缩程序,我们看了前面的压缩原理,将有信心一定能作出一个可以压缩大多数格式、内容的数据的程序,当我们着手要做这样一个程序的时候,会发现有很多的难题需要我们去一个个解决,下面将逐个描述这些难题,并详细分析 zip 算法是如何解决这些难题的,其中很多问题带有普遍意义,比如查找匹配,比如数组排序等等,这些都是说不尽的话题,让我们深入其中,做一番思考。
 

------分隔线----------------------------
标签(Tag):电脑知识 电脑教程 电脑技巧
------分隔线----------------------------
推荐内容
猜你感兴趣