花了很长时间写的哈夫曼压缩,终于完成了,在介绍写哈夫曼压缩软件之前,先给大家普及一些小知识。
1、什么是哈夫曼编码?
哈夫曼编码(Huffman Coding)是一种编码方式,哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字,有时称之为最佳编码,一般就叫作Huffman编码。
2、什么是哈夫曼树?
哈夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。树的带权路径长度记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln),N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树,相应的叶结点的路径长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最小的。
3、什么是压缩软件?
压缩软件是利用算法将文件有损或无损地处理,以达到保留最多文件信息,而令文件体积变小的应用软件。压缩软件一般同时具有解压缩的功能。压缩软件的的基本原理是查找文件内的重复字节,并建立一个相同字节的"词典"文件,并用一个代码表示,比如在文件里有几处有一个相同的词"中华人民共和国"用一个代码表示并写入"词典"文件,这样就可以达到缩小文件的目的。常见的压缩软件有WinRAR ,好压(Haozip),WinZip,7-Zip,WinMount,Peazip等等。
5、什么是哈夫曼压缩?
哈夫曼压缩是个无损的压缩算法,一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号(例如,文本文件中的字符)用一个特定长度的位序列替代。因此,在文件中出现频率高的符号,使用短的位序列,而那些很少出现的符号,则用较长的位序列。
6、什么是哈夫曼算法?
Huffman算法是一种基于统计的压缩方法。它的本质就是对文本文件中的字符进行重新编码,对于使用频率越高的字符,其编码也越短。但是任何2个字符的编码, 是不能出现向前包含的。也就是说字符A(假设为00)的编码的前段,不可能为字符B(则B的编码不可能为001,因为这里B的编码中包含了A的前段00,这会给解码难带来不必要的困难,所以这是不允许的)的编码。经过编码后的文本文件,主要包含2个部分:Huffman码表部分和压缩内容部分。解压缩的时候,先把Huffman码表取出来,然后对压缩内容部分各个字符进行逐一解码,形成源文件。
哈夫曼编码生成步骤:
①扫描要压缩的文件,对字符出现的频率进行计算。
②把字符按出现的频率进行排序,组成一个队列。
③把出现频率最低(权值)的两个字符作为叶子节点,它们的权值之和为根节点组成一棵树。
④把上面叶子节点的两个字符从队列中移除,并把它们组成的根节点加入到队列。
⑤把队列重新进行排序。重复步骤③④⑤直到队列中只有一个节点为止。
⑥把这棵树上的根节点定义为0(可自行定义0或1)左边为0,右边为1。这样就可以得到每个叶子节点的哈夫曼编码了。
接下来就结束哈夫曼编码的大体编程思想,一个程序最重要的就是思想,要事先把思路和步骤理清楚,才开始编程序,因为哈夫曼压缩涉及的方法很多,所以要编写边测试,做到每写一个方法,保证该方法的正确性,防止以后找不到问题所在。
一、哈夫曼压缩步骤:
①扫描要压缩的文件,对字节出现的频率进行计算统计
/** * 读取文件统计字符和字符的出现频率 * @param path 要压缩的文件路径 * @throws IOException */ public void countWeight(String path) throws IOException{ fis = new FileInputStream(path); dis=new DataInputStream(fis); while(dis.available()>0){ int i = dis.read(); byteCount[i]++;//i是字符的ASCII码,数组内容是该字符的出现次数 } }
②根据字符频率,将字符创建成结点加入到优先队列中,建立哈夫曼树
public void createTree(){ //使用优先队列建立哈夫曼树 PriorityQueue<HfmNode> nodeQueue = new PriorityQueue<HfmNode>(); for(int i=0;i<byteCount.length;i++){ //文件中出现次数不为0的字符,建立哈夫曼结点,存入队列 if(byteCount[i]!=0){ HfmNode node = new HfmNode(i,byteCount[i]); nodeQueue.add(node); } }
③根据优先队列的排序,构建哈夫曼树
while(nodeQueue.size()>1){//当队列中的元素个数大于1 //取得最小的两个,并删除掉 HfmNode min1 = nodeQueue.poll(); HfmNode min2 = nodeQueue.poll(); //建立新的结点 HfmNode result = new HfmNode(0,min1.getCounts()+min2.getCounts()); //设置新结点的左右子结点 result.setlChild(min1); result.setrChild(min2); //新结点加入到优先队列中 nodeQueue.add(result); } //循环结束后队列中只有一个元素,该元素就是根节点,获取到但不删除 root = nodeQueue.peek(); // System.out.println("根!"+root.toString()); }
④给叶子节点设置编码
public void setCode(HfmNode root,String s){ //如果左右子结点都为空,即为叶子节点 if(root.getlChild()==null&&root.getrChild()==null){ //实例化一个code对象,设置编码和长度 Code huffman_code = new Code(); huffman_code.setCode(s); //把编码code对象放到SaveCode数组中下标为字符AscII值 SaveCode[root.getAscII()] = huffman_code; } //如果左子结点不为空,递归 if(root.getlChild()!=null){ setCode(root.getlChild(),s+'0'); } //如果右子结点不为空,递归 if(root.getrChild()!=null){ setCode(root.getrChild(),s+'1'); } }
⑤写入文件头信息,写入的编码是补零后的编码 , 然后把码表写入文件头信息,还要加上要补零的个数
public void writeHead(String destPath) throws IOException{ fos = new FileOutputStream(destPath); dos=new DataOutputStream(fos); //统计文件总共用到的字符总数,即编码个数 int codeNum = 0; for(int i=0;i<256;i++){ if(SaveCode[i]!=null){ codeNum++; allString += byteCount[i]*SaveCode[i].getCode().length(); } } //写入总文件中总共有多少个用到的字符 dos.write(codeNum); // System.out.println(codeNum); //循环输出码表,包括(按顺序):字符、补了几个0、编码含有的byte个数、编码(整型)。 for(int i=0;i<256;i++){ //如果该字符在文件中出现过,即编码不为空 if(SaveCode[i]!=null){ //写入:字符的ASCII码值 dos.write(i); // System.out.print(i+"\t"+(char)i); //第i个字符的补零数 if(SaveCode[i].getCode().length()%8!=0){//如果编码字符串程度不是8的整倍数 zeroCount[i] = 8-SaveCode[i].getCode().length()%8;//设置补零的个数 }else{//如果是8的整倍数 zeroCount[i] = 0; } //写入:每个编码末尾补了几个0 dos.write(zeroCount[i]); //补零后的编码,写入头信息 String addZero = SaveCode[i].getCode(); // System.out.println(SaveCode[i].getCode()+"需要补零的个数"+zeroCount[i]); for(int j=0;j<zeroCount[i];j++){//循环次数为:需要补零的个数 //每次在编码后补一个0 addZero = addZero+'0'; } //在补0完成后,写入:编码有几个byte dos.write(addZero.length()/8); //对于补齐0的编码,每次取出一个字节 for(int j=0;j<addZero.length()/8;j++){ String subString = ""; //取出一个字节中的8位赋值给codeString for(int k=j*8;k<(j+1)*8;k++){ subString = subString+addZero.charAt(k); } //读取每个字节,将01串转化成整型数 int cs = changeString(subString); dos.write(cs); }//每个字符读取完毕 } } if(allString%8==0){ dos.write(0); }else{ fileAddZero = 8-allString%8; dos.write(fileAddZero); System.out.println("文章末尾补零"+fileAddZero); } }
⑥读文件并写入内容到另外一个文件
public void writeFile(String path) throws IOException{ //等待中的编码字符串 String str = ""; fis = new FileInputStream(path); dis=new DataInputStream(fis); //如果文件可读内容大于0 while(dis.available()>0){ //读取一个字节字符 int i = dis.read(); //得到该字符的码表中的编码----没有补零的,加入到等待中的字符串后 str = str+SaveCode[i].getCode(); System.out.println("!!~~!!"+str); //如果该编码长度大于等于8 while(str.length()>=8){ //截取8位编码的字符串 String subString = " "; for(int j=0;j<8;j++){ subString = subString+str.charAt(j); } //读取每个字节,将01串转化成整型数 int cs = changeString(subString); dos.write(cs); //删除str的前八位 String tranString = str; str = ""; for(int j=8;j<tranString.length();j++){ str = str+tranString.charAt(j); } } } //文件末尾最后的字符串 System.out.println("mm"+str); for(int t=0;t<fileAddZero;t++){ str = str+'0'; } System.out.println(str); //写入文件 int cs = changeString(str); dos.write(cs); }
二,解压缩的过程(压缩的逆过程):
①读取文件头信息,按写入的顺序依次读出
public void readHead(String path) throws IOException{ fis = new FileInputStream(path); dis=new DataInputStream(fis); //读取字符种类总数 codeNum = dis.read(); System.out.println(codeNum); //实例化记录文件头信息的数组,数组长度为字符种类总数 head = new Head[codeNum]; System.out.println("AscII\t字节数\t补零数\t编码"); //以字符种类总数作为循环限制条件,读取每个字符的编码细则 for(int i=0;i<codeNum;i++){ //创建文件头信息对象 Head info = new Head(); //读取字符ASCII码,给对象设置ASCII码 info.setAscII(dis.read()); System.out.print(info.getAscII()+"\t"+(char)info.getAscII()+" "); //读取编码末尾补零数,并给对象设置 info.setZeroNum(dis.read()); //读取编码所占字节数,给对象设置 info.setByteNum(dis.read()); System.out.print(info.getByteNum()+"\t"); //读取当前编码的每个字节 for(int j=0;j<info.getByteNum();j++){ int code_int = dis.read(); //读取到的整数转换成String---0,1串,该01串不会以0开头 String code_string = Integer.toBinaryString(code_int); // System.out.println("s++"+code_string); int length = code_string.length(); //01串不足8位的在前面补零 if(length%8!=0){ for(int k=0;k<8-length;k++){ code_string = '0'+code_string; } } //给info对象设置编码,含补零,每个字节的前面补零的01串相加 info.setCode(info.getCode()+code_string); } //得到完整的补零后的01串,即文件头信息存储的编码 System.out.print(info.getZeroNum()+"\t"); //根据编码末尾补零个数,恢复编码不补零的编码,即码表中存储的编码, for(int t=0;t<info.getZeroNum();t++){ info.setCode(info.getCode().substring(0, info.getCode().length()-1)); } System.out.println("去0后"+info.getCode()); //将info对象添加到数组中 head[i] = info; } //读取头信息的最后一个内容:文章末尾的补零的个数 fileAddZero = dis.read(); System.out.println("文件末尾补零"+fileAddZero); }
②读取文件内容,再将这些字节写入一个新的文件,后缀名改成和原来文件一样,就能打开了。
public void readFile(String path,String newPath) throws IOException{ fos = new FileOutputStream(newPath); dos=new DataOutputStream(fos); //等待转换的字符串 String str = ""; //当文件可读信息大于零时 while(dis.available()>0){ //读取一个字节,赋值给整数txt int txt = dis.read(); //将该整数转换成01串,该字符串不会以0开头 String temp = Integer.toBinaryString(txt); System.out.println(temp+" nnnn"); //给转换成的01串,前面补零成完整的8位的字符串 int frontAddZero = temp.length()%8; if(frontAddZero!=0){ for(int i=0;i<8-frontAddZero;i++){ temp = '0'+temp; } } System.out.println(temp+">>>>>>>>>>>>"); //加到等待转换的字符串后,等待转换 str = str+temp; System.out.println(str+" !!!!等待转换!!!!"); for(int j=0;j<codeNum;j++){ //判断当前等待转换的字符串,是否以码表中的某个编码开头 if(str.startsWith((head[j].getCode()))){ //如果是,写入这个编码对应的字符 System.out.println(str+" ======== "+head[j].getCode()); System.out.println((char)head[j].getAscII()); dos.write(head[j].getAscII()); //将等待转换的字符串去掉已经写入的编码部分 String tran = str; str = ""; for(int k=head[j].getCode().length();k<tran.length();k++){ str = str+tran.charAt(k); } //设置循环从头开始判断现在的str是否以某编码开头 j = -1; //如果此时已经没有可读的文件信息了 if(dis.available()==0){ //将文件末尾添加的0的个数,在str中删去 String tra = str; str = ""; for(int t=0;t<tra.length()-fileAddZero;t++){ str = str+tra.charAt(t); } //如果删去之后字符串空了,那么跳出循环,文件读取完毕 if(str==""){ break; } //如果str不为空,那么继续j=-1的地方循环判断是否以某编码开头 } } }//for循环 }//while循环 //确认文件读取完毕 System.out.println(str.length()+" 最后str的长度"); }
还要用到其他的类。建立哈夫曼树要用到的哈夫曼的结点类。
public class HfmNode implements Comparable<HfmNode>{ //字符的ASCII码值 private int AscII; //字符的出现次数 private int count; //当前结点的左子结点 private HfmNode lChild; //当前结点的右子结点 private HfmNode rChild; /** * 构造方法 * @param AscII ASCII的值 * @param count 文件中的出现次数 */ public HfmNode(int AscII,int count){ this.AscII = AscII; this.setCounts(count); } /** * 得到结点字符ASCII值得方法 * @return ASCII码值 */ public int getAscII() { return AscII; } /** * 设置结点字符的ASCII值 * @param ascii */ public void setAscII(int AscII) { this.AscII = AscII; } /** * 得到当前结点字符出现次数的方法 * @return */ public int getCounts() { return count; } /** * 设置当前结点字符出现次数的方法 * @param count */ public void setCounts(int count) { this.count = count; } /** * 得到当前结点左孩子的方法 * @return 左子结点 */ public HfmNode getlChild() { return lChild; } /** * 设置当前结点左孩子的方法 * @param lChild */ public void setlChild(HfmNode lChild) { this.lChild = lChild; } /** * 得到当前结点右孩子的方法 * @return 右子结点 */ public HfmNode getrChild() { return rChild; } /** * 设置当前结点右孩子的方法 * @param rChild */ public void setrChild(HfmNode rChild) { this.rChild = rChild; } /** * 输出hfmNode类对象--哈夫曼结点的方法 */ public String toString(){ return "AscII="+(char)AscII+"counts="+count; } /** * 定义在队列中进行排序比较的属性 */ public int compareTo(HfmNode o) { return count-o.getCounts(); } }
要补零的个数,根据ASCII来判断是否是同一个字符
public class Head { //字符ASCII码 private int AscII; //字符编码占用字节数 private int byteNum; //编码末尾补零数 private int zeroNum; //编码 private String code = ""; /** * 得到ASCII码 * @return */ public int getAscII() { return AscII; } /** * 设置AscII码 * @param AscII */ public void setAscII(int AscII) { this.AscII = AscII; } /** * 得到编码占字节数 * @return */ public int getByteNum() { return byteNum; } /** * 设置编码占字节数 * @param byteNum */ public void setByteNum(int byteNum) { this.byteNum = byteNum; } /** * 得到编码 * @return */ public String getCode() { return code; } /** * 设置编码 * @param code */ public void setCode(String code) { this.code = code; } /** * 得到编码末尾补零个数 * @return */ public int getZeroNum() { return zeroNum; } /** * 设置编码末尾补零个数 * @param zeroNum */ public void setZeroNum(int zeroNum) { this.zeroNum = zeroNum; } }
哈夫曼编码类
public class Code { //哈夫曼编码 private String code = ""; /** * 输出Code类对象的方法 */ public String toString(){ return "编码:"+code+"长度:"+code.length(); } /** * 得到编码内容 * @return */ public String getCode() { return code; } /** * 设置编码内容 * @param code */ public void setCode(String code) { this.code = code; } }
期间还会用到一些方法,将8个字符的字符串转换成01串对应的整数
private int changeString(String s) { return ((int)s.charAt(0)-48)*128+((int)s.charAt(1)-48)*64 +((int)s.charAt(2)-48)*32+((int)s.charAt(3)-48)*16 +((int)s.charAt(4)-48)*8+((int)s.charAt(5)-48)*4 +((int)s.charAt(6)-48)*2+((int)s.charAt(7)-48); }
哈夫曼压缩还是有许多问题的,压缩小文件时,压缩好的文件可能比未压缩的还要大,压缩大文件时,又需要很长的时间。所以期待学会下一个压缩方法!
相关推荐
vc++哈夫曼压缩算法 vc++哈夫曼压缩算法
哈夫曼压缩与解压缩源码.zip哈夫曼压缩与解压缩源码.zip哈夫曼压缩与解压缩源码.zip哈夫曼压缩与解压缩源码.zip哈夫曼压缩与解压缩源码.zip哈夫曼压缩与解压缩源码.zip哈夫曼压缩与解压缩源码.zip哈夫曼压缩与解压缩...
哈夫曼压缩和解压和解压,数据结构课程设计,c++源码。
哈夫曼压缩与解压缩程序(JAVA)
哈夫曼算法实现图片的压缩,图片有前后对比。
通过自定义算法创建哈夫曼树和编码,对文件进行二进制操作实现压缩和解压。
C语言实现的huffman压缩解压缩算法
哈夫曼压缩与解压算法(可以直接运行),压缩成二进制文件,而且生成了txt文件可以查看哈夫曼编码。C++代码
哈夫曼实现文件的压缩与解压缩,代码关键部分有注释。
每次选出权值最小且没有双亲的两个节点建立新的哈弗曼树。 无栈非递归遍历Huffman树,求Huffman编码。...要注意的是当文件较小时,不宜使用哈夫曼来进行压缩,此时文件头占比过大,会使压缩结果很差。
c++ 哈夫曼压缩源代码. 多种文件格式 亲测可用
java实现的哈夫曼压缩算法,有swing界面。
利用哈夫曼编码对数据进行无损压缩,实现Huffman压缩的编码器和译码器。 1.首先读入待压缩源文件。 2.然后建立并分析字母表,对每种字符的出现频度进行统计,以频度作为建立Huffman树的权值。 3. 频度表建好后,就...
利用哈夫曼算法进行文件的压缩和解压缩。 利用命令行对指定的文件进行压缩和解压缩。 能对一般的文本文件有较好的压缩能力,对其它格式文件可以进行压缩但不一定能有压缩效果。对于用此程序压缩的文件可以用此程序...
压缩解压缩 源码 VC MFC实现 可供学习研究
这里采用哈夫曼编码方式来对每个字符重新编码,因为哈夫曼树具有最小带权路径长度的性质,能够生成用于压缩的二进制前缀码。程序使用的 “静态统计模型”,也就是说在编码前统计要编码的信息中所有字符的出现频率,...
哈夫曼压缩算法的c++实现,你可以学习到你想学的 这也是一个经典的算法设计题
这是一个典型的哈夫曼压缩程序,能压缩各种格式,适合初学者学习。
哈夫曼压缩算法,使用c#编写,先统计输入字串的权重,权重越大越靠近根节点