哈夫曼树的压缩VC程序和其效果.docVIP

使用huffman编码压缩文件-课设成果 问题描述：　　哈夫曼是一种常用的压缩方法。是1952年为文本文件建立的，其基本原理是频繁使用的数据用较短的代码代替，很少使用的数据用较长的代码代替，每个数据的代码各不相同。这些代码都是二进制码，且码的长度是可变的。如: 有一个原始数据序列，ABACCDAA则编码为A(0)，B(10)，C(110),(D111)，压缩后为010011011011100。产生霍夫曼编码需要对原始数据扫描两遍，第一遍扫描要精确地统计出原始数据中的每个值出现的频率，第二遍是建立霍夫曼树并进行编码，由于需要建立二叉树并遍历二叉树生成编码，因此数据压缩和还原速度都较慢，但简单有效，因而得到广泛的应用。? ?哈夫曼编码是无损压缩当中最好的方法。它使用预先二进制描述来替换每个符号，长度由特殊符号出现的频率决定。常见的符号需要很少的位来表示，而不常见的符号需要很多为来表示。哈夫曼算法在改变任何符号二进制编码引起少量密集表现方面是最佳的。然而，它并不处理符号的顺序和重复或序号的序列??哈夫曼压缩，首先用ASCII值初始化511个哈夫曼节点，然后，计算在输入缓冲区数据中，每个ASCII码出现的频率。然后，根据频率进行排序，现在，构造哈夫曼树，获取每个ASCII码对应的位序列，构造哈夫曼树，将所有的节点放到一个队列中，用一个节点替换两个频率最低的节点，新节点的频率就是这两个节点的频率之和。这样，新节点就是两个被替换节点的父节点了。如此循环，直到队列中只剩一个节点（树根）。压缩的最后一步是将每个ASCII编码写入输出缓冲区中??哈夫曼解压缩，将输入缓冲区中的每个编码用对应的ASCII码逐个替换就可以了。只要记住，这里的输入缓冲区是一个包含每个ASCII值的编码的位流。因此，为了用ASCII值替换编码，我们必须用位流有哪些信誉好的足球投注网站哈夫曼树，直到发现一个叶节点，然后将它的ASCII值添加到输出缓冲区中： 复制内容到剪贴板 代码: /*****************************************************************//*****************************************************************//**程序:? ?? ???compress.c? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ? **//**功能:压缩与解压缩单个文件? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ? **//**详情:利用hufffman算法生成输入文件的huffman编码，并转换成二进制字节?**//**? ?流输出从而达到压缩的效果；解压缩则是从压缩文件中读入huffman树? ??**//**? ??信息，从而还原为原编码，达到解压缩的目的。? ?? ?? ?? ?? ?? ?? ?? ?**//**? ?? ?? ?? ?? ?? ?? ??压缩文件结构? ?? ?? ?? ?? ?? ?? ?? ?**//**? ?? ?偏移量? ?? ?? ?? ?? ?? ??存储信息类型? ?? ?? ?? ?? ? **//**? ???0~3? ?? ?? ?? ?? ?? ?? ?? ?文件头标志? ?? ?? ?? ?? ?? ???**//**? ?? ???4? ?? ?? ?? ?? ?? ? ?源文件名长度:n_s? ?? ?? ?? ?? ? **//**? ?? ???5~4+n_s? ?? ?? ?? ?? ?? ?文件名? ?? ?? ?? ?? ?? ?? ?? ?**//**? ?? ???5+n_s~8+n_s? ?? ? ? 源文件长度? ?? ?? ?? ?? ?? ?? ?? ?**//**? ?? ???9+n_s~1028+n_s? ?? ?? huffman树非叶子节点孩子信息? ??**//**? ?? ?1029+n_s~FILE_END? ?? ?源文件的huffman二级制编码信息? ??**//**环境:?AM2_4000+ Windows_Server_2008 VC++_2008? ?? ?? **//**其他:? ?? ?davelv @ 2008-12-18? ?? ?? ?? ?? ?? ?? ?? ???**//*****************************************************************//*****************************************************************//////////