最優(yōu)樹之赫夫曼樹與赫夫曼編碼的實現(xiàn)二

上一文我們剛研究了赫夫曼樹的原理和實現(xiàn)，

這節(jié)將講一下赫夫曼樹的運用:赫夫曼編碼。

基本介紹

赫夫曼編碼也翻譯為哈夫曼編碼(Huffman Coding)，又稱霍夫曼編碼，是一種編碼方式,屬于一種程序算法
赫夫曼編碼是赫哈夫曼樹在電訊通信中的經(jīng)典的應用之一。

赫夫曼編碼廣泛地用于數(shù)據(jù)文件壓縮。其壓縮率通常在20%～90%之間
赫夫曼碼是可變字長編碼(VLC)的一種。Huffman于1952年提出一種編碼方法，稱之為最佳編碼。

原理刨析

原理剖析

<h2>通信領域中信息的處理方式1-定長編碼</h2>

i like like like java do you like a java // 共40個字符(包括空格)
105 32 108 105 107 101 32 108 105 107 101 32 108 105 107 101 32 106 97 118 97 32 100 111 32 121 111 117 32 108 105 107 101 32 97 32 106 97 118 97 //對應Ascii碼

01101001 00100000 01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101 00100000 01101010 01100001 01110110 01100001 00100000 01100100 01101111 00100000 01111001 01101111 01110101 00100000 01101100 01101001 01101011 01100101 00100000 01100001 00100000 01101010 01100001 01110110 01100001 //對應的二進制
按照二進制來傳遞信息，總的長度是 359 (包括空格)
在線轉(zhuǎn)碼 工具 ：https://www.mokuge.com/tool/asciito16/

<h2>通信領域中信息的處理方式2-變長編碼</h2>

i like like like java do you like a java // 共40個字符(包括空格)

d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9 // 各個字符對應的個數(shù)
0= , 1=a, 10=i, 11=e, 100=k, 101=l, 110=o, 111=v, 1000=j, 1001=u, 1010=y, 1011=d? 說明：按照各個字符出現(xiàn)的次數(shù)進行編碼，原則是出現(xiàn)次數(shù)越多的，則編碼越小，比如 空格出現(xiàn)了9 次， 編碼為0 ,其它依次類推.

按照上面給各個字符規(guī)定的編碼，則我們在傳輸 "i like like like java do you like a java" 數(shù)據(jù)時，編碼就是 ?10010110100...
字符的編碼都不能是其他字符編碼的前綴，符合此要求的編碼叫做前綴編碼， 即不能匹配到重復的編碼(這個在赫夫曼編碼中，我們還要進行舉例說明, 不捉急)

<h2>通信領域中信息的處理方式3-赫夫曼編碼</h2>

i like like like java do you like a java // 共40個字符(包括空格)

d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9 // 各個字符對應的個數(shù)
按照上面字符出現(xiàn)的次數(shù)構建一顆赫夫曼樹, 次數(shù)作為權值.(圖后)

image

//根據(jù)赫夫曼樹，給各個字符
//規(guī)定編碼 ， 向左的路徑為0
//向右的路徑為1 ， 編碼如下:

o: 1000 u: 10010 d: 100110 y: 100111 i: 101
a : 110 k: 1110 e: 1111 j: 0000 v: 0001
l: 001 " " : 01

按照上面的赫夫曼編碼，我們的"i like like like java do you like a java" 字符串對應的編碼為 (注意這里我們使用的無損壓縮)

1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110

長度為 ： 133

說明:

原來長度是 359 , 壓縮了 (359-133) / 359 = 62.9%

此編碼滿足前綴編碼, 即字符的編碼都不能是其他字符編碼的前綴。不會造成匹配的多義性.

注意:

這個赫夫曼樹根據(jù)排序方法不同，也可能不太一樣，這樣對應的赫夫曼編碼也不完全一樣，但是wpl 是一樣的，都是最小的, 比如: 如果我們讓每次生成的新的二叉樹總是排在權值相同的二叉樹的最后一個，則生成的二叉樹為:


image

但是長度是一樣的，同時構成的赫夫曼樹的WPL也是一樣的。

實踐--數(shù)據(jù)壓縮

最佳實踐-數(shù)據(jù)壓縮(創(chuàng)建赫夫曼樹)

將給出的一段文本，比如 "i like like like java do you like a java" ， 根據(jù)前面的講的赫夫曼編碼原理，對其進行數(shù)據(jù)壓縮處理 ，形式如 "1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110
"

步驟

