16、数据结构与算法 - 实战:哈夫曼树和哈夫曼编码

1、先掌握几个概念

先听一遍哈夫曼树的概念:给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度(WPL)达到最小,称这样的二叉树为最优二叉树,也成为哈夫曼树(Huffman Tree)。好的,知道你懵逼了,下面还是先学习几个概念。

1.1 什么是路径?

在一棵树中,从一个结点到另一个结点所经过的所有结点,成为两个结点之间的路径。
 
比如上图这颗二叉树,从根结点A到结点H的路径,就是A、B、D、H。

1.2 什么是路径长度?

在一棵树中,从一个结点到另一个结点所经过的“边”的数量,成为两个结点之间的路径长度。
 
比如从根结点A到叶子结点H,共经历了3个边,因此路径长度为3。

1.3 什么是结点的带权路径长度?

树的每一个结点,都可以拥有自己的权重(Weight),权重在不同算法中起到不同的作用。结点的带权路径长度指的是该结点的路径和权重的乘积。
 
比如,结点G的带权路径长度为:2×8=16。

1.4 什么是树的带权路径长度?

在一棵树中,所有叶子结点(强调:是叶子节点)的带权路径长度之和,称为树的带权路径长度,英文缩写为WPL。
 
 
比如上面这棵树的带权路径长度WPL=3×3+3×6+2×1+2×4+2×8=53。

2、哈夫曼树

2.1 概念

现在再听一遍哈夫曼树的概念:给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度(WPL)达到最小,称这样的二叉树为最优二叉树,也成为哈夫曼树(Huffman Tree)。这下懵逼程度已经减少了50%。下面用通俗的话来解释什么是哈夫曼树:
假设存在6个结点,这6个结点的权重从小到大排列分别为{1,3,4,6,8}。以这6个结点作为叶子结点的二叉树有无数个,比如下面随便凑两个:
 
树A和树B的叶子结点都是这6个结点的组合。那这跟哈夫曼树有什么关系呢?别急,我们先计算一下树A和树B的带权路径长度,计算可得树A的WPL为46,树B的WPL为53。数学验证这6个数字组成的二叉树最小WPL就是46,因此,树A就是哈夫曼树。
现在我们再来听一遍哈夫曼树的概念:给定n个权值作为n个叶子结点(例子里面的6个数字作为6个叶子结点),构造一棵二叉树,若该树的带权路径长度(WPL)达到最小(例子里的树A),称这样的二叉树为最优二叉树,也成为哈夫曼树(Huffman Tree)。这下懵逼程度已经减少到0了。
强调:一组结点构成的哈夫曼树可不止一棵,比如例子里的这6个结点,我改成一下三种树:
 
这三棵树都是这6个结点对应的哈夫曼树,因为WPL值相同且都是最小,但明显不是同一棵树。

2.2 图解构造哈夫曼树

构造哈夫曼树的过程很简单,小学生都看得懂。
比如有一个结点数组arr = {2,7,18,3,9,25},把每一个数字看成结点的权重。
第一步,根据权重大小从小到大排序{2,3,7,9,18,25}
 
第二步:,构建森林,把每一个叶子结点都当成一棵只有根结点的树,于是形成一个森林:
 
上图左边是辅助队列,按照权重大小存储,右边是叶子节点的森林。
第三步:借助辅助队列,找出最小权重的两个结点,明显就是辅助队列的前面两个,生成父结点,父节点的权重是这两个结点权重之和:
 
第四步:删除上一步选择的两个最小结点,把新的父结点加入到辅助队列中,并对辅助排列再次进行排列,以保证辅助队列是从小到大的:
 
循环操作第三步、第四步,直到辅助队列只剩下一个结点。
 
此时,辅助队列只有一个结点,说明整个森林已经合并成一棵树,而这棵树就是这以{2,7,18,3,9,25}为权重的6个结点所对应的哈夫曼树。对于这些中间生成的结点,是没有什么作用的,我们做这么多计算,只是为了获得路径:
 
反思:其实整个过程是计算{2,7,18,3,9,25}的最小WPL,本质就是计算每个数字的乘积因子。

2.3 代码实现

