赫夫曼树的应用：赫夫曼编码（Java版实现）

赫夫曼编码 1、基本介绍

赫夫曼编码也翻译为：哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式,。也属于一种程序算法！赫夫曼码是可变字长编码(VLC)的一种。Huffman于1952 年提出一种编码方法，称之为最佳编码。

需要了解的是赫夫曼编码是赫哈夫曼树在电讯通信中的经典的应用之一。另外赫夫曼编码也广泛地用于数据文件压缩。其压缩率通常在20%～90%之间，大大减少了我们存储文件的空间。

赫夫曼树：

2、通信领域中信息处理的三种方式

方式1：定长编码。言外之意就是根据信息原有的长度和字符进行进制的转换，不做任何压缩！例如现有一段字符串：

String message = "i like like like java do you like a java"; // 共有40个字符（包括空格）

推荐在线转工具：http://www.ab126.com/goju/1711.html

把这段字符串按Ascii编码转为十进制就是

1053210810510710132108105107101321081051071013210697118973210011132121111117321081051071013297321069711897

把这段字符串按Ascii编码转为二进制就是

01101001001000000110110001101001011010110110010100100000011011000110100101101011011001010010000001101100011010010110101101100101001000000110101001100001011101100110000100100000011001000110111100100000011110010110111101110101001000000110110001101001011010110110010100100000011000010010000001101010011000010111011001100001

转为二进制后我们就可以通过网络进行讯息的传输！这种定长编码的缺点就是转成二进制后长度较大，传输效率较低！

---

方式2：可变长编码。变长编码简单理解就就是讯息转换成二进制时根据某种规则压缩，达到减小二进制长度效果！去提高传输效率。例如

String message = "i like like like java do you like a java"; // 共有40个字符（包括空格）

针对这一字符串，我们可以规定0= , 1=a, 10=i, 11=e, 100=k, 101=l, 110=o, 111=v, 1000=j, 1001=u, 1010=y, 1011=d。

然后统计各字符出现的次数：d->1, y->1, u->1, j->2, v->2, o->2, l->4, k->4, e->5, i->5, a->5, 空格->9

统计好后，就按照各个字符出现的次数进行编码，原则是出现的次数越多的，则编码越小，比如空格出现了9次，编码就设为0，其他由此类推！

按照以上规定的编码规则，这一字符串的编码就是：

10 0 101 10 100 …

可变长编码，可以有效的减少转码后二进制的长度，但是需要符合前缀编码才行！前缀编码：字符的编码都不能是其他字符编码的前缀，即不能匹配到重复的编码。

---

方式3：赫夫曼编码。可以说是利用赫夫曼树的特性对可变长编码的改进，也是此文要介绍编码方式！

3、赫夫曼编码的实现 3.1、构建赫夫曼树

还是以这段字符串为例

String message = "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->5, i->5, a->5, 空格->9。我们需要按照字符出现的次数构建一颗赫夫曼树，次数作为权值。

构建赫夫曼树的步骤：

1. 从小到大进行排序，将每一个数据，每个数据都是一个节点，每个节点可以看成是一颗最简单的二叉树
2. 取出根节点权值最小的两颗二叉树
3. 组成一颗新的二叉树，该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
4. 再将这颗新的二叉树，以根节点的权值大小再次排序，不断重复 1-2-3-4 的步骤，直到数列中，所有的数据都被处理，
   就得到一颗赫夫曼树

如下图所示：

3.2、给字符编码

根据赫夫曼树，给各个字符规定编码 (符合前缀编码并以节点所处的路径)，向左的路径为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

实际上赫夫曼编码表是根据赫夫曼树自动生成的（后面会有详细代码实现部分），根据赫夫曼编码编码规则

String message = "i like like like java do you like a java"; // 共有40个字符（包括空格）

这段字符串得到的最终二进制（无损压缩）为

10101001101111011110100110111101111010011011110111101000011000011100110011110000110
01111000100100100110111101111011100100001100001110

对比定长编码，我们发现赫夫曼编码编码方式转出来的二进制长度只有133。原来长度是 359，压缩了 (359-133) / 359 = 62.9%

