哈夫曼树+双缓冲实现压缩算法（已更新）

    认识哈夫曼树之前首先我们简单的来了解一下二叉树，不难理解，二叉树就是每个节点都只有2个子节点的树状结构，也就分为父节点（parent node）、左子树（left child）和右子树（right child）。每个节点最多只能有2个节点，当然也可以更少，比如只有左节点没有右节点或者相反，没有子节点的节点我们称之为叶节点，有子树的称之为根节点。

    二叉树相关就先介绍到这里，我们还是回到主题。首先，哈夫曼树就是一种特殊的二叉树，也是一种加权二叉树。首先，我们对我们需要储存到二叉树的数据赋予权重，权比较高的放在浅层，权重低的放在深层，并且所有的数据都储存在叶节点。接下来的问题就是如何构造这个哈夫曼树了。

    举个例子：我们要储存的数据及其权重分别为：a:1|b:4|c:4|d:2|e:7|f:3，下面将通过例子来讲解哈夫曼树的构造方法

    首先，将数据按权重排序
    a | d | f | b | c | e
    1 | 2 | 3 | 4 | 4 | 7

    我们先将权最低的2个节点组成一个二叉树，根节点为A，没有数据，但权重为2个子节点的和，并将他们的根节点放入列表重新排序：（注意例中的大写字母没有实际意义，只是代号而已，最后一步我们会把打些字母擦除的）

引用

  A(3)   f(3) d(4) c(4) e(7)
  /  \
a(1) b(2)

    重复上一步骤，取新的根节点为B

引用

b(4) c(4)      B(6)     e(7)
                    /      \
                  A(3)  f(3)
                  /    \
                a(1) b(2)

引用

          B(6)        C(8)  e(7)
         /      \         /     \
   A(3)    f(3)   d(4)   c(4)
  /   \
a(1)   b(2)

引用

        e(7)      D(14)
                     /      \
               B(6)       C(8)
                /    \         /    \
           A(3)  f(3) d(4) c(4)
          /    \
     a(1) b(2)

引用

     E(21)
        /    \
     e(7)    D(14)
                /          \
              B(6)     C(8)
             /   \          /    \
           A(3) f(3)  d(4) c(4)
         /    \
      a(1) b(2)

    这个哈夫曼树我们就算完成了，最后将无关的东西去掉：

引用

          ○
         /   \
        e     ○
            /    \
          ○      ○
         /  \    /  \
        ○   f  d    c
       /  \
      a    b

    大功告成！

    哈夫曼树的意义就在于可以对其中的数据重新编码，编码方式很简单，左树为0右树为1，每下一层加一个数字，以上图中的例子来说，abcdef对应编码就是：
|a|1000
|b|1001
|c|111
|d|110
|e|0
|f|101
    大家不难发现，这几个编码没有任何一个是另一个编码的前置。这是由哈夫曼树的特性决定的，哈夫曼树所有的数据都在页节点，如果出现一个数据是另一个数据编码的前置，这个数据必然在另一个数据的路径前，也就是在根节点，然而这是不可能的，这也确保了解码的唯一性，避免了歧义的出现，就拿刚才的例子来说，11111001011001的解码只可能是cdefb而不会是别的。

    对于程序来说，取得这个编码就牵扯到一个二叉树遍历的问题了，通常来说，遍历一个二叉树可以用递归方式解决，这里举个简单的例子：

