哈弗曼树以及压缩运用

     一．介绍

其实在还没有学习压缩之前，在学校学习中已经接触到了哈弗曼，而且已经了解哈弗曼是如何进行编码和解码，只是没有通过编程实现而已，现在就大致介绍一下哈弗曼树。

设根树T有t片树叶V1，V2......Vi,给每一片树叶赋一个权值W1,W2......Wi，则称为T赋权二叉树，其中L(Vi)为叶子节点Vi到根节点的长度，如果存在一种赋权方式，使得 ，则称这棵树为最优二叉树，即哈弗曼树。

WPL的计算方法

由以上的计算方式可以的出，哈弗曼树的WPL是最小的。完全二叉树不一定是哈弗曼树。

二．构造方法及编码

HuffMan树的构造方法：

（1）对所有权值从低到高排队。

（2）找出两个最小的权值，记为W1，W2。

（3）用（W1加W2）代替W1与W2，产生新的队列。

（4）若队列中的点数大于1，则回到第一步，否则进行下一步。

（5）逆序将以上组合过程画出来得到HuffMan树。

构造原则：左小右大、组合优先、左0右1、不足补零

 

哈弗曼树构造图：

 

按照上面介绍的原则：可得出每一个字符对应的编码

a ：0;   b : 10;  c : 110; d : 111

 

三．哈弗曼压缩以及实现原理

对于现代科技的高速发展，数据的存储和传输越来越多，量也越来越大，对于存储和传输的介质要求越来越高，所以如果能进行数据压缩，将在一定程度上解决这个问题。哈弗曼压缩是一种无损压缩，对于大部分文件数据是不允许有任何损失的，所以哈弗曼对于此类文件的压缩无疑是非常好的选择。

四．哈弗曼压缩的实现

哈弗曼压缩就是通过用01串构成的编码代替字符的存储，就像上面的的a,b,c,d四个字符,一个字符在文件存储时需要两个字节及16位，四个就需要64位，而用上面的编码把他们变成01串即为010110111 之后，可以看出占用的空间明显小了很多。

1).权值的获取：其实此时的权值即为-128~127中每个字节在文件里出现的次数，然后按照上面的构造方法构造哈夫曼树，可以看出，重复率越高的字节最终的编码越短，这样就达到压缩的目的了

 

//计算文件中每个字节出现的次数

           while (bis2.available() > 0) {

              int i = bis2.read();

              date[i]++;

      }

 

2).构建哈夫曼树

先以每个出现的字节以及出现的次数创建结点对象，把他们放入事先定义好的优先队列（hufQueue）中去

// 构建哈夫曼树

       while (hufQueue.size() > 1) {

           

           hufNode min1 = hufQueue.poll();// 获取头对象,获得并删除对象

           hufNode min2 = hufQueue.poll();

           

           //通过两个子节点合成一个父节点

           hufNode result = new hufNode(0, min1.getTimes() + min2.getTimes());

           

           //设定左右子节点

           result.setLeftChild(min1);

           result.setRightChild(min2);

           

         hufQueue.add(result);// 加入合并节点

}

 

3).获得编码,其中以根节点为起始点进行编码，并存入数组中

/**

     * 获得编码

     * @param root  ： 根节点

     * @param s     ：编码

     */

    public void getCode(hufNode root, String s) {

 

       if ((root.getLeftChild() == null) && (root.getRightChild() == null)) {// 左右子节点都为空，则编码结束

           //创建一个编码对象

           Code code = new Code(s.length(),s);

       

           saveCode[root.getDate()] = code;

       }

 

       if (root.getLeftChild() != null) {// 左子节点不为null，则继续编码

           getCode(root.getLeftChild(), s + "0");// 左 0

       }

 

       if (root.getRightChild() != null) {// 右子节点不为null，则继续编码

           getCode(root.getRightChild(), s + "1");// 右 1

       }

}

 

 

4).写入码表,因为有解压肯定要解压，如果直接给你一长串01串，谁也不知到是什么意思，所以必须把压缩方式写进去，以方便解压缩，写入码表的方式是把所有的字节编码连起来，然后8个一截取，转化为字节然后再存储到文件里，

当最后不足8个时就用0补齐再存储，需要注意的是在写入码表之前要把每一个字节对应编码的长度先写入文件，以方便解压时的截取

while ((bis.available() > 0) || (count >= 8)) {

              // 如果缓冲区的写入字符个数大于8

              if (count >= 8) {

                  // 清空要转化的字符串

                  waiteString = writes.substring(0, 8);

                  

                  // 去除writes的前8位

                  writes = writes.substring(8);

                  

                  count -= 8;// 写入一个8位字节

                  int tempw = changeString(waiteString);

                  // 写入文件

                  bos2.write(tempw);

 

              } else {

                  

                  idate = bis.read();

                  // 得到第i个字节的编码信息

                  count += saveCode[idate].getN();

                  writes += saveCode[idate].getNode();

                  

              }

           }

 

 

 

5).解析文件，完成压缩，其实这一步就是把文件里字节一个一个读取出来然后与码表进行比对，换成对应的编码，然后再重新写入文件，方式与写入码表时是一样的。这是压缩的整个过程，对于小文件，由于码表的写入,也许最终压缩后的占用空间并不一定减小，但对于较大的文件和重复率较高的文件最终的压缩率还是比较可观的。