赫夫曼樹及赫夫曼編碼

上一篇 字典樹

下一篇 B樹及其實作

赫夫曼樹

簡介

給定n個權值作為n個葉子結點，構造一棵二叉樹，若該樹的帶權路徑長度(wpl)達到最小，稱這樣的二叉樹為最優二叉樹，也稱為哈夫曼樹(Huffman Tree)

赫夫曼樹是帶權路徑長度最短的樹，權值較大的結點離根較近

路徑：

在一棵樹中，從一個結點到另一個結點所經過的所有結點，被我們稱為兩個結點之間的路徑

下圖：根節點到F節點路徑為：A ->B->D->F

路徑長度

在一棵樹中，從一個結點到另一個結點所經過的“邊”的數量，被我們稱為兩個結點之間的路徑長度;若規定根結點的層數為1，則從根結點到第L層結點的路徑長度為L-1;下圖中

從根結點A到葉子結點F，共經過了3條邊，是以路徑長度是3

結點的帶權路徑長度

結點的權及帶權路徑長度：若将樹中結點賦給一個有着某種含義的數值，則這個數值稱為該結點的權。結點的帶權路徑長度為：從根結點到該結點之間的路徑長度與該結點的權的乘積

樹的帶權路徑長度

樹的帶權路徑長度：樹的帶權路徑長度規定為所有葉子結點的帶權路徑長度之和，記為WPL(weighted path length) ,權值越大的結點離根結點越近的二叉樹才是最優二叉樹。

上圖樹的帶全路徑長度則為50。

WPL最小的就是赫夫曼樹

如：上圖的第二個樹WPL最小即為赫夫曼樹

赫夫曼樹建立

建立赫夫曼樹的步驟：

• 1 從小到大進行排序, 将每一個資料，每個資料都是一個節點，每個節點可以看成是一顆最簡單的二叉樹
• 2 取出根節點權值最小的兩顆二叉樹
• 3 組成一顆新的二叉樹, 該新的二叉樹的根節點的權值是前面兩顆二叉樹根節點權值的和
• 4 再将這顆新的二叉樹，将該根節點的權值大小與剩下的資料進行比較即再次排序，不斷重複1-2-3-4的步驟，直到數列中，所有的資料都被處理，就得到一顆赫夫曼樹

使用代碼建構

public  static void createHuffmanTree(int[] arr){

        //需要比較大小，且需要重複比較大小優先使用優先級隊列
        var  priorityQueue=new PriorityQueue<Node>(Comparator.comparingInt(e->e.value));
        for (int i : arr) {
            priorityQueue.add(new Node(i));
        }

        while (priorityQueue.size()>1){

            Node nodeLeft = priorityQueue.poll();
            Node nodeRight=priorityQueue.poll();
            if (nodeLeft!=null&&nodeRight != null){

                Node parentNode=new Node(nodeLeft.value+nodeRight.value);
                parentNode.left=nodeLeft;
                parentNode.right=nodeRight;
                priorityQueue.remove(nodeLeft);
                priorityQueue.remove(nodeRight);
                priorityQueue.add(parentNode);
            }
        }
        Node root = priorityQueue.poll();

        TreeOperation<Node> tree = new TreeOperation<>();
        tree.show(root);
    }



           

建構結果與上圖所畫完全一緻

赫夫曼樹的應用場景

apache負載均衡的按權重請求政策的底層算法、 生活中的路由器的路由算法、利用哈夫曼樹實作漢字點陣字形的壓縮存儲

赫夫曼編碼

基本介紹

赫夫曼編碼也翻譯為 哈夫曼編碼(Huffman Coding)，又稱霍夫曼編碼，是一種編碼方式, 屬于一種程式算法

赫夫曼編碼是赫哈夫曼樹在電訊通信中的經典的應用之一。

赫夫曼編碼廣泛地用于資料檔案壓縮。其壓縮率通常在20%～90%之間

赫夫曼碼是可變字長編碼(VLC)的一種。Huffman于1952年提出一種編碼方法，稱之為最佳編碼

背景

赫夫曼編碼出現以前

通信領域中資訊的處理方式

1 定長編碼

比如 一段文字“BADCADFEED”，顯然用二進制數字（0和1）表示是很自然的想法。

傳輸的資料就是“001000011010000011101100100011”，對方接收時同樣按照3位一組解碼。如果一篇文章很長，這樣的二進制串也非常的可怕。而且事實上，每個字母或者漢子的出現頻率是不同的。

