赫夫曼树应用-文件解压缩

深碍√TFBOYSˉ_ 2021-07-24 16:54 314阅读 0赞

# 一 需求 #

对上一篇博客用赫夫曼编码压缩的文件进行解压缩，恢复成原来的文件。

# 二 思路 #

1 压缩文件中包括数据和赫夫曼编码表。

2 读取压缩文件。

3 完成解码。

# 三 代码 #

package com.atguigu.huffmancode;
    
    import java.io.*;
    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 srcFile = "G://c1.png";
            // 压缩后的文件
            String dstFile = "G://c1.zip";
            // 压缩文件
            zipFile(srcFile, dstFile);
            System.out.println("压缩文件成功！");
    
            // 压缩后的文件
            String zipFile = "G://c1.zip";
            // 压缩前的文件
            String unzipFile = "G://c2.png";
            unZipFile(zipFile, unzipFile);
            System.out.println("解压成功!");
        }
    
        /**
         * 功能描述：用哈夫曼编码对压缩文件解压
         *
         * @param zipFile 已压缩的文件
         * @param dstFile 解压后的文件
         */
        public static void unZipFile(String zipFile, String dstFile) {
            // 文件输入流
            InputStream is = null;
            // 对象输入流
            ObjectInputStream ois = null;
            // 文件的输出流
            OutputStream os = null;
            try {
                // 文件输入流
                is = new FileInputStream(zipFile);
                // 和is关联的对象输入流
                ois = new ObjectInputStream(is);
                // 读取 huffmanBytes 到 byte数组
                byte[] huffmanBytes = (byte[]) ois.readObject();
                // 读取赫夫曼编码表
                Map<Byte, String> huffmanCodes = (Map<Byte, String>) ois.readObject();
                // 解码
                byte[] bytes = decode(huffmanCodes, huffmanBytes);
                // 将 bytes 数组写入到目标文件
                os = new FileOutputStream(dstFile);
                // 写数据到 dstFile 文件
                os.write(bytes);
            } catch (Exception e) {
                System.out.println(e.getMessage());
            } finally {
                try {
                    os.close();
                    ois.close();
                    is.close();
                } catch (Exception e2) {
                    System.out.println(e2.getMessage());
                }
            }
        }
    
        /**
         * 功能描述: 文件压缩
         *
         * @param srcFile 压缩前文件全路径
         * @param dstFile 压缩后文件全路径
         */
        public static void zipFile(String srcFile, String dstFile) {
            // 输出流
            OutputStream os = null;
            // 对象输出流
            ObjectOutputStream oos = null;
            // 文件的输入流
            FileInputStream is = null;
            try {
                // 文件的输入流
                is = new FileInputStream(srcFile);
                // 创建一个和源文件大小一样的byte[]
                byte[] b = new byte[is.available()];
                // 读取文件
                is.read(b);
                // 直接对源文件压缩
                byte[] huffmanBytes = huffmanZip(b);
                // 文件的输出流,用于存放压缩文件
                os = new FileOutputStream(dstFile);
                // 和文件输出流关联的 ObjectOutputStream
                oos = new ObjectOutputStream(os);
                // 以对象流的方式写入赫夫曼编码，是为了恢复源文件时使用
                // 把赫夫曼编码后的字节数组写入压缩文件
                oos.writeObject(huffmanBytes); //我们是把
                // 把赫夫曼编码表写入压缩文件
                oos.writeObject(huffmanCodes);
            } catch (Exception e) {
                System.out.println(e.getMessage());
            } finally {
                try {
                    is.close();
                    oos.close();
                    os.close();
                } catch (Exception e) {
                    System.out.println(e.getMessage());
                }
            }
        }
    
        /**
         * 功能描述：完成对压缩数据的解码
         * 思路
         * 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 + "]";
        }
    }

# 四 测试 #

压缩文件成功!
    解压成功!

解压后，文件大小和原来一样，说明哈夫曼压缩是无损压缩。

# 五 赫夫曼编码压缩文件注意事项 #

1 如果文件本身就是经过压缩处理的， 那么使用赫夫曼编码再压缩效率不会有明显变化, 比如视频、ppt 等等文件。

2 赫夫曼编码是按字节来处理的，因此可以处理所有的文件(二进制文件、文本文件)。

3 如果一个文件中的内容，重复的数据不多，压缩效果也不会很明显。