哈弗曼编码以及用其实现压缩软件
1.什么是哈夫曼树?
专注于为中小企业提供成都网站设计、成都网站建设、外贸网站建设服务,电脑端+手机端+微信端的三站合一,更高效的管理,为中小企业珠山免费做网站提供优质的服务。我们立足成都，凝聚了一批互联网行业人才，有力地推动了上千家企业的稳健成长，帮助中小企业通过网站建设实现规模扩充和转变。
哈夫曼树是一种最优二叉树，它的最优点体现在它的的带权路径长度最小。(结点的带权路径长度为：结点的路径长度乘以结点的权值，树的带权路径长度为所有叶子结点带权路径长度之和)
2.什么是哈弗曼编码?
从哈弗曼树的根结点开始，按照左子树分配代码“0”，右子树分配代码“1”的规则，直到叶子结点为止，每个叶子结点的哈弗曼编码就是从根结点开始，一直到该叶子结点为止，把途中经过的代码按顺序串起来就OK了。
3.什么是哈弗曼压缩?
Huffman( 哈夫曼 ) 算法在上世纪五十年代初提出来了，它是一种无损压缩方法，在压缩过程中不会丢失信息熵，而且可以证明 Huffman 算法在无损压缩算法中是最优的。 Huffman 原理简单，实现起来也不困难，在现在的主流压缩软件得到了广泛的应用。对应用程序、重要资料等绝对不允许信息丢失的压缩场合， Huffman 算法是非常好的选择。
哈夫曼压缩，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号(例如，文本文件中的字符)用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。
有了以上的基本概念，我们就可以动手实现哈弗曼压缩软件了!
4.哈弗曼压缩软件的实现：
在文件中，所有的数据都是以字节的形式存在的，一个字节是8位，所以所有可能出现的字节在0——256之间(不包括256)，所以，第一步要做的事情就是，把文件所有的字节的出现频率统计出来，并用频率做为权值生成一棵哈弗曼树：
Java代码
- int[] ByteCount = new int[256];//字节频率统计
- InputStream fis = new FileInputStream(pathName_former);
- InputStream bis = new BufferedInputStream(fis);//创建文件输入流
- while(bis.available()>0){
- int tmp = bis.read();
- ByteCount[tmp]++;
- }//统计频率
- //构造哈弗曼树
- hfmTree hfm = new hfmTree(ByteCount);
Java代码
- public hfmTree(int[] rank){//根据频率构造哈弗曼树
- //把频率不为零的字节加入节点优先级队列
- PriorityQueue nodes = new java.util.PriorityQueue ();
- for(int i=0;i
- if(rank[i]!=0){
- nodes.add(new hfmNode(rank[i],i));
- }
- }
- //构造哈弗曼树
- while(nodes.size()!=1){
- hfmNode node_1 = nodes.poll();//1
- hfmNode node_2 = nodes.poll();//2
- hfmNode addNode = new hfmNode(node_1.getRank()+node_2.getRank(),0);
- addNode.setLeft(node_1);
- addNode.setRight(node_2);
- nodes.add(addNode);
- }
- root = nodes.poll();
- }//构造函数(correct)
接下来，要做的就是获得0——256之间每个字节所对应的哈弗曼编码，用一个String[] Code = new Code[256]保存 下来
Java代码
- //获得编码
- private void getStrByte(hfmNode node,String s){
- if(node.getLeft()==null&&node.getRight()==null){
- Code[node.getData()] = s;//获得编码字符串
- }
- if(node.getLeft()!=null){
- getStrByte(node.getLeft(),s+"0");
- }//左零
- if(node.getRight()!=null){
- getStrByte(node.getRight(),s+"1");
- }//右1
- }
然后就是把每个字节的编码长度打入文件：
Java代码
- //先将0-255的编码长度打到文件里
- for(int i=0;i
- if(Code[i]==null||Code[i]==""){
- Code[i] = "";
- bos.write(0);
- }else{
- bos.write(Code[i].length());
- }
- }
接下来就是，将每个字节的编码打入文件(这里需要吧8个长度的01串转换成一个byte打入文件)：
Java代码
- //把每个字节的编码表打到文件里
- int i = 0;//第i个字节
- int count = 0;//满8打一，计数器
- String writeCode = "";//写入的8位编码
- String allCode = "";//所有待写入的编码
- String inCode = "";
- while(i<256||count>=8){
- if(count>=8){//满8
- writeCode = allCode.substring(0,8);//前8位
- count-=8;
- allCode = allCode.substring(8);
- bos.write(changeString(writeCode));//写入一个字节
- }else{
- count+=Code[i].length();
- allCode+=Code[i];
- inCode+=Code[i];
- i++;//严重错误发生地
- }
- }
- //如果不满8位的
- if(allCode.length()>0){
- int len = 8-allCode.length();//补零
- for(int j=0;j
- allCode+="0";
- }
- inCode+=allCode;
- bos.write(changeString(allCode));
- }
最后就是把文件中的所有字节按照这种哈弗曼的编码方式保存到文件中，过程类似于上一步(在最后打入末尾补入的0的个数，主要是为了方便解压缩)：
Java代码
- //编码表输出完毕，将文件中的字节按照这种编码方式压缩
- InputStream ins = new FileInputStream(pathName_former);
- InputStream buf = new BufferedInputStream(ins);//创建输入流
- count = 0;
- writeCode = "";
- allCode = "";
- while(buf.available()>0||count>=8){
- if(count>=8){//满8
- writeCode = 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
- allCode+="0";
- }
- bos.write(changeString(allCode));
- bos.write(len);//补入了几个0
- }else{
- bos.write(0);//补入了0个0
- }
到这里，整个压缩过程基本完成了，解压缩就是压缩的逆过程，在此不再赘述，所有的操作都保存在附上源代码中。
当前标题：哈弗曼编码以及用其实现压缩软件
当前URL：http://www.shufengxianlan.com/qtweb/news42/60992.html
网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等
声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联