赫夫曼编码实现二进制文件压缩解压

小咪咪 2022-12-30 08:03 199阅读 0赞

### 赫夫曼树基本介绍 ###

1、给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度(wpl)达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree), 还有的书翻译为霍夫曼树。

2、赫夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

赫夫曼树几个重要概念和举例说明

1、路径和路径长度：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1

2、结点的权及带权路径长度：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积

3、树的带权路径长度：树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL(weighted path length) ,权值越大的结点离根结点越近的二叉树才是最优二叉树。

4、WPL最小的就是赫夫曼树

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70][]

### 生成赫夫曼数的基本思路 ###

给你一个数列 \{13, 7, 8, 3, 29, 6, 1\}，要求转成一颗赫夫曼树.

构成赫夫曼树的步骤：

1、从小到大进行排序, 将每一个数据，每个数据都是一个节点 ， 每个节点可以看成是一颗最简单的二叉树

2、取出根节点权值最小的两颗二叉树

3、组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和

4、再将这颗新的二叉树，以根节点的权值大小 再次排序， 不断重复  1-2-3-4 的步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树

图解

\{13, 7, 8, 3, 29, 6, 1\}

1、排序 \{1, 3, 6, 7, 8, 13, 29\}

![20201224151818414.png][]

2、重新排序，重新构建新的树

![20201224152022530.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 2][]

以此类推........

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 3][]

代码实现

构建节点

class Node implements Comparable<Node>{
        public int value;
        public Node left;
        public Node right;
    
        public Node(int value){
            this.value = value;
        }
    
        public void preOrder(){
            System.out.println(this);
            if(this.left != null)
                this.left.preOrder();
            if(this.right != null)
                this.right.preOrder();
        }
    
        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    '}';
        }
    
        @Override
        public int compareTo(Node o) {
            return this.value - o.value;
        }
    }

创建赫夫曼树

public static Node createHuffmanTree(int[]arr){
            ArrayList<Node> nodes = new ArrayList<>();
            for (int i = 0; i < arr.length; i++) {
                nodes.add(new Node(arr[i]));
            }
            while(nodes.size() > 1){
                Collections.sort(nodes);
                Node left = nodes.get(0);
                Node right = nodes.get(1);
                Node parent = new Node(left.value + right.value);
                parent.left = left;
                parent.right = right;
                nodes.add(parent);
                nodes.remove(left);
                nodes.remove(right);
            }
            return nodes.get(0);
        }

### 赫夫曼编码 ###

1、赫夫曼编码也翻译为    哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式, 属于一种程序算法

2、赫夫曼编码是赫哈夫曼树在电讯通信中的经典的应用之一。

3、赫夫曼编码广泛地用于数据文件压缩。其压缩率通常在20%～90%之间

4、赫夫曼码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，称之为最佳编码

通信领域中信息的处理方式1-定长编码 i like like like java do you like a java       // 共40个字符(包括空格)

105 32 108 105 107 101 32 108 105 107 101 32 108 105 107 101 32 106 97 118 97 32 100 111 32 121 111 117 32 108 105 107 101 32 97 32 106 97 118 97  //对应Ascii码

01101001 00100000 01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101 00100000 01101010 01100001 01110110 01100001 00100000 01100100 01101111 00100000 01111001 01101111 01110101 00100000 01101100 01101001 01101011 01100101 00100000 01100001 00100000 01101010 01100001 01110110 01100001 //对应的二进制

按照二进制来传递信息，总的长度是  359   (包括空格)

[在线转码工具][Link 1]

通信领域中信息的处理方式2-变长编码

i like like like java do you like a java       // 共40个字符(包括空格)

d:1 y:1 u:1 j:2  v:2  o:2  l:4  k:4  e:4 i:5  a:5   :9  // 各个字符对应的个数 0=  ,  1=a, 10=i, 11=e, 100=k, 101=l, 110=o, 111=v, 1000=j, 1001=u, 1010=y, 1011=d  说明：按照各个字符出现的次数进行编码，原则是出现次数越多的，则编码越小，比如 空格出现了9 次， 编码为0 ,其它依次类推.

按照上面给各个字符规定的编码，则我们在传输  "i like like like java do you like a java" 数据时，编码就是 10010110100...

字符的编码都不能是其他字符编码的前缀，符合此要求的编码叫做前缀编码， 即不能匹配到重复的编码

通信领域中信息的处理方式3-赫夫曼编码

i like like like java do you like a java       // 共40个字符(包括空格)

d:1 y:1 u:1 j:2  v:2  o:2  l:4  k:4  e:4 i:5  a:5   :9  // 各个字符对应的个数 按照上面字符出现的次数构建一颗赫夫曼树, 次数作为权值.

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 4][]

//根据赫夫曼树，给各个字符 //规定编码 ， 向左的路径为0 //向右的路径为1 ， 编码如下:

o: 1000   u: 10010  d: 100110  y: 100111  i: 101 a : 110     k: 1110    e: 1111       j: 0000       v: 0001 l: 001          : 01

按照上面的赫夫曼编码，我们的"i like like like java do you like a java"   字符串对应的编码为 (注意这里我们使用的无损压缩) 1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110

