【IT168 文档】认识哈夫曼树之前首先我们简单的来了解一下二叉树，不难理解，二叉树就是每个节点都只有2个子节点的树状结构，也就分为父节点(parent node)、左子树(left child)和右子树(right child)。每个节点最多只能有2个节点，当然也可以更少，比如只有左节点没有右节点或者相反，没有子节点的节点我们称之为叶节点，有子树的称之为根节点。
二叉树相关就先介绍到这里，我们还是回到主题。首先，哈夫曼树就是一种特殊的二叉树，也是一种加权二叉树。首先，我们对我们需要储存到二叉树的数据赋予权重，权比较高的放在浅层，权重低的放在深层，并且所有的数据都储存在叶节点。接下来的问题就是如何构造这个哈夫曼树了。
举个例子：我们要储存的数据及其权重分别为：a:1|b:4|c:4|d:2|e:7|f:3，下面将通过例子来讲解哈夫曼树的构造方法
首先，将数据按权重排序
1 | 2 | 3 | 4 | 4 | 7
我们先将权最低的2个节点组成一个二叉树，根节点为A，没有数据，但权重为2个子节点的和，并将他们的根节点放入列表重新排序：
引用
/ \
a(1) b(2)
重复上一步骤，取新的根节点为B
引用
/ \
A(3) f(3)
/ \
a(1) b(2)
引用
/ \ / \
A(3) f(3) d(4) c(4)
/ \
a(1) b(2)
引用
/ \
B(6) C(8)
/ \ / \
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 ○
/ \
○ ○
/ \ / \
○ f d c
/ \
a b
大功告成!
哈夫曼树的意义就在于可以对其中的数据重新编码，编码方式很简单，左树为0右树为1，每下一层加一个数字，以上图中的例子来说，abcdef对应编码就是：
|b|1001
|c|111
|d|110
|e|0
|f|101
大家不难发现，这几个编码没有任何一个是另一个编码的前置。这是由哈夫曼树的特性决定的，哈夫曼树所有的数据都在页节点，如果出现一个数据是另一个数据编码的前置，这个数据必然在另一个数据的路径前，也就是在根节点，然而这是不可能的，这也确保了解码的唯一性，避免了歧义的出现，就拿刚才的例子来说，11111001011001的解码只可能是cdefb而不会是别的。
对于程序来说，取得这个编码就牵扯到一个二叉树遍历的问题了，通常来说，遍历一个二叉树可以用递归方式解决，这里举个简单的例子：
//分别取得左子节点和右子节点，然后一个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[]表示
*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方法
*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方法，此处用的是位运算
* 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，c过程就会需要把一个byte拆分为8个bit，方法同样有很多，我这里提供一种方法：
* 将一个byte的bit拆分方法
* 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加权不是由出现次数来定而是事先约定，压缩的时候不将编码表存入文件，那么我们做出来的就是一个加密程序~~
