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

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

1.什么是哈夫曼树?

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

2.什么是哈弗曼编码?

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

3.什么是哈弗曼压缩?

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

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

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

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

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

Java代码：

 
 
 
    
  
  
  
  1. int[] ByteCount = new int[256];//字节频率统计  
    2. 
  
  
  
  2. InputStream fis = new FileInputStream(pathName_former);  
    3. 
  
  
  
  3. InputStream bis = new BufferedInputStream(fis);//创建文件输入流  
    4. 
  
  
  
  4. while(bis.available()>0){  
    5. 
  
  
  
  5. int tmp = bis.read();  
    6. 
  
  
  
  6. ByteCount[tmp]++;  
    7. 
  
  
  
  7. }//统计频率  
    8. 
  
  
  
  8. //构造哈弗曼树  
    9. 
  
  
  
  9. hfmTree hfm = new hfmTree(ByteCount);  
    10. 
  
  
  
  10. Java代码  
    11. 
  
  
  
  11. public hfmTree(int[] rank){//根据频率构造哈弗曼树  
    12. 
  
  
  
  12. //把频率不为零的字节加入节点优先级队列  
    13. 
  
  
  
  13. PriorityQueue nodes = new java.util.PriorityQueue();  
    14. 
  
  
  
  14. for(int i=0;i  
    15. 
  
  
  
  15. if(rank[i]!=0){  
    16. 
  
  
  
  16. nodes.add(new hfmNode(rank[i],i));  
    17. 
  
  
  
  17. }  
    18. 
  
  
  
  18. }  
    19. 
  
  
  
  19. //构造哈弗曼树  
    20. 
  
  
  
  20. while(nodes.size()!=1){  
    21. 
  
  
  
  21. hfmNode node_1 = nodes.poll();//1  
    22. 
  
  
  
  22. hfmNode node_2 = nodes.poll();//2  
    23. 
  
  
  
  23. hfmNode addNode = new hfmNode(node_1.getRank()+node_2.getRank(),0);  
    24. 
  
  
  
  24. addNode.setLeft(node_1);  
    25. 
  
  
  
  25. addNode.setRight(node_2);  
    26. 
  
  
  
  26. nodes.add(addNode);  
    27. 
  
  
  
  27. }  
    28. 
  
  
  
  28. root = nodes.poll();  
    29. 
  
  
  
  29. }//构造函数(correct) 
    30.

 

接下来，要做的就是获得0——256之间每个字节所对应的哈弗曼编码，用一个String[] Code = new Code[256]保存下来：

 
 
 
    
  
  
  
  1. Java代码//获得编码  
    2. 
  
  
  
  2. private void getStrByte(hfmNode node,String s){  
    3. 
  
  
  
  3. if(node.getLeft()==null&&node.getRight()==null){  
    4. 
  
  
  
  4. Code[node.getData()] = s;//获得编码字符串  
    5. 
  
  
  
  5. }  
    6. 
  
  
  
  6. if(node.getLeft()!=null){  
    7. 
  
  
  
  7. getStrByte(node.getLeft(),s+"0");  
    8. 
  
  
  
  8. }//左零 if(node.getRight()!=null){  
    9. 
  
  
  
  9. getStrByte(node.getRight(),s+"1");  
    10. 
  
  
  
  10. }//右1  
    11. 
  
  
  
  11. }  
    12. 
  
  
  
  12. 然后就是把每个字节的编码长度打入文件：Java代码//先将0-255的编码长度打到文件里  
    13. 
  
  
  
  13. for(int i=0;i  
    14. 
  
  
  
  14. if(Code[i]==null||Code[i]==""){  
    15. 
  
  
  
  15. Code[i] = "";  
    16. 
  
  
  
  16. bos.write(0);  
    17. 
  
  
  
  17. }else{  
    18. 
  
  
  
  18. bos.write(Code[i].length());  
    19. 
  
  
  
  19. }  
    20. 
  
  
  
  20. } 
    21.