长度为 ： 133

说明:

1、原来长度是  359 , 压缩了  (359-133) / 359 = 62.9%

2、此编码满足前缀编码, 即字符的编码都不能是其他字符编码的前缀。不会造成匹配的多义性

注意, 这个赫夫曼树根据排序方法不同，也可能不太一样，这样对应的赫夫曼编码也不完全一样，但是wpl 是一样的，都是最小的, 比如: 如果我们让每次生成的新的二叉树总是排在权值相同的二叉树的最后一个，则生成的二叉树为:

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 5][]

### 赫夫曼编码代码实现 ###

构建节点

class Node implements Comparable<Node>{
        public Byte data;
        public int weight;
        public Node left;
        public Node right;
    
        public Node(Byte data,int weight){
            this.data = data;
            this.weight = weight;
        }
    
        public void preOrder(){
            System.out.println(this);
            if (this.left != null)
                this.left.preOrder();
            if(this.right != null)
                this.right.preOrder();
        }
    
        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data +
                    ", weight=" + weight +
                    '}';
        }
    
        @Override
        public int compareTo(Node o) {
            return this.weight - o.weight;
        }
    }

1、将每个数据转换成一个节点，存放在List集合中

private static ArrayList<Node> getList(byte[]bytes){
            ArrayList<Node> nodes = new ArrayList<>();
            Map<Byte,Integer> map = new HashMap<>();
            for(byte b : bytes){
                Integer count = map.get(b);
                if(count == null){
                    map.put(b,1);
                }else
                    map.put(b,map.get(b) + 1);
            }
            //遍历map
            for(Map.Entry<Byte,Integer> entry : map.entrySet()){
                nodes.add(new Node(entry.getKey(),entry.getValue()));
            }
            return nodes;
        }

2、根据List集合获取哈夫曼树

private static Node createHuffmanTree(List<Node> nodes){
            while(nodes.size() > 1){
                Collections.sort(nodes);
                Node leftNode = nodes.get(0);
                Node rightNode = nodes.get(1);
                Node parent = new Node(null,leftNode.weight + rightNode.weight);
                parent.left = leftNode;
                parent.right = rightNode;
                nodes.remove(leftNode);
                nodes.remove(rightNode);
                nodes.add(parent);
            }
            return nodes.get(0);
        }

3、根据哈夫曼树获取哈夫曼编码表(这里使用了方法重载机制，方便传参)

static Map<Byte,String> huffmanCodes = new HashMap<>();
        static StringBuilder stringBuilder = new StringBuilder();
    
        private static Map<Byte,String> getCodes(Node root){
            if (root == null)
                return null;
            getCodes(root,"",stringBuilder);
            return huffmanCodes;
        }
    
        //根据哈夫曼树获得哈夫曼编码
        private static void getCodes(Node node,String code,StringBuilder stringBuilder){
            StringBuilder stringBuilder1 = new StringBuilder(stringBuilder);
            stringBuilder1.append(code);
            if(node.data == null) {//非叶子节点
                //向左递归
                getCodes(node.left,"0",stringBuilder1);
                //向右递归
                getCodes(node.right,"1",stringBuilder1);
            }else {
                huffmanCodes.put(node.data,stringBuilder1.toString());
            }
        }

4、根据原字节数组和哈夫曼编码表对数据进行压缩

private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
            StringBuilder builder = new StringBuilder();
            for(byte b : bytes){
                builder.append(huffmanCodes.get(b));
            }
            int length = (builder.length() + 7) / 8 ;
            byte[] by = new byte[length];
            int index = 0;
            String str;
            for (int i = 0; i < builder.length(); i += 8) {
                if((i + 8) > builder.length()){
                    str = builder.substring(i);
                    by[index] = (byte)Integer.parseInt(str,2);
                    index++;
                }else {
                    str = builder.substring(i, i + 8);
                    by[index] = (byte)Integer.parseInt(str,2);
                    index++;
                }
            }
            return by;
        }

5、为了方便后期的使用，对压缩进行一下封装

private static byte[] huffmanZip(byte[] bytes){
            //获取ArrayList<Node>集合
            ArrayList<Node> nodes = getList(bytes);
            //获取哈夫曼树
            Node root = createHuffmanTree(nodes);
            //获取哈夫曼编码表
            Map<Byte,String>huffmanCodes = getCodes(root);
            //压缩数据
            byte[]huffmanCodesBytes = zip(bytes,huffmanCodes);
            return huffmanCodesBytes;
        }

压缩后的哈夫曼字节数组是\[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28\]

### 解码（解压） ###

6、编写一个方法将字节转换成二进制，这里正数需要补全高八位，负数需要截取第八位补码，如果是最后一位，则不需要做任何操作，直接转换

/**
         * 将字节类型的十进制转换为二进制的字符串类型
         * @param flag 是否是最后一位，最后一位不需要补高位
         * @param b 带转换的字节
         * @return
         */
        private static String byteToBitString(boolean flag,byte b){
            int temp = b;
            if(flag){
                temp |= 256;//正数需要补高位；
            }
            String str = Integer.toBinaryString(temp);
            if(flag){
                return str.substring(str.length() - 8);
            }else
                return str;
        }