结点类:

package cn.klb.datastructures.tree;

/**
 * @author DDKK.COM 弟弟快看,程序员编程资料站
 * @Description: 二叉树结点类
 * @Date: Create in 2023/4/10 16:06
 * @Modified By:
 */
public class Node implements Comparable<Node> {
   
     
    public int id;  
    public String data;
    public Node left;
    public Node right;

    public Node(int id){
   
     
        this.id = id;
    }

    public Node(int id, String data) {
   
     
        this.id = id;
        this.data = data;
    }

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

    @Override
    public int compareTo(Node o) {
   
     
        return this.id - o.id;
    }
}

哈夫曼树类:

package cn.klb.datastructures.tree;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author DDKK.COM 弟弟快看,程序员编程资料站
 * @Description: 哈夫曼树
 * @Date: Create in 2023/4/15 15:36
 * @Modified By:
 */
public class HuffmanTree {
   
     

    private List<Node> nodes;

    public HuffmanTree(List<Node> nodes){
   
     
        this.nodes = nodes;
    }

    /**
     * 生成哈夫曼树
     *
     */
    public void generate() {
   
     
        // 当nodes剩下一个结点时,说明生成完毕
        while (nodes.size() > 1) {
   
     
            // 对结点列表进行升序排列
            Collections.sort(nodes);

            // 取出id最小的前两个结点(把结点看成没有子结点的二叉树)
            Node left = nodes.get(0);
            Node right = nodes.get(1);

            // 把取出的两个结点生成新的二叉树
            Node parent = new Node(left.id + right.id);
            parent.left = left;
            parent.right = right;

            // 删除这处理完的这两个结点
            nodes.remove(left);
            nodes.remove(right);

            // 把新的二叉树添加回去
            nodes.add(parent);
        }
    }

3、哈夫曼编码

3.1 背景

上面讲了一堆概念来介绍哈夫曼树,那么,哈夫曼树有什么作用呢?一个牛逼的作用就是哈夫曼编码。
比如有一句字符串:“i like like like java do you like a java”,总共40个字符(包括空格),那么,转成ASCII编码就是:[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],统计这个字节数组,其实总共有12种字节,用json来表示就是{32:9,97:5,100:1,101:4,117:1,118:2,105:5,121:1,106:2,107:4,108:4,111:2}。冒号前面表示某一种字节,冒号后面表示重复次数。如:32:9表示字节32出现了9次(ASCII的32表示空格,数一下字符串果然有9个空格)。
统计这个有什么用呢?仔细观察,如果我把32看成结点,把9看成这个结点的权。是不是就可以构造一个哈夫曼树了?然而这又有什么用呢?回顾刚才那句字符串,总共40个字节,如果传输的话,就传输40个字节。而计算机低层传输的就是0和1,那么总共传输40×8=320个二进制。
哈夫曼编码就是一种缩减每一个字符所占用的二进制位数,把重复频率高的字符用最少的二进制位表示。听到这里,是不是跟哈夫曼树联系上了?哈夫曼编码就是一种无损压缩编码。

3.2 原理

就用字符串"i like like like java do you like a java"来举例,如果不压缩,总共320个二进制位。那如何进行压缩呢?
首先统计每个字符出现的频率{32:9,97:5,100:1,101:4,117:1,118:2,105:5,121:1,106:2,107:4,108:4,111:2},这里总共12种字符,对应12种字节。我们把它看成12个结点,重复次数看成结点的权。然后对这12个结点构造出哈夫曼树,左路为0,右路为1,最后统计每一个叶子结点的路径,得到编码。
假设有一个哈夫曼树如下:
 
那么,A的编码为“1”,B的编码为“01”,C的编码为“00”。
根据这个原理,这12个结点生成的编码就为:{32=01, 97=100, 100=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011}
原来的字符串对应的二进制总共320位,经过哈夫曼编码后,变成1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100,共133个二进制位,压缩率为(320-133)/320=58%。
解码的时候只需要根据编码表进行解码,即可恢复原样,无损解压。

3.1 代码实现

3.1.1 构造结点类

package cn.klb.datastructures.huffman;

/**
 * @author DDKK.COM 弟弟快看,程序员编程资料站
 * @Description: 二叉树结点类
 * @Date: Create in 2023/4/10 16:06
 * @Modified By:
 */
public class Node implements Comparable<Node> {
   
     
    public int count;
    public Byte data;
    public Node left;
    public Node right;