傳輸?shù)?字符串

  1. i like like like java do you like a java

  2. d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9 // 各個字符對應的個數(shù)

  3. 按照上面字符出現(xiàn)的次數(shù)構建一顆赫夫曼樹, 次數(shù)作為權值

步驟：

構成赫夫曼樹的步驟：

  1. 從小到大進行排序, 將每一個數(shù)據(jù)，每個數(shù)據(jù)都是一個節(jié)點 ， 每個節(jié)點可以看成是一顆最簡單的二叉樹

  2. 取出根節(jié)點權值最小的兩顆二叉樹

  3. 組成一顆新的二叉樹, 該新的二叉樹的根節(jié)點的權值是前面兩顆二叉樹根節(jié)點權值的和

  4. 再將這顆新的二叉樹，以根節(jié)點的權值大小 再次排序， 不斷重復 1-2-3-4 的步驟，直到數(shù)列中，所有的數(shù)據(jù)都被處理，就得到一顆赫夫曼樹

  5. 根據(jù)赫夫曼樹，給各個字符,規(guī)定編碼 (前綴編碼)， 向左的路徑為0 向右的路徑為1 ， 編碼如下:
    o: 1000 u: 10010 d: 100110 y: 100111 i: 101
    a : 110 k: 1110 e: 1111 j: 0000 v: 0001
    l: 001 : 01

  6. 按照上面的赫夫曼編碼，我們的"i like like like java do you like a java" 字符串對應的編碼為 (注意這里我們使用的無損壓縮)
    1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110 通過赫夫曼編碼處理 長度為 133

代碼實現(xiàn)

思路:

(1) Node { data (存放數(shù)據(jù))， weight (權值)， left 和 right }

(2) 得到 "i like like like java do you like a java" 對應的 byte[] 數(shù)組

(3) 編寫一個方法，將準備構建赫夫曼樹的Node 節(jié)點放到 List , 形式 [Node[date=97 ,weight = 5], Node[]date=32,weight = 9]......], 體現(xiàn) d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9

(4) 可以通過List 創(chuàng)建對應的赫夫曼樹.

創(chuàng)建節(jié)點

//創(chuàng)建Node ,待數(shù)據(jù)和權值
class Node implements Comparable<Node>  {
    Byte data; // 存放數(shù)據(jù)(字符)本身，比如'a' => 97 ' ' => 32
    int weight; //權值, 表示字符出現(xiàn)的次數(shù)
    Node left;//
    Node right;
    public Node(Byte data, int weight) {
        
        this.data = data;
        this.weight = weight;
    }
    @Override
    public int compareTo(Node o) {
        // 從小到大排序
        return this.weight - o.weight;
    }
    @Override
    public String toString() {
        return "Node [data = " + data + " weight=" + weight + "]";
    }
    
    //前序遍歷
    public void preOrder() {
        System.out.println(this);
        if(this.left != null) {
            this.left.preOrder();
        }
        if(this.right != null) {
            this.right.preOrder();
        }
    }
}

創(chuàng)建接收字節(jié)數(shù)組，并轉(zhuǎn)化為匹配權值和數(shù)據(jù)本身的list

/**
     * 
     * @param bytes 接收字節(jié)數(shù)組
     * @return 返回的就是 List 形式   [Node[date=97 ,weight = 5], Node[]date=32,weight = 9]......],
     */
    private static List<Node> getNodes(byte[] bytes) {
        
        //1創(chuàng)建一個ArrayList
        ArrayList<Node> nodes = new ArrayList<Node>();
        
        //遍歷 bytes , 統(tǒng)計 每一個byte出現(xiàn)的次數(shù)->map[key,value]
        Map<Byte, Integer> counts = new HashMap<>();
        for (byte b : bytes) {
            Integer count = counts.get(b);
            if (count == null) { // Map還沒有這個字符數(shù)據(jù),第一次
                counts.put(b, 1);
            } else {
                counts.put(b, count + 1);
            }
        }
        
        //把每一個鍵值對轉(zhuǎn)成一個Node 對象，并加入到nodes集合
        //遍歷map
        for(Map.Entry<Byte, Integer> entry: counts.entrySet()) {
            nodes.add(new Node(entry.getKey(), entry.getValue()));
        }
        return nodes;
        
    }

