• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            

    
            

            




            







												


        

            
	

            
	
            
		
            
			
				
            逛奔的蝸牛
            
				
             我不聰明，但我會很努力
            
			            		
		
            
	
            

            

            
	
            
		
            
			
 
 ::
 ::
新隨筆 ::
 ::

 ::
管理 ::


			
			
				
			
		
            
	
            

            


            


            
	
					

            
	
	
	
            
		
            說到文件壓縮大家很容易想到的就是 rar,zip 等我們常見的壓縮格式。然而，還有一種就是大家在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)最常見到的哈夫曼樹的數(shù)據(jù)結(jié)構(gòu)，以前還不知道他又什么用，其實他最大的用途就是用來做壓縮，也是一些 rar,zip 壓縮的祖先，稱為哈弗曼壓縮（什么你不知道誰是哈弗曼，也不知道哈弗曼壓縮，不急等下介紹）。
               隨著網(wǎng)絡(luò)與多媒體技術(shù)的興起，人們需要存儲和傳輸?shù)臄?shù)據(jù)越來越多，數(shù)據(jù)量越來越大，以前帶寬有限的傳輸網(wǎng)絡(luò)和容量有限的存儲介質(zhì)難以滿足用戶的需求。
            特別是聲音、圖像和視頻等媒體在人們的日常生活和工作中的地位日益突出，這個問題越發(fā)顯得嚴(yán)重和迫切。如今，數(shù)據(jù)壓縮技術(shù)早已是多媒體領(lǐng)域中的關(guān)鍵技術(shù)之一。
            一、什么是哈弗曼壓縮
            　　 Huffman( 哈夫曼 ) 算法在上世紀(jì)五十年代初提出來了，它是一種無損壓縮方法，在壓縮過程中不會丟失信息熵，而且可以證明Huffman 算法在無損壓縮算法中是最優(yōu)的。 Huffman 原理簡單，實現(xiàn)起來也不困難，在現(xiàn)在的主流壓縮軟件得到了廣泛的應(yīng)用。對應(yīng)用程序、重要資料等絕對不允許信息丟失的壓縮場合， Huffman 算法是非常好的選擇。
            二、怎么實現(xiàn)哈弗曼壓縮
               哈夫曼壓縮是個無損的壓縮算法，一般用來壓縮文本和程序文件。哈夫曼壓縮屬于可變代碼長度算法一族。意思是個體符號（例如，文本文件中的字符）用一個特定長度的位序列替代。因此，在文件中出現(xiàn)頻率高的符號，使用短的位序列，而那些很少出現(xiàn)的符號，則用較長的位序列。
               故我們得了解幾個概念：
              1 、二叉樹 ： 在計算機(jī)科學(xué)中，二叉樹是每個結(jié)點最多有兩個子樹的有序樹。通常子樹的根被稱作 “ 左子樹 ” （ left subtree ）和 “右子樹 ” （ right subtree ）。

             
            2 、哈夫曼編碼 (Huffman Coding) ：是一種編碼方式，哈夫曼編碼是可變字長編碼 (VLC) 的一種。 uffman 于 1952 年提出一種編碼方法，該方法完全依據(jù)字符出現(xiàn)概率來構(gòu)造異字頭的平均長 度最短的碼字，有時稱之為最佳編碼，一般就叫作 Huffman 編碼。
             
            三、哈夫曼編碼生成步驟：
            ① 掃描要壓縮的文件，對字符出現(xiàn)的頻率進(jìn)行計算。
            ② 把字符按出現(xiàn)的頻率進(jìn)行排序，組成一個隊列。
            ③ 把出現(xiàn)頻率最低（權(quán)值）的兩個字符作為葉子節(jié)點，它們的權(quán)值之和為根節(jié)點組成一棵樹。
            ④ 把上面葉子節(jié)點的兩個字符從隊列中移除，并把它們組成的根節(jié)點加入到隊列。
            ⑤ 把隊列重新進(jìn)行排序。重復(fù)步驟 ③④⑤ 直到隊列中只有一個節(jié)點為止。
            ⑥ 把這棵樹上的根節(jié)點定義為 0 （可自行定義 0 或 1 ）左邊為 0 ，右邊為 1 。這樣就可以得到每個葉子節(jié)點的哈夫曼編碼了。

            既如 (a) 、 (b) 、 (c) 、 (d) 幾個圖，就可以將離散型的數(shù)據(jù)轉(zhuǎn)化為樹型的了。
             
            如果假設(shè)樹的左邊用0 表示右邊用 1 表示，則每一個數(shù)可以用一個 01 串表示出來。

            則可以得到對應(yīng)的編碼如下：
            1-->110
            2-->111
            3-->10
            4-->0
            每一個01 串，既為每一個數(shù)字的哈弗曼編碼。
            為什么能壓縮：
            壓縮的時候當(dāng)我們遇到了文本中的1 、 2 、 3 、 4 幾個字符的時候，我們不用原來的存儲，而是轉(zhuǎn)化為用它們的 01 串來存儲不久是能減小了空間占用了嗎。（什么 01 串不是比原來的字符還多了嗎？怎么減少？）大家應(yīng)該知道的，計算機(jī)中我們存儲一個 int 型數(shù)據(jù)的時候一般式占用了 2^32-1 個 01 位，因為計算機(jī)中所有的數(shù)據(jù)都是最后轉(zhuǎn)化為二進(jìn)制位去存儲的。所以，想想我們的編碼不就是只含有 0 和 1 嘛，因此我們就直接將編碼按照計算機(jī)的存儲規(guī)則用位的方法寫入進(jìn)去就能實現(xiàn)壓縮了。
            比如：
            1這個數(shù)字，用整數(shù)寫進(jìn)計算機(jī)硬盤去存儲，占用了 2^32-1 個二進(jìn)制位
              而如果用它的哈弗曼編碼去存儲，只有110 三個二進(jìn)制位。
            效果顯而易見。
             
             
            開始寫程序:
             
            開始些程序之前，必須想好自己的文件存儲格式，和存儲規(guī)則是什么
            為了簡便，我自定義存儲的基本信息，格式如下：
             
             
            SaveCode[i].n    int型   // 每一個字節(jié)的編碼長度  i:0~256
            B yte[]   byte數(shù)組型 // 每一個字節(jié)的編碼 SaveCode[i].node 中 String 的 01 串轉(zhuǎn)化而來。
             Byte[]  byte數(shù)組型 // 對文件中每一個 byte 的重新編碼的哈夫曼編碼寫入。
             
            有了定義好的格式我們的讀寫就非常的方便了，
            創(chuàng)建步驟：
            ①讀入文件中的所有字節(jié)：
            Java代碼 
            1. // 創(chuàng)建文件輸入流  
            2.             java.io.FileInputStream fis = new java.io.FileInputStream(path);  
            3.             //讀入所有的文件字節(jié)  
            4.             while(fis.available()>0){  
            5.                 int i=fis.read();  
            6.                 byteCount[i]++;  
            7.             }  
             
            ②構(gòu)建哈夫曼樹：
            Java代碼 
            1. /** 
            2.     * 使用優(yōu)先隊列構(gòu)建哈弗曼樹 
            3.     */  
            4.    public void createTree(){  
            5.    //優(yōu)先隊列  
            6.   PriorityQueue<hfmNode> nodeQueue = new PriorityQueue<hfmNode>();  
            7.     
            8.    //把所有的節(jié)點都加入到 隊列里面去  
            9.     for (int i=0;i<256;i++){  
            10.         if(byteCount[i]!=0){  
            11.             hfmNode node = new hfmNode(i,byteCount[i]);  
            12.             nodeQueue.add(node);//加入節(jié)點  
            13.         }  
            14.     }  
            15.     //構(gòu)建哈弗曼樹  
            16.     while(nodeQueue.size()>1)  
            17.        {  
            18.         hfmNode min1 = nodeQueue.poll();//獲取隊列頭  
            19.         hfmNode min2 = nodeQueue.poll();  
            20.           
            21.         hfmNode result = new hfmNode(0,min1.times+min2.times);  
            22.         result.lChild=min1;  
            23.         result.rChild=min2;  
            24.            nodeQueue.add(result);//加入合并節(jié)點  
            25.        }  
            26.     root=nodeQueue.peek(); //得到根節(jié)點  
            27. }  
             
            這里我采用了優(yōu)先隊列的方法，因為優(yōu)先隊列比較符合哈夫曼的構(gòu)造方法，形式上也非常的相似。
            ③取得每一個葉子節(jié)點的哈夫曼編碼:
            Java代碼 
            1. /** 
            2.    * 獲得葉子節(jié)點的哈弗曼編碼  
            3.    * @param root 根節(jié)點 
            4.    * @param s 
            5.    */  
            6.   public void getMB(hfmNode root,String s){  
            7.       if ((root.lChild==null)&&(root.rChild==null)){  
            8.         Code hc=new Code();  
            9.         hc.node=s;  
            10.         hc.n=s.length();  
            11.         System.out.println("節(jié)點"+root.data+"編碼"+hc.node);  
            12.         SaveCode[root.data]=hc;//保存字節(jié)  root.data 的編碼 HC  
            13.        }  
            14.     if (root.lChild!=null){//左0 右 1  
            15.         getMB(root.lChild,s+'0');  
            16.     }  
            17.     if (root.rChild!=null){  
            18.         getMB(root.rChild,s+'1');  
            19.         }  
            20.     }  
             
            如此一來我們的哈夫曼樹就建好了。
            下面就是按照我們之前定義的文件存儲格式直接寫進(jìn)文件就可以了。
            壓縮文件的寫入:
            ①  寫出0~256 每一個字節(jié)對應(yīng)編碼的長度
            Java代碼 
            1. //寫出每一個編碼的長度  
            2.           for (int i=0;i<256;i++){  
            3.             fos.write(SaveCode[i].n);  
            4.           }    
             
            ② 寫出每一個字節(jié)所對應(yīng)的編碼
            這一步較為復(fù)雜，因為JAVA 中沒有自己定義的二進(jìn)制為寫入，我們就不得不將每 8 個 01 String 轉(zhuǎn)化為一個byte 再將 byte 寫入。但是，問題又來了不是所有的 01String 都是 8 的整數(shù)倍，所以就又得在不是 8 整數(shù)倍的String 后面補(bǔ)上 0
            Java代碼 
            1. /////寫入每一個字節(jié)所對應(yīng)的 String編碼  
            2.         int count=0;//記錄中轉(zhuǎn)的字符個數(shù)  
            3.         int i=0;//第i個字節(jié)  
            4.         String writes ="";  
            5.         String tranString="";//中轉(zhuǎn)字符串  
            6.         String waiteString;//保存所轉(zhuǎn)化的所有字符串  
            7.         while((i<256)||(count>=8)){  
            8.             //如果緩沖區(qū)的等待寫入字符大于8  
            9.             if (count>=8){  
            10.                 waiteString="";//清空要轉(zhuǎn)化的的碼  
            11.                 for (int t=0;t<8;t++){  
            12.                     waiteString=waiteString+writes.charAt(t);     
            13.                  }  
            14.               
            15.                 //將writes前八位刪掉  
            16.                 if (writes.length()>8){  
            17.                   tranString="";  
            18.                   for (int t=8;t<writes.length();t++){  
            19.                         tranString=tranString+writes.charAt(t);  
            20.                      }  
            21.                   writes="";  
            22.                   writes=tranString;  
            23.                   }else{  
            24.                       writes="";  
            25.                   }  
            26.                   
            27.                   count=count-8;//寫出一個8位的字節(jié)  
            28.                   int intw=changeString(waiteString);//得到String轉(zhuǎn)化為int  
            29.                   //寫入文件  
            30.                   fos.write(intw);  
            31.             }else{  
            32.                 //得到地i個字節(jié)的編碼信息，等待寫入  
            33.                 count=count+SaveCode[i].n;  
            34.                 writes=writes+SaveCode[i].node;  
            35.                 i++;  
            36.             }  
            37.         }  
            38.         //把所有編碼沒有足夠8的整數(shù)倍的String補(bǔ)0使得足夠8的整數(shù)倍，再寫入  
            39.         if (count>0){  
            40.             waiteString="";//清空要轉(zhuǎn)化的的碼  
            41.             for (int t=0;t<8;t++){  
            42.                 if (t<writes.length()){  
            43.                     waiteString=waiteString+writes.charAt(t);     
            44.                 }else{  
            45.                     waiteString=waiteString+'0';  
            46.                 }  
            47.             }  
            48.             fos.write(changeString(waiteString));//寫入  
            49.             System.out.println("寫入了->"+waiteString);  
            50.         }  
            51.   
            52.   
            53.    /** 
            54.     * 將一個八位的字符串轉(zhuǎn)成一個整數(shù) 
            55.     * @param s 
            56.     * @return 
            57.     */  
            58.    public int changeString(String s){  
            59.     return ((int)s.charAt(0)-48)*128+((int)s.charAt(1)-48)*64+((int)s.charAt(2)-48)*32  
            60.             +((int)s.charAt(3)-48)*16+((int)s.charAt(4)-48)*8+((int)s.charAt(5)-48)*4  
            61.             +((int)s.charAt(6)-48)*2+((int)s.charAt(7)-48);  
            62. }  
             
            ③ 將源文件中的所有byte 轉(zhuǎn)化為 01 哈夫曼編碼，寫入壓縮文件
               這一步也比較復(fù)雜，原理同上一步，在SaveCode 中查找一個 byte 所對應(yīng)的哈夫曼編碼，不夠 8 的整數(shù)倍的就不足，再寫入。
               值得注意的事，最后一定要寫一個byte 表示，補(bǔ)了多少個 0 方便解壓縮時的刪除 0
             
            Java代碼 
            1. //再次讀入文件的信息，對應(yīng)每一個字節(jié)寫入編碼  
            2.             count=0;  
            3.             writes ="";  
            4.             tranString="";  
            5.             int idata=fis.read();  
            6.             //文件沒有讀完的時候  
            7.             while ((fis.available()>0)||(count>=8)){  
            8.                 //如果緩沖區(qū)的等待寫入字符大于8  
            9.                 if (count>=8){  
            10.                     waiteString="";//清空要轉(zhuǎn)化的的碼  
            11.                     for (int t=0;t<8;t++){  
            12.                         waiteString=waiteString+writes.charAt(t);     
            13.                      }  
            14.                      
            15.                    //將writes前八位刪掉  
            16.                    if (writes.length()>8){  
            17.                      tranString="";  
            18.                      for (int t=8;t<writes.length();t++){  
            19.                         tranString=tranString+writes.charAt(t);  
            20.                        }  
            21.                       writes="";  
            22.                      writes=tranString;  
            23.                     }else{  
            24.                       writes="";  
            25.                     }  
            26.                      
            27.                      
            28.                   count=count-8;//寫出一個8位的字節(jié)  
            29.                   int intw=changeString(waiteString);  
            30.                   fos.write(intw);//寫到文件中區(qū)  
            31.                 }else{  
            32.                     //讀入idata字節(jié)，對應(yīng)編碼寫出信息  
            33.                     count=count+SaveCode[idata].n;  
            34.                     writes=writes+SaveCode[idata].node;  
            35.                     idata=fis.read();  
            36.                 }  
            37.             }  
            38.             count=count+SaveCode[idata].n;  
            39.             writes=writes+SaveCode[idata].node;  
            40.             //把count剩下的寫入  
            41.              int endsint=0;  
            42.              if (count>0){  
            43.                 waiteString="";//清空要轉(zhuǎn)化的的碼  
            44.                 for (int t=0;t<8;t++){  
            45.                     if (t<writes.length()){  
            46.                     waiteString=waiteString+writes.charAt(t);     
            47.                 }else{  
            48.                     waiteString=waiteString+'0';  
            49.                     endsint++;  
            50.                     }  
            51.                 }  
            52.                 fos.write(changeString(waiteString));//寫入所補(bǔ)的0  
             
            如此一來，整個的壓縮過程就完畢了。
             
            解壓縮過程：
                與壓縮過程剛好是反著來進(jìn)行的，知道的存儲的方式我們就反著來讀取看看。
            ①  讀入所有字節(jié)所對應(yīng)的編碼長度：
             
            Java代碼 
            1. //讀入文件中的每一個編碼的長度  
            2.        for (int i=0;i<256;i++){  
            3.                Code hC=new Code();  
            4.                hC.n=fis.read();  
            5.                hC.node="";  
            6.            SaveCode[i]=hC;  
            7.        }  
             
            ② 讀入每一個字節(jié)所對應(yīng)的編碼
            Java代碼 
            1. int i=0;  
            2.        int count=0;  
            3.        String coms="";  
            4.        //讀SaveCode中0~256字節(jié)的的數(shù)據(jù)  
            5.        while (i<256){  
            6.                //當(dāng)緩存區(qū)的編碼長度比編碼[i]的長度長的時候  
            7.                if (coms.length()>=SaveCode[i].n){  
            8.                       for (int t=0;t<SaveCode[i].n;t++){//SaveCode[i].node取得該編碼  
            9.                           SaveCode[i].node=SaveCode[i].node+coms.charAt(t);  
            10.                       }  
            11.                         
            12.                       //把coms前這幾位去掉  
            13.                       String coms2="";  
            14.                       for (int t=SaveCode[i].n;t<coms.length();t++){  
            15.                           coms2=coms2+coms.charAt(t);  
            16.                       }  
            17.                       coms="";  
            18.                       coms=coms2;//累計的下一個編碼，繼續(xù)的使用  
            19.                       i++;  
            20.                }else{  
            21.                     //如果已經(jīng)沒有寫出的話，再度入一個byte轉(zhuǎn)化為01 String  
            22.                     coms=coms+IntToString(fis.read());  
            23.                }  
            24.        }  
             
            ③ 讀入文件的哈夫曼編碼
            得注意的事，前面我們又補(bǔ)0 的位，所以在我們讀取的時候，記得把之前所補(bǔ)得東西，給刪除掉就 OK 了。
            Java代碼 
            1. String rsrg;//存轉(zhuǎn)換成的Sting  
            2.        String compString="";//存要比較的字符串  
            3.        //讀入文件，寫出文件  
            4.        while(fis.available()>1){  
            5.            if (search(compString)>=0){  
            6.                int cint=search(compString);  
            7.                fos.write(cint);  
            8.                //刪掉前n個數(shù)據(jù)  
            9.                String compString2="";  
            10.                for (int t=SaveCode[cint].n;t<compString.length();t++){  
            11.                   compString2=compString2+compString.charAt(t);  
            12.                }  
            13.                compString="";  
            14.                compString=compString2;  
            15.                  
            16.            }else{//繼續(xù)讀入  
            17.                compString=compString+IntToString(fis.read());  
            18.            }  
            19.        }  
            20.          
            21.          
            22.        //處理最后一個字節(jié)  
            23.       int cint=fis.read();  
            24.       String compString2="";  
            25.       for (int t=0;t<compString.length()-cint;t++){  
            26.          compString2=compString2+compString.charAt(t);  
            27.       }  
            28.       compString=compString2;  
            29.         
            30.         
            31.        //刪掉前n個數(shù)據(jù)  
            32.       while (compString.length()>0){  
            33.            int ccint=search(compString);  
            34.            fos.write(ccint);     
            35.            compString2="";  
            36.            for (int t=SaveCode[ccint].n;t<compString.length();t++){  
            37.             compString2=compString2+compString.charAt(t);  
            38.            }  
            39.            compString="";  
            40.            compString=compString2;  
            41.       }  
             
            如此而來，一個簡單的小壓縮軟件就實現(xiàn)了。

            本次的文件讀寫比較復(fù)雜，之前些的時候遇到了很多的困難，參考了很多前輩的思路和代碼，今天終于完成了，我~內(nèi)牛滿面
            因為沒有對其做任何的優(yōu)化壓縮的效率比較低，時間比較長，個位大俠不要見笑。

            From: http://stchou.javaeye.com/blog/833232
            

	
            
	
	
            
		posted on 2010-12-04 18:27 逛奔的蝸牛 閱讀(3979) 評論(1)  編輯 收藏 引用  所屬分類: Java 
	
            

            







            
	    
    


            

            
	
            評論
            
		
		
				
            			
					
            
						# re: Java：自己動手寫壓縮軟件，超詳細(xì)解釋（哈夫曼實現(xiàn)）[未登錄]
							
								2011-08-13 10:35
							
						123
					
            
					
            
						很多方法都木有寫出來，看的暈死了···很桑心···  回復(fù)  更多評論
						
            
						  
					
            
				
            
				
            
			

            




            






            

				

            



    
    







            
	   
	



久久国产亚洲精品无码|
少妇无套内谢久久久久|
久久黄视频|
久久综合九色综合欧美狠狠|
久久www免费人成看片|
色老头网站久久网|
国产产无码乱码精品久久鸭|
久久996热精品xxxx|
伊人色综合九久久天天蜜桃|
久久精品综合网|
大伊人青草狠狠久久|
久久av高潮av无码av喷吹|
久久久久99这里有精品10
|
国产免费久久精品丫丫|
国产精品99久久久久久人|
国产精品综合久久第一页|
国产香蕉久久精品综合网|
18岁日韩内射颜射午夜久久成人|
国产精品久久久久影院色|
九九久久精品无码专区|
久久一日本道色综合久久|
久久综合丁香激情久久|
久久精品麻豆日日躁夜夜躁|
亚洲国产精品人久久|
久久亚洲精品国产精品|
色天使久久综合网天天|
日韩影院久久|
久久久一本精品99久久精品66
|
国产精品久久久久久福利69堂|
伊人久久大香线蕉成人|
性高朝久久久久久久久久|
香蕉久久久久久狠狠色|
久久久不卡国产精品一区二区|
久久婷婷五月综合色奶水99啪|
国产精品VIDEOSSEX久久发布|
青草影院天堂男人久久|
亚洲国产成人精品久久久国产成人一区二区三区综|
亚洲va久久久久|
一本一道久久a久久精品综合|
亚洲一本综合久久|
精品久久久久一区二区三区|