备注：此编码规则满足前缀编码， 即字符的编码都不能是其他字符编码的前缀。不会造成匹配的多义性赫夫曼编码是无损处理方案

3.3、代码实现

经过前面的学习，我们已经知道了赫夫曼编码是怎样得出来的！只掌握原理远远不够，最终我们都要落实到代码中。

最佳实战：将以下字符串根据赫夫曼编码原理，对其进行数据压缩处理（转为二进制）。

String message = "i like like like java do you like a java"; // 共有40个字符（包括空格）

首先我们需要创建i like like like java do you like a java对应的赫夫曼树，大概思路如下

1. 有一个节点类Node {data（存放数据）, weight（权值）, left 和 right}
2. 得到i like like like java do you like a java对应的byte[]数组
3. 编写一个方法，将准备构建赫夫曼树的Node节点放到List，形式如 [Node[data=xxx,weight=xx]…]，体现d->1, y->1, u->1, j->2, v->2, o->2, l->4, k->4, e->5, i->5, a->5, 空格->9
4. 通过List构建赫夫曼树

package com.laizhenghua.demo.Huffman;

import java.util.*;


public class HuffmanCode {
    public static void main(String[] args) {
        String message = "i like like like java do you like a java"; // 共有40个字符（包括空格）
        byte[] messageBytes = message.getBytes(); // 得到由ASCII转码后的十进制编码

        

        List nodeList = getNodeList(messageBytes); // 拿到List，用于构建赫夫曼树

        // 创建赫夫曼树
        Node huffmanTreeRoot = createHuffmanTree(nodeList);

        huffmanTreePreOrder(huffmanTreeRoot); // 赫夫曼树前序遍历
    }

    
    public static List getNodeList(byte[] bytes) {
        List nodeList = new ArrayList();
        Map byteCount = new HashMap<>();
        // 1.统计每个字符出现的次数并以map进行存储
        for (byte b : bytes) {
            Integer num = byteCount.get(b);
            byteCount.put(b, num == null ? 1 : num + 1);
        }
        // System.out.println(byteCount);
        // 2.将map数据转为Node并添加到nodeList中
        for (Map.Entry entry : byteCount.entrySet()) {
            nodeList.add(new Node(entry.getKey(), entry.getValue()));
        }
        return nodeList;
    }

    
    public static Node createHuffmanTree(List nodeList) {
        Node parentNode = null;
        while(nodeList.size() > 1) {
            Collections.sort(nodeList); // 从小到大排序
            Node leftNode = nodeList.get(0); // 取出第一颗最小的二叉树
            Node rightNode = nodeList.get(1); // 取出第二颗最小的二叉树

            // 创建一颗新的二叉树，它的根节点没有data，只有权值
            parentNode = new Node(null, leftNode.weight + rightNode.weight);
            parentNode.left = leftNode;
            parentNode.right = rightNode;

            // 将意见处理的两颗二叉树从nodeList中删除
            nodeList.remove(leftNode);
            nodeList.remove(rightNode);

            // 将新的二叉树加入到nodeList中
            nodeList.add(parentNode);
        }
        return parentNode;
        // nodeList.get(0); nodeList的最后一个元素赫夫曼树的根节点
    }

    
    public static void huffmanTreePreOrder(Node huffmanTreeRootNode) {
        if (huffmanTreeRootNode == null) {
            System.out.println("赫夫曼树为空，无法遍历");
        } else {
            huffmanTreeRootNode.preOrder();
        }
    }
}

