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

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

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

            則可以得到對應的編碼如下：
            1-->110
            2-->111
            3-->10
            4-->0
            每一個01 串，既為每一個數字的哈弗曼編碼。
            為什么能壓縮：
            壓縮的時候當我們遇到了文本中的1 、 2 、 3 、 4 幾個字符的時候，我們不用原來的存儲，而是轉化為用它們的 01 串來存儲不久是能減小了空間占用了嗎。（什么 01 串不是比原來的字符還多了嗎？怎么減少？）大家應該知道的，計算機中我們存儲一個 int 型數據的時候一般式占用了 2^32-1 個 01 位，因為計算機中所有的數據都是最后轉化為二進制位去存儲的。所以，想想我們的編碼不就是只含有 0 和 1 嘛，因此我們就直接將編碼按照計算機的存儲規則用位的方法寫入進去就能實現壓縮了。
            比如：
            1這個數字，用整數寫進計算機硬盤去存儲，占用了 2^32-1 個二進制位
              而如果用它的哈弗曼編碼去存儲，只有110 三個二進制位。
            效果顯而易見。
             
             
            開始寫程序:
             
            開始些程序之前，必須想好自己的文件存儲格式，和存儲規則是什么
            為了簡便，我自定義存儲的基本信息，格式如下：
             
             
            SaveCode[i].n    int型   // 每一個字節的編碼長度  i:0~256
            B yte[]   byte數組型 // 每一個字節的編碼 SaveCode[i].node 中 String 的 01 串轉化而來。
             Byte[]  byte數組型 // 對文件中每一個 byte 的重新編碼的哈夫曼編碼寫入。
             
            有了定義好的格式我們的讀寫就非常的方便了，
            創建步驟：
            ①讀入文件中的所有字節：
            Java代碼 
            1. // 創建文件輸入流  
            2.             java.io.FileInputStream fis = new java.io.FileInputStream(path);  
            3.             //讀入所有的文件字節  
            4.             while(fis.available()>0){  
            5.                 int i=fis.read();  
            6.                 byteCount[i]++;  
            7.             }  
             
            ②構建哈夫曼樹：
            Java代碼 
            1. /** 
            2.     * 使用優先隊列構建哈弗曼樹 
            3.     */  
            4.    public void createTree(){  
            5.    //優先隊列  
            6.   PriorityQueue<hfmNode> nodeQueue = new PriorityQueue<hfmNode>();  
            7.     
            8.    //把所有的節點都加入到 隊列里面去  
            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);//加入節點  
            13.         }  
            14.     }  
            15.     //構建哈弗曼樹  
            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);//加入合并節點  
            25.        }  
            26.     root=nodeQueue.peek(); //得到根節點  
            27. }  
             
            這里我采用了優先隊列的方法，因為優先隊列比較符合哈夫曼的構造方法，形式上也非常的相似。
            ③取得每一個葉子節點的哈夫曼編碼:
            Java代碼 
            1. /** 
            2.    * 獲得葉子節點的哈弗曼編碼  
            3.    * @param root 根節點 
            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("節點"+root.data+"編碼"+hc.node);  
            12.         SaveCode[root.data]=hc;//保存字節  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.     }  
             
            如此一來我們的哈夫曼樹就建好了。
            下面就是按照我們之前定義的文件存儲格式直接寫進文件就可以了。
            壓縮文件的寫入:
            ①  寫出0~256 每一個字節對應編碼的長度
            Java代碼 
            1. //寫出每一個編碼的長度  
            2.           for (int i=0;i<256;i++){  
            3.             fos.write(SaveCode[i].n);  
            4.           }    
             
            ② 寫出每一個字節所對應的編碼
            這一步較為復雜，因為JAVA 中沒有自己定義的二進制為寫入，我們就不得不將每 8 個 01 String 轉化為一個byte 再將 byte 寫入。但是，問題又來了不是所有的 01String 都是 8 的整數倍，所以就又得在不是 8 整數倍的String 后面補上 0
            Java代碼 
            1. /////寫入每一個字節所對應的 String編碼  
            2.         int count=0;//記錄中轉的字符個數  
            3.         int i=0;//第i個字節  
            4.         String writes ="";  
            5.         String tranString="";//中轉字符串  
            6.         String waiteString;//保存所轉化的所有字符串  
            7.         while((i<256)||(count>=8)){  
            8.             //如果緩沖區的等待寫入字符大于8  
            9.             if (count>=8){  
            10.                 waiteString="";//清空要轉化的的碼  
            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位的字節  
            28.                   int intw=changeString(waiteString);//得到String轉化為int  
            29.                   //寫入文件  
            30.                   fos.write(intw);  
            31.             }else{  
            32.                 //得到地i個字節的編碼信息，等待寫入  
            33.                 count=count+SaveCode[i].n;  
            34.                 writes=writes+SaveCode[i].node;  
            35.                 i++;  
            36.             }  
            37.         }  
            38.         //把所有編碼沒有足夠8的整數倍的String補0使得足夠8的整數倍，再寫入  
            39.         if (count>0){  
            40.             waiteString="";//清空要轉化的的碼  
            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.     * 將一個八位的字符串轉成一個整數 
            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 轉化為 01 哈夫曼編碼，寫入壓縮文件
               這一步也比較復雜，原理同上一步，在SaveCode 中查找一個 byte 所對應的哈夫曼編碼，不夠 8 的整數倍的就不足，再寫入。
               值得注意的事，最后一定要寫一個byte 表示，補了多少個 0 方便解壓縮時的刪除 0
             
            Java代碼 
            1. //再次讀入文件的信息，對應每一個字節寫入編碼  
            2.             count=0;  
            3.             writes ="";  
            4.             tranString="";  
            5.             int idata=fis.read();  
            6.             //文件沒有讀完的時候  
            7.             while ((fis.available()>0)||(count>=8)){  
            8.                 //如果緩沖區的等待寫入字符大于8  
            9.                 if (count>=8){  
            10.                     waiteString="";//清空要轉化的的碼  
            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位的字節  
            29.                   int intw=changeString(waiteString);  
            30.                   fos.write(intw);//寫到文件中區  
            31.                 }else{  
            32.                     //讀入idata字節，對應編碼寫出信息  
            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="";//清空要轉化的的碼  
            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));//寫入所補的0  
             
            如此一來，整個的壓縮過程就完畢了。
             
            解壓縮過程：
                與壓縮過程剛好是反著來進行的，知道的存儲的方式我們就反著來讀取看看。
            ①  讀入所有字節所對應的編碼長度：
             
            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.        }  
             
            ② 讀入每一個字節所對應的編碼
            Java代碼 
            1. int i=0;  
            2.        int count=0;  
            3.        String coms="";  
            4.        //讀SaveCode中0~256字節的的數據  
            5.        while (i<256){  
            6.                //當緩存區的編碼長度比編碼[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;//累計的下一個編碼，繼續的使用  
            19.                       i++;  
            20.                }else{  
            21.                     //如果已經沒有寫出的話，再度入一個byte轉化為01 String  
            22.                     coms=coms+IntToString(fis.read());  
            23.                }  
            24.        }  
             
            ③ 讀入文件的哈夫曼編碼
            得注意的事，前面我們又補0 的位，所以在我們讀取的時候，記得把之前所補得東西，給刪除掉就 OK 了。
            Java代碼 
            1. String rsrg;//存轉換成的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個數據  
            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{//繼續讀入  
            17.                compString=compString+IntToString(fis.read());  
            18.            }  
            19.        }  
            20.          
            21.          
            22.        //處理最后一個字節  
            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個數據  
            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.       }  
             
            如此而來，一個簡單的小壓縮軟件就實現了。

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

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

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

            







            
	    
    


            

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

            




            






            

				

            



    
    







            
	   
	



97久久精品午夜一区二区|
久久青草国产精品一区|
国产一区二区久久久|
久久精品国产亚洲AV忘忧草18|
久久精品国产AV一区二区三区|
久久91精品国产91久久麻豆|
久久久久亚洲AV成人网人人网站
|
久久国产精品无码HDAV|
国产福利电影一区二区三区，免费久久久久久久精
|
久久久久亚洲AV无码网站|
AAA级久久久精品无码区|
中文字幕乱码人妻无码久久|
中文字幕亚洲综合久久2|
伊人久久大香线蕉亚洲五月天|
国产ww久久久久久久久久|
无码人妻精品一区二区三区久久久|
国产精品午夜久久|
久久精品国产亚洲av水果派|
亚洲国产成人久久综合区|
国内精品免费久久影院|
久久91精品国产91久久麻豆|
亚洲精品高清国产一线久久|
无码乱码观看精品久久|
99热都是精品久久久久久|
久久96国产精品久久久|
无码人妻少妇久久中文字幕蜜桃
|
中文无码久久精品|
亚洲婷婷国产精品电影人久久|
狠狠色丁香婷婷综合久久来|
伊人久久大香线蕉亚洲五月天
|
久久久久久综合一区中文字幕|
久久久久久久精品妇女99|
欧美伊人久久大香线蕉综合69|
9191精品国产免费久久|
久久99国产精品久久99|
粉嫩小泬无遮挡久久久久久|
性做久久久久久久久浪潮|
一本久久免费视频|
婷婷久久五月天|
亚洲国产欧洲综合997久久|
一本色综合网久久|