Java編程內(nèi)功-數(shù)據(jù)結(jié)構(gòu)與算法「赫夫曼編碼」

作者：Java精髓 2021-03-26 08:40:28

開(kāi)發(fā) 后端算法

本篇繼續(xù)給大家介紹Java編程數(shù)據(jù)結(jié)構(gòu)與算法相關(guān)知識(shí)，今天主要介紹關(guān)于赫夫曼編碼的前世今生。

基本介紹

赫夫曼編碼也翻譯為(哈夫曼編碼)Huffman Coding，又稱(chēng)為霍夫曼編碼，是一種編碼方式，屬于一種程序算法。
赫夫曼編碼是赫夫曼樹(shù)在電訊通訊中的經(jīng)典的應(yīng)用場(chǎng)景之一。
赫夫曼編碼廣泛的用于數(shù)據(jù)文件壓縮。其壓縮率通常在20%~90%之間。
赫夫曼碼是可變字長(zhǎng)編碼(VLC)的一種.Hufuuman于1952年提出一種編碼方法，稱(chēng)之為最佳編碼。

原理剖析

在通信領(lǐng)域中信息的處理方式1：定長(zhǎng)編碼

如: i like like like java do you like a java 共40個(gè)字符，包括空格，其對(duì)應(yīng)的ASCII碼,與二進(jìn)制編碼如下圖

按照二進(jìn)制來(lái)傳遞信息，總的長(zhǎng)度是359(包含空格)

在通信領(lǐng)域中信息的處理方式2：變長(zhǎng)編碼

i like like like java do you like a java 共40個(gè)字符，包括空格。變長(zhǎng)編碼處理如下圖

字符的編碼都不能是其他字符編碼的前綴，符合此要求的編碼叫做前綴編碼，即不能匹配到重復(fù)的編碼。

在通信領(lǐng)域中信息的處理方式3：赫夫曼編碼

i like like like java do you like a java 共40個(gè)字符，包括空格。變長(zhǎng)編碼處理如下圖

按照上面字符出現(xiàn)的次數(shù)構(gòu)建一顆赫夫曼樹(shù)，次數(shù)作為權(quán)值。

根據(jù)赫夫曼樹(shù)，給各個(gè)字符，規(guī)定編碼(前綴編碼),向左的路徑為0 向右的路徑為1：編碼如下：

按照上面的赫夫曼編碼，我們的"i like like like java do you like a java" 字符串對(duì)應(yīng)的編碼(注意這里我們使用的無(wú)損壓縮)如下圖。

說(shuō)明：

原來(lái)的長(zhǎng)度是359，壓縮了(359-133)/359=62.9%

此編碼滿足前綴編碼，即字符的編碼都不能是其他字符編碼的前綴。不會(huì)造成匹配的多義性。

赫夫曼編碼是無(wú)損壓縮!!

注意：

這個(gè)赫夫曼樹(shù)根據(jù)排序方法不同，也可能不一樣，這樣對(duì)應(yīng)的赫夫曼編碼也不完全一樣，但是wpl是一樣的，都是最小的，比如我們讓每次生成的新的二叉樹(shù)總是排在權(quán)值相同的二叉樹(shù)的最后一個(gè)，則生成的二叉樹(shù)為：

創(chuàng)建對(duì)應(yīng)的赫夫曼樹(shù)

根據(jù)赫夫曼編碼壓縮數(shù)據(jù)的原理，需要?jiǎng)?chuàng)建"i like like like java do you like a java" 對(duì)應(yīng)的赫夫曼樹(shù)

思路：

先創(chuàng)建Node節(jié)點(diǎn)，Node {data{存放數(shù)據(jù)}，weight(權(quán)值),left,right};

得到"i like like like java do you like a java" 對(duì)應(yīng)的byte[] 數(shù)組;

編寫(xiě)一個(gè)方法，將準(zhǔn)備構(gòu)建赫夫曼樹(shù)的node節(jié)點(diǎn)放到List集合;

可以通過(guò)集合List創(chuàng)建對(duì)應(yīng)的赫夫曼樹(shù);