// 创建Node 存放数据和权值
class Node implements Comparable {
    Byte data; // 存放数据（字符本身），比如 "a" => 97, " " => 32
    Integer weight; // 权值（字符串出现的次数）
    Node left;
    Node right;
    public Node(Byte data, Integer 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 int compareTo(Node o) {
        // 从小到大排序
        return this.weight - o.weight;
    }

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

前面呢，我们已经生成了message字符串对应的赫夫曼树！这也是赫夫曼编码实现的第一步！接下来就是根据赫夫曼树生成赫夫曼编码和进行二进制转码。

根据赫夫曼树生成如下赫夫曼编码表：

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

记住编码原则，出现的次数越多，给定的编码值越小

生成赫夫曼树对应的赫夫曼编码思路分析：

1. 将赫夫曼编码表，存放到Map中，形式如32/空格 -> 01
2. 在生成赫夫曼编码表时，需要去拼接路径，定义一个StringBuilder存储某个叶子节点的路径

代码实现（基于以上代码新增）：

public static Map huffmanCodeTable = new HashMap<>();

public static StringBuilder codeString = new StringBuilder();


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


public static Map getHuffmanCodeTable(Node node) {
    if (node == null) {
        System.out.println("赫夫曼树为空，无法获取赫夫曼编码表！");
        return null;
    }
    getHuffmanCodeTable(node, "", codeString);
    return huffmanCodeTable;
}

在main方法中输出赫夫曼编码表

Map huffmanCodeTableMap = getHuffmanCodeTable(huffmanTreeRoot);
// 输出生成的赫夫曼编码表
System.out.println(huffmanCodeTableMap); // {32=01, 97=100, 100=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011}

赫夫曼编码表生成后，我们就可以进行转码处理了！编写一个方式，将字符串对应的byte[]数组，通过生成的赫夫曼编码表，返回一个赫夫曼编码压缩后的byte[]。也是在原有的代码上新增一个方法：

public static byte[] getHuffmanCodeZip(byte[] bytes, Map huffmanCodeTable) {
    // 1.根据赫夫曼编码表将byte转成赫夫曼对应的二进制
    StringBuilder stringBuilder = new StringBuilder();
    for (Byte b : bytes) {
        stringBuilder.append(huffmanCodeTable.get(b));
    }
    System.out.println(stringBuilder);
    // 1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100
    // 到这里，转码（无损压缩）工作已经完毕，但是我们得到的是StringBuilder类型的字符串，不能以这种方式去进行传输（反而把数据扩大了），所以我们还要转成byte数组

    // 2.将二进制字符串转成8位为一个元素的byte数组
    int length = 0;
    if (stringBuilder.length() % 8 == 0) {
        length = stringBuilder.length() / 8;
    } else {
        length = (stringBuilder.length() / 8) + 1;
    }
    byte[] codeBytes = new byte[length];
    int index = 0; // codeBytes 索引
    for (int i = 0; i < stringBuilder.length(); i += 8) {
        String substring = null;
        if (i + 8 > stringBuilder.length()) {
            substring = stringBuilder.substring(i);
        } else {
            substring = stringBuilder.substring(i, i + 8);
        }
        codeBytes[index] = (byte) Integer.parseInt(substring, 2);
        index++;
    }
    return codeBytes;
}

在main方法中测试

byte[] huffmanCode = getHuffmanCodeZip(messageBytes, huffmanCodeTable);
System.out.println(Arrays.toString(huffmanCode));
// [-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]

这是我们最终得到的赫夫曼编码！原始字符串长度有40，而我们最终得到的byte[]长度只有17。相当于压缩了50%左右，最后进行网络传输时，也就只用发送17byte，大大提升了传输效率！！！

4、赫夫曼解码的实现

以上数据的无损压缩称为编码，我们进行数据的传输，是通过字节传输，对方只收到[-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。

最佳实战：数据解压（使用赫夫曼编码解码），将前面得到的字节数组[-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。

解码过程就是编码的一个逆向操作，大概思路如下：

1. 将字节数组还原为赫夫曼编码对应的二进制字符串
2. 对照赫夫曼编码表将二进制字符串转成原来的字符串

代码实现（新增解码方法）：

public static byte[] deHuffmanCode(Map huffmanCodeTable, byte[] bytes) {
    // 1.获取字节数组对应的二进制字符串
    StringBuilder stringBuilder = new StringBuilder();
    for (int i = 0; i < bytes.length; i++) {
        boolean flag = (i == bytes.length - 1);
        String bitString = toBitString(!flag, bytes[i]);
        stringBuilder.append(bitString);
    }
    // System.out.println(stringBuilder.toString());

    // 2.根据赫夫曼编码表进行解码
    // 赫夫曼编码表映射关系反转
    Map huffmanCodeMap = new HashMap<>();
    for (Map.Entry entry : huffmanCodeTable.entrySet()) {
        huffmanCodeMap.put(entry.getValue(), entry.getKey());
    }
    // System.out.println(huffmanCodeMap);
    // 从二进制字符串中遍历获取对应的ASCII码，并保存到List中
    List byteList = new ArrayList<>();
    for (int i = 0; i < stringBuilder.length();) {
        int count = 1;
        boolean flag = true;
        Byte temp = null;
        while (flag) {
            String key = stringBuilder.substring(i, i + count);
            temp = huffmanCodeMap.get(key);
            if (temp == null) {
                count++;
            } else {
                flag = false;
            }
        }
        byteList.add(temp);
        i += count;
    }
    // System.out.println(byteList); [105, 97, 105, 107, 97, 108, 32, 107, 97, 108, 32, 107, 97, 106, 111, 101, 32, 97, 111, 101, 108, 101, 105, 106, 107, 117, 108, 106, 111, 101]
    byte[] byteArray = new byte[byteList.size()];
    for (int i = 0; i < byteList.size(); i++) {
        byteArray[i] = byteList.get(i);
    }
    return byteArray;
}


private static String toBitString(boolean flag, byte b) {
    int byteCode = b; // 临时变量，将b转成int
    // 如果是正数我们还存在补高位
    if (flag) {
        byteCode |= 256; // 按位于256 1 0000 0000 | 0000 0001 => 1 0000 0001
    }
    String binaryString = Integer.toBinaryString(byteCode); // 返回byteCode对应的二进制补码
    if (flag) {
        return binaryString.substring(binaryString.length() - 8);
    }
    return binaryString;
}

最后在main方法中测试：

// 注意：huffmanCode 是之前我们得到的赫夫曼编码字节数组
byte[] sourceByteCode = deHuffmanCode(huffmanCodeTable, huffmanCode);
System.out.println(new String(sourceByteCode)); // i like like like java do you like a java

5、赫夫曼编码压缩文件 5.1、压缩文件

我们学习了通过赫夫曼编码对一个字符串进行编码和解码，下面我们来完成对文件的压缩和解压。实现思路其实和压缩字符串相似，只是读取文件时增加了一些流的知识。

要求：给定一个图片！通过赫夫曼编码对其无损压缩。

大概思路：

1. 读取文件
2. 得到赫夫曼编码表
3. 完成压缩

完整代码：

package com.laizhenghua.demo.Huffman;

import java.io.*;
import java.util.*;


public class HuffmanFileCode {
    public static void main(String[] args) {
        String filePath = "F:\java\huffman-code\src\main\java\com\laizhenghua\demo\Huffman\test.bmp";
        String distPath = "F:\java\huffman-code\src\main\java\com\laizhenghua\demo\Huffman\src.zip";
        String message = zipFileByHuffmanCoding(filePath, distPath);
        System.out.println(message);
    }

    
    public static String zipFileByHuffmanCoding(String srcFilePath, String distFilePath) {
        FileInputStream inputStream = null;
        FileOutputStream outputStream = null;
        ObjectOutputStream oos = null; // 创建一个和文件输出流关联的ObjectOutputStream
        try {
            inputStream = new FileInputStream(srcFilePath);
            // 1.创建和源文件大小一致的byte数组
            byte[] fileBytes = new byte[inputStream.available()];
            // 2.读取文件
            inputStream.read(fileBytes);
            // 3.压缩文件
            byte[] huffmanBytes = enHuffmanCode(fileBytes);

            // 4.存放压缩文件
            outputStream = new FileOutputStream(distFilePath);
            oos = new ObjectOutputStream(outputStream);
            oos.writeObject(huffmanBytes); // 这里我们使用以对象流的方式写入 赫夫曼编码，是为了以后我们恢复源文件时使用
            // 注意：一定要要把赫夫曼编码表也写入到压缩文件中，后序恢复文件使用
            oos.writeObject(huffmanCodeTable);

            return "Success please see " + distFilePath;
        } catch (IOException e) {
            System.out.println(e.getMessage());
        } finally {
            if (inputStream != null) {
                try {
                    inputStream.close();
                } catch (IOException e) {
                    System.out.println(e.getMessage());
                }
            }
            if (outputStream != null) {
                try {
                    outputStream.close();
                } catch (IOException e) {
                    System.out.println(e.getMessage());
                }
            }
            if (oos != null) {
                try {
                    oos.close();
                } catch (IOException e) {
                    System.out.println(e.getMessage());
                }
            }
        }
        return "fail";
    }

    public static byte[] enHuffmanCode(byte[] bytes) {
        List nodeList = getNodeList(bytes);
        Node huffmanTreeRootNode = createHuffmanTree(nodeList);
        Map huffmanCodeTableMap = getHuffmanCodeTable(huffmanTreeRootNode);

        StringBuilder stringBuilder = new StringBuilder();
        for (Byte b : bytes) {
            stringBuilder.append(huffmanCodeTableMap.get(b));
        }
        int length = 0;
        if (stringBuilder.length() % 8 == 0) {
            length = stringBuilder.length() / 8;
        } else {
            length = (stringBuilder.length() / 8) + 1;
        }
        byte[] codeBytes = new byte[length];
        int index = 0; // codeBytes 索引
        for (int i = 0; i < stringBuilder.length(); i += 8) {
            String substring = null;
            if (i + 8 > stringBuilder.length()) {
                substring = stringBuilder.substring(i);
            } else {
                substring = stringBuilder.substring(i, i + 8);
            }
            codeBytes[index] = (byte) Integer.parseInt(substring, 2);
            index++;
        }
        return codeBytes;
    }
    
    public static Map huffmanCodeTable = new HashMap<>();
    
    public static StringBuilder codeString = new StringBuilder();

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

    
    public static Map getHuffmanCodeTable(Node node) {
        if (node == null) {
            System.out.println("赫夫曼树为空，无法获取赫夫曼编码表！");
            return null;
        }
        getHuffmanCodeTable(node, "", codeString);
        return huffmanCodeTable;
    }

    
    public static Node createHuffmanTree(List nodeList) {
        Node parentNode = null;
        while(nodeList.size() > 1) {
            Collections.sort(nodeList); // 从小到大排序
            Node leftNode = nodeList.get(0); // 取出第一颗最小的二叉树
            Node rightNode = nodeList.get(1); // 取出第二颗最小的二叉树

            // 创建一颗新的二叉树，它的根节点没有data，只有权值
            parentNode = new Node(null, leftNode.weight + rightNode.weight);
            parentNode.left = leftNode;
            parentNode.right = rightNode;

            // 将意见处理的两颗二叉树从nodeList中删除
            nodeList.remove(leftNode);
            nodeList.remove(rightNode);

            // 将新的二叉树加入到nodeList中
            nodeList.add(parentNode);
        }
        return parentNode;
        // nodeList.get(0); nodeList的最后一个元素赫夫曼树的根节点
    }

    
    public static List getNodeList(byte[] bytes) {
        List nodeList = new ArrayList();
        Map byteCount = new HashMap<>();
        // 1.统计每个字符出现的次数并以map进行存储
        for (byte b : bytes) {
            Integer num = byteCount.get(b);
            byteCount.put(b, num == null ? 1 : num + 1);
        }
        // System.out.println(byteCount);
        // 2.将map数据转为Node并添加到nodeList中
        for (Map.Entry entry : byteCount.entrySet()) {
            nodeList.add(new Node(entry.getKey(), entry.getValue()));
        }
        return nodeList;
    }
}

// 创建Node 存放数据和权值
class Node implements Comparable {
    Byte data; // 存放数据（字符本身），比如 "a" => 97, " " => 32
    Integer weight; // 权值（字符串出现的次数）
    Node left;
    Node right;
    public Node(Byte data, Integer 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 int compareTo(Node o) {
        // 从小到大排序
        return this.weight - o.weight;
    }

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

可更换文件地址，自行执行下代码！那么压缩效果如何呢？

亲测！换成其他文件形式，就没有明显的压缩效果。反而文件更大！后面5.3章节有解释！

5.2、解压文件

前面我们写的代码，把赫夫曼编码表也写入压缩文件里了。这是因为压缩文件的算法是我们自定义的，现有的解压工具是不能解压我们压缩过的文件。想要还原文件还需要我们自己根据赫夫曼编码表手动实现！

代码示例（在原有的代码上新增方法）：

public static String unZipFileByHuffmanCoding(String zipFilePath, String distFilePath) {
    InputStream inputStream = null;
    OutputStream outputStream = null;
    ObjectInputStream ois = null;
    try {
        inputStream = new FileInputStream(zipFilePath);
        ois = new ObjectInputStream(inputStream);
        // 读取byte数组 huffmanBytes
        byte[] huffmanBytes = (byte[]) ois.readObject();
        Map huffmanCodeTable = (Map) ois.readObject();

        // 解码
        byte[] sourceBytes = deHuffmanCode(huffmanCodeTable, huffmanBytes);
        // 将sourceBytes写入目标文件
        outputStream = new FileOutputStream(distFilePath);
        outputStream.write(sourceBytes);
        return "success";
    } catch (Exception e) {
        System.out.println(e.getMessage());
    } finally {
        if (inputStream != null) {
            try {
                inputStream.close();
            } catch (IOException e) {
                System.out.println(e.getMessage());
            }
        }
        if (outputStream != null) {
            try {
                outputStream.close();
            } catch (IOException e) {
                System.out.println(e.getMessage());
            }
        }
        if (ois != null) {
            try {
                ois.close();
            } catch (IOException e) {
                System.out.println(e.getMessage());
            }
        }
    }
    return "fail";
}


public static byte[] deHuffmanCode(Map huffmanCodeTable, byte[] bytes) {
    // 1.获取字节数组对应的二进制字符串
    StringBuilder stringBuilder = new StringBuilder();
    for (int i = 0; i < bytes.length; i++) {
        boolean flag = (i == bytes.length - 1);
        String bitString = toBitString(!flag, bytes[i]);
        stringBuilder.append(bitString);
    }
    // System.out.println(stringBuilder.toString());

    // 2.根据赫夫曼编码表进行解码
    // 赫夫曼编码表映射关系反转
    Map huffmanCodeMap = new HashMap<>();
    for (Map.Entry entry : huffmanCodeTable.entrySet()) {
        huffmanCodeMap.put(entry.getValue(), entry.getKey());
    }
    // System.out.println(huffmanCodeMap);
    // 从二进制字符串中遍历获取对应的ASCII码，并保存到List中
    List byteList = new ArrayList<>();
    for (int i = 0; i < stringBuilder.length();) {
        int count = 1;
        boolean flag = true;
        Byte temp = null;
        while (flag) {
            String key = stringBuilder.substring(i, i + count);
            temp = huffmanCodeMap.get(key);
            if (temp == null) {
                count++;
            } else {
                flag = false;
            }
        }
        byteList.add(temp);
        i += count;
    }
    byte[] byteArray = new byte[byteList.size()];
    for (int i = 0; i < byteList.size(); i++) {
        byteArray[i] = byteList.get(i);
    }
    return byteArray;
}


private static String toBitString(boolean flag, byte b) {
    int byteCode = b; // 临时变量，将b转成int
    // 如果是正数我们还存在补高位
    if (flag) {
        byteCode |= 256; // 按位于256 1 0000 0000 | 0000 0001 => 1 0000 0001
    }
    String binaryString = Integer.toBinaryString(byteCode); // 返回byteCode对应的二进制补码
    if (flag) {
        return binaryString.substring(binaryString.length() - 8);
    }
    return binaryString;
}

在main方法中测试：

public static void main(String[] args) {
    

    String srcFilePath = "F:\java\huffman-code\src\main\java\com\laizhenghua\demo\Huffman\src.zip";
    String distFilePath = "F:\java\huffman-code\src\main\java\com\laizhenghua\demo\Huffman\new.bmp";
    String message = unZipFileByHuffmanCoding(srcFilePath, distFilePath);
    System.out.println(message);
}

再来看解压后生成的文件！

5.3、压缩文件注意事项

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

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

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

END THANKS FOR WATCHING END