//首先，我们假设节点类为Node，包含getLChild()和getRChild()两个方法
//分别取得左子节点和右子节点，然后一个char data属性储存值
//code为储存编码的字符串，Code类为编码类，包含data和code两个个属性
public void viewBTree(Node nd,String code,List<Code> cL){
    Node leftNode = nd.getLChild();//取得左子树
    Node rightNode = nd.getRChild();//取得右子树
    if(leftNode!=null){
        viewBTree(leftNode,code+”0”,cL);//递归，编码字符串加0
    }
    if(rightNode!=null){
        viewBTree(rightNode,code+”1”,cL);//递归遍历右子树
    }
    if(leftNode==null && rightNode==null){//左右子树都为空，页节点
        Code nCode = new Code(nd.data,code);//新建编码对象
        cL.add(nCode);//存入队列
    }
}

    当然也有其他方法，这里就不赘述了。

    哈夫曼树大家应该基本了解了，现在我们就需要应用它做点事了，就是今天的另一个主题：压缩算法。哈夫曼树压缩算法的原理就是对所有的byte进行重新编码，由于哈夫曼树生成的编码是长短不一的。我们可以把出现频率高的byte放在哈夫曼树的上层，出现频率低的放在下层，缩短出现频率高的byte的编码，延长出现频率低的byte的编码，替换掉固定的8位二进制编码，达到压缩的目的。所以一个所有byte完全平均的文件经过哈夫曼树压缩算法后大小不会有变化，然而这个可能性很低，通常一篇文章中总有一些字词出现频率很高，在文件中也是一样，有些byte出现频率也比较高，这种情况越不平均，哈夫曼树压缩算法的压缩效率越高。

    通过以上原理，我们就需要在对文件压缩前对文件中的所有byte做一个统计，把该byte出现的次数作为它的权，然后生成哈夫曼树，然后遍历生成编码。现在又出现一个新的问题了，我们在之前的例子中生成的编码是用字符串保存的，如何将其转换为二进制位就成了一个新的问题，因为java中最小的单位是byte，怎样把一个byte分解为单二进制位就是一个瓶颈了。当然，方法很多~~如下就是一个方法，由于java没有保存bit的单位，我们暂且用byte数组表示

/**
 *将String编码转换为二进制位，用byte[]表示
 *@param:code: String 编码
 *@return:用byte[]表示的二进制位代码
 */
public byte[] getBit(String code){
    byte[] bi = new byte[code.length];
    for(int i=0;i<code.length;i++){//取出String中的每个字符
        char ch = code.charAt(i);
        if(ch=='0'){
             bi[i]=0;
        }
        if(ch=='1'){
             bi[i]=1;
        }
    }
    return bi;
}

    然而这还不够，因为哈夫曼树组生成的编码是不等长的，而一个byte必须是8个bit组成，所以需要拼接，将不足8位的用下一个byte的编码补充完整并截断，如若a的编码是01101，b的编码是0011，那么ab组成的byte就应该是01101001 1.......，后面的则由下一位补齐。将二进制位转成二进制不算太难，如二进制位运算、二进制四则运算都可以完成。
    举个例子，我们假设byte[] changeByte(byte oBt)方法就是将原byte转换为用byte[]表示的二进制位，注意：此方法不完善！

/**
 *将二进制位转换为byte方法
 *@param:oBytes 组成源文件的byte[]
 *@return:转换后的Byte队列
 */
public byte[] compressor(byte[] oBytes){
    byte[] bits = new byte[8];//储存8位二进制位
    List<Byte> bL = new ArrayList<Byte>();//转换后长度未知，先用list储存
    int bitsLeft = 8;//储存当前bits中剩余位数
    for(byte b:oBytes){
        byte[] nBits = changeByte(b);//转码，得到二进制位
        for(byte oneBit:nBits){
            bits[8-bitsLeft]=oneBit;//将新二进制位加入到当前byte的二进制位中
            bitsLeft--;//当前byte剩余位数-1
            if(bitsLeft==0){//当当前byte填满的时候
                try{
                byte nByte = changeToByte();
                bL.add(nByte);
                bitsLeft=8;
                }catch(Exception ef){}
            }
        }
    }
}
/**
 * 将8位二进制位转换为byte方法，此处用的是位运算
 * @param:bits : 储存8个二进制位的byte[]
 * @return : 转换成的byte
 * throws:bits不是8个二进制位格式：不是8位或不止0和1
 */
