赫夫曼編碼

一、基礎知識總結

赫夫曼編碼是一種變長編碼。

賦予高頻詞的字元較短的碼字，低頻次的字元較長的碼字。

所謂字首碼是沒有任何碼字是其他碼字的字首，使用字首碼使得在解碼過程中更加簡單無歧義。

二叉樹結構對于生成字首碼有特殊的優勢，因為每一個葉節點到其他葉節點之間無關聯，無法找到一個葉節點到其他葉節點的連續簡單路徑。

這樣的性質很好的滿足和字首碼的需求。

構造赫夫曼樹利用了貪心的算法思想，維護一個優先隊列，隊列中初始狀态為單節點子樹，節點的值為字元權重。

每次從優先隊列中挑出最小和次小元素，進行合并，合并後的局部根節點為兩子節點的值之和，然後把該合并後的子樹加入優先隊列中。

重複以上過程直到優先隊列中隻剩一個元素，即為赫夫曼樹的根節點。

更一般的講，該算法思想能夠構造一棵具有n個葉節點的最小權重路徑長度的二叉樹。其中權重路徑長度定義為：

常見的應用常見比如：構造決策樹。

二、算法實作

package aggreedy;
import java.util.Comparator;
import java.util.Deque;
import java.util.PriorityQueue;

public class HuffmanTree {
    // 樹節點的資料結構
    static class Node {
        private int weight = 0;
        private Node left = null;
        private Node right = null;
        Node(int w){
            this.weight = w; 
        }
    }
    
    // 構造赫夫曼樹
    public static Node createHuffmanTree(double[] w){
        
         Comparator<Node> cmp = new Comparator<Node>() {// 執行個體化比較器
                @Override
                public int compare(Node node1, Node node2) {
                    if (node2.weight > node1.weight) {
                        return -1;
                    }else if(node2.weight ==  node1.weight){
                        return 0;
                    }else {
                        return 1;
                    }
                }
          };
        PriorityQueue<Node> queen = new PriorityQueue<Node>(10,cmp);
        for (int i = 0; i < w.length; i++) {// 初始狀态為單節點子樹
            queen.add(new Node((int)(w[i]*100)));
        }
        Node tmpNode1,tmpNode2,tmpMerge;
        while(queen.size()>1){
            // 取出優先隊列中最小和次小的元素，合并成新的子樹，并加入隊列
            tmpNode1 = queen.poll();
            tmpNode2 = queen.poll();
            tmpMerge = new Node(tmpNode1.weight + tmpNode2.weight);
            tmpMerge.left = tmpNode1;
            tmpMerge.right = tmpNode2;
            queen.add(tmpMerge);
        }
        return queen.poll();
    }
    // 先序周遊赫夫曼樹
    public static void preTravel(Node node){
        if (node != null) {
            System.out.println(node.weight);
            preTravel(node.left);
            preTravel(node.right);
        }
    }
    // 工具方法，判定是否為葉節點
    private static boolean isLeaf(Node node){
        return (node.left == null) && (node.right == null);
    }
    
    // 遞歸實作編碼：左字數編碼0，右子樹編碼為1
    private static void innerCode(Node node,String code){
        if (!isLeaf(node)) {
            StringBuilder tmpCode1 = new StringBuilder(code);
            if (node.left != null) {
                tmpCode1.append("0");
            }
            innerCode(node.left, tmpCode1.toString());
            StringBuilder tmpCode2 = new StringBuilder(code);
            if (node.right != null) {
                tmpCode2.append("1");
            }
            innerCode(node.right, tmpCode2.toString());
        }else {
            System.out.println(code);
        }
    }
    public static void code(Node node){// 根據赫夫曼樹進行編碼
        innerCode(node, "");
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        double[] ary = {0.15,0.10,0.30,0.20,0.20,0.05};
//        double[] ary = {0.10,0.15,0.20,0.20,0.35};
        Node root = createHuffmanTree(ary);
//        preTravel(root);
        code(root);
    }
}      

 三、參考資料

1、算法導論.第十六章

2、算法設計與分析基礎.第九章