構造赫夫曼樹

    //可以通過List 創(chuàng)建對應的赫夫曼樹
    private static Node createHuffmanTree(List<Node> nodes) {
        
        while(nodes.size() > 1) {
            //排序, 從小到大
            Collections.sort(nodes);
            //取出第一顆最小的二叉樹
            Node leftNode = nodes.get(0);
            //取出第二顆最小的二叉樹
            Node rightNode = nodes.get(1);
            //創(chuàng)建一顆新的二叉樹,它的根節(jié)點 沒有data, 只有權值
            Node parent = new Node(null, leftNode.weight + rightNode.weight);
            parent.left = leftNode;
            parent.right = rightNode;
            
            //將已經(jīng)處理的兩顆二叉樹從nodes刪除
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            //將新的二叉樹，加入到nodes
            nodes.add(parent);
            
        }
        //nodes 最后的結點，就是赫夫曼樹的根結點
        return nodes.get(0);
    }

測試是否符合預期結果:

public static void main(String[] args) {
        String content = "i like like like java do you like a java";
        byte[] contentBytes = content.getBytes();
        System.out.println(contentBytes.length); //40

        List<HuffManNode> nodes = getNodes(contentBytes);
        HuffManNode node = createHuffManNode(nodes);
        preOrder(node);
    }

預期結果:,前序遍歷輸出得

image

選擇幾個data有值得，查具體的Ascall碼，對比對應的次數(shù)weight是否正確。全部正確。

生成赫夫曼編碼:

//生成赫夫曼樹對應的赫夫曼編碼
    //思路:
    //1. 將赫夫曼編碼表存放在 Map<Byte,String> 形式
    //   生成的赫夫曼編碼表{32=01, 97=100, 100=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011}
    static Map<Byte, String> huffmanCodes = new HashMap<Byte,String>();
    //2. 在生成赫夫曼編碼表示，需要去拼接路徑, 定義一個StringBuilder 存儲某個葉子結點的路徑
    static StringBuilder stringBuilder = new StringBuilder();
    
    
    //為了調(diào)用方便，我們重載 getCodes
    private static Map<Byte, String> getCodes(Node root) {
        if(root == null) {
            return null;
        }
        //處理root的左子樹
        getCodes(root.left, "0", stringBuilder);
        //處理root的右子樹
        getCodes(root.right, "1", stringBuilder);
        return huffmanCodes;
    }
    
    /**
     * 功能：將傳入的node結點的所有葉子結點的赫夫曼編碼得到，并放入到huffmanCodes集合
     * @param node  傳入結點
     * @param code  路徑： 左子結點是 0, 右子結點 1
     * @param stringBuilder 用于拼接路徑
     */
    private static void getCodes(Node node, String code, StringBuilder stringBuilder) {
        StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
        //將code 加入到 stringBuilder2
        stringBuilder2.append(code);
        if(node != null) { //如果node == null不處理
            //判斷當前node 是葉子結點還是非葉子結點
            if(node.data == null) { //非葉子結點
                //遞歸處理
                //向左遞歸
                getCodes(node.left, "0", stringBuilder2);
                //向右遞歸
                getCodes(node.right, "1", stringBuilder2);
            } else { //說明是一個葉子結點
                //就表示找到某個葉子結點的最后
                huffmanCodes.put(node.data, stringBuilder2.toString());
            }
        }
    }
    
       Map<Byte, String> huffManNodeMap = getCodes(node);

        for(Map.Entry<Byte,String> entry:huffManNodeMap.entrySet()){
            System.out.println(entry.getKey()+":路徑值為"+entry.getValue());
        }

結果為:


image

打印成二進制數(shù)，相當于壓縮數(shù)據(jù)，進行數(shù)據(jù)壓縮

private static byte[] huffmanZip(byte[] bytes) {
        List<HuffManNode> nodes = getNodes(bytes);
        //根據(jù) nodes 創(chuàng)建的赫夫曼樹
        HuffManNode huffmanTreeRoot = createHuffManNode(nodes);
        //對應的赫夫曼編碼(根據(jù) 赫夫曼樹)
        Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);
        //根據(jù)生成的赫夫曼編碼，壓縮得到壓縮后的赫夫曼編碼字節(jié)數(shù)組
        byte[] huffmanCodeBytes = zip(bytes, huffmanCodes);
        return huffmanCodeBytes;
    }
    