public byte changeToByte throws Exception(byte[] bits){
    if(bits.length!=8){//排除非8位数组的异常
        throw new Exception("不是8位！");
    }
    byte b=0;
    for(int i = 0;i<8;i++){
        if(bits[i]!=0 && bits[i]!=1){//排除值不为0或1的异常
            throw new Exception("值不是0或1")
        }
        b=(byte)(b<<1);//左移1位
        b+=bits[i];
    }
    return b;
}

    相信有些人又发现问题了，最后一个byte编完的时候很可能出现没有补满的情况，那么最后一位怎么填满就成了第二个比较重要的问题了，弄不好就会出现解压时候多了个byte的情况，当然解决的方法也有很多，可以在最前面添加一个参数表示最后一位的空位数然后填满，也可以填入一个编码表中不存在的编码，我采用的是后者，可以节省1个byte的说明。

    这样下来，一个文件算是压缩完了，然而不能只压缩不解压，要解压的话，我们需要把编码表存入文件。由于文件长度未知，一般可以保存在文件头部。当然，编码表和正文部分需要用标记来区分开的，我自己是计算出编码表长度在开头用个int值注明，然后读取int个字节作为编码表，后面的就是正文了。当然还有别的方法，就看各位看官自己探索了~~~

    下面就是解压了，由于哈夫曼树生成的编码长度的不同，压缩过程中我们需要把8个bit转换为一个byte，解压过程就会需要把一个byte拆分为8个bit，方法同样有很多，我这里提供一种方法：

/**
 * 将一个byte的bit拆分方法
 * @param b: 需要拆分的byte
 * @return:一个长度为8的byte[]，每个元素储存一位bit
 */
public byte[] getBits(byte b){
    byte[] bits = new byte[8];//定义用于储存bit的byte[]
    for(int i=0;i<8;i++){
        byte t = (byte)(b<<i);//左移i位
        t = (byte)(t>>7)//再右移7位，这样最低位就是从高位开始第一位了
        t = (byte)(Math.abs(t));//避免负数的影响，主要是当该位为1时
        bits[i] = t;//赋值
    }
    return bits;
}

    特别注意的是，将bit[]合并为byte和将byte拆分为bit[]的过程千万不要将byte的高低位弄颠倒！我就犯过这个错误。。找了半天才找到问题。有了这个方法，我们就可以做出解压动作了，将文件中每个byte依次读出（前面的编码表不要再读进来了），将byte拆分为bit[]，然后一位一位的对照，就是先取bit[]第一位，查看编码表，没有再取前2位对照，如此反复，找到对应的就储存下来，一个byte读完了读下一个，一直到结束，这个文件就被解压完成了。

    后面的扩展就靠各位看官了，比如如何提高压缩/解压效率、压缩多个文件如何实现等，另外，如果修改下这个算法，各byte加权不是由出现次数来定而是事先约定，压缩的时候不将编码表存入文件，那么我们做出来的就是一个加密程序~~

***************************我是华丽的分割线**************************
    大家好~~今天刚刚实现了多线程双缓冲完成压缩文件的程序，不过还是只能压缩单个文件，只是速度较以前有了较大提升。这里把我的一点心得发出来吧。
 
    首先谢谢之前朋友的支持，也欢迎更多的朋友来交流和指正。

    闲话不谈了，开始正题。前面的内容我们已经比较完善的讲述了用哈夫曼完成一个压缩程序，但我们的操作基本是读取一个字节→转换→写入→读取下一个字节这个流程，由于读取和写入操作耗时教多，效率有限，现在我们将流程修改一下：
读取一个字节→转换→存入队列1→读取下一个字节
                                               ↓（当队列1足够满了就将数据转到队列2）
                                           将队列2的数据取出→写入文件→取出队列2中下一组数据