接下来就是，将每个字节的编码打入文件(这里需要吧8个长度的01串转换成一个byte打入文件)：

 
 
 
    
  
  
  
  1. Java代码//把每个字节的编码表打到文件里  
    2. 
  
  
  
  2. int i = 0;//第i个字节  
    3. 
  
  
  
  3. int count = 0;//满8打一，计数器  
    4. 
  
  
  
  4. String writeCode = "";//写入的8位编码  
    5. 
  
  
  
  5. String allCode = "";//所有待写入的编码  
    6. 
  
  
  
  6. String inCode = "";  
    7. 
  
  
  
  7. while(i<256||count>=8){  
    8. 
  
  
  
  8. if(count>=8){//满8  
    9. 
  
  
  
  9. writeCode = allCode.substring(0,8);//前8位  
    10. 
  
  
  
  10. count-=8;  
    11. 
  
  
  
  11. allCode = allCode.substring(8);  
    12. 
  
  
  
  12. bos.write(changeString(writeCode));//写入一个字节  
    13. 
  
  
  
  13. }else{  
    14. 
  
  
  
  14. count+=Code[i].length();  
    15. 
  
  
  
  15. allCode+=Code[i];  
    16. 
  
  
  
  16. inCode+=Code[i];  
    17. 
  
  
  
  17. i++;//严重错误发生地  
    18. 
  
  
  
  18. }  
    19. 
  
  
  
  19. }  
    20. 
  
  
  
  20. //如果不满8位的  
    21. 
  
  
  
  21. if(allCode.length()>0){  
    22. 
  
  
  
  22. int len = 8-allCode.length();//补零  
    23. 
  
  
  
  23. for(int j=0;j  
    24. 
  
  
  
  24. allCode+="0";  
    25. 
  
  
  
  25. }  
    26. 
  
  
  
  26. inCode+=allCode;  
    27. 
  
  
  
  27. bos.write(changeString(allCode));  
    28. 
  
  
  
  28. } 
    29.

 

***就是把文件中的所有字节按照这种哈弗曼的编码方式保存到文件中，过程类似于上一步(在***打入末尾补入的0的个数，主要是为了方便解压缩)：Java代码//编码表输出完毕，将文件中的字节按照这种编码方式压缩。

 
 
 
    
  
  
  
  1. InputStream ins = new FileInputStream(pathName_former);  
    2. 
  
  
  
  2. InputStream buf = new BufferedInputStream(ins);//创建输入流  
    3. 
  
  
  
  3. count = 0;  
    4. 
  
  
  
  4. writeCode = "";  
    5. 
  
  
  
  5. allCode = "";  
    6. 
  
  
  
  6. while(buf.available()>0||count>=8){  
    7. 
  
  
  
  7. if(count>=8){//满8  
    8. 
  
  
  
  8. writeCode = allCode.substring(0,8);//前8位  
    9. 
  
  
  
  9. count-=8;  
    10. 
  
  
  
  10. allCode = allCode.substring(8);  
    11. 
  
  
  
  11. bos.write(changeString(writeCode));//写入一个字节  
    12. 
  
  
  
  12. }else{  
    13. 
  
  
  
  13. int data = buf.read();  
    14. 
  
  
  
  14. count+=Code[data].length();  
    15. 
  
  
  
  15. allCode+=Code[data];  
    16. 
  
  
  
  16. }  
    17. 
  
  
  
  17. }  
    18. 
  
  
  
  18. //如果不满8位的  
    19. 
  
  
  
  19. if(allCode.length()>0){  
    20. 
  
  
  
  20. int len = 8-allCode.length();//补零  
    21. 
  
  
  
  21. for(int j=0;j  
    22. 
  
  
  
  22. allCode+="0";  
    23. 
  
  
  
  23. }  
    24. 
  
  
  
  24. bos.write(changeString(allCode));  
    25. 
  
  
  
  25. bos.write(len);//补入了几个0  
    26. 
  
  
  
  26. }else{  
    27. 
  
  
  
  27. bos.write(0);//补入了0个0  
    28. 
  
  
  
  28. } 
    29.

到这里，整个压缩过程基本完成了。希望对大家有帮助。

本文标题：用哈弗曼编码实现压缩软件
本文网址：http://www.hantingmc.com/qtweb/news28/314428.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

网站建设知识

分类信息网

成都包装设计公司　　 　大英泰恒网站　　 　响应式报价　　 　关键词优化　　 　德阳电信服务器托管　　 　宜宾做网站　　 　兴发搬家　　 　全网营销　　 　四川成都网站设计　　 　雕琢时光茶叶　　 　重庆网站建设　　 　和正源建设　　 　营销型网站建设　　 　医药医疗网站建设方案　　 　成都网站排名　　 　响应式网站建设　　 　成都铺面装修　　 　成都网站设计　　 　乐山做网站　　 　成都画册制作