数据结构：赫夫曼编码

1. 基本介绍

赫夫曼编码是一种编码方式, 属于一种程序算法
赫夫曼编码是赫夫曼树在电讯通信中的经典的应用之一
赫夫曼编码广泛地用于数据文件压缩。其压缩率通常在20%～90%之间
赫夫曼码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，称之为最佳编码

2. 原理剖析

2.1 通信领域中信息的处理方式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 (包括空格)

2.2 通信领域中信息的处理方式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…
字符的编码都不能是其他字符编码的前缀，符合此要求的编码叫做前缀编码，即不能匹配到重复的编码

2.3 通信领域中信息的处理方式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 // 各个字符对应的个数
按照上面字符出现的次数构建一颗赫夫曼树, 次数作为权值
构成赫夫曼树的步骤：

从小到大进行排序, 将每一个数据，每个数据都是一个节点，每个节点可以看成是一颗最简单的二叉树
取出根节点权值最小的两颗二叉树
组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
再将这颗新的二叉树，以根节点的权值大小再次排序，不断重复 1-2-3-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
6）长度为： 133
说明:
原来长度是 359 , 压缩了 (359-133) / 359 = 62.9%
此编码满足前缀编码, 即字符的编码都不能是其他字符编码的前缀。不会造成匹配的多义性
赫夫曼编码是无损处理方案

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

在这里插入图片描述

3. 数据压缩(创建赫夫曼树)

将给出的一段文本，比如 “i like like like java do you like a java” ，根据前面的讲的赫夫曼编码原理，对其进行数据压缩处理，形式如 "1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110
"
步骤1：根据赫夫曼编码压缩数据的原理，需要创建 “i like like like java do you like a java” 对应的赫夫曼树.

    // 通过list创建赫夫曼树
    public 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;
            // 将已经处理的2颗二叉树从nodes中删除
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            // 将新的二叉树，加入到nodes
            nodes.add(parent);
        }
        // nodes最后的节点，就是赫夫曼树的根节点
        return nodes.get(0);
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

4. 数据压缩(生成赫夫曼编码和赫夫曼编码后的数据)

已经生成了赫夫曼树, 下面继续完成任务

