赫夫曼树应用-数据解压

àì夳堔傛蜴生んèń 2021-07-25 00:36 309阅读 0赞

# 一 需求 #

使用赫夫曼编码来解码数据，需要满足下面两点。

# 二 思路分析 #

1 上一篇博客得到了赫夫曼编码表和对应的编码。

\[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28\]。

2 现在要求使用赫夫曼编码进行解码，重新得到原来的字符串"i like like like java do you like a java"。

3 解码的过程，就是编码的一个逆向操作。

# 三 代码 #

package com.atguigu.huffmancode;
    
    import java.util.*;
    
    /**
    * @className: HuffmanCode
    * @description: 赫夫曼编码
    * @date: 2021/3/21
    * @author: cakin
    */
    public class HuffmanCode {
        /**
         * 功能描述：赫夫曼编码测试
         *
         * @param args 命令行
         * @author cakin
         * @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);
            byte[] sourceBytes = decode(huffmanCodes, huffmanCodesBytes);
            System.out.println("原来的字符串=" + new String(sourceBytes)); // "i like like like java do you like a java"
        }
    
        /**
         * 功能描述：完成对压缩数据的解码
         * 思路
         * 1 将 huffmanBytes [-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28] 先转成赫夫曼编码对应的二进制的字符串 "1010100010111..."
         * 2 将 赫夫曼编码对应的二进制的字符串 "1010100010111..." 对照赫夫曼编码表转化成 "i like like like java do you like a java"
         *
         * @param huffmanCodes 赫夫曼编码表
         * @param huffmanBytes 赫夫曼编码得到的字节数组
         * @return 原来的字符串对应的数组
         */
        private static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) {
            // 1 将 huffmanBytes [-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28] 先转成赫夫曼编码对应的二进制的字符串 "1010100010111..."
            StringBuilder stringBuilder = new StringBuilder();
            // 将byte数组转成二进制的字符串
            for (int i = 0; i < huffmanBytes.length; i++) {
                byte b = huffmanBytes[i];
                // 判断是不是最后一个字节
                boolean flag = (i == huffmanBytes.length - 1);
                // 根据是不是最后一个字节来来决定采用怎样的策略追加二进制的字符串
                stringBuilder.append(byteToBitString(!flag, b));
            }
            // 把字符串按照指定的赫夫曼编码表进行解码
            Map<String, Byte> map = new HashMap<>();
            // 把原来的赫夫曼编码表键值对进行调换。例如 a->100 转化成 100->a
            for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {
                map.put(entry.getValue(), entry.getKey());
            }
    
            // 创建要给集合，存放byte
            List<Byte> list = new ArrayList<>();
            // i 可以理解成索引,扫描 stringBuilder
            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 不动，让count移动，用来匹配一个编码
                    b = map.get(key); // 编码对应的字符
                    if (b == null) { // 没有匹配到
                        count++;
                    } else {
                        //匹配到
                        flag = false;
                    }
                }
                list.add(b);
                i += count;// i 直接移动到 count，用来匹配下一个编码
            }
            // 当for循环结束后，list 中就存放了所有的字符"i like like like java do you like a java"
            // 把 list 中的数据放入到byte[] 并返回
            byte b[] = new byte[list.size()];
            for (int i = 0; i < b.length; i++) {
                b[i] = list.get(i);
            }
            return b;
        }
    
        /**
         * 功能描述：把一个 byte 转成一个二进制的字符串
         *
         * @param b    传入的 byte
         * @param flag 标志是否需要补高位。如果是true，表示需要补高位，如果是false表示不需要补高位。如果是最后一个字节，无需补高位，其他情况需要补高位
         * @return b 对应的二进制的字符串，注意是按补码返回。
         */
        private static String byteToBitString(boolean flag, byte b) {
            // 使用变量保存 b
            int temp = b; // 将 b 转成 int
            // 如果是正数，还存在补高位
            if (flag) {
                temp |= 256; // 按位与。 例如： 256 | 1    转化成二进制   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;
            }
        }
    
        /**
         * 功能描述：封装赫夫曼编码步骤
         *
         * @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
    原来的字符串=i like like like java do you like a java