赫夫曼樹(shù)應(yīng)用案例

將一串字符串進(jìn)行壓縮與解壓縮

package com.xie.huffmancode; 
 
import java.util.*; 
 
public class HuffmanCode { 
    public static void main(String[] args) { 
        String str = "i like like like java do you like a java"; 
        byte[] contentBytes = str.getBytes(); 
        System.out.println("contentBytes=" + Arrays.toString(contentBytes)); 
        List<Node> nodes = getNodes(contentBytes); 
 
        //生成赫夫曼樹(shù) 
        Node hufffmanTreeRoot = createHufffmanTree(nodes); 
 
        //生成的赫夫曼編碼表 
        getCodes(hufffmanTreeRoot, "", stringBuilder); 
 
        byte[] huffmanCodeBytes = zip(contentBytes, huffmanCodes); 
        System.out.println("huffmanCodeBytes = " + Arrays.toString(huffmanCodeBytes)); 
 
        byte[] decode = decode(huffmanCodes, huffmanCodeBytes); 
        System.out.println("赫夫曼解碼后對(duì)應(yīng)的數(shù)組" + new String(decode)); 
 
        /** 
         * contentBytes=[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] 
         * huffmanCodeBytes = [-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28] 
         * 赫夫曼解碼后對(duì)應(yīng)的數(shù)組i like like like java do you like a java 
         */ 
 
    } 
 
    //完成數(shù)據(jù)的解壓思路 
    //1.將huffmanCodeBytes[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28] 
    //  重新轉(zhuǎn)成 赫夫曼編碼對(duì)應(yīng)的二進(jìn)制字符串"101010001011111111001000101111...." 
    //2.赫夫曼編碼對(duì)應(yīng)的二進(jìn)制字符串"101010001011111111001000101111...." => 對(duì)照赫夫曼編碼表 => "i like like like java do you like a java" 
 