2 變長編碼

比如 “I want to get more money” 總共24個字元(包含空格)

各個字元對應的個數：

a:1 r:1 y:1 w:1 I:1 g:1 m:2 n:2 e:3 o:3 t:3 空格：5

對應二進制為：

按照各個字元出現的次數進行編碼，原則是出現次數越多的，則編碼越小，比如 空格出現了5次， 編碼為0 ,其它依次類推.

0= , 1=e 10=o, 11=t, 100=m, 101=n, 110=a, 111=r, 1000=y, 1001=w, 1010=I ，1011=g

按以上規則則在傳輸"I want to get more money" 字元串時則對應編碼為：

10100100111010111…

字元的編碼都不能是其他字元編碼的字首，符合此要求的編碼叫做字首編碼， 即不能比對到重複的編碼.很明顯變長編碼不是字首編碼,會造成比對的多義性；是以就有了赫夫曼編碼

編碼

var string=“I want to get more money”; --以此字元串說明

1 統計各個字元出現的次數

a:1 r:1 y:1 w:1 I:1 g:1 m:2 n:2 e:3 o:3 t:3 空格：5

對應的byte： 97:1 114:1 121:1 119:1 73:1 103:1 109:2 110:2 101:3 111:3 116:3 32:5

private static HashMap<Byte, Integer> getByteCount(byte[] byteArray){

         var map=new HashMap<Byte, Integer>();
         for (var cb : byteArray) {

             //map.merge(cb, 1, (k, v)->(map.get(cb)+1));

            map.compute(cb, (k,v)->map.getOrDefault(cb, 0)+1);
        }
        
        return map;
    }
           

2 按照上面字元出現的次數建構一顆赫夫曼樹, 次數作為權值

private static TreeNode<Byte>  createHuffmanTree(byte[] byteArray,List<TreeNode<Byte>> list){

        var map= getByteCount(byteArray);//統計的字元将作為赫夫曼樹的葉子節點

        var  priorityQueue=new PriorityQueue<TreeNode<Byte>>(Comparator.comparingInt(e->e.value));

        map.forEach((k,v)-> {

            TreeNode<Byte> characterTreeNode = new TreeNode<>(k, v);

            priorityQueue.add(characterTreeNode);
            list.add(characterTreeNode);

        });

       while (priorityQueue.size() >1){

           var nodeLeft = priorityQueue.poll();
           var nodeRight = priorityQueue.poll();
           if (nodeLeft!=null&&nodeRight != null){

               var nodeParent=new TreeNode<Byte>(null,nodeLeft.value+nodeRight.value);
               nodeParent.left=nodeLeft;
               nodeParent.right=nodeRight;

               nodeLeft.parent=nodeParent;
               nodeRight.parent=nodeParent;
               priorityQueue.remove(nodeRight);
               priorityQueue.remove(nodeLeft);

               priorityQueue.add(nodeParent);
           }
       }

        return priorityQueue.poll();
    }
           

3 根據赫夫曼樹，給各個字元規定編碼，向左的路徑為0，向右的路徑為1 ，各個字元最終作為赫夫曼樹的葉子節點

每個字元的路徑：

：00 a:0100 r:0101 t:011 e:100 o:101 g:11000 w:11001 y:11010 I:11011 m:1110 n:1111

private static void getTreePathCodeStatus(List<TreeNode<Byte>> list) {


        var build=new StringBuilder();

        list.forEach(node -> {

            var currentNode=node;
            while (currentNode.parent!=null){//由于字元位于葉子節點則直接向上找父節點即可得出路徑
                build.insert(0, currentNode.parent.left== currentNode ?'0':'1');
                currentNode = currentNode.parent;
            }

            if (node.key!=null){
                ENCODE_MAP.put(node.key, build.toString());
                build.delete(0, build.length());
            }
        });
 
    }
           

4 按照上面的赫夫曼編碼， 對應字元串對應的編碼(補碼)為 (赫夫曼是無損壓縮)

11011001100101001111011000111010011000100011001110101010110000111010111110011010

此編碼滿足字首編碼, 即字元的編碼都不能是其他字元編碼的字首。不會造成比對的多義性

注意

• 此編碼串是以補碼的形式存在
• 這個赫夫曼樹根據排序方法(有相同權值的時候)不同，也可能不太一樣，這樣對應的赫夫曼編碼也不完全一樣，但是樹的帶權路徑長度(wpl)是一樣的，都是最小的。
• 實際開發中均已byte位元組進行編碼壓縮