分2个线程同时运行，效率就可以提高很多。这就是双缓冲的方法。

    下面，我们需要更深入理解何为双缓冲。这就牵扯到生成-销售模型了。我们可以理解为两个线程，一端不断的在产生数据（也就是生产方生产出产品），另一端不断在消耗这些数据（也就是消费掉这些生产的产品），首先明确的一点是我们不能保证生产出的数据能立刻被消费端消耗掉，也就是两端不是同步的。因此，我们需要在中间建立一个仓库来储存被生产出来而没被消费掉的数据，这里用的就是队列了。生产-消费模型本质上还是一个数据传递方法，因此，顺序是被严格要求的，也就是先生产的数据必须先被消费掉。而队列正好胜任这个职责。

    这里先举一个例子：
    线程1：

/**
 *生产端，将一个数据（暂定为Object）存入仓库
 */
public void run(){
    while(true){//不断重复这个动作
        Object o = new Object();
        synchronized(list){//synchronized关键字，将list对象锁定不让其他线程读取
            list.add(o);//队列list为仓库队列
            list.notifyAll();//唤醒所有线程，解除锁定
        }
    }
}

    线程2：

/**
 *消费端，将一个数据从仓库取出
 */
public void run(){
    while(true){
        if(list.size()>0){
            synchronized(list){//将list对象锁定不让其他线程读取
                Object o = list.remove(0);//读取队列中第一个元素并移除
                list.notifyAll();//解除锁定状态
            }
        }
    }
}

    以上只是个简单的例子。值得注意的是使用了synchronized()关键字，该方法就是将一个对象锁定不让其他线程读取，主要作用就是防止多线程同时修改一个对象的时候导致错误结果。就如同两个线程之间的仓库有2个门，一个线程进去后放东西放了一半另一个线程进来把东西又取走了，如果第一个线程还需要用到刚刚放进来的东西就会出错。synchronized可以有效避免这种情况的发生。需要注意：synchronized必须和notify()或notifyAll()同时使用

    以上的例子就是单缓冲队列的例子，生产方生产数据，存入仓库，然后消费方再进去把需要取出的数据取出来。就解决了两端不同步的问题，当然，如果只是这样的话，当仓库没有数据时消费端是一个没有任何操作的while(true){}动作，将会造成极大的CPU消耗，我们可以在if后加入else{try{Thread.sleep(10);}catch(Exception e){}}来降低系统消耗。

    单缓冲模型中，生产端和消费端之间只有一个仓库，还是那种只有一个门的，每次都是一个人进去反锁，处理完了再出来，另一个人只有等没锁的时候才能进去，很多时间就浪费在等待上面了。为了改善这一现象，又出现了双缓冲模型，原理就是在生产端和消费端建立两座仓库，生产端只管将生产的数据放入生产端仓库，消费端只管从消费端仓库里取出数据，互不影响了，自然快很多。我们只需要在生产端仓库满的时候或者消费端仓库空掉的时候将生产端仓库的数据一起运到消费端仓库就可以了，两种方法视情况而定二选一，虽然还是需要锁门，但锁门的时间大大减少了，时间就节省出来了。举例代码如下，假定list1和list2是2个仓库：
    线程一：

public void run(){
    while(true){
        Object o = new Object();
        list1.add(o);//先存入1号仓库
        if(list1.size()>100){//1号仓库满了
            synchronized(list1){//锁1号仓库门
                synchronized(list2){//锁2号仓库门
                    list2.addAll(list1);//将1号仓库的数据全部运到2号仓库
                    list2.notifyAll();//2号仓库解锁
                }
                list1.clear();//清空1号仓库
                list1.notifyAll();//1号仓库解锁
            }
        }
        try{
            Thread.sleep(10);//不想机器太卡的话不妨加上这句
        }catch(Exception e){}
    }
}

    线程2：

public void run(){
    while(true){
        if(list2.size()<1){
            Thread.sleep(100);//仓库是空的就先睡一会吧
        }
        synchronized(list2){
            //取出仓库2中的数据，当然，也可以一次取出一批，这样效率更高
            Object o = list2.remove(0);
            list2.notifyAll();
        }
    }
}

    一次取出一批的消费端方法