    /** 
     * 完成對(duì)壓縮數(shù)據(jù)的解碼 
     * 
     * @param huffmanCodes 赫夫曼編碼表 
     * @param huffmanBytes 赫夫曼編碼得到的字節(jié)數(shù)組 
     * @return 原來(lái)的字符串對(duì)應(yīng)的數(shù)組 
     */ 
    public static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) { 
        StringBuilder stringBuilder = new StringBuilder(); 
        for (int i = 0; i < huffmanBytes.length; i++) { 
            //判斷是不是最后一個(gè)字節(jié) 
            boolean flag = (i == huffmanBytes.length - 1); 
            stringBuilder.append(byteToBitString(!flag, huffmanBytes[i])); 
        } 
 
        Map<String, Byte> map = new HashMap<>(); 
        for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) { 
            Byte k = entry.getKey(); 
            String v = entry.getValue(); 
            map.put(v, k); 
        } 
 
        List<Byte> list = new ArrayList<>(); 
        for (int i = 0; i < stringBuilder.length();) { 
            int count = 1; 
            boolean flag = true; 
            Byte b = null; 
            while (flag) { 
                String key = stringBuilder.substring(i, i + count);//i 不動(dòng)，count移動(dòng)，直到匹配一個(gè)字符 
                b = map.get(key); 
                if (b == null) { 
                    count++; 
                } else { 
                    flag = false; 
                } 
            } 
            list.add(b); 
            i += count; 
        } 
        byte[] bytes = new byte[list.size()]; 
        for (int i = 0; i < list.size(); i++) { 
            bytes[i] = list.get(i); 
        } 
        return bytes; 
    } 
 
    /** 
     * 將一個(gè)byte 轉(zhuǎn)成一個(gè)二進(jìn)制的字符串 
     * 
     * @param flag 標(biāo)識(shí)是否需要補(bǔ)高位，true標(biāo)識(shí)需要補(bǔ)高位,如果是false表示不補(bǔ)，如果是最后一個(gè)字節(jié)，無(wú)需補(bǔ)高位 
     * @param b    傳入的byte 
     * @return 該byte對(duì)應(yīng)的二進(jìn)制字符串，（注意是按補(bǔ)碼返回) 
     */ 
    public static String byteToBitString(boolean flag, byte b) { 
        //將b 轉(zhuǎn)成 int 
        int temp = b; 
 
        //如果temp是正數(shù)還需要補(bǔ)高位 
        if (flag) { 
            // 按位或 如 256|1=> 1 0000 0000|0000 0001 => 1 0000 0001 
            temp |= 256; 
        } 
 
        //返回的是temp二進(jìn)制的補(bǔ)碼 
        String bitStr = Integer.toBinaryString(temp); 
        if (flag) { 
            //取后8位 
            return bitStr.substring(bitStr.length() - 8); 
        } else { 
            return bitStr; 
        } 
    } 
 
    /** 
     * 封裝原始字節(jié)數(shù)組轉(zhuǎn)赫夫曼字節(jié)數(shù)組 
     * 
     * @param bytes 
     * @return 
     */ 
    public static byte[] huffmanZip(byte[] bytes) { 
        List<Node> nodes = getNodes(bytes); 
 
        //創(chuàng)建赫夫曼樹(shù) 
        Node hufffmanTreeRoot = createHufffmanTree(nodes); 
        //生成赫夫曼編碼 
        getCodes(hufffmanTreeRoot, "", stringBuilder); 
        //返回壓縮后的赫夫曼編碼字節(jié)數(shù)組 
        return zip(bytes, huffmanCodes); 
 
    } 
 
    /** 
     * 將字符串對(duì)應(yīng)的byte[] 數(shù)組，通過(guò)赫夫曼編碼表，返回一個(gè)赫夫曼編碼壓縮后的byte[] 
     * 
     * @param bytes        原始字符串對(duì)應(yīng)的byte[] 
     * @param huffmanCodes 生成的赫夫曼編碼 
     * @return 返回赫夫曼編碼處理后的byte[] 
     */ 
    public static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) { 
        //利用huffmanCodes 將 bytes 轉(zhuǎn)成赫夫曼編碼對(duì)應(yīng)的字符串 
        StringBuilder stringBuilder = new StringBuilder(); 
        for (byte b : bytes) { 
            stringBuilder.append(huffmanCodes.get(b)); 
        } 
 
        // 將"101010001011111111001000101111...." 轉(zhuǎn)成byte[] 
        // 統(tǒng)計(jì)返回byte[] huffmanCodeBytes 長(zhǎng)度 
        int len; 
        if (stringBuilder.length() % 8 == 0) { 
            len = stringBuilder.length() / 8; 
        } else { 
            len = stringBuilder.length() / 8 + 1; 
        } 
        //創(chuàng)建 存儲(chǔ)壓縮后的byte[]數(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()) { 
                strByte = stringBuilder.substring(i); 
            } else { 
                strByte = stringBuilder.substring(i, i + 8); 
            } 
            //將strByte 轉(zhuǎn)成一個(gè)byte ,放入到huffmanCodeBytes 
            huffmanCodeBytes[index] = (byte) Integer.parseInt(strByte, 2); 
            index++; 
        } 
        return huffmanCodeBytes; 
    } 
 
    //生成赫夫曼樹(shù)對(duì)應(yīng)的赫夫曼編碼表 
    //思路： 
    //1. 將赫夫曼編碼表存放在Map<Byte,String>,形式如32->01,97->100... 
    static Map<Byte, String> huffmanCodes = new HashMap<>(); 
    //2. 在生成赫夫曼編碼表時(shí)，需要拼接路徑，定義一個(gè)StringBuilder  存儲(chǔ)某個(gè)葉子節(jié)點(diǎn)的路徑 
    static StringBuilder stringBuilder = new StringBuilder(); 
 
    /** 
     * 將傳入的node 節(jié)點(diǎn)的所有葉子的赫夫曼編碼得到，并放入huffmanCodes集合 
     * 
     * @param node          傳入節(jié)點(diǎn) 
     * @param code          路徑：左子節(jié)點(diǎn)是0，右子節(jié)點(diǎn)是1 
     * @param stringBuilder 用于拼接路徑 
     */ 
    public static void getCodes(Node node, String code, StringBuilder stringBuilder) { 
        StringBuilder stringBuilder2 = new StringBuilder(stringBuilder); 
        stringBuilder2.append(code); 
        if (node != null) { 
            //判斷當(dāng)前node 是葉子節(jié)點(diǎn)還是非葉子節(jié)點(diǎn) 
            if (node.data == null) {//非葉子節(jié)點(diǎn) 
 
                //向左遞歸處理 
                getCodes(node.left, "0", stringBuilder2); 
                //向右遞歸處理 
                getCodes(node.right, "1", stringBuilder2); 
            } else {//葉子節(jié)點(diǎn) 
                huffmanCodes.put(node.data, stringBuilder2.toString()); 
            } 
        } 
    } 
 
    //前序遍歷 
    public static void preOrder(Node root) { 
        if (root != null) { 
            root.preOrder(); 
        } else { 
            System.out.println("赫夫曼樹(shù)不能為空~~"); 
        } 
    } 
 
    /** 
     * 將字節(jié)數(shù)組轉(zhuǎn)成node集合 
     * 
     * @param bytes 字節(jié)數(shù)組 
     * @return 
     */ 
    public static List<Node> getNodes(byte[] bytes) { 
        ArrayList<Node> nodes = new ArrayList<>(); 
 
        //存儲(chǔ)每個(gè)byte出現(xiàn)的次數(shù) 
        Map<Byte, Integer> counts = new HashMap<>(); 
        for (byte b : bytes) { 
            counts.merge(b, 1, (a, b1) -> a + b1); 
        } 
 
        //把每個(gè)鍵值對(duì)轉(zhuǎn)成一個(gè)node對(duì)象，并加入到nodes 集合 
        counts.forEach((k, v) -> nodes.add(new Node(k, v))); 
        return nodes; 
    } 
 
    /** 
     * 生成赫夫曼樹(shù) 
     * @param nodes 傳入的節(jié)點(diǎn) 
     * @return 
     */ 
    public static Node createHufffmanTree(List<Node> nodes) { 
        while (nodes.size() > 1) { 
            //排序，從小到大 
            Collections.sort(nodes); 
 
            //(1)取出權(quán)值最小的節(jié)點(diǎn)(二叉樹(shù)) 
            Node leftNode = nodes.get(0); 
 
            //(2) 取出權(quán)值第二小的節(jié)點(diǎn)(二叉樹(shù)) 
            Node rightNode = nodes.get(1); 
            //(3) 構(gòu)建一顆新的二叉樹(shù) 
            Node parent = new Node(null, leftNode.weight + rightNode.weight); 
            parent.left = leftNode; 
            parent.right = rightNode; 
 
            //(4) 從ArrayList中刪除處理過(guò)的二叉樹(shù) 
            nodes.remove(leftNode); 
            nodes.remove(rightNode); 
            //(5) 將parent加入nodes 
            nodes.add(parent); 
        } 
        //nodes 的最后一個(gè)就是赫夫曼樹(shù)的root節(jié)點(diǎn) 
        return nodes.get(0); 
    } 
} 
 
//創(chuàng)建Node，帶數(shù)據(jù)和權(quán)值 
class Node implements Comparable<Node> { 
    //存放數(shù)據(jù)本身,比如'a'=>'97'，' ' =>'32' 
    Byte data; 
    //權(quán)值，表示字符出現(xiàn)的次數(shù) 
    int weight; 
 
    Node left; 
    Node right; 
 
    public Node(Byte data, int weight) { 
        this.data = data; 
        this.weight = weight; 
    } 
 
    public void preOrder() { 
        System.out.println(this); 
        if (this.left != null) { 
            this.left.preOrder(); 
        } 
        if (this.right != null) { 
            this.right.preOrder(); 
        } 
    } 
 
    @Override 
    public int compareTo(Node o) { 
        //從小到大排序 
        return this.weight - o.weight; 
    } 
 
    @Override 
    public String toString() { 
        return "Node{" + 
                "data=" + data + 
                ", weight=" + weight + 
                '}'; 
    } 
}