赫夫曼树应用-文件压缩

淩亂°似流年 2021-07-24 12:58 338阅读 0赞

# 一 需求 #

通过赫夫曼编码对文件的进行压缩。

具体要求如下：

给一个图片文件，要求对其进行无损压缩,看看压缩效果如何。

# 二 思路 #

1 读取文件。

2 得到赫夫曼编码表。

3 完成压缩。

# 三 代码 #

package com.atguigu.huffmancode;
    
    import java.io.FileInputStream;
    import java.io.FileOutputStream;
    import java.io.ObjectOutputStream;
    import java.io.OutputStream;
    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("压缩文件成功！");
        }
    
        /**
         * 功能描述: 文件压缩
         *
         * @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());
                }
            }
        }
    
        /**
         * 功能描述：封装赫夫曼编码步骤
         *
         * @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 + "]";
        }
    }

# 四 测试 #

压缩文件成功！