java实现哈夫曼压缩的实例
哈夫曼压缩的原理:
通过统计文件中每个字节出现的频率,将8位的01串转换为位数较短的哈夫曼编码.
其中哈夫曼编码是根据文件中字节出现的频率构建的,其中出现频率越高的字节,其路径长度越短;
出现频率越低的字节其路径长度越长.从而达到压缩的目的.
如何构造哈夫曼树?
一. 定义字节类
我的字节类定义了一下属性
publicintdata;//节点数据 publicintweight;//该节点的权值 publicintpoint;//该节点所在的左右位置0-左1-右 privateNodeDataparent;//父节点引用 privateNodeDataleft;//左节点引用 privateNodeDataright;//右节点引用
二.建哈夫曼树
1.定义一个存储字节信息的数组:intarray_Bytes[256];
其中数组的下标[0,256)代表字节数值(一个字节8位,其值在[0,256)范围内);数组存储字节出现的次数.
2.遍历要压缩的文件,统计字节出现的次数.
InputStreamdata=newFileInputStream(path); /********文件中字符个数********/ intnumber=data.available(); for(inti=0;i3.将字节类对象存入优先队列
4.运用HashMap构造码表
哈夫曼压缩代码如下:
1.字节类
packagecompressFile; /** *节点数据 *功能:定义数据,及其哈夫曼编码 *@authorAndrew * */ publicclassNodeData{ publicNodeData(){ } publicintdata;//节点数据 publicintweight;//该节点的权值 publicintpoint;//该节点所在的左右位置0-左1-右 privateNodeDataparent; privateNodeDataleft; privateNodeDataright; publicintgetData(){ returndata; } publicNodeDatagetParent(){ returnparent; } publicvoidsetParent(NodeDataparent){ this.parent=parent; } publicNodeDatagetLeft(){ returnleft; } publicvoidsetLeft(NodeDataleft){ this.left=left; } publicNodeDatagetRight(){ returnright; } publicvoidsetRight(NodeDataright){ this.right=right; } }2.统计字节的类,并生成码表
packagecompressFile; importjava.io.BufferedInputStream; importjava.io.FileInputStream; importjava.io.IOException; importjava.io.InputStream; importjava.util.ArrayList; importjava.util.Comparator; importjava.util.HashMap; importjava.util.List; importjava.util.Map; importjava.util.PriorityQueue; /** *统计指定文件中每个字节数功能:定义数组,将文件中的字节类型及个数写入数组 *创建优先队列和哈夫曼树 *@authorAndrew * */ publicclassStatisticBytes{ /** *第一步: *统计文件中字节的方法 * *@parampath *所统计的文件路径 *@return字节个数数组 */ privateint[]statistic(Stringpath){ /******储存字节数据的数组--索引值代表字节类型-存储值代表权值******/ int[]array_Bytes=newint[256]; try{ InputStreamdata=newFileInputStream(path); BufferedInputStreambuffered=newBufferedInputStream(data); /********文件中字符个数********/ intnumber=data.available(); System.out.println("字节个数》》》"+number); for(inti=0;icreateQueue(int[]array){ //定义优先队列,根据数据的权值排序从小到大 PriorityQueue queue= newPriorityQueue (array.length,newComparator (){ publicintcompare(NodeDatao1,NodeDatao2){ returno1.weight-o2.weight; } }); for(inti=0;i queue){ while(queue.size()>1){ NodeDataleft=queue.poll();//取得左节点 NodeDataright=queue.poll();//取得右节点 NodeDataroot=newNodeData();//创建新节点 root.weight=left.weight+right.weight; root.setLeft(left); root.setRight(right); left.setParent(root); right.setParent(root); left.point=0; right.point=1; queue.add(root); } NodeDatafirstNode=queue.poll(); returnfirstNode; } /** *第四步: *寻找叶节点并获得哈夫曼编码 *@paramroot根节点 */ privatevoidachievehfmCode(NodeDataroot){ if(null==root.getLeft()&&null==root.getRight()){ array_Str[root.data]=this.achieveLeafCode(root); /** * *得到将文件转换为哈夫曼编码后的文集长度 *文件长度=一种编码的长度*该编码出现的次数 */ WriteFile.size_File+=(array_Str[root.data].length())*(root.weight); } if(null!=root.getLeft()){ achievehfmCode(root.getLeft()); } if(null!=root.getRight()){ achievehfmCode(root.getRight()); } } /** *根据某叶节点获得该叶节点的哈夫曼编码 *@paramleafNode叶节点对象 */ privateStringachieveLeafCode(NodeDataleafNode){ Stringstr=""; /*****************存储节点01编码的队列****************/ List list_hfmCode=newArrayList (); list_hfmCode.add(leafNode.point); NodeDataparent=leafNode.getParent(); while(null!=parent){ list_hfmCode.add(parent.point); parent=parent.getParent(); } intsize=list_hfmCode.size(); for(inti=size-2;i>=0;i--){ str+=list_hfmCode.get(i); } System.out.println(leafNode.weight+"的哈夫曼编码为>>>"+str); returnstr; } /** *第五步: *根据获得的哈夫曼表创建码表 *Integer为字节byte[0~256) *String为哈夫曼编码 *@return码表 */ publicMap createMap(){ int[]hfm_Codes=this.statistic("F:\\JAVA\\压缩前.txt");//获得文件字节信息 PriorityQueue queue=this.createQueue(hfm_Codes);//获得优先队列 /* *获得哈夫曼树的根节点, *this.createTree(queue)方法调用之后(含有poll()),queue.size()=0 */ NodeDataroot=this.createTree(queue); this.achievehfmCode(root);//获得哈夫曼编码并将其存入数组中 Map map=newHashMap (); for(inti=0;i<256;i++){ if(null!=array_Str[i]){ map.put(i,array_Str[i]); } } returnmap; } /** *存储字节哈夫曼编码的数组 *下标:字节数据 *元素:哈夫曼编码 */ publicString[]array_Str=newString[256]; } 3.将码表写入压缩文件并压缩正文
packagecompressFile; importjava.io.BufferedInputStream; importjava.io.BufferedOutputStream; importjava.io.DataOutputStream; importjava.io.FileInputStream; importjava.io.FileOutputStream; importjava.io.IOException; importjava.util.Iterator; importjava.util.Map; importjava.util.Set; /** *将码表和文件写入新的文件中 *@authorAndrew * */ publicclassWriteFile{ //实例化创建码表类对象 privateStatisticBytesstatistic=newStatisticBytes(); privateMapmap=statistic.createMap();//获得码表 //字节接收变量,接收哈夫曼编码连接够8位时转换的字节 privateintexmpCode; publicstaticintsize_File; publicstaticvoidmain(String[]args){ WriteFilewriteFile=newWriteFile(); writeFile.init(); } privatevoidinit(){ StringfilePath="F:\\JAVA\\压缩后.txt"; this.writeFile(filePath); } /** *第一步:向文件中写入码表 * *@paramdataOut *基本数据流 */ privatevoidwriteCodeTable(DataOutputStreamdataOut){ Set set=map.keySet(); Iterator p=set.iterator(); try{ //向文件中写入码表的长度 dataOut.writeInt(map.size()); while(p.hasNext()){ Integerkey=p.next(); StringhfmCode=map.get(key); dataOut.writeInt(key);//写入字节 //写入哈夫曼编码的长度 dataOut.writeByte(hfmCode.length()); for(inti=0;i >"); waiteString=this.changeStringToByte(transString+statistic.array_Str[j]); if(waiteString!=""){ bOut.write(exmpCode); transString=waiteString; }else{ transString+=statistic.array_Str[j]; } } if(""!=transString){ intnum=8-transString.length()%8; for(inti=0;i 二.哈夫曼解压
原理:将压缩的逆向,即你是如何压缩的就怎样去解压。相当于你根据自己定义的协议进行压缩与解压缩文件。
代码如下:
packagedecompressionFile; importjava.io.DataInputStream; importjava.io.FileInputStream; importjava.io.FileOutputStream; importjava.io.IOException; importjava.io.InputStream; importjava.io.OutputStream; importjava.util.ArrayList; importjava.util.HashMap; importjava.util.Iterator; importjava.util.List; importjava.util.Map; importjava.util.Set; /** *解压文件从压缩文件中读入数据解压 * *@authorAndrew * */ publicclassReadFile{ /** *码表Integter:字节[0,255)String:哈夫曼编码 */ privateMapcode_Map=newHashMap (); publicstaticvoidmain(String[]args){ ReadFilereadFile=newReadFile(); readFile.readFile(); } /** *第一步:从文件中读出码表 * *@paramdataInput *基本数据输入流 * */ privatevoidreadMap(DataInputStreamdataInput){ try{ //读出码表的长度 intsize_Map=dataInput.readInt(); /****************读出码表信息************************************/ for(inti=0;i >>>"+data+"!!!!!!!>>"+str); code_Map.put(data,str); } /***************************************************************/ }catch(IOExceptione){ e.printStackTrace(); } } /** *第二步:解压正式文件 */ privatevoidreadFile(){ try{ //文件输入流 InputStreaminput=newFileInputStream("F:\\JAVA\\压缩后.txt"); //BufferedInputStreambIn=newBufferedInputStream(input); DataInputStreamdInput=newDataInputStream(input); //调用读出码表的方法 this.readMap(dInput); bytezerofill=dInput.readByte();//读出文件补零个数 System.out.println("补零个数》》》>>>>"+zerofill); //文件输出流 OutputStreamout=newFileOutputStream("F:\\JAVA\\解压后.txt"); StringtransString="";//接收用于匹配码表中哈夫曼编码的字符串 StringwaiteString="";//接收截取哈夫曼编码后剩余的字符串 /***********************************不耗内存的方法*****************************************/ intreadCode=input.read();//从压缩文件中读出一个数据 intsize=input.available(); for(intj=0;j<=size;j++){ System.out.println("readCodereadCodereadCode》》>>>>"+readCode); waiteString+=this.changeIntToBinaryString(readCode);//将读到的整数转化为01字符串 for(inti=0;i list=newArrayList (); //while(-1!=readCode){ //Stringstr=this.changeIntToBinaryString(readCode); //for(inti=0;i set=code_Map.keySet(); Iterator p=set.iterator(); while(p.hasNext()){ Integerkey=p.next();//获得码表中的字节数据 StringhfmCode=code_Map.get(key);//获得哈夫曼编码 if(hfmCode.equals(str)){ out.write(key); returntrue; } } returnfalse; } /** *根据"除2取余,逆序排列"法 *将十进制数字转化为二进制字符串 *@parama要转化的数字 *@return01字符串 */ privateStringchangeIntToBinaryString(inta){ intb=a; intcount=0;//记录a可转化为01串的个数,在不够8为时便于补零 Stringstr="";//逆序二进制字符串 StringexmpStr="";//顺序二进制字符串 while(a!=0){ b=a/2; if(a%2!=0){ str+=1; }else{ str+=0; } a=b; count++; } //不够8位的地方补零 for(inti=0;i<8-count;i++){ str+=0; } //将转化后的二进制字符串正序 for(intj=7;j>=0;j--){ System.out.print(str.charAt(j)); exmpStr+=str.charAt(j); } System.out.println("转化后的字符串>>>>>>>>>"+exmpStr); returnexmpStr; } }