赫夫曼树应用-数据压缩

比眉伴天荒 2021-07-24 14:47 298阅读 0赞

# 一 需求 #

将给出的一段文本，比如 "i like like like java do you like a java" ，根据赫夫曼编码原理，对其进行数据压缩处理。

压缩后的形式如下：

"1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110"。

然后8个一组，转化到byte数组。

# 二 代码 #

package com.atguigu.huffmancode;
    
    import java.util.*;
    
    /**
    * @className: HuffmanCode
    * @description: 赫夫曼编码
    * @date: 2021/3/21
    * @author: cakin
    */
    public class HuffmanCode {
        /**
         * 功能描述：赫夫曼编码测试
         *
         * @param args 命令行
         * @author 贝医
         * @date 2021/3/21
         */
        public static void main(String[] args) {
            // 待编码的字符串
            String content = "i like like like java do you like a java";
            // 将字符串转化为byte数组
            byte[] contentBytes = content.getBytes();
            System.out.println(contentBytes.length); // 40
            // 编码后的结果
            byte[] huffmanCodesBytes = huffmanZip(contentBytes);
            System.out.println("压缩后的结果是:" + Arrays.toString(huffmanCodesBytes) + " 长度= " + huffmanCodesBytes.length);
        }
    
        
        /**
         * 功能描述：封装赫夫曼编码步骤
         *
         * @param bytes 原始的字符串对应的字节数组
         * @return 经过赫夫曼编码处理后的字节数组
         */
        private static byte[] huffmanZip(byte[] bytes) {
            List<Node> nodes = getNodes(bytes);
            // 根据 nodes 创建的赫夫曼树
            Node huffmanTreeRoot = createHuffmanTree(nodes);
            // 根据赫夫曼树得到对应的赫夫曼编码表
            Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);
            // 根据赫夫曼编码表，压缩得到压缩后的赫夫曼编码字节数组
            byte[] huffmanCodeBytes = zip(bytes, huffmanCodes);
            return huffmanCodeBytes;
        }
    
        /**
        * 功能描述：将字符串对应的byte[]，通过生成的赫夫曼编码表，返回一个赫夫曼编码压缩后的byte[]
        *
        * @param bytes        原始的字符串对应的 byte[]
        * @param huffmanCodes 生成的赫夫曼编码map
        * @return 返回赫夫曼编码处理后的 byte[]
        * 举例：
        * String content = "i like like like java do you like a java";
        * 1 将上面字符串存放到 bytes 数组中。
        * 2 通过 huffmanCodes 存放到 stringBuilder中，形式如下：
        * "1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100"
        * 3 将上面的字符串以8位为一组,放入到 huffmanCodeBytes
        * 说明：二进制举例 补码 = ~原码 + 1，源码 = ~（补码-1）
        * huffmanCodeBytes[0] =  10101000(以补码存储) ，它对应的原码是 ~（10101000-1)=~10100111=11011000 =-88
        */
        private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
            // 1 利用 huffmanCodes 将  bytes 转成赫夫曼编码对应的字符串
            StringBuilder stringBuilder = new StringBuilder();
            // 遍历bytes 数组
            for (byte b : bytes) {
                stringBuilder.append(huffmanCodes.get(b));
            }
            System.out.println("stringBuilder=" + stringBuilder.toString());
    
            // 将"1010100010111111110..." 转成 byte[]
            // 统计返回  byte[] huffmanCodeBytes 长度
            // 一句话 int len = (stringBuilder.length() + 7) / 8;
            int len;
            if (stringBuilder.length() % 8 == 0) {
                len = stringBuilder.length() / 8;
            } else {
                len = stringBuilder.length() / 8 + 1;
            }
            // 存储压缩后的 byte数组
            byte[] huffmanCodeBytes = new byte[len];
            int index = 0; // 记录是第几个byte
            for (int i = 0; i < stringBuilder.length(); i += 8) { // 因为是每8位对应一个byte,所以步长为8
                String strByte;
                if (i + 8 > stringBuilder.length()) { // 以长度为8进行分组，最后一组，可能不够8位
                    strByte = stringBuilder.substring(i);
                } else {
                    strByte = stringBuilder.substring(i, i + 8);
                }
                // 将 strByte 转成一个byte,放入到 huffmanCodeBytes
                huffmanCodeBytes[index] = (byte) Integer.parseInt(strByte, 2);
                index++;
            }
            return huffmanCodeBytes;
        }
    
        // 赫夫曼编码表 {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<>();
        // 存储某个叶子结点的路径
        static StringBuilder stringBuilder = new StringBuilder();
    
        /**
         * 功能描述：根据赫夫曼树得到对应的赫夫曼编码表
         *
         * @param root 赫夫曼树的根节点
         * @return Map<Byte, String> 赫夫曼树编码表
         * @author cakin
         * @date 2021/3/21
         */
        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，形式如下：
         * 空格=01 a=100 d=11000 u=11001 e=1110 v=11011 i=101 y=11010 j=0010 k=1111 l=000 o=0011
         *
         * @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中
                    huffmanCodes.put(node.data, stringBuilder2.toString());
                }
            }
        }
    
        /**
         * 功能描述：将bytes数组以List<Node>的形式存储
         *
         * @param bytes 接收字节数组
         * @return 返回 List<Node> 形式：[Node[date=97 ,weight = 5], Node[]date=32,weight = 9]......]
         */
        private static List<Node> getNodes(byte[] bytes) {
            // 1 创建一个 ArrayList
            ArrayList<Node> nodes = new ArrayList<>();
            // 2 遍历 bytes , 统计 每一个byte出现的次数，用 map[key,value] 进行存储
            Map<Byte, Integer> counts = new HashMap<>();
            for (byte b : bytes) {
                Integer count = counts.get(b);
                if (count == null) { // Map还没有这个字符数据
                    counts.put(b, 1);
                } else {
                    counts.put(b, count + 1);
                }
            }
            // 把每一个键值对转成一个 Node 对象，并加入到 nodes 集合
            for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
                nodes.add(new Node(entry.getKey(), entry.getValue()));
            }
            return nodes;
        }
    
        /**
         * 功能描述：通过List<Node>创建赫夫曼树
         *
         * @param nodes 待创建的节点
         * @return Node 创建完赫夫曼树的根节点
         * @author cakin
         * @date 2021/3/21
         */
        private static Node createHuffmanTree(List<Node> nodes) {
            while (nodes.size() > 1) {
                // 从小到大排序,
                Collections.sort(nodes);
                // 取出第一颗最小的二叉树
                Node leftNode = nodes.get(0);
                // 取出第二颗最小的二叉树
                Node rightNode = nodes.get(1);
                // 创建一颗新的二叉树,它的根节点没有 data,只有权值
                Node parent = new Node(null, leftNode.weight + rightNode.weight);
                parent.left = leftNode;
                parent.right = rightNode;
                // 将已经处理的两颗二叉树从nodes删除
                nodes.remove(leftNode);
                nodes.remove(rightNode);
                // 将新的二叉树，加入到nodes
                nodes.add(parent);
            }
            // nodes 最后的结点，就是赫夫曼树的根结点
            return nodes.get(0);
        }
    }
    
    /**
    * @className: HuffmanCode
    * @description: 赫夫曼节点
    * @date: 2021/3/21
    * @author: cakin
    */
    class Node implements Comparable<Node> {
        // 存放数据(字符)本身。比如'a' => 97 ' ' => 32
        Byte data;
        // 权值, 表示字符出现的次数
        int weight;
        // 左子树
        Node left;
        // 右子树
        Node right;
    
        public Node(Byte data, int weight) {
            this.data = data;
            this.weight = weight;
        }
    
        /**
         * 功能描述：实现 Node 从小到大的排序
         *
         * @param o 节点
         * @author cakin
         * @date 2021/3/21
         */
        @Override
        public int compareTo(Node o) {
            // 从小到大排序
            return this.weight - o.weight;
        }
    
        public String toString() {
            return "Node [data = " + data + " weight=" + weight + "]";
        }
    }

# 三 测试 #

40
    stringBuilder=1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100
    压缩后的结果是:[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28] 长度= 17