1.什么是哈夫曼樹?

哈夫曼樹是一種最優(yōu)二叉樹，它的最優(yōu)點體現(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 算法在無損壓縮算法中是最優(yōu)的。 Huffman 原理簡單，實現(xiàn)起來也不困難，在現(xiàn)在的主流壓縮軟件得到了廣泛的應用。對應用程序、重要資料等絕對不允許信息丟失的壓縮場合， 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é)所對應的哈弗曼編碼，用一個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     
        }    

到這里，整個壓縮過程基本完成了，解壓縮就是壓縮的逆過程，在此不再贅述，所有的操作都保存在附上源代碼中。

【編輯推薦】

1. Java編碼問題完全解決方案
2. 淺談Java中的編碼理論
3. JAVA里字符編碼的探索與理解