哈夫曼压缩

哈夫曼压缩总结

树是一种数据结构，哈夫曼树是一种WPL(树的带权路径)最小的二叉树，那么我们如何用哈夫曼树进行文件压缩呢？

我们先分析一个文本文件的组成1：文件头 2：文件内容：

利用哈夫曼进行压缩大体上要经过这四个步骤：

1：扫描文件内容，统计每个字符出现的频率，由于我们常见的字符可以用0—255相对应的ASCII码值表示，所以可以建立一个长度为256的int型数组来存储各个字符出现的次数。

2：循环上面得到的数组并建树，树节点中的数据包括某个字符i和它相对应出现的次数。这里我们要利用Comparable接口中的方法和java自带的优先队列PriorityQueue实现来哈夫曼树的构建，队列头的数据始终是字符出现次数最少的（由于优先队列和排序）我们可以得到出现次数最少的两个字符节点,然后我们可以依据规律建立出一个哈夫曼树。

3：遍历哈夫曼树，得到每一个字符所对应的哈夫曼编码（设定左孩子为0，右孩子为1）。

4：根据上面得到的信息分为头信息和文件信息（按照头信息的编码格式）分别写入文件中，这里要注意记录最后一位补0的个数，并写入文件中，这样就完成了文件的压缩。具体方法见下：

比如我们要压缩的文件内容为aaabbbccddeeeee；

先扫描文件

while (fis.available() > 0) {

int i = fis.read();

byteCount[i]++;

}

经过建树和扫描得到编码那么对应的

SaveCode[97].code=00;

SaveCode[98].code=01;

SaveCode[99].code=100；

SaveCode[100].code=101；

SaveCode[101].code=11；

我们要将对应字符的哈夫曼码的长度存入一个数组中并写入文件中;

for(int i=0;i<256;i++){

if(byteCount[i]!=0){

fos.write(SaveCode[i].length);

}

}

然后将每个字符对应的码一个byte为单位写入文件中最后如果不足8位，则用0补齐。那么上面文件头部分的码表就应该为 00011001 01110000,写完头文件后就要开始写文件内容了，和头文件类似，上面文件内容用对应的哈夫曼编码后为00000001 01011001 00101101 11111111 11000000（补了6个0）。当然，上面的01串只是写入文件前的格式，为了达到压缩的目的，我们要将一个byte的01串变为一个0-255的整形数字存到文件中。将8位01字符串变成相应的0-255的整形数字的方法如下：

public int changeString(String s) {

return ((int) s.charAt(0) - 48) * 128 + ((int) s.charAt(1) - 48) * 64+ ((int) s.charAt(2) - 48) * 32 + ((int) s.charAt(3) -

48) * 16+ ((int) s.charAt(4) - 48) * 8 + ((int) s.charAt(5) - 48) * 4+ ((int) s.charAt(6) - 48) * 2 + ((int) s.charAt(7) - 48);

}

综上所述，压缩完后写入文件的内容包括：

1：码表的长度 2：码表 3:文件内容（包括最后的补0个数）。这样，压缩就完成了。

压缩完成后，就要考虑如何解压了，解压是压缩的逆过程，按照上面的压缩方法，我们就要先读出码表，然后再根据码表一个byte一个byte的读出文件的内容。

我们读出的内容是整形的，先要把它变成01字符串，转换的代码是public String IntToString（int n）{

int n= b； String s="";

for（int i =0；i<8;i++）{

if(n%2==0){

s =‘0’+s；

}

if(%2==1){

S=‘1’+s；

}

b=b/2;}

return s;

}

1：读码表 :由于有了相应字符哈夫曼码的长度，所以可以直接截取相应长度的01字符串。

2：读文件内容：和读码表的时候类似，每次读取一个位，读完后就与相应的码表做对照，如果遇到与码表内容相同的01字符串就将它还原为原来的字符。

public int compare(String s){

if(s.length()==byteCount[i].length&&s.equals(SaveCode[i].code)){

return i;

}

return -1;

}

当读到最后一个byte时，由于补过0，所以要将补的0去掉，再读取文件，这样，文件就还原完了，文件的解压也就搞定了。

做哈夫曼压缩的开始，我没有理清思路，以为自己知道了整体思路，其实还很混乱，导致我做的比较慢，同时这个思路也不是我自己想出来的，还是借鉴别人的想法，以上理解属于菜鸟自解，有错的地方欢迎大家指正。

<!--EndFragment-->