生成赫夫曼树对应的赫夫曼编码 , 如下表:=01 a=100 d=11000 u=11001 e=1110 v=11011 i=101 y=11010 j=0010 k=1111 l=000 o=0011
使用赫夫曼编码来生成赫夫曼编码数据 ,即按照上面的赫夫曼编码，将"i like like like java do you like a java" 字符串生成对应的编码数据, 形式如下. 1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100

    // 赫夫曼树转赫夫曼编码
    public static Map<Byte, String> getCodes(Node root) {
        if (root == null) {
            return null;
        }
        // 处理左子树
        getCodes(root.left, "0", stringBuilder);
        // 处理右子树
        getCodes(root.right, "1", stringBuilder);
        return huffmanCodes;
    }

    public static void getCodes(Node node, String code, StringBuilder stringBuilder) {
        StringBuilder builder = new StringBuilder(stringBuilder);
        // 将code加入到builder
        builder.append(code);
        if (node != null) {
            // 判断当前node是叶子节点还是非叶子节点
            if (node.data == null) { // 非叶子节点
                // 递归处理
                // 向左递归
                getCodes(node.left, "0", builder);
                // 向右递归
                getCodes(node.right, "1", builder);
            } else { // 说明是叶子节点
                // 表示找到某个叶子节点的最后
                huffmanCodes.put(node.data, builder.toString());
            }

        }
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

5. 数据解压(使用赫夫曼编码解码)

使用赫夫曼编码来解码数据，具体要求是

前面我们得到了赫夫曼编码和对应的编码byte[] , 即:[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
现在要求使用赫夫曼编码，进行解码，又重新得到原来的字符串"i like like like java do you like a java"
解码过程，就是编码的一个逆向操作

    /**
     * 对压缩的数据进行解码
     *
     * @param huffmanCodes 赫夫曼编码表
     * @param huffmanBytes 赫夫曼编码后的字节数组
     * @return 原始的字符串数组
     */
    public static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) {
        // 1.先得到huffmanBytes对应的二进制字符串，形式如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));
        }
        // 把字符串安装指定的赫夫曼编码进行解码
        // 赫夫曼编码表进行调换，因为要反向查询 a->100 100->a
        Map<String, Byte> map = new HashMap<>();
        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) {
                // 1010100010111...
                // 递增的取出 key 1
                // i不动，让count移动，直到匹配到一个字符
                String key = stringBuilder.substring(i, 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 flag 标志是否需要补高位，如果是最后一个字节，不需要补高位，为false
     * @param b    传入的byte
     * @return 该b对应的二进制字符串（是按补码返回）
     */
    public static String byteToBitString(boolean flag, byte b) {
        // 使用变量保存b，将b转成int
        int temp = b;
        // 如果是正数，还存在补高位
        if (flag) {
            // 按位与 256，1 0000 0000 | 0000 0001 => 1 0000 0001
            temp |= 256;
        }
        // temp对应的二进制补码
        String str = Integer.toBinaryString(temp);
        if (flag) {
            return str.substring(str.length() - 8);
        } else {
            return str;
        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

6. 文件压缩

给你一个图片文件，要求对其进行无损压缩, 看看压缩效果如何。
思路：读取文件-> 得到赫夫曼编码表 -> 完成压缩


    /**
     * 文件压缩
     *
     * @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()];
            // 读取文件到b中
            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) {
            e.printStackTrace();
        } finally {
            try {
                is.close();
                oos.close();
                os.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

7. 文件解压(文件恢复)

将前面压缩的文件，重新恢复成原来的文件。
思路：读取压缩文件(数据和赫夫曼编码表)-> 完成解压(文件恢复)

    /**
     * 文件解压
     *
     * @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);
            // 读取byte数组 huffmanBytes
            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) {
            e.printStackTrace();
        } finally {
            try {
                os.close();
                ois.close();
                is.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

在这里插入图片描述

原始图片

在这里插入图片描述

解压后的图片

在这里插入图片描述

8. 完整代码

import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.OutputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class HuffmanCode {

    public static void main(String[] args) {

        String content = "i like like like java do you like a java";
        System.out.println("content length = " + content.length());
        byte[] contentBytes = content.getBytes();
        System.out.println(contentBytes.length);
        byte[] huffmanCodesBytes = huffmanZip(contentBytes);
        System.out.println("压缩后的结果是：" + Arrays.toString(huffmanCodesBytes) + " 长度 =" + huffmanCodesBytes.length);
        byte[] decode = decode(huffmanCodes, huffmanCodesBytes);
        System.out.println("原始的字符串：" + new String(decode));

        // 压缩文件
        String srcFile = "E:\\test\\111.jpg";
        String zipFile = "E:\\test\\111.zip";
        zipFile(srcFile, zipFile);
        System.out.println("完成压缩~~~");
        // 解压文件
        String dstFile = "E:\\test\\111-2.jpg";
        unZipFile(zipFile, dstFile);
        System.out.println("完成解压~~~");

    }

    public static byte[] huffmanZip(byte[] bytes) {
        List<Node> nodes = getNodes(bytes);
        // 根据nodes创建赫夫曼树
        Node huffmanTreeRoot = createHuffmanTree(nodes);
        huffmanTreeRoot.preOrder();
        // 对应的赫夫曼编码
        Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);
        // 根据生成的赫夫曼编码，压缩得到压缩后的赫夫曼编码字节数组
        return zip(bytes, huffmanCodes);
    }

    public static List<Node> getNodes(byte[] bytes) {
        List<Node> nodes = new ArrayList<>();
        // 遍历bytes，统计每一个byte出现的次数
        HashMap<Byte, Integer> counts = new HashMap<>();
        for (byte b : bytes) {
            Integer count = counts.get(b);
            if (count == null) {
                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创建赫夫曼树
    public 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;
            // 将已经处理的2颗二叉树从nodes中删除
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            // 将新的二叉树，加入到nodes
            nodes.add(parent);
        }
        // nodes最后的节点，就是赫夫曼树的根节点
        return nodes.get(0);
    }

    // 1.将赫夫曼编码表放在Map
    // 生成的赫夫曼编码表：{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<>();
    // 2.在生成赫夫曼编码表示，需要拼接路径，定义一个stringBuilder存储某个叶子节点的路径
    static StringBuilder stringBuilder = new StringBuilder();

    // 赫夫曼树转赫夫曼编码
    public static Map<Byte, String> getCodes(Node root) {
        if (root == null) {
            return null;
        }
        // 处理左子树
        getCodes(root.left, "0", stringBuilder);
        // 处理右子树
        getCodes(root.right, "1", stringBuilder);
        return huffmanCodes;
    }

    public static void getCodes(Node node, String code, StringBuilder stringBuilder) {
        StringBuilder builder = new StringBuilder(stringBuilder);
        // 将code加入到builder
        builder.append(code);
        if (node != null) {
            // 判断当前node是叶子节点还是非叶子节点
            if (node.data == null) { // 非叶子节点
                // 递归处理
                // 向左递归
                getCodes(node.left, "0", builder);
                // 向右递归
                getCodes(node.right, "1", builder);
            } else { // 说明是叶子节点
                // 表示找到某个叶子节点的最后
                huffmanCodes.put(node.data, builder.toString());
            }

        }
    }

    /**
     * 编写一个方法，将字符串对应的byte[]数组，通过生成的赫夫曼编码表，返回一个赫夫曼编码压缩后的byte[]
     *
     * @param bytes        原始的字符串对应的byte[]
     * @param huffmanCodes 生成的赫夫曼编码map
     * @return 返回赫夫曼编码处理后的byte[]
     * 举例： String content = "i like like like java do you like a java"; =》 byte[] contentBytes = content.getBytes();
     * 返回的是 字符串 "1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100"
     * 对应的 byte[] huffmanCodeBytes  ，即 8位对应一个 byte,放入到 huffmanCodeBytes
     */
    public 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));
        }
        //将 "1010100010111111110..." 转成 byte[]
        // 统计返回 byte[] huffmanCodeBytes长度
        int len;
        if (stringBuilder.length() % 8 == 0) {
            len = stringBuilder.length() / 8;
        } else {
            len = stringBuilder.length() / 8 + 1;
        }
        // 创建存储压缩后的byte数组
        byte[] huffmanCodeBytes = new byte[len];
        // 记录是第几个byte
        int index = 0;
        // 因为每8位对应一个byte，所以步长+8
        for (int i = 0; i < stringBuilder.length(); i += 8) {
            String strByte;
            // 不够8位
            if (i + 8 > stringBuilder.length()) {
                strByte = stringBuilder.substring(i);
            } else {
                strByte = stringBuilder.substring(i, i + 8);
            }
            // 将strByte转成一个byte，放入到huffmanCodeBytes
            huffmanCodeBytes[index] = (byte) Integer.parseInt(strByte, 2);
            index++;
        }
        return huffmanCodeBytes;
    }


    /**
     * 对压缩的数据进行解码
     *
     * @param huffmanCodes 赫夫曼编码表
     * @param huffmanBytes 赫夫曼编码后的字节数组
     * @return 原始的字符串数组
     */
    public static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) {
        // 1.先得到huffmanBytes对应的二进制字符串，形式如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));
        }
        // 把字符串安装指定的赫夫曼编码进行解码
        // 赫夫曼编码表进行调换，因为要反向查询 a->100 100->a
        Map<String, Byte> map = new HashMap<>();
        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) {
                // 1010100010111...
                // 递增的取出 key 1
                // i不动，让count移动，直到匹配到一个字符
                String key = stringBuilder.substring(i, 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 flag 标志是否需要补高位，如果是最后一个字节，不需要补高位，为false
     * @param b    传入的byte
     * @return 该b对应的二进制字符串（是按补码返回）
     */
    public static String byteToBitString(boolean flag, byte b) {
        // 使用变量保存b，将b转成int
        int temp = b;
        // 如果是正数，还存在补高位
        if (flag) {
            // 按位与 256，1 0000 0000 | 0000 0001 => 1 0000 0001
            temp |= 256;
        }
        // temp对应的二进制补码
        String str = Integer.toBinaryString(temp);
        if (flag) {
            return str.substring(str.length() - 8);
        } else {
            return str;
        }

    }

    /**
     * 文件压缩
     *
     * @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()];
            // 读取文件到b中
            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) {
            e.printStackTrace();
        } finally {
            try {
                is.close();
                oos.close();
                os.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }

    /**
     * 文件解压
     *
     * @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);
            // 读取byte数组 huffmanBytes
            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) {
            e.printStackTrace();
        } finally {
            try {
                os.close();
                ois.close();
                is.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

    }


    static 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;
        }


        @Override
        public int compareTo(Node o) {
            // 从小到大排序
            return this.weight - o.weight;
        }

        @Override
        public String toString() {
            return "Node{" + "data=" + data + ", weight=" + weight + '}';
        }

        // 前序遍历
        public void preOrder() {
            System.out.println(this);
            if (this.left != null) {
                this.left.preOrder();
            }
            if (this.right != null) {
                this.right.preOrder();
            }
        }
    }


}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387

9. 赫夫曼编码压缩文件注意事项

如果文件本身就是经过压缩处理的，那么使用赫夫曼编码再压缩效率不会有明显变化, 比如视频,ppt 等等文件 [举例压一个 .ppt]
赫夫曼编码是按字节来处理的，因此可以处理所有的文件(二进制文件、文本文件) [举例压一个.xml文件]
如果一个文件中的内容，重复的数据不多，压缩效果也不会很明显.

相关阅读:
kafka-listener
Redis集群配置
 SpringBoot配置文件和日志
 集美大学 - 2840 - 实验10和11 - 编程题
 elasticsearch高级篇：核心概念和实现原理
 Python入门都实践需要多长时间？|猿代码科技
 【5G MAC】RA-RNTI的计算过程
 VSCode python extension loading 终极解决方案
 SpringBoot+ShardingSphere彻底解决生产环境数据库字段加解密问题
 如何避免示波器电流探头损坏
原文地址：https://blog.csdn.net/qq_40977118/article/details/126805128

数据结构：赫夫曼编码

目录

1. 基本介绍

2. 原理剖析

2.1 通信领域中信息的处理方式1-定长编码

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

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

3. 数据压缩(创建赫夫曼树)

4. 数据压缩(生成赫夫曼编码和赫夫曼编码后的数据)

5. 数据解压(使用赫夫曼编码解码)

6. 文件压缩

7. 文件解压(文件恢复)

8. 完整代码

9. 赫夫曼编码压缩文件注意事项