Go语言视频零基础入门到精通

javalearner

本文主要介绍如何使用Huffman算法来对文本进行压缩和解压缩.本文提供完整的eclipse工程，包括测试样例和压缩文件格式viso文档。
   
   
   
   
     
      
      
       Huffman算法简介
       Huffman算法是一种基于统计的压缩方法。它的本质就是对文本文件中的字符进行重新编码，对于使用频率越高的字符，其编码也越短。但是任何2个字符的编码，是不能出现向前包含的。也就是说字符A的编码的前段，不可能为字符B的编码。经过编码后的文本文件，主要包含2个部分：Huffman码表部分和压缩内容部分。解压缩的时候，先把Huffman码表取出来，然后对压缩内容部分各个字符进行逐一解码,形成源文件。
       由此可见，使用Huffman算法的关键是形成Huffman码表。怎样才能生成一个“使用频率越高的字符，其编码也越短”的码表呢?这里就要用到Huffman树的数据结构。当把一棵Huffman树生成后，码表也就生成了。以下举例说明，假定我们的原始文本为"abcbbcccc"
      
      
     
   
  
   
   
     
   

     
   
  
  Huffman树生成步骤:


  
   
    1.扫描源文件，对字符频率进行统计。
    对于我们的样例，统计结果是:a:1  b:3 c:5 (按频率升序排列)
   
      
    2.从上述队列中取出频率最低的2个节点，合并成一个频率为2节点频率之和的树枝节点X，加入到原队列中，加入后，继续保持队列按频率升序排列.
   
    3.重复步骤2，直到队列中只有一个节点。
   
    4.这样，我们就形成了一棵Huffman树。叶子节点为字符，从树根节点到叶子节点的路径即为该字符的Huffman编码。从一个节点导航到其左孩子，该段路径为0，导航到右孩子，该段路径为1.所以，a字符的编码就是00,b字符的编码为01,c字符的编码为1，符合"使用频率越高的字符，编码越短"的要求。理论论证过程见<算法导论>P233
    5.Huffman码表生成后，原文本"abcbbcccc"就变成了0001101011111的位串，按每个字符占用2个byte计算，大小由原来的18个字节(9*2),共144个bit,变成了13个bit,2个字节。达到了压缩的目的。
    解压缩过程:
    解压缩也分成2部分进行，首先是根据压缩文件中的Huffman码表，在内存中生成一棵Huffman树，然后，根据Huffman树，对压缩内容进行解压缩。比如如果压缩内容为位串0001101011111，那么从树根节点起，因为第一个bit为0，先转向左子树，第二个bit为0,再转向左子树,到达叶子a,所以解码出来的第一个字符就是a,每次解压一个字符，都从根节点起，根据bit流，向左或向右转，直到到达叶子节点，也就是解压出来的字符。一直重复此过程，直到所有的字符都被解压缩。  
    压缩文件格式
    使用Huffman压缩算法对文本文件压缩后，就形成了一个压缩文件，该压缩文件包含2部分，一部分为Huffman码表，也就是Huffman树，第二部分为根据码表生成的内容位串。如何设计Huffman树的存储格式呢?本文采用从上到下，从左到右分层遍历节点，顺序存储的方式。如下图:
   
    也就是说，对于前述的Huffman树，其持久化形式为:0xfffe 0xfffe 0x0063  0x0061  0x0062,其中0xfffe代表树枝节点,而0x0061,0x0062,0x0063分别为a,b,c的Unicode码。因为所有的树枝节点的值都是0xfffe，所有树枝节点都有2个孩子，节点排列方式是按从上到下，从左到右分层排列，所以能根据此持久化字节数组，把Huffman树在内存中重新生成。
    另外为了升级版本，嵌入了magic number和version。
    完整工程下载
    本文涉及到的完整的eclipse工程，可以从这里下载。注:内含测试样例《平凡的世界》文本文件，体积较大，请使用下载工具下载。另外，本程序中采用了泛型，请在至少在JDK1.5版本上编译运行。
    代码简要说明
    1.HuffmanTextEncoder类完成压缩功能，可直接运行，压缩测试用文本文件。
    2.HuffmanTextDecoder类完成解压缩功能，可直接运行，解压缩 压缩后的文本文件。
    3.BitReader,工具类，实现对BufferedInputStream的按位读取。
    4.BitWriter,工具类，实现按位写入的功能。该类来自网络。
    5.MinHeap<T> ,模板工具类，实现了一个最小堆。生成Huffman树时使用。
    压缩效果
    使用本程序对《平凡的世界》做压缩测试，压缩前为文本文件，大小为1.7M,压缩后为二进制文件，大小接近1M（988,817byte）,而zip压缩后体积为920,997byte,比zip差，压缩文件存储格式待改善。另外，因为从Huffman压缩算法的原理可知，该算法对字符重复率高的文本最有效，比如长篇小说或者英文小说。
    作者信息
    Jagie，移动开发爱好者，可以通过chen_cwf@163.com与他联系。本文来源于Jagie的Google page:      http://chencwf.googlepages.com/huffman
   
   
  


  
  
   
   

     
   

     
   
  

复制代码

源码下载：http://file.javaxxz.com/2014/11/4/000148765.zip