JAVA基础：用哈弗曼编码实现压缩软件（1）

会计考友

　　1.什么是哈夫曼树?
　　哈夫曼树是一种最优二叉树，它的最优点体现在它的的带权路径长度最小。(结点的带权路径长度为：结点的路径长度乘以结点的权值，树的带权路径长度为所有叶子结点带权路径长度之和)
　　2.什么是哈弗曼编码?
　　从哈弗曼树的根结点开始，按照左子树分配代码“0”，右子树分配代码“1”的规则，直到叶子结点为止，每个叶子结点的哈弗曼编码就是从根结点开始，一直到该叶子结点为止，把途中经过的代码按顺序串起来就OK了。
　　3.什么是哈弗曼压缩?
6 l  n  a8 H, J' B' `8 I3 t　　Huffman( 哈夫曼 ) 算法在上世纪五十年代初提出来了，它是一种无损压缩方法，在压缩过程中不会丢失信息熵，而且可以证明 Huffman 算法在无损压缩算法中是最优的。 Huffman 原理简单，实现起来也不困难，在现在的主流压缩软件得到了广泛的应用。对应用程序、重要资料等绝对不允许信息丢失的压缩场合， Huffman 算法是非常好的选择。
　　哈夫曼压缩，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号(例如，文本文件中的字符)用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。
% \5 C0 C5 A' X6 u　　有了以上的基本概念，我们就可以动手实现哈弗曼压缩软件了! www.examｗ.com
　　4.哈弗曼压缩软件的实现：
　　在文件中，所有的数据都是以字节的形式存在的，一个字节是8位，所以所有可能出现的字节在0——256之间(不包括256)，所以，第一步要做的事情就是，把文件所有的字节的出现频率统计出来，并用频率做为权值生成一棵哈弗曼树：
　　Java代码
" y4 D  Z4 r2 y- y　　int[] ByteCount = new int[256];//字节频率统计
- t! j9 W  G0 K/ h6 K6 u4 x0 F　　InputStream fis = new FileInputStream(pathName_former);
　　InputStream bis = new BufferedInputStream(fis);//创建文件输入流
* S2 l& `' e8 P# b; v( e　　while(bis.available()>0){
& H/ x7 U# U4 U) v& J$ O# x9 Z　　int tmp = bis.read();
　　ByteCount[tmp]++;
　　}//统计频率
　　//构造哈弗曼树
　　hfmTree hfm = new hfmTree(ByteCount);
　　Java代码
; `' ~( \( p) o/ K8 m4 G$ _　　public hfmTree(int[] rank){//根据频率构造哈弗曼树
　　//把频率不为零的字节加入节点优先级队列
2 D. `4 A0 v3 T, ]" \0 N; O　　PriorityQueue nodes = new java.util.PriorityQueue();
　　for(int i=0;i
8 T8 v$ Y. |" Y# ^4 b/ i( z" D: C　　if(rank!=0){
) C% U" j9 @! c1 t; B# q　　nodes.add(new hfmNode(rank,i));
　　}
　　}
/ D) E+ d# z) u9 X  O　　//构造哈弗曼树
　　while(nodes.size()!=1){
　　hfmNode node_1 = nodes.poll();//1
　　hfmNode node_2 = nodes.poll();//2
3 l5 k' ?% @% t6 y# V: M) F　　hfmNode addNode = new hfmNode(node_1.getRank()+node_2.getRank(),0);
+ S9 b3 T# n7 A* ~　　addNode.setLeft(node_1);
　　addNode.setRight(node_2);
2 @2 E) i5 ]# D( M0 y% Z$ e　　nodes.add(addNode);
4 m( Y# m8 x2 P/ F6 B　　}
+ u/ Y! g! G: n& X5 M9 B: ]　　root = nodes.poll();
+ W( _- y) ~' V8 E. N* V1 p　　}//构造函数(correct)