public void run(){
    while(true){
        if(list2.size()<1){
            Thread.sleep(100);//仓库是空的就先睡一会吧
        }
        int size = list2.size()<100 ? list2.size() : 100;
        Object[] os = new Object[size];
        synchronized(list2){
            //批量取出仓库2中的数据
            for(int i=0;i<size;i++){
                os[i] = list2.remove(0);
            }
            list2.notifyAll();
        }
    }
}

    想查看结果的话可以将Object修改，然后读出数据后输出就可以了。这个例子中由于生产端是无限生产的，不需要考虑剩余数据的问题，如果你的生产端生产的数据是有限的，一定记住最后将没有满的仓库中数据全部转入消费端仓库！

    双缓冲就先说到这里了，看到这里，用双缓冲完成压缩/解压的意义大家应该明白了吧~~就是加快我们压缩/解压的速度。

    前面已经大致介绍过了流程，比起前面的压缩文件，我们需要增加一个压缩线程，一个解压线程和一个写入文件线程，将原来ActionListener里的代码移出来，然后添加2个仓库队列用于储存需要写入的byte。就是List<Byte>啦~~~再把压缩/解压的输出（原来是直接写入文件）改成添加到list1，最后加个双缓冲的转移就可以了。中间出了个小问题，由于前4个byte是用来保存编码表长度的，将一个int转换为4个byte确实伤了一番脑筋，这里给出代码吧，最后还是在网上找的，另求解位运算符>>和>>>有啥区别：

/**
	 * 将int值转换为长度为4的byte数组
	 * 
	 * @param num
	 *            需要转换的int值
	 * @return 长度为4的byte[]数组
	 */
	public byte[] getIntByte(int num) {
		byte[] b = new byte[4];
		for (int i = 0; i < 4; i++) {
			b[i] = (byte) (num >> (24 - i * 8));
		}
		return b;
	}

当然可以有别的方法，看各位大虾各显神通啦。此外还增加了进度条和百分比显示，不过总体来说还是比较简陋的。刚想到一种3线程的方法，一个线程读取数据，一个线程处理，一个线程写入，中间需要用到2个双缓冲，不知道效率如何，有兴趣的朋友也可以尝试下~。后面准备尝试添加多文件压缩了，不过目前还比较纠结，没有太好的方法~~

    整个项目代码在下面已经给出来了，compressorII.rar那个，可能还有点小漏洞什么的，发现的朋友提醒下哈~~

最后，本人是湖南师大大二学生，QQ327667882，欢迎志同道合的朋友多多交流学习，加好友请注明：javaeye网友~~谢谢大家捧场

评论

19 楼 feipigzi 2010-11-21  

将byte拆分为bit[]，然后一位一位的对照，就是先取bit[]第一位，查看编码表，没有再取前2位对照，如此反复，找到对应的就储存下来，一个byte读完了读下一个，一直到结束，这个文件就被解压完成了。

这个方法我试过了，实际效率不如下面方法

按照编码表，构造一个二叉树（每个节点为0或1）,根据读入的二进流，寻找一条从根（根不含0或1）到叶子节点的路径

18 楼 feipigzi 2010-11-21  

我记得io包有个字节缓冲流

17 楼 bluepeer 2010-02-28  

真的不错，这个很实用，不只在加密和文件处理。实际应用也应用可以用到。

16 楼 yixiandave 2010-02-26  

Yaw.Eno 写道

http://blog.csdn.net/dingxy/archive/2009/04/30/4140149.aspx
给你参考哈，>>与>>>的区别……
师大大三……NetJava。
哈哈……

哦。。。知道了。。无符号移位。。。那我有一些代码又可以改了啊~~

15 楼 Yaw.Eno 2010-02-26  

http://blog.csdn.net/dingxy/archive/2009/04/30/4140149.aspx
给你参考哈，>>与>>>的区别……
师大大三……NetJava。
哈哈……

14 楼 yixiandave 2010-02-26  

恩恩，刚刚更新了下，把双缓冲也加进来了~~大家多多捧场啊，有错误请多多指正
同时欢迎交流学习QQ：327667882，加好友的话注明一下javaeye哈~~~否则不知道是谁
嘿嘿

