【資料結構-Java】最佳實踐-資料壓縮(使用赫夫曼樹)

一、需求

將給出的一段文本，比如 “i like like like java do you like a java” ， 根據前面的講的赫夫曼編碼原理，對其進行資料壓縮處理

二、步驟

根據赫夫曼編碼壓縮資料的原理，需要創建 “i like like like java do you like a java” 對應的赫夫曼樹

1. 創建節點Node{data(存放資料)，weight(權值)，left和right}
2. 得到"i like like like java do you like a java"的byte[]陣列
3. 撰寫方法，將準備構建赫夫曼樹的Node放入List
4. 通過list創建對應的赫夫曼樹

1、創建赫夫曼樹所需的節點Node

class Node implements Comparable<Node> {
    Byte data;//存放資料 'a'=> 97
    int weight;//權值:統計出現的次數
    Node left;
    Node right;
    public Node(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }
    /**
     * 前序遍歷
     */
    public void preOder() {
        System.out.println(this);
        if (this.left != null) this.left.preOder();
        if (this.right != null) this.right.preOder();
    }
    @Override
    public String toString() {
        return new StringJoiner(", ", Node.class.getSimpleName() + "[", "]")
                .add("data=" + data)
                .add("weight=" + weight)
                .toString();
    }
    //根據權值從小到大排序
    @Override
    public int compareTo(Node o) {
        return this.weight - o.weight;
    }
}

2、得到字串的byte陣列

得到"i like like like java do you like a java"的byte[]陣列

 byte[] contentBytes = str.getBytes();

3、接受位元組陣列回傳list

/**
     * 接受位元組陣列回傳list
     * Node[data=32, weight=9],Node[data=100, weight=1].....
     *
     * @param bytes
     * @return
     */
    private static List<Node> getNodes(byte[] bytes) {
        List<Node> list = new ArrayList<>();
        //統計每個字串出現的次數,使用map集合
        HashMap<Byte, Integer> map = new HashMap<>();
        for (byte aByte : bytes) {
            Integer count = map.get(aByte);
            if (count == null) {//說明當前map中沒有存入該字符
                map.put(aByte, 1);
            } else {//說明之前存入過
                count++;
                map.put(aByte, count);
            }
        }
        //將map中的資料取出放入list中
        for (Map.Entry<Byte, Integer> entry : map.entrySet()) {
            list.add(new Node(entry.getKey(), entry.getValue()));
        }
        return list;
    }

4、通過list回傳一棵赫夫曼樹

通過list回傳一棵赫夫曼樹

 /**
     * 通過list回傳一棵赫夫曼樹
     *
     * @param list
     * @return
     */
    private static Node getHoffumanTree(List<Node> list) {
        while (list.size() > 1) {
            Collections.sort(list);
            Node leftNode = list.get(0);
            Node rightNode = list.get(1);
            //通過取出的兩個節點權重計算他們的根節點，root沒有date
            Node root = new Node(null, (leftNode.weight + rightNode.weight));
            root.left = leftNode;
            root.right = rightNode;
            list.remove(leftNode);
            list.remove(rightNode);
            list.add(root);
        }
        return list.get(0);
    }

5、生成赫夫曼樹對應的赫夫曼編碼表

1. 將赫夫曼編碼表存放在map集合中Map<Byte,String>

形式：32->01 97->100 100->11000

2. 在生成赫夫曼編碼表時，拼接路徑，創建StringBuilder存盤某個葉子節點的路徑

 /**
     * 多載，傳一個根節點即可得到赫夫曼編碼表
     *
     * @param node
     */
    private static Map<Byte, String> getCodes(Node node) {
        if (node == null) return null;
        getCodes(node,"",stringBuilder);
        return hoffuCodes;
    }
    /*
     * 生成霍夫曼樹對應的赫夫曼編碼表
     * 1、將赫夫曼編碼表存放在map集合中Map<Byte,String>
     *     形式：32->01 97->100 100->11000
     * 2、在生成赫夫曼編碼表時，拼接路徑，創建StringBuilder存盤某個葉子節點的路徑
     */
    static Map<Byte, String> hoffuCodes = new HashMap<>();
    static StringBuilder stringBuilder = new StringBuilder();
    /**
     * 功能：將傳入的Node節點的所有葉子節點赫夫曼編碼得到并存放到hoffumap中
     *
     * @param node          節點，默認根節點
     * @param code          路徑，左子節點為0，右子節點為1
     * @param stringBuilder 拼接路徑
     */
    private static void getCodes(Node node, String code, StringBuilder stringBuilder) {
        //進行字串拼接
        StringBuilder stringBuilder1 = new StringBuilder(stringBuilder);
        stringBuilder1.append(code);
        if (node != null) {
            //if(node.data ==null) 不進行處理
            if (node.data == null) {//說明時非葉子節點，繼續尋找直到找到某一個葉子節點
                //往左邊查找
                getCodes(node.left, "0", stringBuilder1);
                //往右邊查找
                getCodes(node.right, "1", stringBuilder1);
            } else {//如果當前已經為葉子節點，表示這個字符的赫夫曼編碼已經產生，放入map集合中
                hoffuCodes.put(node.data, stringBuilder1.toString());
            }
        }
    }

