用哈弗曼編碼實現(xiàn)壓縮軟件
哈夫曼壓縮是個無損的壓縮算法，一般用來壓縮文本和程序文件。哈夫曼壓縮屬于可變代碼長度算法一族。意思是個體符號（例如，文本文件中的字符）用一個特定長度的位序列替代。因此，在文件中出現(xiàn)頻率高的符號，使用短的位序列，而那些很少出現(xiàn)的符號，則用較長的位序列。我們先來看基本概念。
1.什么是哈夫曼樹?
哈夫曼樹是一種***二叉樹，它的***點體現(xiàn)在它的的帶權(quán)路徑長度最小。(結(jié)點的帶權(quán)路徑長度為：結(jié)點的路徑長度乘以結(jié)點的權(quán)值，樹的帶權(quán)路徑長度為所有葉子結(jié)點帶權(quán)路徑長度之和)
2.什么是哈弗曼編碼?
從哈弗曼樹的根結(jié)點開始，按照左子樹分配代碼“0”，右子樹分配代碼“1”的規(guī)則，直到葉子結(jié)點為止，每個葉子結(jié)點的哈弗曼編碼就是從根結(jié)點開始，一直到該葉子結(jié)點為止，把途中經(jīng)過的代碼按順序串起來就OK了。
3.什么是哈弗曼壓縮?
Huffman( 哈夫曼 ) 算法在上世紀五十年代初提出來了，它是一種無損壓縮方法，在壓縮過程中不會丟失信息熵，而且可以證明 Huffman 算法在無損壓縮算法中是***的。 Huffman 原理簡單，實現(xiàn)起來也不困難，在現(xiàn)在的主流壓縮軟件得到了廣泛的應(yīng)用。對應(yīng)用程序、重要資料等絕對不允許信息丟失的壓縮場合， Huffman 算法是非常好的選擇。
哈夫曼壓縮，一般用來壓縮文本和程序文件。哈夫曼壓縮屬于可變代碼長度算法一族。意思是個體符號(例如，文本文件中的字符)用一個特定長度的位序列替代。因此，在文件中出現(xiàn)頻率高的符號，使用短的位序列，而那些很少出現(xiàn)的符號，則用較長的位序列。
有了以上的基本概念，我們就可以動手實現(xiàn)哈弗曼壓縮軟件了!
4.哈弗曼壓縮軟件的實現(xiàn)：
在文件中，所有的數(shù)據(jù)都是以字節(jié)的形式存在的，一個字節(jié)是8位，所以所有可能出現(xiàn)的字節(jié)在0——256之間(不包括256)，所以，***步要做的事情就是，把文件所有的字節(jié)的出現(xiàn)頻率統(tǒng)計出來，并用頻率做為權(quán)值生成一棵哈弗曼樹：
Java代碼：
- int[] ByteCount = new int[256];//字節(jié)頻率統(tǒng)計
- InputStream fis = new FileInputStream(pathName_former);
- InputStream bis = new BufferedInputStream(fis);//創(chuàng)建文件輸入流
- while(bis.available()>0){
- int tmp = bis.read();
- ByteCount[tmp]++;
- }//統(tǒng)計頻率
- //構(gòu)造哈弗曼樹
- hfmTree hfm = new hfmTree(ByteCount);
- Java代碼
- public hfmTree(int[] rank){//根據(jù)頻率構(gòu)造哈弗曼樹
- //把頻率不為零的字節(jié)加入節(jié)點優(yōu)先級隊列
- PriorityQueue nodes = new java.util.PriorityQueue();
- for(int i=0;i
- if(rank[i]!=0){
- nodes.add(new hfmNode(rank[i],i));
- }
- }
- //構(gòu)造哈弗曼樹
- 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();
- }//構(gòu)造函數(shù)(correct)
接下來，要做的就是獲得0——256之間每個字節(jié)所對應(yīng)的哈弗曼編碼，用一個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
- }
- 然后就是把每個字節(jié)的編碼長度打入文件：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());
- }
- }
接下來就是，將每個字節(jié)的編碼打入文件(這里需要吧8個長度的01串轉(zhuǎn)換成一個byte打入文件)：
- Java代碼//把每個字節(jié)的編碼表打到文件里
- int i = 0;//第i個字節(jié)
- int count = 0;//滿8打一，計數(shù)器
- 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));//寫入一個字節(jié)
- }else{
- count+=Code[i].length();
- allCode+=Code[i];
- inCode+=Code[i];
- i++;//嚴重錯誤發(fā)生地
- }
- }
- //如果不滿8位的
- if(allCode.length()>0){
- int len = 8-allCode.length();//補零
- for(int j=0;j
- allCode+="0";
- }
- inCode+=allCode;
- bos.write(changeString(allCode));
- }
***就是把文件中的所有字節(jié)按照這種哈弗曼的編碼方式保存到文件中，過程類似于上一步(在***打入末尾補入的0的個數(shù)，主要是為了方便解壓縮)：Java代碼//編碼表輸出完畢，將文件中的字節(jié)按照這種編碼方式壓縮。
- InputStream ins = new FileInputStream(pathName_former);
- InputStream buf = new BufferedInputStream(ins);//創(chuàng)建輸入流
- 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));//寫入一個字節(jié)
- }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
- }
到這里，整個壓縮過程基本完成了。希望對大家有幫助。
【編輯推薦】