    public Node(int count){
   
     
        this.count = count;
    }

    public Node(Byte data,int count) {
   
     
        this.count = count;
        this.data = data;
    }

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

    @Override
    public int compareTo(Node o) {
   
     
        return this.count - o.count;
    }
}

3.1.2 实现哈夫曼编码/解码的类

package cn.klb.datastructures.huffman;

/**
 * @author DDKK.COM 弟弟快看,程序员编程资料站
 * @Description: 实现哈夫曼编码
 * @Date: Create in 2023/4/16 16:35
 * @Modified By:
 */

import java.util.*;

public class Huffman {
   
     

    // 哈夫曼编码表
    // 在 generateCodingSchedule 方法中实例化
    private Map<Byte, String> encodeSchedule = new HashMap<Byte, String>();

    public Map<Byte, String> getEncodeSchedule() {
   
     
        return encodeSchedule;
    }

    /**
     * 对哈夫曼编码后的数组进行解码,返回解码后的字节数组
     *
     * @param target
     * @return
     */
    public byte[] unzip(byte[] target) {
   
     
        StringBuilder targetStringBuilder = new StringBuilder();
        // 遍历解压前的字节数组,把每个字节对应的二进制字符串拼接到 targetStringBuilder 中
        for (int i = 0; i < target.length; i++) {
   
     
            boolean isLast = (i == target.length - 1);// 是不是最后一个字节
            // 如果是最后一个字节,那么就不需要把最后一个字节高位的0补充完整
            targetStringBuilder.append(byteToBitString(!isLast, target[i]));
        }

        // 获取解码表
        Map<String, Byte> decodeSchedule = getDecodeSchedule();

        // 存放targetStringBuilder截取后的字节
        List<Byte> bytesList = new ArrayList<Byte>();
        int count; //  遍历targetStringBuilder的所有字符的计数器
        Byte b = null; // 临时存放匹配到的字节
        boolean notMached = true;    // 是否从targetStringBuilder中扫描到了可以匹配的二进制字符串
        // 遍历targetStringBuilder所有可能长度的子字符串
        for (int i = 0; i < targetStringBuilder.length(); i += count) {
   
     
            count = 1;
            notMached = true;
            b = null;
            while (notMached) {
   
     
                // key 会从1开始递增来扫描
                String key = targetStringBuilder.substring(i, i + count);
                b = decodeSchedule.get(key);    // 看这个 key 可不可以解码
                if (b == null) {
   
       // 解码表没有对应可解码
                    count++;    // 加长截取长度,然后再看一次能不能解码
                } else {
   
     
                    notMached = false;  // 匹配到了,可以解码了
                }
            }
            bytesList.add(b);
        }

        // 把list转成byte
        byte[] source = new byte[bytesList.size()];
        for (int i = 0; i < source.length; i++) {
   
     
            source[i] = bytesList.get(i);
        }

        return source;
    }

    /**
     * 获取解码表
     *
     * @return
     */
    public Map<String, Byte> getDecodeSchedule() {
   
     
        Map<String, Byte> decodeSchedule = new HashMap<String, Byte>();
        for (Map.Entry<Byte, String> entry : encodeSchedule.entrySet()) {
   
     
            decodeSchedule.put(entry.getValue(), entry.getKey());
        }
        return decodeSchedule;
    }

    /**
     * 对传进来的源字节数组进行哈夫曼编码,返回编码后的字节数组
     *
     * @param source
     * @return
     */
    public byte[] zip(byte[] source) {
   
     
        // 1.根据源字节数组生成 nodes
        List<Node> nodes = createNodes(source);

        // 2.nodes生成哈夫曼树
        generate(nodes);

        // 3.生成哈夫曼树对应的编码表
        generateEncodeSchedule(nodes);

        // 4.对源字节数组进行编码
        byte[] target = encoding(source, encodeSchedule);

        return target;
    }