1. 生成赫夫曼樹對應的赫夫曼編碼 , 如下表:

=01 a=100 d=11000 u=11001 e=1110 v=11011 i=101 
y=11010 j=0010 k=1111 l=000 o=0011

2. 使用赫夫曼編碼來生成赫夫曼編碼資料 ,即按照上面的赫夫曼編碼，將"i like like like java do you like a java"
   字串生成對應的編碼資料, 形式如下.

10101000101111111100100010111111110010001011111111001001010011011100011100000110111010001111001010 00101111111100110001001010011011100

6、對赫夫曼樹得到的二進制字符通過赫夫曼編碼表進行資料壓縮

1. 利用赫夫曼編碼表，將byte陣列轉成赫夫曼編碼字串
2. 將生成的赫夫曼編碼字串裝成byte[]，8位一個byte

/**
     * 使用一個方法封裝
     *
     * @param contentBytes 原始的字串byte
     * @return 經過赫夫曼編碼處理過后的編碼，壓縮過后的編碼
     */
    private static byte[] huffmanZip(byte[] contentBytes) {
        List<Node> nodes = getNodes(contentBytes);
        //1、創建赫夫曼樹
        Node hofumanNode = getHoffumanTree(nodes);
        //2、根據赫夫曼數生成對應的赫夫曼編碼
        Map<Byte, String> codes = getCodes(hofumanNode);
        //3、根據赫夫曼編碼對原始資料壓縮，得到壓縮后的位元組碼陣列
        byte[] zip = zip(contentBytes, codes);
        return zip;
    }

    /**
     * 撰寫一個方法，將字串對應的byte[]陣列，通過生成霍夫曼編碼表，回傳一個赫夫曼編碼壓縮過后的byte[]
     *
     * @param bytes      原始字串對應的byte[]
     * @param hoffuCodes 生成的赫夫曼編碼表map
     * @return 回傳赫夫曼編碼處理后的byte陣列
     * "i like like like java do you like a java" => byte[] contentBytes
     * => 對應的byte[]hoffumanCodeByte，8位對應一個byte放入到hoffumanCodeByte
     */
    private static byte[] zip(byte[] bytes, Map<Byte, String> hoffuCodes) {
        //1、利用赫夫曼編碼表，將byte陣列轉成赫夫曼編碼字串
        StringBuilder hoffmanSB = new StringBuilder();
        //遍歷byte
        for (byte b : bytes) {
            hoffmanSB.append(hoffuCodes.get(b));
        }
        //2、將生成的hoffmanSB裝成byte[]，8位一個byte
        int len = 0;
        if (hoffmanSB.length() % 8 == 0) {//長度剛好位8的整數
            len = hoffmanSB.length() / 8;
        } else {
            len = hoffmanSB.length() / 8 + 1;
        }
        //簡化：int length = (hoffmanSB.length() +7)/ 8 ;
        //創建存盤壓縮后的byte[]
        byte[] hoffumanByte = new byte[len];
        int index = 0;//統計第多少個byte
        for (int i = 0; i < hoffmanSB.length(); i += 8) {//8位一個byte，所以步長為8
            String strByte;
            if (i + 8 > hoffmanSB.length()) {//說明不夠8位
                strByte = hoffmanSB.substring(i);
            } else {
                strByte = hoffmanSB.substring(i, i + 8);
            }
            //將strByte轉成byte放入到hoffumanByte
            hoffumanByte[index] = (byte) Integer.parseInt(strByte);
            index++;
        }
        return hoffumanByte;
    }