7、解压，这里先将哈夫曼编码字节数组转换成StringBuilder，然后将哈夫曼编码表反转得到解码表，然后对照解码表进行解码。并封装在List集合中

/**
         * 解压
         * @param huffmanCodesBytes 哈夫曼编码后的字节数组
         * @param huffmanCodes 哈夫曼编码表
         * @return 哈夫曼编码前的字节数组
         */
        public static byte[] deCode(byte[]huffmanCodesBytes,Map<Byte,String> huffmanCodes){
            boolean flag = true;
            StringBuilder builder = new StringBuilder();
            for (int i = 0; i < huffmanCodesBytes.length; i++) {
                byte b = huffmanCodesBytes[i];
                if(i == huffmanCodesBytes.length - 1)
                    flag = false;
                builder.append(byteToBitString(flag,b));
            }
            String str = builder.toString();
            //将hashMap反转
            Map<String,Byte> map = new HashMap<>();
            for (Map.Entry<Byte,String> entry : huffmanCodes.entrySet()){
                map.put(entry.getValue(),entry.getKey());
            }
            ArrayList<Byte> list = new ArrayList<>();
            int start = 0;
            int end = 1;
            while(start < str.length()){
                while(end < str.length() && map.get(str.substring(start,end)) == null){
                    end++;
                }
                list.add(map.get(str.substring(start,end)));
                start = end;
            }
            byte[] b = new byte[list.size()];
            for (int i = 0; i < b.length; i++) {
                if(list != null) {
                    b[i] = list.get(i);
                }
            }
            return b;
        }

测试

public static void main(String[] args) {
            String constant = "i like like like java do you like a java";
            System.out.println(constant);
            byte[] constantBytes = constant.getBytes();
            byte[] huffmanCodesBytes = huffmanZip(constantBytes);
            Map<Byte, String> huffmanCodes = getCodes(createHuffmanTree(getList(constantBytes)));
            byte[] sourceBytes = deCode(huffmanCodesBytes, huffmanCodes);
            System.out.println(new String(sourceBytes));
        }

![20201224154202997.png][]

可以看到编码前后完全一样，这就实现了整个压缩和解压过程

### 实践 ###

实现对二进制文件的压缩和解压

压缩

public static void zipFile(String srcFile,String dstFile){
            //创建输入流
            FileInputStream is = null;
            //创建输出流和对象输出流
            FileOutputStream os = null;
            ObjectOutputStream oos = null;
            try {
                is = new FileInputStream(srcFile);
                byte[] b = new byte[is.available()];
                is.read(b);
                os = new FileOutputStream(dstFile);
                oos = new ObjectOutputStream(os);
                byte[] huffmanBytes = huffmanZip(b);
                oos.writeObject(huffmanBytes);
                oos.writeObject(huffmanCodes);
            } catch (Exception e) {
                e.printStackTrace();
            }finally {
                try {
                    oos.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                try {
                    os.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                try {
                    is.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }

解压

public static void unZipFile(String zipFile,String dstFile){
            //创建输入流和对象输入流
            FileInputStream is = null;
            ObjectInputStream ois = null;
            //创建输出流
            FileOutputStream os = null;
            try {
                is = new FileInputStream(zipFile);
                ois = new ObjectInputStream(is);
                byte[] huffmanBytes = (byte[])ois.readObject();
                Map<Byte,String> huffmanCodes = (Map<Byte,String>)ois.readObject();
                byte[] bytes = deCode(huffmanBytes,huffmanCodes);
                os = new FileOutputStream(dstFile);
                os.write(bytes);
            } catch (Exception e) {
                e.printStackTrace();
            }finally {
                try {
                    os.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                try {
                    ois.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                try {
                    is.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }

测试

//测试压缩文件
            /*String srcFile = "d://src.bmp";
            String dstFile = "d://src.zip";
            zipFile(srcFile,dstFile);
            System.out.println("压缩成功！");*/
    
            //测试解压文件
            String zipFile = "d://src.zip";
            String dstFile = "d://src1.bmp";
            unZipFile(zipFile,dstFile);
            System.out.println("解压成功！");

![20201224155143141.png][]

压缩前后图片对比

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 6][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70]: /images/20221120/18ccf2b1f467483ab790a9bed37ac80f.png
[20201224151818414.png]: /images/20221120/80b2fcbe9fbf4b0babe9f7b4fbb9bcbf.png
[20201224152022530.png]: /images/20221120/dabd410be68a497bafdb186dd87fed9d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201224152226974.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201224152331765.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20201224152354147.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4,size_16,color_FFFFFF,t_70
[Link 1]: https://www.mokuge.com/tool/asciito16/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20201224153002361.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20201224153104606.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4,size_16,color_FFFFFF,t_70
[20201224154202997.png]: https://img-blog.csdnimg.cn/20201224154202997.png
[20201224155143141.png]: https://img-blog.csdnimg.cn/20201224155143141.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20201224155245540.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1Nzk2MjA4,size_16,color_FFFFFF,t_70