壓縮軟件（哈夫曼算法實現(xiàn)）.doc

壓縮軟件（哈夫曼算法實現(xiàn)） 項目總結(jié) 算法CC+C#DOS一、在講具體代碼實現(xiàn)之前，先給大家普及一下壓縮軟件的相關(guān)知識 引用壓縮軟件是利用算法將文件有損或無損地處理，以達到保留最多文件信息，而令文件體積變小的應(yīng)用軟件。壓縮軟件一般同時具有解壓縮的功能。壓縮軟件的的基本原理是查找文件內(nèi)的重復(fù)字節(jié),并建立一個相同字節(jié)的詞典文件,并用一個代碼表示,比如在文件里有幾處有一個相同的詞中華人民共和國用一個代碼表示并寫入詞典文件,這樣就可以達到縮小文件的目的。常見的壓縮軟件有WinRAR ,好壓(Haozip),WinZip,7-Zip,WinMount,Peazip等等。 哈夫曼樹作為數(shù)據(jù)結(jié)構(gòu)二叉樹章節(jié)中最為華彩的一部分，有著其獨特的魅力。給定n個權(quán)值作為n個葉子結(jié)點，構(gòu)造一棵二叉樹，若帶權(quán)路徑長度達到最小，這樣的二叉樹便是哈夫曼樹，也稱為最優(yōu)二叉樹。 二、哈夫曼算法 引用 Huffman算法是一種基于統(tǒng)計的壓縮方法。它的本質(zhì)就是對文本文件中的字符進行重新編碼，對于使用頻率越高的字符，其編碼也越短。但是任何2個字符的編碼， 是不能出現(xiàn)向前包含的。也就是說字符A(假設(shè)為00)的編碼的前段，不可能為字符B（則B的編碼不可能為001，因為這里B的編碼中包含了A的前段00，這會給解碼難帶來不必要的困難，所以這是不允許的）的編碼。經(jīng)過編碼后的文本文件，主要包含2個部分：Huffman碼表部分和壓縮內(nèi)容部分。解壓縮的時候，先把Huffman碼表取出來，然后對壓縮內(nèi)容部分各個字符進行逐一解碼,形成源文件。 哈夫曼編碼生成步驟： 掃描要壓縮的文件，對字符出現(xiàn)的頻率進行計算。 把字符按出現(xiàn)的頻率進行排序，組成一個隊列。 把出現(xiàn)頻率最低（權(quán)值）的兩個字符作為葉子節(jié)點，它們的權(quán)值之和為根節(jié)點組成一棵樹。 把上面葉子節(jié)點的兩個字符從隊列中移除，并把它們組成的根節(jié)點加入到隊列。 把隊列重新進行排序。重復(fù)步驟直到隊列中只有一個節(jié)點為止。 把這棵樹上的根節(jié)點定義為0（可自行定義0或1）左邊為0，右邊為1。這樣就可以得到每個葉子節(jié)點的哈夫曼編碼了。 三、編碼流程（大體思路） 壓縮： 1、將要壓縮的文件一個一個字節(jié)的讀出來即掃描要壓縮的文件，并統(tǒng)計每個字節(jié)的權(quán)值即出現(xiàn)的頻率。 2、以每個字節(jié)的權(quán)值來構(gòu)造哈夫曼樹，并給每個字節(jié)進行哈夫曼編碼。 3、將每個字節(jié)和其對應(yīng)得哈夫曼編碼存放進一個Map中，即碼表。 4、以這個碼表為依照，將文件中的所有字節(jié)一一進行編碼（生成10字符串），最后在把所有字節(jié)的編碼依次末尾相加合成一個10字符串。 5、將這個10字符串重新組合，8個為一組，若最后一組不足8個則補0，并記錄補0的個數(shù)，將每一組的10字符串轉(zhuǎn)化為一個字節(jié)， 并將所有的10字符串合成一個字節(jié)數(shù)組，數(shù)組的最后一個元素存放補0的個數(shù)。 6、創(chuàng)建一個壓縮文件，先將碼表的大小寫入文件，再將碼表寫入文件（碼表里還有每個字節(jié)的哈夫曼編碼長度的信息）。 7、最后將之前生成的字節(jié)數(shù)組寫入文件（文件的主要信息）。 解壓縮： 1、將壓縮的文件同樣一個一個字節(jié)的讀出來。 2、先讀出碼表的大小，再通過碼表的大小讀出碼表，并將碼表的信息存放進一個Map。 3、再接著讀出后面的所有字節(jié)，并轉(zhuǎn)化成一個10字符串。 4、通過與碼表的匹配，從10字符串的第一個字符開始讀，若讀到的子字符串與碼表的某個字節(jié)的的編碼相同，解壓出相應(yīng)的字節(jié)，把該字節(jié)保存起來。 并把上面的子字符串從編碼中刪除，重復(fù)上一步驟，直到該項編碼解析完成，最后將此10字符串還原成原來的文件的一個個字節(jié)。 5、再將這些字節(jié)寫入一個新的文件，后綴名改成和原來文件一樣，就能打開了。 四、核心代碼 1、壓縮文件 Java代碼 1. /* 2. *壓縮的文件操作 3. * 4. *authorking 5. * 6. */7. publicclassCompressFileOption 8. 9. /* 10. *讀取文件 11. * 12. *parampath 13. *:文件路徑 14. *return:將文件的內(nèi)容以字節(jié)數(shù)組的樣式返回 15. */16. publicstaticbytereadFile(Stringpath) 17. bytedataByte=null; 18. try 19. java.io.FileInputStreamfis=newjava.io.FileInputStream(path); 20. intsize=fis.available();/可讀的字節(jié)數(shù) 21. dataByte=newbytesize; 22. fis.read(dataByte); 23. 24. catch(Exceptione) 25. /TODOAuto-generatedcatchblock 26. e.printStackTrace(); 27. 28. returndataByte; 29. 30. 31. /* 32. *將碼表的相關(guān)信息寫入文件 33. * 34. *paramfileSize 35. *:原文件大小 36. *parammap 37. *:存放碼表的map 38. *paramlistCh 39. *:存放關(guān)鍵碼的字符隊列 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);/將每個字節(jié)寫入文件 56. Stringhfmcode_next=map.get(listBy.get(i);/得到每個字節(jié)對應(yīng)的哈夫曼編碼 57. bytecodeSize=(byte)hfmcode_next.length();/每個字節(jié)對應(yīng)的哈夫曼編碼大小 58. fos.write(codeSize);/將每個字節(jié)對應(yīng)的哈夫曼編碼大小寫入文件 59. dos.writeChars(hfmcode_next);/將每個字符對應(yīng)的哈夫曼編碼寫入文件 60. 61. dos.flush(); 62. fos.close(); 63. 64. 65. /* 66. *將壓縮好的字節(jié)數(shù)組寫入文件 67. * 68. *paramb 69. *:壓縮好的字節(jié)數(shù)組 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. /寫入字節(jié)數(shù)組的大小 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字符串轉(zhuǎn)化為一個字節(jié) 92. * 93. *paramstr 94. *:傳入的字符串 95. *return:一個字節(jié) 96. */97. privatebyteCharArrayToByte(Stringstr) 98. charc=str.toCharArray();/將字符串str轉(zhuǎn)化為字符數(shù)組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個為一組轉(zhuǎn)化為一個字節(jié)數(shù)組 116. * 117. *paramstr 118. *return 119. */120. privatebyteStringToByteArray(Stringstr) 121. charc=str.toCharArray();/將字節(jié)串str轉(zhuǎn)化為字符數(shù)組c 122. intlen=c.length;/字符串字符的個數(shù) 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+個字符串轉(zhuǎn)化為字節(jié)后的值：+bi); 139. 140. blenByte-1=0;/字節(jié)數(shù)組的最后一個存放補0的個數(shù) 141. else/如果字符串的長度不能被8整除 142. 143. lenByte=len/8+2; 144. b=newbytelenByte; 145. intremainder=len%8;/求出除8的余數(shù) 146. intzeroNum=8-remainder;/補0的個數(shù) 147. System.out.println(補0數(shù)：+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后的字符串的字符個數(shù)：+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+個字符串轉(zhuǎn)化為字節(jié)后的值：+bi); 164. 165. blenByte-1=(byte)zeroNum;/字節(jié)數(shù)組的最后一個存放補0的個數(shù) 166. 167. returnb; 168. 169. 170. /* 171. *壓縮文件 172. * 173. *parampath1 174. *:原文件路徑 175. *parampath2 176. *:壓縮后的文件路徑 177. *throwsException 178. */179. publicvoidCompressFile(Stringpath1,Stringpath2)throwsException 180. /從文件中得到字節(jié)數(shù)組 181. byteb=CompressFileOption.readFile(path1); 182. intb_size=b.length;/原文件大小 183. byteb_compress;/字節(jié)數(shù)組，存放壓縮的字符串 184. 185. Stringhfmcode=;/文件內(nèi)所有字節(jié)的哈夫曼編碼 186. Stringhfmcode_next;/文件中每個字節(jié)的哈夫曼編碼 187. /計算字符串中每個字節(jié)的權(quán)值，并返回一個存放字節(jié)和它對應(yīng)權(quán)值的節(jié)點隊列 188. Listlist=calWeight.calweight(b); 189. intsize=list.size(); 190. Huffmanhfm=newHuffman(); 191. /構(gòu)建哈夫曼樹并返回根節(jié)點 192. TreeNoderoot=hfm.createHuffman(list); 193. /創(chuàng)建哈夫曼編碼使其與字符一一對應(yīng) 194. hfm.createHfmCode(root,); 195. 196. java.util.HashMapmap=hfm.getMap();/得到碼表 197. ListlistBy=hfm.getList();/得到存放關(guān)鍵碼隊列 198. 199. System.out.println(mapsize-:+map.size(); 200. System.out.println(b-:+b.length); 201. for(inti=0;ib_size;i+) 202. /得到每個字節(jié)的哈夫曼編碼 203. hfmcode_next=map.get(bi); 204. System.out.println(第+i+個：+bi+的編碼：+hfmcode_next); 205. hfmcode=hfmcode+hfmcode_next;/將每個字節(jié)的哈夫曼編碼依次相加為一個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);/得到字節(jié)數(shù)組 213. for(inti=0;ib_compress.length;i+) 214. System.out.println(第+i+個字節(jié)+b_compressi); 215. 216. /將文件大小和碼表相關(guān)信息寫入文件 217. writeMap(b_size,map,listBy,path2); 218. /將字節(jié)數(shù)組寫入文件 219. writeFile(b_compress,path2); 220. /* * 壓縮的文件操作 * * author king * */public class CompressFileOption /* * 讀取文件 * * param path * :文件路徑 * return:將文件的內(nèi)容以字節(jié)數(shù)組的樣式返回 */public static byte readFile(String path) byte dataByte = null;try java.io.FileInputStream fis = new java.io.FileInputStream(path);int size = fis.available();/ 可讀的字節(jié)數(shù)dataByte = new bytesize;fis.read(dataByte); catch (Exception e) / TODO Auto-generated catch blocke.printStackTrace();return dataByte;/* * 將碼表的相關(guān)信息寫入文件 * * param fileSize * :原文件大小 * param map * :存放碼表的map * param listCh * :存放關(guān)鍵碼的字符隊列 * 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);/ 將每個字節(jié)寫入文件String hfmcode_next = map.get(listBy.get(i);/ 得到每個字節(jié)對應(yīng)的哈夫曼編碼byte codeSize = (byte) hfmcode_next.length();/ 每個字節(jié)對應(yīng)的哈夫曼編碼大小fos.write(codeSize);/ 將每個字節(jié)對應(yīng)的哈夫曼編碼大小寫入文件dos.writeChars(hfmcode_next);/ 將每個字符對應(yīng)的哈夫曼編碼寫入文件dos.flush();fos.close();/* * 將壓縮好的字節(jié)數(shù)組寫入文件 * * param b * :壓縮好的字節(jié)數(shù)組 * 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);/ 寫入字節(jié)數(shù)組的大小dos.writeInt(b.length);fos.write(b);fos.flush();fos.close(); catch (Exception e) / TODO Auto-generated catch blocke.printStackTrace();/* * 將10字符串轉(zhuǎn)化為一個字節(jié) * * param str * :傳入的字符串 * return:一個字節(jié) */private byte CharArrayToByte(String str) char c = str.toCharArray();/ 將字符串str轉(zhuǎn)化為字符數(shù)組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個為一組轉(zhuǎn)化為一個字節(jié)數(shù)組 * * param str * return */private byte StringToByteArray(String str) char c = str.toCharArray();/ 將字節(jié)串str轉(zhuǎn)化為字符數(shù)組cint len = c.length;/ 字符串字符的個數(shù)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 + 個字符串轉(zhuǎn)化為字節(jié)后的值： + bi);blenByte - 1 = 0;/ 字節(jié)數(shù)組的最后一個存放補0的個數(shù) else / 如果字符串的長度不能被8整除lenByte = len / 8 + 2;b = new bytelenByte;int remainder = len % 8;/ 求出除8的余數(shù)int zeroNum = 8 - remainder;/ 補0的個數(shù)System.out.println(補0數(shù)： + 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后的字符串的字符個數(shù)： + 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 + 個字符串轉(zhuǎn)化為字節(jié)后的值： + bi);blenByte - 1 = (byte) zeroNum;/ 字節(jié)數(shù)組的最后一個存放補0的個數(shù)return b;/* * 壓縮文件 * * param path1 * :原文件路徑 * param path2 * :壓縮后的文件路徑 * throws Exception */public void CompressFile(String path1, String path2) throws Exception / 從文件中得到字節(jié)數(shù)組byte b = CompressFileOption.readFile(path1);int b_size = b.length;/ 原文件大小byte b_compress;/ 字節(jié)數(shù)組，存放壓縮的字符串String hfmcode = ;/ 文件內(nèi)所有字節(jié)的哈夫曼編碼String hfmcode_next;/ 文件中每個字節(jié)的哈夫曼編碼/ 計算字符串中每個字節(jié)的權(quán)值，并返回一個存放字節(jié)和它對應(yīng)權(quán)值的節(jié)點隊列List list = calWeight.calweight(b);int size = list.size();Huffman hfm = new Huffman();/ 構(gòu)建哈夫曼樹并返回根節(jié)點TreeNode root = hfm.createHuffman(list);/ 創(chuàng)建哈夫曼編碼使其與字符一一對應(yīng)hfm.createHfmCode(root, );java.util.HashMap map = hfm.getMap();/ 得到碼表List listBy = hfm.getList();/ 得到存放關(guān)鍵碼隊列System.out.println(mapsize-: + map.size();System.out.println(b-: + b.length);for (int i = 0; i b_size; i+) / 得到每個字節(jié)的哈夫曼編碼hfmcode_next = map.get(bi);System.out.println(第+i+個： + bi + 的編碼： + hfmcode_next);hfmcode = hfmcode + hfmcode_next;/ 將每個字節(jié)的哈夫曼編碼依次相加為一個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);/ 得到字節(jié)數(shù)組for (int i = 0; i b_compress.length; i+) System.out.println(第 + i + 個字節(jié) + b_compressi);/ 將文件大小和碼表相關(guān)信息寫入文件writeMap(b_size, map, listBy, path2);/ 將字節(jié)數(shù)組寫入文件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. *將整型數(shù)組還原成之前的10串，即文件內(nèi)容的哈夫曼編碼 31. * 32. *paramn 33. *return 34. */35. privateStringInttoBinaryString(intn) 36. intlen=n.length; 37. Strings=newStringlen;/一個字符串?dāng)?shù)組存放二進制數(shù)據(jù) 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的個數(shù)，現(xiàn)在減去 47. System.out.println(減0前的字符串大小:+BinaryStrLen); 48. System.out.println(需要在字符串末尾減0的個數(shù)表示:+zeroSub); 49.