哈弗曼编码以及用其实现压缩软件

1.什么是哈夫曼树？

?? 哈夫曼树是一种最优二叉树，它的最优点体现在它的的带权路径长度最小。（结点的带权路径长度为：结点的路径长度乘以结点的权值，树的带权路径长度为所有叶子结点带权路径长度之和）

2.什么是哈弗曼编码？

?? 从哈弗曼树的根结点开始，按照左子树分配代码“0”，右子树分配代码“1”的规则，直到叶子结点为止，每个叶子结点的哈弗曼编码就是从根结点开始，一直到该叶子结点为止，把途中经过的代码按顺序串起来就OK了。

?

3.什么是哈弗曼压缩？

???? Huffman( 哈夫曼 ) 算法在上世纪五十年代初提出来了，它是一种无损压缩方法，在压缩过程中不会丢失信息熵，而且可以证明 Huffman 算法在无损压缩算法中是最优的。 Huffman 原理简单，实现起来也不困难，在现在的主流压缩软件得到了广泛的应用。对应用程序、重要资料等绝对不允许信息丢失的压缩场合， Huffman 算法是非常好的选择。

????? 哈夫曼压缩，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。

?

有了以上的基本概念，我们就可以动手实现哈弗曼压缩软件了！

?

4.哈弗曼压缩软件的实现：

?? 在文件中，所有的数据都是以字节的形式存在的，一个字节是8位，所以所有可能出现的字节在0——256之间（不包括256），所以，第一步要做的事情就是，把文件所有的字节的出现频率统计出来，并用频率做为权值生成一棵哈弗曼树：

???

//编码表输出完毕，将文件中的字节按照这种编码方式压缩InputStream ins = new FileInputStream(pathName_former);InputStream buf = new BufferedInputStream(ins);//创建输入流count = 0;writeCode = "";allCode = "";while(buf.available()>0||count>=8){if(count>=8){//满8writeCode = allCode.substring(0,8);//前8位count-=8;allCode = allCode.substring(8);bos.write(changeString(writeCode));//写入一个字节}else{int data = buf.read();count+=Code[data].length();allCode+=Code[data];}}//如果不满8位的if(allCode.length()>0){int len = 8-allCode.length();//补零for(int j=0;j<len;j++){allCode+="0";}bos.write(changeString(allCode));bos.write(len);//补入了几个0}else{bos.write(0);//补入了0个0}

?到这里，整个压缩过程基本完成了，解压缩就是压缩的逆过程，在此不再赘述，所有的操作都保存在附上源代码中。