    /**
     * 根据字节数组生成结点序列 nodes,其中 其中每一个node的data表示字节,count表示字节重复的次数
     * 比如字符串为:“I love my country”
     * 则,其中一个 node为:Node{count=2,data=121} 121的 ascii 对应 y
     *
     * @param bytes
     * @return nodes
     */
    private List<Node> createNodes(byte[] bytes) {
   
     
        List<Node> nodes = new ArrayList<Node>();

        // 用于临时统计
        // Byte表示字节
        // Integer 表示这个字节重复的次数
        Map<Byte, Integer> map = new HashMap<Byte, Integer>();

        // 遍历字节数组
        for (byte b : bytes) {
   
     
            Integer count = map.get(b); // 获取字节b对应的重复次数
            if (count == null) {
   
       // 如果字节b第一次出现,则现在新加入字节b
                map.put(b, 1);
            } else {
   
         // 字节 b不是第一次出现,说明又重复了一次
                map.put(b, count + 1);
            }
        }

        // 根据统计好的 map 生成 nodes
        for (Map.Entry<Byte, Integer> entry : map.entrySet()) {
   
     
            nodes.add(new Node(entry.getKey(), entry.getValue()));
        }
        return nodes;
    }

    /**
     * 调整nodes为哈夫曼树
     *
     * @param nodes
     * @return
     */
    private void generate(List<Node> nodes) {
   
     
        // 当nodes剩下一个结点时,说明生成完毕
        while (nodes.size() > 1) {
   
     
            // 先对结点列表进行升序排列
            Collections.sort(nodes);

            // 取出id最小的前两个结点(把结点看成没有子结点的二叉树)
            Node left = nodes.get(0);
            Node right = nodes.get(1);

            // 把取出的两个结点生成新的二叉树
            Node parent = new Node(left.count + right.count);
            parent.left = left;
            parent.right = right;

            // 删除这处理完的这两个结点
            nodes.remove(left);
            nodes.remove(right);

            // 把新的二叉树添加回去
            nodes.add(parent);
        }
    }

    /**
     * 获取哈夫曼树对应的编码表
     */
    private void generateEncodeSchedule(List<Node> nodes) {
   
     
        if (nodes.size() == 1) {
   
      // size == 1 才有可能是哈夫曼树
            if (encodeSchedule.size() == 0) {
   
      // 如果编码表键值对数量为0,说明没有编码过,执行编码
                // 临时存放叶子节点的路径
                StringBuilder accumulativeTag = new StringBuilder();
                // 处理根结点的左子树
                coding(nodes.get(0).left, '0', accumulativeTag, encodeSchedule);
                // 处理根结点的右子树
                coding(nodes.get(0).right, '1', accumulativeTag, encodeSchedule);
            }
        }
    }

    /**
     * 生成编码表
     *
     * @param node            准备处理的结点
     * @param tag             如果这个结点是其父节点的左结点,则为0,反之为1
     * @param accumulativeTag 走到这个结点所经历 tag 的累积拼接
     */
    private void coding(Node node, char tag, StringBuilder accumulativeTag, Map<Byte, String> codingSchedule) {
   
     
        StringBuilder path = new StringBuilder(accumulativeTag);
        path.append(tag);
        if (node != null) {
   
        // node不为空才处理
            if (node.data == null) {
   
       // data == null 说明该结点不是叶子结点
                // 向左递归
                coding(node.left, '0', path, codingSchedule);
                // 向右递归
                coding(node.right, '1', path, codingSchedule);
            } else {
   
       // data != null,说明这个node是叶子结点,可以收尾了
                codingSchedule.put(node.data, path.toString());
            }
        }
    }

