压缩软件（哈夫曼算法实现）.doc

压缩软件（哈夫曼算法实现） 项目总结 算法CC+C#DOS一、在讲具体代码实现之前，先给大家普及一下压缩软件的相关知识 引用压缩软件是利用算法将文件有损或无损地处理，以达到保留最多文件信息，而令文件体积变小的应用软件。压缩软件一般同时具有解压缩的功能。压缩软件的的基本原理是查找文件内的重复字节,并建立一个相同字节的词典文件,并用一个代码表示,比如在文件里有几处有一个相同的词中华人民共和国用一个代码表示并写入词典文件,这样就可以达到缩小文件的目的。常见的压缩软件有WinRAR ,好压(Haozip),WinZip,7-Zip,WinMount,Peazip等等。 哈夫曼树作为数据结构二叉树章节中最为华彩的一部分，有着其独特的魅力。给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，这样的二叉树便是哈夫曼树，也称为最优二叉树。 二、哈夫曼算法 引用 Huffman算法是一种基于统计的压缩方法。它的本质就是对文本文件中的字符进行重新编码，对于使用频率越高的字符，其编码也越短。但是任何2个字符的编码， 是不能出现向前包含的。也就是说字符A(假设为00)的编码的前段，不可能为字符B（则B的编码不可能为001，因为这里B的编码中包含了A的前段00，这会给解码难带来不必要的困难，所以这是不允许的）的编码。经过编码后的文本文件，主要包含2个部分：Huffman码表部分和压缩内容部分。解压缩的时候，先把Huffman码表取出来，然后对压缩内容部分各个字符进行逐一解码,形成源文件。 哈夫曼编码生成步骤： 扫描要压缩的文件，对字符出现的频率进行计算。 把字符按出现的频率进行排序，组成一个队列。 把出现频率最低（权值）的两个字符作为叶子节点，它们的权值之和为根节点组成一棵树。 把上面叶子节点的两个字符从队列中移除，并把它们组成的根节点加入到队列。 把队列重新进行排序。重复步骤直到队列中只有一个节点为止。 把这棵树上的根节点定义为0（可自行定义0或1）左边为0，右边为1。这样就可以得到每个叶子节点的哈夫曼编码了。 三、编码流程（大体思路） 压缩： 1、将要压缩的文件一个一个字节的读出来即扫描要压缩的文件，并统计每个字节的权值即出现的频率。 2、以每个字节的权值来构造哈夫曼树，并给每个字节进行哈夫曼编码。 3、将每个字节和其对应得哈夫曼编码存放进一个Map中，即码表。 4、以这个码表为依照，将文件中的所有字节一一进行编码（生成10字符串），最后在把所有字节的编码依次末尾相加合成一个10字符串。 5、将这个10字符串重新组合，8个为一组，若最后一组不足8个则补0，并记录补0的个数，将每一组的10字符串转化为一个字节， 并将所有的10字符串合成一个字节数组，数组的最后一个元素存放补0的个数。 6、创建一个压缩文件，先将码表的大小写入文件，再将码表写入文件（码表里还有每个字节的哈夫曼编码长度的信息）。 7、最后将之前生成的字节数组写入文件（文件的主要信息）。 解压缩： 1、将压缩的文件同样一个一个字节的读出来。 2、先读出码表的大小，再通过码表的大小读出码表，并将码表的信息存放进一个Map。 3、再接着读出后面的所有字节，并转化成一个10字符串。 4、通过与码表的匹配，从10字符串的第一个字符开始读，若读到的子字符串与码表的某个字节的的编码相同，解压出相应的字节，把该字节保存起来。 并把上面的子字符串从编码中删除，重复上一步骤，直到该项编码解析完成，最后将此10字符串还原成原来的文件的一个个字节。 5、再将这些字节写入一个新的文件，后缀名改成和原来文件一样，就能打开了。 四、核心代码 1、压缩文件 Java代码 1. /* 2. *压缩的文件操作 3. * 4. *authorking 5. * 6. */7. publicclassCompressFileOption 8. 9. /* 10. *读取文件 11. * 12. *parampath 13. *:文件路径 14. *return:将文件的内容以字节数组的样式返回 15. */16. publicstaticbytereadFile(Stringpath) 17. bytedataByte=null; 18. try 19. java.io.FileInputStreamfis=newjava.io.FileInputStream(path); 20. intsize=fis.available();/可读的字节数 21. dataByte=newbytesize; 22. fis.read(dataByte); 23. 24. catch(Exceptione) 25. /TODOAuto-generatedcatchblock 26. e.printStackTrace(); 27. 28. returndataByte; 29. 30. 31. /* 32. *将码表的相关信息写入文件 33. * 34. *paramfileSize 35. *:原文件大小 36. *parammap 37. *:存放码表的map 38. *paramlistCh 39. *:存放关键码的字符队列 40. *parampath 41. *:文件路径 42. *throwsException 43. */44. publicstaticvoidwriteMap(intfileSize, 45. java.util.HashMapmap,ListlistBy,Stringpath) 46. throwsException 47. 48. java.io.FileOutputStreamfos=newjava.io.FileOutputStream(path); 49. java.io.DataOutputStreamdos=newjava.io.DataOutputStream(fos); 50. 51. dos.writeInt(fileSize);/将原文件大小写入文件 52. intmapSize=map.size();/码表的大小 53. dos.writeInt(mapSize);/将码表的大小写入文件 54. for(inti=0;imapSize;i+) 55. fos.write(listBy.get(i);/将每个字节写入文件 56. Stringhfmcode_next=map.get(listBy.get(i);/得到每个字节对应的哈夫曼编码 57. bytecodeSize=(byte)hfmcode_next.length();/每个字节对应的哈夫曼编码大小 58. fos.write(codeSize);/将每个字节对应的哈夫曼编码大小写入文件 59. dos.writeChars(hfmcode_next);/将每个字符对应的哈夫曼编码写入文件 60. 61. dos.flush(); 62. fos.close(); 63. 64. 65. /* 66. *将压缩好的字节数组写入文件 67. * 68. *paramb 69. *:压缩好的字节数组 70. *parampath 71. *:文件路径 72. */73. publicstaticvoidwriteFile(byteb,Stringpath) 74. 75. try 76. java.io.FileOutputStreamfos=newjava.io.FileOutputStream(path, 77. true); 78. java.io.DataOutputStreamdos=newjava.io.DataOutputStream(fos); 79. /写入字节数组的大小 80. dos.writeInt(b.length); 81. fos.write(b); 82. fos.flush(); 83. fos.close(); 84. catch(Exceptione) 85. /TODOAuto-generatedcatchblock 86. e.printStackTrace(); 87. 88. 89. 90. /* 91. *将10字符串转化为一个字节 92. * 93. *paramstr 94. *:传入的字符串 95. *return:一个字节 96. */97. privatebyteCharArrayToByte(Stringstr) 98. charc=str.toCharArray();/将字符串str转化为字符数组c 99. intlen=c.length; 100. byteb=newbytelen; 101. bytevalue=0; 102. bytevalue_next; 103. for(inti=0;ilen;i+) 104. bi=Byte.parseByte(ci+); 105. /System.out.println(bi); 106. 107. for(inti=0;ilen;i+) 108. value_next=(byte)(bi*Math.pow(2,len-i-1);/幂计算 109. value=(byte)(value+value_next); 110. 111. returnvalue; 112. 113. 114. /* 115. *将10字符串以8个为一组转化为一个字节数组 116. * 117. *paramstr 118. *return 119. */120. privatebyteStringToByteArray(Stringstr) 121. charc=str.toCharArray();/将字节串str转化为字符数组c 122. intlen=c.length;/字符串字符的个数 123. intlenByte; 124. Strings=; 125. charc_next; 126. byteb; 127. if(len%8=0)/如果字符串的长度能被8整除 128. lenByte=len/8+1; 129. b=newbytelenByte; 130. for(inti=0;ilenByte-1;i+) 131. for(intj=i*8;j(i+1)*8;j+) 132. c_next=cj; 133. s=s+c_next; 134. 135. System.out.println(第+i+个字符串：+s); 136. bi=CharArrayToByte(s); 137. s=; 138. System.out.println(第+i+个字符串转化为字节后的值：+bi); 139. 140. blenByte-1=0;/字节数组的最后一个存放补0的个数 141. else/如果字符串的长度不能被8整除 142. 143. lenByte=len/8+2; 144. b=newbytelenByte; 145. intremainder=len%8;/求出除8的余数 146. intzeroNum=8-remainder;/补0的个数 147. System.out.println(补0数：+zeroNum); 148. System.out.println(原字符串：+str); 149. for(inti=0;izeroNum;i+) 150. str=str+0;/在字符串后面补0 151. 152. System.out.println(补0后的字符串：+str); 153. c=str.toCharArray(); 154. System.out.println(补0后的字符串的字符个数：+c.length); 155. for(inti=0;ilenByte-1;i+) 156. for(intj=i*8;j(i+1)*8;j+) 157. c_next=cj; 158. s=s+c_next; 159. 160. System.out.println(第+i+个字符串：+s); 161. bi=CharArrayToByte(s); 162. s=; 163. System.out.println(第+i+个字符串转化为字节后的值：+bi); 164. 165. blenByte-1=(byte)zeroNum;/字节数组的最后一个存放补0的个数 166. 167. returnb; 168. 169. 170. /* 171. *压缩文件 172. * 173. *parampath1 174. *:原文件路径 175. *parampath2 176. *:压缩后的文件路径 177. *throwsException 178. */179. publicvoidCompressFile(Stringpath1,Stringpath2)throwsException 180. /从文件中得到字节数组 181. byteb=CompressFileOption.readFile(path1); 182. intb_size=b.length;/原文件大小 183. byteb_compress;/字节数组，存放压缩的字符串 184. 185. Stringhfmcode=;/文件内所有字节的哈夫曼编码 186. Stringhfmcode_next;/文件中每个字节的哈夫曼编码 187. /计算字符串中每个字节的权值，并返回一个存放字节和它对应权值的节点队列 188. Listlist=calWeight.calweight(b); 189. intsize=list.size(); 190. Huffmanhfm=newHuffman(); 191. /构建哈夫曼树并返回根节点 192. TreeNoderoot=hfm.createHuffman(list); 193. /创建哈夫曼编码使其与字符一一对应 194. hfm.createHfmCode(root,); 195. 196. java.util.HashMapmap=hfm.getMap();/得到码表 197. ListlistBy=hfm.getList();/得到存放关键码队列 198. 199. System.out.println(mapsize-:+map.size(); 200. System.out.println(b-:+b.length); 201. for(inti=0;ib_size;i+) 202. /得到每个字节的哈夫曼编码 203. hfmcode_next=map.get(bi); 204. System.out.println(第+i+个：+bi+的编码：+hfmcode_next); 205. hfmcode=hfmcode+hfmcode_next;/将每个字节的哈夫曼编码依次相加为一个01字符串 206. 207. System.out.println(01串大小：+hfmcode.length(); 208. System.out.println(01串：+hfmcode); 209. charch=hfmcode.toCharArray(); 210. System.out.println(01串的大小：+ch.length); 211. 212. b_compress=StringToByteArray(hfmcode);/得到字节数组 213. for(inti=0;ib_compress.length;i+) 214. System.out.println(第+i+个字节+b_compressi); 215. 216. /将文件大小和码表相关信息写入文件 217. writeMap(b_size,map,listBy,path2); 218. /将字节数组写入文件 219. writeFile(b_compress,path2); 220. /* * 压缩的文件操作 * * author king * */public class CompressFileOption /* * 读取文件 * * param path * :文件路径 * return:将文件的内容以字节数组的样式返回 */public static byte readFile(String path) byte dataByte = null;try java.io.FileInputStream fis = new java.io.FileInputStream(path);int size = fis.available();/ 可读的字节数dataByte = new bytesize;fis.read(dataByte); catch (Exception e) / TODO Auto-generated catch blocke.printStackTrace();return dataByte;/* * 将码表的相关信息写入文件 * * param fileSize * :原文件大小 * param map * :存放码表的map * param listCh * :存放关键码的字符队列 * param path * :文件路径 * throws Exception */public static void writeMap(int fileSize,java.util.HashMap map, List listBy, String path)throws Exception java.io.FileOutputStream fos = new java.io.FileOutputStream(path);java.io.DataOutputStream dos = new java.io.DataOutputStream(fos);dos.writeInt(fileSize);/ 将原文件大小写入文件int mapSize = map.size();/ 码表的大小dos.writeInt(mapSize);/ /将码表的大小写入文件for (int i = 0; i mapSize; i+) fos.write(listBy.get(i);/ 将每个字节写入文件String hfmcode_next = map.get(listBy.get(i);/ 得到每个字节对应的哈夫曼编码byte codeSize = (byte) hfmcode_next.length();/ 每个字节对应的哈夫曼编码大小fos.write(codeSize);/ 将每个字节对应的哈夫曼编码大小写入文件dos.writeChars(hfmcode_next);/ 将每个字符对应的哈夫曼编码写入文件dos.flush();fos.close();/* * 将压缩好的字节数组写入文件 * * param b * :压缩好的字节数组 * param path * :文件路径 */public static void writeFile(byte b, String path) try java.io.FileOutputStream fos = new java.io.FileOutputStream(path,true);java.io.DataOutputStream dos = new java.io.DataOutputStream(fos);/ 写入字节数组的大小dos.writeInt(b.length);fos.write(b);fos.flush();fos.close(); catch (Exception e) / TODO Auto-generated catch blocke.printStackTrace();/* * 将10字符串转化为一个字节 * * param str * :传入的字符串 * return:一个字节 */private byte CharArrayToByte(String str) char c = str.toCharArray();/ 将字符串str转化为字符数组cint len = c.length;byte b = new bytelen;byte value = 0;byte value_next;for (int i = 0; i len; i+) bi = Byte.parseByte(ci + );/ System.out.println(bi);for (int i = 0; i len; i+) value_next = (byte) (bi * Math.pow(2, len - i - 1);/ 幂计算value = (byte) (value + value_next);return value;/* * 将10字符串以8个为一组转化为一个字节数组 * * param str * return */private byte StringToByteArray(String str) char c = str.toCharArray();/ 将字节串str转化为字符数组cint len = c.length;/ 字符串字符的个数int lenByte;String s = ;char c_next;byte b;if (len % 8 = 0) / 如果字符串的长度能被8整除lenByte = len / 8 + 1;b = new bytelenByte;for (int i = 0; i lenByte - 1; i+) for (int j = i * 8; j (i + 1) * 8; j+) c_next = cj;s = s + c_next;System.out.println(第 + i + 个字符串： + s);bi = CharArrayToByte(s);s = ;System.out.println(第 + i + 个字符串转化为字节后的值： + bi);blenByte - 1 = 0;/ 字节数组的最后一个存放补0的个数 else / 如果字符串的长度不能被8整除lenByte = len / 8 + 2;b = new bytelenByte;int remainder = len % 8;/ 求出除8的余数int zeroNum = 8 - remainder;/ 补0的个数System.out.println(补0数： + zeroNum);System.out.println(原字符串： + str);for (int i = 0; i zeroNum; i+) str = str + 0;/ 在字符串后面补0System.out.println(补0后的字符串： + str);c = str.toCharArray();System.out.println(补0后的字符串的字符个数： + c.length);for (int i = 0; i lenByte - 1; i+) for (int j = i * 8; j (i + 1) * 8; j+) c_next = cj;s = s + c_next;System.out.println(第 + i + 个字符串： + s);bi = CharArrayToByte(s);s = ;System.out.println(第 + i + 个字符串转化为字节后的值： + bi);blenByte - 1 = (byte) zeroNum;/ 字节数组的最后一个存放补0的个数return b;/* * 压缩文件 * * param path1 * :原文件路径 * param path2 * :压缩后的文件路径 * throws Exception */public void CompressFile(String path1, String path2) throws Exception / 从文件中得到字节数组byte b = CompressFileOption.readFile(path1);int b_size = b.length;/ 原文件大小byte b_compress;/ 字节数组，存放压缩的字符串String hfmcode = ;/ 文件内所有字节的哈夫曼编码String hfmcode_next;/ 文件中每个字节的哈夫曼编码/ 计算字符串中每个字节的权值，并返回一个存放字节和它对应权值的节点队列List list = calWeight.calweight(b);int size = list.size();Huffman hfm = new Huffman();/ 构建哈夫曼树并返回根节点TreeNode root = hfm.createHuffman(list);/ 创建哈夫曼编码使其与字符一一对应hfm.createHfmCode(root, );java.util.HashMap map = hfm.getMap();/ 得到码表List listBy = hfm.getList();/ 得到存放关键码队列System.out.println(mapsize-: + map.size();System.out.println(b-: + b.length);for (int i = 0; i b_size; i+) / 得到每个字节的哈夫曼编码hfmcode_next = map.get(bi);System.out.println(第+i+个： + bi + 的编码： + hfmcode_next);hfmcode = hfmcode + hfmcode_next;/ 将每个字节的哈夫曼编码依次相加为一个01字符串System.out.println(01串大小： + hfmcode.length();System.out.println(01串： + hfmcode);char ch = hfmcode.toCharArray();System.out.println(01串的大小： + ch.length);b_compress = StringToByteArray(hfmcode);/ 得到字节数组for (int i = 0; i b_compress.length; i+) System.out.println(第 + i + 个字节 + b_compressi);/ 将文件大小和码表相关信息写入文件writeMap(b_size, map, listBy, path2);/ 将字节数组写入文件writeFile(b_compress, path2);2、解压缩文件 Java代码 1. /* 2. *解压缩的文件操作 3. * 4. *authorking 5. * 6. */7. publicclassUncompressFileOption 8. 9. publicstaticlongfileSize; 10. 11. /* 12. *将8位10字符串前面缺0的补上0 13. * 14. *paramstr 15. *return 16. */17. privateStringaddZero(Stringstr) 18. intstrLen=str.length(); 19. intzeroNum; 20. if(strLen8)/若字符串长度小于8则补0 21. zeroNum=8-strLen; 22. for(inti=0;izeroNum;i+) 23. str=0+str; 24. 25. 26. returnstr; 27. 28. 29. /* 30. *将整型数组还原成之前的10串，即文件内容的哈夫曼编码 31. * 32. *paramn 33. *return 34. */35. privateStringInttoBinaryString(intn) 36. intlen=n.length; 37. Strings=newStringlen;/一个字符串数组存放二进制数据 38. StringBinaryStr=; 39. for(inti=0;ilen-1;i+) 40. si=Integer.toBinaryString(ni); 41. si=addZero(si); 42. BinaryStr=BinaryStr+si; 43. 44. System.out.println(二进制形式表示:+BinaryStr); 45. intBinaryStrLen=BinaryStr.length();/得到为减0前的字符串大小 46. intzeroSub=nlen-1;/之前在末尾补0的个数，现在减去 47. System.out.println(减0前的字符串大小:+BinaryStrLen); 48. System.out.println(需要在字符串末尾减0的个数表示:+zeroSub); 49.