public static  byte[] huffmanEnCode(byte[] byteArray,String name,String parentDirName,boolean isCreateFile){

            Objects.requireNonNull(byteArray);

            if (byteArray.length==0){
                System.out.println("The file is empty!");
                return null;
            }

            var list = new ArrayList<TreeNode<Byte>>();
            //生成赫夫曼樹
            var root= createHuffmanTree(byteArray,list);


            //顯示赫夫曼樹
            if(byteArray.length<30){
                new TreeOperation<TreeNode<Byte>>().show(root);
            }

            //擷取赫夫曼路徑二進制字元串
           getTreePathCodeStatus(list);

         return encode(byteArray,name,parentDirName,isCreateFile);

    }
           

解碼

赫夫曼解碼是對編碼的進行反編譯過程，即還原過程

1 首先我們需要擷取解碼表，編碼表一般會在編碼的時候寫入壓縮檔案中，是以我們需要讀取檔案擷取編碼表，更據編碼表建構解碼表

public  static  byte[] huffmanDecode(byte[] encodedArr,HashMap<Byte,String> encodedMap){


        StringBuilder encodedStr= new StringBuilder();

        //将位元組數組轉成二進制字元編碼串
        for (var i = 0; i < encodedArr.length; i++) {

            encodedStr.append(decodeBytesToInt(encodedArr[i],i==encodedArr.length-1));
        }


        //擷取解碼表
        var decodedMap=new HashMap<String,Byte>();//解碼表

        encodedMap.forEach((Key,Value)-> decodedMap.put(Value,Key));
        encodedMap.clear();

        return  decode(decodedMap, encodedStr);
    }
           

2 讀取檔案中的位元組數組解析成編碼串，即對應1101100…此種形式的赫夫曼樹路徑編碼串

解析關鍵函數

private static String decodeBytesToInt( byte bytes,boolean isLast) {

        var s=Integer.toBinaryString(Byte.toUnsignedInt(bytes));//toUnsignedInt轉成無符号位整型，如果是負數二進制則為8位，如果是正數或者0，會存在高位丢失不滿足8位的情況

        if (isLast&&s.length() <=lastLength){//最後一位如果是正數或者本身就是0則需要和壓縮前時的最後一位長度比較。
            // 假如壓縮前最後位為00111，現在轉成二進制高位的0都被省略後是111。長度差2，這種需要補2個0，
            // 假如壓縮前最後位為111，現在轉成二進制後也是111。長度相等,這種無需補0
            //處理最後一個位元組是正數或者是0，可能不足8位。因為其在壓縮的時候長度就不夠8位,但是在使用補碼的時候原來前面的0會被忽略掉，是以要補齊
            return  "0".repeat(lastLength-s.length())+s;
        }
        //負數底層是32位，無符号處理後肯定長度為8,則不會拼接，如果是正數或者0經過toBinarySting處理高位會丢失導緻不滿足8位的情況則需要拼接
        return  "0".repeat(8-s.length())+s;

    }
           

3 從第二步驟的編碼串從解碼表裡進行比對解析

private  static byte[] decode(HashMap<String,Byte> decodedMap, StringBuilder encodedBuilder){

        int startIndex=0;

        var list= new ArrayList<Byte>();

        for (var i = 1; i < encodedBuilder.length()+1; i++) {
            String str;

            if (decodedMap.containsKey(str=encodedBuilder.substring(startIndex, i))){

                list.add(decodedMap.get(str));
                startIndex=i ;

            }
        }

        //解壓後的位元組數組
        var bytes =new byte[list.size()];
        for (var i = 0; i < bytes.length; i++) {
            bytes[i]=list.get(i);
        }

        list.clear();
        decodedMap.clear();

        System.out.println("解壓成功");

        return  bytes;
    }
           

• 赫夫曼壓縮注意事項：
• 1 如果檔案本身就是經過壓縮處理的，那麼使用赫夫曼編碼再壓縮效率不會有明顯變化, 比如視訊,ppt 等等檔案 [舉例壓一個 .ppt]
• 2 赫夫曼編碼是按位元組來處理的，是以可以處理所有的檔案(二進制檔案、文本檔案) [舉例壓一個.xml檔案]
• 3 如果一個檔案中的内容，重複的資料不多，壓縮效果也不會很明顯.

完整代碼

使用赫夫曼樹對檔案進行壓縮及解壓