private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {

        //1.利用 huffmanCodes 將  bytes 轉(zhuǎn)成  赫夫曼編碼對應的字符串
        StringBuilder stringBuilder = new StringBuilder();
        //遍歷bytes 數(shù)組
        for (byte b : bytes) {
            stringBuilder.append(huffmanCodes.get(b));
        }
        System.out.println("赫夫曼編碼為"+stringBuilder.toString());
        int len;

        if(stringBuilder.length() % 8 == 0){
            len = stringBuilder.length() / 8;
        } else {
            len = stringBuilder.length() /8 +1;
        }

        //創(chuàng)建存儲壓縮后的數(shù)組
        byte[] huffmanCodeBytes = new byte[len];
        int index = 0;
        for(int i=0;i< stringBuilder.length();i+=8){

            String strByte;

            if(i+8 > stringBuilder.length()) {//不夠8位
                strByte = stringBuilder.substring(i);
            }else{
                strByte = stringBuilder.substring(i, i + 8);
            }

            //將strByte 轉(zhuǎn)成一個byte,放入到 huffmanCodeBytes
            huffmanCodeBytes[index] = (byte)Integer.parseInt(strByte, 2);
            index++;
        }
        return huffmanCodeBytes;
    }

測試:

 String content = "i like like like java do you like a java";
 byte[] contentBytes = content.getBytes();
 System.out.println("壓縮后的數(shù)組(轉(zhuǎn)為二進制格式)："+Arrays.toString(huffmanZip(contentBytes)));

結果:

image

原來的字符為40，現(xiàn)在最長為17個字節(jié)。無損壓縮率為57%。

如何將壓縮后的字節(jié)碼數(shù)組解壓成原來的數(shù)據(jù)呢？

/**
     * 將一個byte 轉(zhuǎn)成一個二進制的字符串, 如果看不懂，可以參考我講的Java基礎 二進制的原碼，反碼，補碼
     * @param b 傳入的 byte
     * @param flag 標志是否需要補高位如果是true ，表示需要補高位，如果是false表示不補, 如果是最后一個字節(jié)，無需補高位
     * @return 是該b 對應的二進制的字符串，（注意是按補碼返回）
     */
    private static String byteToBitString(boolean flag, byte b) {
        //使用變量保存 b
        int temp = b; //將 b 轉(zhuǎn)成 int
        //如果是正數(shù)我們還存在補高位
        if(flag) {
            temp |= 256; //按位與 256  1 0000 0000  | 0000 0001 => 1 0000 0001
        }
        String str = Integer.toBinaryString(temp); //返回的是temp對應的二進制的補碼
        if(flag) {
            return str.substring(str.length() - 8);
        } else {
            return str;
        }
    }
    
    
//編寫一個方法，完成對壓縮數(shù)據(jù)的解碼
    /**
     * 
     * @param huffmanCodes 赫夫曼編碼表 map
     * @param huffmanBytes 赫夫曼編碼得到的字節(jié)數(shù)組
     * @return 就是原來的字符串對應的數(shù)組
     */
    private static byte[] decode(Map<Byte,String> huffmanCodes, byte[] huffmanBytes) {
        
        //1. 先得到 huffmanBytes 對應的 二進制的字符串 ， 形式 1010100010111...
        StringBuilder stringBuilder = new StringBuilder();
        //將byte數(shù)組轉(zhuǎn)成二進制的字符串
        for(int i = 0; i < huffmanBytes.length; i++) {
            byte b = huffmanBytes[i];
            //判斷是不是最后一個字節(jié)
            boolean flag = (i == huffmanBytes.length - 1);
            stringBuilder.append(byteToBitString(!flag, b));
        }
        //把字符串安裝指定的赫夫曼編碼進行解碼
        //把赫夫曼編碼表進行調(diào)換，因為反向查詢 a->100 100->a
        Map<String, Byte>  map = new HashMap<String,Byte>();
        for(Map.Entry<Byte, String> entry: huffmanCodes.entrySet()) {
            map.put(entry.getValue(), entry.getKey());
        }
        
        //創(chuàng)建要給集合，存放byte
        List<Byte> list = new ArrayList<>();
        //i 可以理解成就是索引,掃描 stringBuilder 
        for(int  i = 0; i < stringBuilder.length(); ) {
            int count = 1; // 小的計數(shù)器
            boolean flag = true;
            Byte b = null;
            
            while(flag) {
                //1010100010111...
                //遞增的取出 key 1 
                String key = stringBuilder.substring(i, i+count);//i 不動，讓count移動，指定匹配到一個字符
                b = map.get(key);
                if(b == null) {//說明沒有匹配到
                    count++;
                }else {
                    //匹配到
                    flag = false;
                }
            }
            list.add(b);
            i += count;//i 直接移動到 count  
        }
        //當for循環(huán)結束后，我們list中就存放了所有的字符  "i like like like java do you like a java"
        //把list 中的數(shù)據(jù)放入到byte[] 并返回
        byte b[] = new byte[list.size()];
        for(int i = 0;i < b.length; i++) {
            b[i] = list.get(i);
        }
        return b;
    }

大家可以自己測試運行下。

?著作權歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容