哈弗曼編碼以及用其實現壓縮軟件

1.什麼是哈夫曼樹?

哈夫曼樹是一種最優二叉樹，它的最優點體現在它的的帶權路徑長度最小。(結點的帶權路徑長度為：結點的路徑長度乘以結點的權值，樹的帶權路徑長度為所有葉子結點帶權路徑長度之和)

2.什麼是哈弗曼編碼?

從哈弗曼樹的根結點開始，按照左子樹分配代碼“0”，右子樹分配代碼“1”的規則，直到葉子結點為止，每個葉子結點的哈弗曼編碼就是從根結點開始，一直到該葉子結點為止，把途中經過的代碼按順序串起來就OK了。

3.什麼是哈弗曼壓縮?

Huffman( 哈夫曼 ) 算法在上世紀五十年代初提出來了，它是一種無損壓縮方法，在壓縮過程中不會丟失信息熵，而且可以證明 Huffman 算法在無損壓縮算法中是最優的。 Huffman 原理簡單，實現起來也不困難，在現在的主流壓縮軟件得到了廣泛的應用。對應用程序、重要資料等絕對不允許信息丟失的壓縮場合， Huffman 算法是非常好的選擇。

哈夫曼壓縮，一般用來壓縮文本和程序文件。哈夫曼壓縮屬於可變代碼長度算法一族。意思是個體符號(例如，文本文件中的字符)用一個特定長度的位序列替代。因此，在文件中出現頻率高的符號，使用短的位序列，而那些很少出現的符號，則用較長的位序列。

有了以上的基本概念，我們就可以動手實現哈弗曼壓縮軟件了!

4.哈弗曼壓縮軟件的實現：

在文件中，所有的數據都是以字節的形式存在的，一個字節是8位，所以所有可能出現的字節在0——256之間(不包括256)，所以，第一步要做的事情就是，把文件所有的字節的出現頻率統計出來，並用頻率做為權值生成一棵哈弗曼樹：

Java代碼

int[] ByteCount = new int[256];//字節頻率統計     
             
        InputStream fis = new FileInputStream(pathName_former);          
        InputStream bis = new BufferedInputStream(fis);//創建文件輸入流     
             
        while(bis.available()>0){     
            int tmp = bis.read();     
            ByteCount[tmp]++;     
        }//統計頻率     
             
        //構造哈弗曼樹     
        hfmTree hfm = new hfmTree(ByteCount);   

Java代碼

public hfmTree(int[] rank){//根據頻率構造哈弗曼樹     
    
        //把頻率不為零的字節加入節點優先級隊列     
        PriorityQueue nodes = new Java.util.PriorityQueue();     
             
        for(int i=0;i
            if(rank[i]!=0){     
                nodes.add(new hfmNode(rank[i],i));     
            }     
        }     
        //構造哈弗曼樹     
        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();     
             
             
    }//構造函數(correct)    

接下來，要做的就是獲得0——256之間每個字節所對應的哈弗曼編碼，用一個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     
    }    

然後就是把每個字節的編碼長度打入文件：

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());     
            }     
        }    

接下來就是，將每個字節的編碼打入文件(這裡需要吧8個長度的01串轉換成一個byte打入文件)：

Java代碼

//把每個字節的編碼表打到文件裡     
        int i = 0;//第i個字節     
        int count = 0;//滿8打一，計數器     
        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));//寫入一個字節     
            }else{     
                count+=Code[i].length();     
                allCode+=Code[i];     
                inCode+=Code[i];     
                i++;//嚴重錯誤發生地     
            }     
        }     
        //如果不滿8位的     
        if(allCode.length()>0){     
            int len = 8-allCode.length();//補零     
            for(int j=0;j
                allCode+="0";     
            }     
            inCode+=allCode;     
            bos.write(changeString(allCode));     
        }    

最後就是把文件中的所有字節按照這種哈弗曼的編碼方式保存到文件中，過程類似於上一步(在最後打入末尾補入的0的個數，主要是為了方便解壓縮)：

Java代碼

//編碼表輸出完畢，將文件中的字節按照這種編碼方式壓縮     
        InputStream ins = new FileInputStream(pathName_former);     
        InputStream buf = new BufferedInputStream(ins);//創建輸入流     
        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));//寫入一個字節     
            }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     
        }    

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