    /**
     * 根据编码表对字节数组进行编码,返回编码后的字节数组
     *
     * @param source
     * @param codingSchedule
     * @return
     */
    private byte[] encoding(byte[] source, Map<Byte, String> codingSchedule) {
   
     
        StringBuilder targetStringBuilder = new StringBuilder();
        // 对待编码字节数组进行编码,编码后的二进制拼接成字符串
        for (byte b : source) {
   
     
            targetStringBuilder.append(codingSchedule.get(b));  // 对编码后的0101这些二进制转成字符串形式,方便后面截取
        }

        // 后面要把targetStringBuilder对应的字符串形式进行截取,每8个二进制装进一个byte中
        // 如果targetStringBuilder长度为12,那么len就为 (12+7)/8=2
        int len = (targetStringBuilder.length() + 7) / 8;

        byte[] targetBytes = new byte[len];
        int index = 0;
        // 把拼接好的字符串以8位为单位进行截取,把截取到的8位看成是一个字节
        String targetString;
        for (int i = 0; i < targetStringBuilder.length(); i += 8) {
   
     
            if (targetStringBuilder.length() < i + 8) {
   
        // 不够8位
                targetString = targetStringBuilder.substring(i);    // 截取剩余的所有
            } else {
   
     
                targetString = targetStringBuilder.substring(i, i + 8); // 截取8个
            }
            // 把strByte转成一个byte,放到encodedBytes中
            // 如果targetStringBuilder不是8的倍数,最后剩下如 0101四位,调用parseInt会把它当成 0000 0101
            // parseInt("1100110", 2) returns 102,而102的补码为 01100110,前面多了一个0,所以最后一个字节在解码的时候要特别小心
            targetBytes[index++] = (byte) Integer.parseInt(targetString, 2);
        }
        return targetBytes;
    }

    /**
     * 0xff默认为整形,二进制位最低8位是1111 1111,前面24位都是0;所以和0xff进行&运算后会变为int
     * toBinaryString方法有个毛病,就是二进制如果最高位为0,转为字符串时会被省略
     * 比如:00000000 00000000 00000000 10011101,调用toBinaryString方法后获得的字符串为 10011101
     * <p>
     * 如果 b = -88,根据计算机组成原理,-88 的原码为 1101 1000,反码为 1010 0111,补码为 1010 1000
     * 计算机保存数字保存的都是补码,所以 -88 计算机保存的其实是它的补码,为 1010 1000
     * 如果要杠,说你看到的就是原码,那你看到的其实是正数的补码,正数的原码反码和补码都是一样的
     * <p>
     * b & 0xFF 使得字节类型转为int类型,加 0x100 是为了兼容正数(负数加了也没影响,因为会截取掉)
     * 比如:b = 88,那么补码就是 0101 1000(正数的原码、反码、补码都一样)
     * 执行 b & 0xFF 后变成了 00000000 00000000 00000000 01011000
     * 上面说了 toBinaryString 会把前面的0全给省略了,所以执行 toBinaryString(b & 0xFF)会得到字符串 “1011000”
     * 但我们要的是 01011000,所以 b & 0xFF 加上 0x100后,会变成 00000000 00000000 00000001 01011000
     * 执行toBinaryString方法后就得到 “101011000”,然后再截取第一位后面的所有,得到 “01011000”
     *
     * @param flag 是否要一个完整的 8位二进制字节
     * @param b
     * @return
     */
    private String byteToBitString(boolean flag, byte b) {
   
     
        if (flag) {
   
     
            return Integer.toBinaryString((b & 0xFF) + 0x100).substring(1);
        } else {
   
     
            return Integer.toBinaryString((b & 0xFF));
        }
    }
}

3.1.3 测试类

    @Test
    public void testEncode() {
   
     
        String content = "i like like like java do you like a java";
        byte[] source = content.getBytes();
        Huffman huffman = new Huffman();
        byte[] target = huffman.zip(source);
        System.out.println("编码前:" + Arrays.toString(source));
        System.out.println("编码后:" + Arrays.toString(target));

        System.out.println("编码表:"+huffman.getEncodeSchedule());
        System.out.println("解码表:"+huffman.getDecodeSchedule());

        byte[] source1 = huffman.unzip(target);
        System.out.println("解码后:"+Arrays.toString(source1));
    }

注意:代码中private byte[] encoding(byte[] source, Map<Byte, String> codingSchedule)方法存在一个bug,当最后剩下的二进制位的从左到右第一个是0时,就会出问题。因时间关系,加上和哈夫曼编码知识点无关,有空再回来处理。