13 楼 sxjkk 2010-02-26  

好东西啊，不错

现在论坛中讲的都是高端应用，很少有讲数据结构和底层的算法了

12 楼 yixiandave 2010-02-26  

抛出异常的爱 写道

yixiandave 写道

|b:4|c:4|d:2|e:7|f:3，下面将通过例子来讲解哈夫曼树的构造方法

superheizai 写道

        e(7)      D(14)
                     /      \
               B(6)          C(8)
                /    \         /    \
           A(3)  f(3)          d(4) c(4)
          /    \
     a(1) b(2)
这里是不是应该B(6)和e（7）？

B(6)和C(8)之前已经成为啦D(14)的左右子树了，排序只排最顶端的，所以队列里应该只剩下e(7)和D(14)了

这说明算法说明有问题
大写字母不是真正的单词........是合并后的指代名词

e(7)                  abfdc(14)
                     /      \
                  abf(6)    dc(8)
                /    \      /    \
           ab(3)    f(3)   d(4) c(4)
          /    \
     a(1)     b(2) 

恩，多谢指正，你的意思就是我的意思，大写字母为指代名词，最后一步有处理的，这个例子真正储存的只有abcdef

11 楼 抛出异常的爱 2010-02-26  

yixiandave 写道

|b:4|c:4|d:2|e:7|f:3，下面将通过例子来讲解哈夫曼树的构造方法

superheizai 写道

        e(7)      D(14)
                     /      \
               B(6)          C(8)
                /    \         /    \
           A(3)  f(3)          d(4) c(4)
          /    \
     a(1) b(2)
这里是不是应该B(6)和e（7）？

B(6)和C(8)之前已经成为啦D(14)的左右子树了，排序只排最顶端的，所以队列里应该只剩下e(7)和D(14)了

这说明算法说明有问题
大写字母不是真正的单词........是合并后的指代名词

e(7)                  abfdc(14)
                     /      \
                  abf(6)    dc(8)
                /    \      /    \
           ab(3)    f(3)   d(4) c(4)
          /    \
     a(1)     b(2) 

10 楼 yixiandave 2010-02-26  

|b:4|c:4|d:2|e:7|f:3，下面将通过例子来讲解哈夫曼树的构造方法

superheizai 写道

        e(7)      D(14)
                     /      \
               B(6)          C(8)
                /    \         /    \
           A(3)  f(3)          d(4) c(4)
          /    \
     a(1) b(2)
这里是不是应该B(6)和e（7）？

B(6)和C(8)之前已经成为啦D(14)的左右子树了，排序只排最顶端的，所以队列里应该只剩下e(7)和D(14)了

9 楼 likeblood 2010-02-25  

请lz把哈弗曼树的简介里的笔误修改一下
支持原创

8 楼 lioncin 2010-02-24  

数字影像编码不就是基于这个东西的吗(原谅我大学的时候，上数据结构和多媒体的时候没用心)

7 楼 superheizai 2010-02-24  

        e(7)      D(14)
                     /      \
               B(6)          C(8)
                /    \         /    \
           A(3)  f(3)          d(4) c(4)
          /    \
     a(1) b(2)
这里是不是应该B(6)和e（7）？

6 楼 hommy8 2010-02-24  

zli.ray 写道

lz讲的很好呀，理论与实践相结合，受教。

   

好文章！！！

5 楼 zli.ray 2010-02-24  

lz讲的很好呀，理论与实践相结合，受教。

4 楼 achenbj 2010-02-24  

很强大，学习！

3 楼 fengzl 2010-02-24  

受教了，收藏

2 楼 yixiandave 2010-02-23  

lyy3323 写道

文件压缩算法？

这是文件压缩算法的其中之一，还有一种字典压缩算法，2者可以一起用，字典压缩算法我还没摸熟~~呵呵
这2种压缩算法同时使用后理论上文件就无法再次被压缩了

1 楼 lyy3323 2010-02-23  

文件压缩算法？