（11）《数据结构与算法》之赫夫曼树

阅读量：5234 次

发布时间：2019-06-14

本文共 29533 字，大约阅读时间需要 98 分钟。

在我们开始介绍赫夫曼树之前，我们先带入一个情景。你想发送一个文件给你朋友，但是文件太大，所以你决定将文件压缩，变小再发送。你有没有考虑文件是怎么压缩呢？作为程序员，没有考虑过这里使用的什么算法呢？赫夫曼编码就是其中的一种解决方法。

在介绍赫夫曼编码之前，我们先介绍先导知识——赫夫曼树

赫夫曼树

赫夫曼树，又称最优树，是一类带权路径长度最短的树。

定义： 假设有n个权值{$W_1,W_2...W_n$},试构造一个有n个叶子结点的二叉树，每个叶子结点带权为w,则其中带权路径长度WPL最小的二叉树称做最优二叉树或赫夫曼树

光看着定义，大部分人，肯定云里雾里的。接下来我们就好好解释下，什么叫做赫夫曼树。

首先我们了解两个基本概念：

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

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

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

$WPL= \sum_{k = 1} ^ {n} {W_k L_k}$最小的就是赫夫曼树

画图描述，更加直观

现在有3棵二叉树，都有4个结点，分别带权13， 7， 8， 3

第二棵树的WPL= 59，最小，故，为赫夫曼树。

赫夫曼树创建思路图解

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

思路分析

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

构成赫夫曼树的步骤

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

取出根节点权值最小的两棵二叉树

利用上面取出的两棵二叉树，组成一棵新的二叉树，该新的二叉树根节点的权值是这两棵二叉树根节点权值之和

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

接下来我们就开始写程序

import java.util.*;/** * 先导知识： *      1. String 类的方法 public byte[] getBytes() *          功能：使用平台的默认字符集将此 String 编码为 byte 序列，并将结果存储到一个新的 byte 数组中。即，将字符串 转化成 字符数组，便于操作 *      2. HashMap 
    
       类的方法 public V get(Object key) *          功能：返回指定键所映射的值；如果对于该键来说，此映射不包含任何映射关系，则返回 null。 *      3. Collecctions 类的 public static  void sort(List
     
       list) *          功能：根据元素的 自然顺序 对指定列表按升序进行排序。 * *//** * 功能：根据赫夫曼编码压缩的原理，需要创建"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 = '7', weight = '5']...], *      体现 d: 1, y: 1, u: 1, j: 2, v: 2, o: 2, l: 4, k: 4, k: 4, e: 4, i: 5, a: 5, (空格)：9 *      (4) 可以通过List创建对应的赫夫曼树 */public class HuffmanCode {    public static void main(String[] args) {        //(2) 得到"i like like like java do you like a java" 对应的byte[]数组        String content = "i like like like java do you like a java";        //如何计算出，content字符串中各个字符出现的频率，即，对应weight        //把字符串变成单个的字符        byte[] contentBytes = content.getBytes();        System.out.println(contentBytes.length);        List
      
        nodes = getNodes(contentBytes);        System.out.println("nodes = " + nodes);        //测试创建的二叉树        System.out.println("赫夫曼树");        Node huffmanTreeRoot = createHuffmanTree(nodes);        System.out.println("前序遍历");        huffmanTreeRoot.preOrder();         }    //前序遍历的方法    private static void preOrder(Node root) {        if (root != null) {            root.preOrder();        } else {            System.out.println("赫夫曼树为空");        }    }    //(3) 编写一个方法，将准备构建赫夫曼的Node 结点 放到List， 形式[Node[data = '7', weight = '5']...],    //体现 d: 1, y: 1, u: 1, j: 2, v: 2, o: 2, l: 4, k: 4, k: 4, e: 4, i: 5, a: 5, (空格)：9    /**     *     * @param bytes 接收字节数组     * @return 返回List 形式   [Node[data = '7', weight = 97]...]     */    private static List
       
         getNodes(byte[] bytes) {        //1. 创建一个ArrayList        ArrayList
        
          nodes = new ArrayList
         
          (); //遍历bytes， 统计每一个byte出现的次数 ->map[key, value] Map
          
            counts = new HashMap<>(); for (byte b : bytes) { Integer count = counts.get(b); if (count == null) { //Map还没有这个字符数据 //第一次，加入map counts.put(b, 1); } else { counts.put(b, count + 1); } } //！！！重点，难点！！！ //把每一个键值对转成一个Node 对象，并加入到nodes集合 //遍历map for (Map.Entry
           
             entry : counts.entrySet()) { nodes.add(new Node(entry.getKey(), entry.getValue())); } return nodes; } //(4) 可以通过List创建对应的赫夫曼树 /** * * @param nodes List类的结点 集合 * @return */ private static Node createHuffmanTree(List
            
              nodes) { while (nodes.size() > 1) { //排序,从小到大 Collections.sort(nodes); //取出第一棵最小的二叉树 Node leftNode = nodes.get(0); //取出第二小的二叉树 Node rightNode = nodes.get(1); //创建一个新的二叉树，它的根结点parent，没有data，只有权值weight Node parent = new Node(null, leftNode.weight + rightNode.weight); parent.left = leftNode; parent.right = rightNode; //将已经处理的两个二叉树从nodes删除。nodes 是 List 类型 nodes.remove(leftNode); nodes.remove(rightNode); //将新的二叉树加入到nodes， nodes.add(parent); } //nodes 最后的结点，就是赫夫曼树的根结点 return nodes.get(0); }}//(1) Node{data (存放数据)， weight(权值)， left， right}//创建Node，带数据和权值//接口Comparable
             
               对Node类型的数据进行比较class Node implements Comparable
              
                { //存放数据（字符）本身，比如'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) { //Node类型的数据从小到大排序 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(); } }}

以上即是构成赫夫曼树的程序。

接下来我们就开始介绍赫夫曼编码

赫夫曼编码

基本介绍

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

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

赫夫曼码是可变字长编码(VLC)的一种。

原理剖析

定长编码

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 (包括空格)

变长编码

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...

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

赫夫曼编码

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 ，编码如下:
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

　说明:

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

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

注意事项

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

在这里插入图片描述

接下来我们开始进行实际应用

根据赫夫曼编码编码原理对字符串"i like like like java do you like a java" ，对其进行数据压缩处理，形式如 1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110，最后得到，十进制数组 [-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]。但是这并不是结束，因为压缩之后，必定也需要解压。解压的过程就是将 [-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： 根据赫夫曼编码压缩数据的原理，需要创建 "i like like like java do you like a java" 对应的赫夫曼树.

步骤2

生成赫夫曼树对应的赫夫曼编码 , 如下表: （空格） =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

再将取得的字符串，每取8位，获得十进制数组[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]，例如：1010 1000(负数补码)=》源码 1101 1000 =》十进制 -88
步骤3

将压缩后的结果[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28],重新先转成赫夫曼编码对应的二进制字符串“1010100010111...”

将赫夫曼编码对应的二进制的字符串"1010100010111..." =》对照赫夫曼编码 =》"i like like like java do you like a java"

具体代码实现

import java.util.*;/** *  压缩 =》 解压 */ public class HuffmanCode {    public static void main(String[] args) {        //(2) 得到"i like like like java do you like a java" 对应的byte[]数组        String content = "i like like like java do you like a java";        //如何计算出，content字符串中各个字符出现的频率，即，对应weight        //把字符串变成单个的字符        byte[] contentBytes = content.getBytes();        System.out.println(contentBytes.length);        byte[] huffmanCodeBytes = huffmanZip(contentBytes);        System.out.println("压缩后的结果huffmanCodeBytes = " + Arrays.toString(huffmanCodeBytes));        System.out.println("长度 = " + huffmanCodeBytes.length);                /**         *  数据压缩已经完成，那么解压怎么操作呢？         */        //测试 byteToBitString方法        System.out.println("===========================================================");//        byteToBitString((byte)-1);        //但是当输入为 1 时，就会出现新的问题，StringIndexOutOfBoundsException: String index out of range: -7//        byteToBitString((byte) 1);        byte[] sourceBytes =decode(huffmanCodes,huffmanCodeBytes);        System.out.println("原来的字符串 = " + new String(sourceBytes) );        //输出：原来的字符串 = i like like like java do you like a java    }    //完成数据的解压    //思路    //1. 将压缩后的结果huffmanCodeBytes = [-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]    //    重新先转成 赫夫曼编码对应的二进制字符串“1010100010111...”    //2. 将赫夫曼编码对应的二进制的字符串"1010100010111..." => 对照 赫夫曼编码 =》"i like like like java do you like a java"    /**     *     * @param huffmanCodes 赫夫曼编码表 Map     * @param huffmanBytes 赫夫曼编码得到的字节数组     * @return 就是原来的字符串对应的数组     */    //编写一个方法完成对压缩数据的解码    private static byte[] decode(Map
    
     huffmanCodes, byte[] huffmanBytes) {        //1. 先得到huffmanBytes 对应的 二进制的字符串，形式如"1010100010111..."        StringBuilder stringBuilder = new StringBuilder();        //将byte数组,形式如：[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]，转成二进制的字符串        for (int i = 0; i < huffmanBytes.length; i++) {            byte b = huffmanBytes[i];            //判断是不是最后一个字节            boolean flag = (i == huffmanBytes.length - 1);            stringBuilder.append(byteToBitString(!flag, b));        }        System.out.println("赫夫曼字节数组对应的二进制字符串 = " + stringBuilder.toString());        //把字符串按照指定的赫夫曼编码进行解码        //把赫夫曼编码表进行调换，因为反向查询 97 =》 100 100 -> a        Map
     
       map = new HashMap
      
       ();        for (Map.Entry
       
         entry : huffmanCodes.entrySet()) {            map.put(entry.getValue(), entry.getKey());        }        //创建一个集合，存放byte        List 
        
          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 b     * @param flag 标志是否需要补高位。如果是true， 表示需要补高位；如果是false表示不补。如果是最后一个字节，无需补高位     * @return 是该b 对应二进制的字符串，（注意是按补码返回）     */    private static String byteToBitString(boolean flag, byte b) {        //使用变量保存b,将b 转成 int        int temp = b;        //如果是正数，还存在补高位的问题        if (flag) {            // temp 按位与 256 ， 假如temp = 1， 1 0000 0000 | 0000 0001 =》 1 0000 0001            /**             * 为什么要存在 temp |= 256;?             *  huffmanBytes 存在 负数 和 正数。负数转化成二进制补码是8位，但是 正数 转成 二进制 并不一定是 8位，比如 77，这个数，转化成二进制位 100 1101             *  根据赫夫曼压缩程序可知， 压缩后的数据 77 是取压缩后的二进制字符数组的 8位而得来， 所以我们在将77 重新转为而二进制时，每一位（包括高位的0）均不可省略             *  所以，我们 将 77 | 256 得到 1 0100 1101 ，再取后8位，这样就可以得到77 完整的二进制数             *             *  可能你又要问，为什么在flag为 true，即，不是最后一个数的时候，执行temp |= 256;？             *   同样，我们要看压缩的时候，是怎么取二进制数，并将其转为 byte 数的。我们就会发现，就算最后一位数的二进制数，不满8位，也不影响，因为压缩的时候就没有取 8位             */            temp |= 256;        }        String str = Integer.toBinaryString(temp);        if (flag) {            System.out.println("str = " + str);            //输出结果：str = 11111111111111111111111111111111            //但是我们只要后8位即可            System.out.println("str = " + str.substring(str.length() - 8));            //输出结果：str = 11111111        } else {            return str;        }        return str.substring(str.length() - 8);    }    //使用一个方法，将面前的方法封装起来，便于我们的调用    /**     *     * @param contentBytes 原始的字符串对应的字节数组     * @return 是经过赫夫曼编码后的字节数组（压缩后的数据）     */    private static byte[] huffmanZip(byte[] contentBytes) {        List
         
           nodes = getNodes(contentBytes); //根据nodes创建赫夫曼树 Node huffmaTreeRoot = createHuffmanTree(nodes); //生成对应的哈夫曼编码(根据赫夫曼树) Map
          
            huffmanCodes = getCodes(huffmaTreeRoot); //根据生成的赫夫曼编码压缩得到压缩后的赫夫曼编码字节数组 byte[] huffmanCodeBytes = zip(contentBytes,huffmanCodes); return huffmanCodeBytes; } //编写一个方法，将一个字符串对应的byte[] 数组，通过生成的赫夫曼编码表，返回一个赫夫曼编码 压缩后的byte数组 /** * * @param bytes 原始的字符串对应的byte[]，即，对应程序中的contentBytes * @param huffmanCodes 生成的赫夫曼编码Map * @return 返回赫夫曼编码处理后的byte[] ， * 举例：String content = "i like like like java do you like a java"; =》 byte[] contentBytes = content.getBytes(); * 返回的字符串是：1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110 * =》 对应的byte[] huffmanCodeBytes , 即 8位对应一个byte， 放入huffmanCodeBytes * huffmanCodeBytes[0] = 1010 1000(补码)=》源码 1101 1000 =》 十进制 -88 * huffmanCodeBytes[1] */ private static byte[] zip(byte[] bytes, Map
           
             huffmanCodes) { //1. 先利用huffmanCodes 将 bytes 转成 赫夫曼编码对应的字符串 StringBuilder stringBuilder = new StringBuilder(); //遍历bytes 数组 for (byte b : bytes) { stringBuilder.append(huffmanCodes.get(b)); } System.out.println("生成的赫夫曼编码表stringBuilder = " + stringBuilder); //将字符串“101010011011...” 转成 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; } //创建huffmanCodeBytes //创建 存储压缩后的 byte 数组 byte[] huffmanCodeBytes = new byte[len]; //记录第几个byte int index = 0; for (int i = 0; i < stringBuilder.length(); i += 8 ) { //因为是每8位 对应一个byte，所以步长 +8 String strByte; if (i + 8 > stringBuilder.length()) { //不够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; } //生成的赫夫曼树对应的赫夫曼编码 /** * 思路： * 1. 将赫夫曼编码表放在Map
            
              形式如下： * （空格）= 01， a = 100, d = 1100, u = 11001, e = 1110, v = 11011, i = 101 * y = 11010, j = 0010, k = 1111, l = 000, o = 0011 * 2. 在生成赫夫曼编码表时，需要创建拼接路径，定义一个StringBuilder，存储某个叶子结点的路径 * */ static Map
             
               huffmanCodes = new HashMap
              
               (); static StringBuilder stringBuilder = new StringBuilder(); //调用方便，我们重载getCodes private static Map
               
                 getCodes(Node root) { if (root == null) { return null; } //处理root的左子树 getCodes(root.left, "0", stringBuilder); //处理root的右子树 getCodes(root.right, "1", stringBuilder); return huffmanCodes; } /** * 功能：将传入的node结点的所有叶子结点的赫夫曼编码得到，并放入huffmanCodes集合 * @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); //如果node == null 则不处理 if (node != null) { //判断当前node 是叶子结点还是非叶子结点 if (node.data == null) { //非叶子结点 //递归处理 //向左递归 getCodes(node.left, "0", stringBuilder2); //向右递归 getCodes(node.right, "1", stringBuilder2); } else { //说明是个叶子结点 //表示找到了叶子结点的最后 huffmanCodes.put(node.data, stringBuilder2.toString()); } } } //前序遍历的方法 private static void preOrder(Node root) { if (root != null) { root.preOrder(); } else { System.out.println("赫夫曼树为空"); } } //(3) 编写一个方法，将准备构建赫夫曼的Node 结点 放到List， 形式[Node[data = '7', weight = '5']...], //体现 d: 1, y: 1, u: 1, j: 2, v: 2, o: 2, l: 4, k: 4, k: 4, e: 4, i: 5, a: 5, (空格)：9 /** * * @param bytes 接收字节数组 * @return 返回List 形式 [Node[data = '7', weight = 97]...] */ private static List
                
                  getNodes(byte[] bytes) { //1. 创建一个ArrayList ArrayList
                 
                   nodes = new ArrayList
                  
                   (); //遍历bytes， 统计每一个byte出现的次数 ->map[key, value] Map
                   
                     counts = new HashMap<>(); for (byte b : bytes) { Integer count = counts.get(b); if (count == null) { //Map还没有这个字符数据 //第一次，加入map counts.put(b, 1); }else { counts.put(b, count + 1); } } //把每一个键值对转成一个Node 对象，并加入到nodes集合 //遍历map for (Map.Entry
                    
                      entry : counts.entrySet()) { nodes.add(new Node(entry.getKey(),entry.getValue())); } return nodes; } //(4) 可以通过List创建对应的赫夫曼树 private static Node createHuffmanTree(List
                     
                       nodes) { while (nodes.size() > 1) { //排序,从小到大 Collections.sort(nodes); //取出第一棵最小的二叉树 Node leftNode = nodes.get(0); //取出第二小的二叉树 Node rightNode = nodes.get(1); //创建一个新的二叉树，它的根结点parent，没有data，只有权值weight 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); }}//(1) Node{data (存放数据)， weight(权值)， left， right}//创建Node，带数据和权值//接口Comparable
                      
                        对Node类型的数据进行比较class Node implements Comparable
                       
                        { //存放数据（字符）本身，比如'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) { //Node类型的数据从小到大排序 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(); } }}

赫夫曼编码应用：文件压缩与解压

代码

注意： 文件压缩的代码是直接在上面代码的基础上写的，所以，有很多残留的的注释。所以，本文的三个代码最好先从第一个开始看起

import java.io.*;import java.util.*;/** * 实际应用：将 文件 压缩 */public class HuffmanCode {    public static void main(String[] args) {        //测试压缩文件        String srcFile = "E:\\1学习\\程序\\Data-Structures(java)\\src.bmp";        String dstFile = "E:\\1学习\\程序\\Data-Structures(java)\\dst.zip";        zipFile(srcFile, dstFile);        System.out.println("压缩文件成功");//        //测试解压文件//        String zipFile = "E:\\\\1学习\\\\程序\\\\Data-Structures(java)\\\\dst.zip";//        String dstFile = "E:\\\\1学习\\\\程序\\\\Data-Structures(java)\\\\src2.bmp";//        unZipFile(zipFile, dstFile);//        System.out.println("解压成功");    }    //编写一个方法完成对压缩文件的解压    /**     * @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
    
      huffumanCodes = (Map
     
      ) ois.readObject();            //解码            byte[] bytes = decode(huffumanCodes, 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();            }        }    }    //编写方法， 将一个文件进行压缩    /**     * @param srcFile 传入的希望压缩的文件的全路径     * @param dstFile 我们压缩后将压缩文件放到哪个文件目录下     */    public static void zipFile(String srcFile, String dstFile) {        //创建输出流        OutputStream os = null;        //创建文件的输出流的对象        //！！！关键        ObjectOutputStream oos = null;        //创建文件的输入流        FileInputStream fis = null;        try {            //创建一个文件的输入流            fis = new FileInputStream(srcFile);            //创建一个和源文件大小一样的byte[]            byte[] b = new byte[fis.available()];            //读取文件            fis.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 {                fis.close();                oos.close();                os.close();            } catch (Exception e) {                System.out.println(e.getMessage());            }        }    }    /**     * @param huffmanCodes 赫夫曼编码表 Map     * @param huffmanBytes 赫夫曼编码得到的字节数组     * @return 就是原来的字符串对应的数组     */    //编写一个方法完成对压缩数据的解码    private static byte[] decode(Map
      
        huffmanCodes, byte[] huffmanBytes) {        //1. 先得到huffmanBytes 对应的 二进制的字符串，形式如"1010100010111..."        StringBuilder stringBuilder = new StringBuilder();        //将byte数组,形式如：[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]，转成二进制的字符串        for (int i = 0; i < huffmanBytes.length; i++) {            byte b = huffmanBytes[i];            //判断是不是最后一个字节            boolean flag = (i == huffmanBytes.length - 1);            stringBuilder.append(byteToBitString(!flag, b));        }//        System.out.println("赫夫曼字节数组对应的二进制字符串 = " + stringBuilder.toString());        //把字符串按照指定的赫夫曼编码进行解码        //把赫夫曼编码表进行调换，因为反向查询 97 =》 100 100 -> a        Map
       
         map = new HashMap
        
         ();        for (Map.Entry
         
           entry : huffmanCodes.entrySet()) { map.put(entry.getValue(), entry.getKey()); } //创建一个集合，存放byte List
          
            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 b * @param flag 标志是否需要补高位，如果是true， 表示需要补高位，如果是false表示不补.如果是最后一个字节，无需补高位 * @return 是该b 对应二进制的字符串，（注意是按补码返回） */ private static String byteToBitString(boolean flag, byte b) { //使用变量保存b,将b 转成 int int temp = b; //如果是正数，还存在补高位的问题 if (flag) { // temp 按位与 256 ， 假如temp = 1， 1 0000 0000 | 0000 0001 =》 1 0000 0001 temp |= 256; } String str = Integer.toBinaryString(temp); if (flag) {// System.out.println("str = " + str); //输出结果：str = 11111111111111111111111111111111 //但是我们只要后8位即可// System.out.println("str = " + str.substring(str.length() - 8)); //输出结果：str = 11111111 } else { return str; } return str.substring(str.length() - 8); } //使用一个方法，将面前的方法封装起来，便于我们的调用 /** * @param contentBytes 原始的字符串对应的字节数组 * @return 是经过赫夫曼编码后的字节数组（压缩后的数据） */ private static byte[] huffmanZip(byte[] contentBytes) { //根据数组创造结点 List
           
             nodes = getNodes(contentBytes); //根据nodes创建赫夫曼树 Node huffmaTreeRoot = createHuffmanTree(nodes); //生成对应的哈夫曼编码(根据赫夫曼树) Map
            
              huffmanCodes = getCodes(huffmaTreeRoot); //根据生成的赫夫曼编码压缩得到压缩后的赫夫曼编码字节数组 byte[] huffmanCodeBytes = zip(contentBytes, huffmanCodes); return huffmanCodeBytes; } //编写一个方法，将一个字符串对应的byte[] 数组，通过生成的赫夫曼编码表，返回一个赫夫曼编码 压缩后的byte数组 /** * @param bytes 原始的字符串对应的byte[]，即，对应程序中的contentBytes * @param huffmanCodes 生成的赫夫曼编码Map * @return 返回赫夫曼编码处理后的byte[] ， * 举例：String content = "i like like like java do you like a java"; =》 byte[] contentBytes = content.getBytes(); * 返回的字符串是：1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110 * =》 对应的byte[] huffmanCodeBytes , 即 8位对应一个byte， 放入huffmanCodeBytes * huffmanCodeBytes[0] = 1010 1000(补码)=》源码 1101 1000 =》 十进制 -88 * huffmanCodeBytes[1] */ private static byte[] zip(byte[] bytes, Map
             
               huffmanCodes) { //1. 先利用huffmanCodes 将 bytes 转成 赫夫曼编码对应的字符串 StringBuilder stringBuilder = new StringBuilder(); //遍历bytes 数组 for (byte b : bytes) { stringBuilder.append(huffmanCodes.get(b)); }// System.out.println("生成的赫夫曼编码表stringBuilder = " + stringBuilder); //将字符串“101010011011...” 转成 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; } //创建huffmanCodeBytes //创建 存储压缩后的 byte 数组 byte[] huffmanCodeBytes = new byte[len]; //记录第几个byte int index = 0; for (int i = 0; i < stringBuilder.length(); i += 8) { //因为是每8位 对应一个byte，所以步长 +8 String strByte; if (i + 8 > stringBuilder.length()) { //不够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; } //生成的赫夫曼树对应的赫夫曼编码 static Map
              
                huffmanCodes = new HashMap
               
                (); static StringBuilder stringBuilder = new StringBuilder(); //调用方便，我们重载getCodes private static Map
                
                  getCodes(Node root) { if (root == null) { return null; } //处理root的左子树 getCodes(root.left, "0", stringBuilder); //处理root的右子树 getCodes(root.right, "1", stringBuilder); return huffmanCodes; } /** * 功能：将传入的node结点的所有叶子结点的赫夫曼编码得到，并放入huffmanCodes集合 * * @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); //如果node == null 则不处理 if (node != null) { //判断当前node 是叶子结点还是非叶子结点 if (node.data == null) { //非叶子结点 //递归处理 //向左递归 getCodes(node.left, "0", stringBuilder2); //向右递归 getCodes(node.right, "1", stringBuilder2); } else { //说明是个叶子结点 //表示找到了叶子结点的最后 huffmanCodes.put(node.data, stringBuilder2.toString()); } } } //前序遍历的方法 private static void preOrder(Node root) { if (root != null) { root.preOrder(); } else { System.out.println("赫夫曼树为空"); } } //(3) 编写一个方法，将准备构建赫夫曼的Node 结点 放到List， 形式[Node[data = '7', weight = '5']...], //体现 d: 1, y: 1, u: 1, j: 2, v: 2, o: 2, l: 4, k: 4, k: 4, e: 4, i: 5, a: 5, (空格)：9 /** * @param bytes 接收字节数组 * @return 返回List 形式 [Node[data = '7', weight = 97]...] */ private static List
                 
                   getNodes(byte[] bytes) { //1. 创建一个ArrayList ArrayList
                  
                    nodes = new ArrayList
                   
                    (); //遍历bytes， 统计每一个byte出现的次数 ->map[key, value] Map
                    
                      counts = new HashMap<>(); for (byte b : bytes) { Integer count = counts.get(b); if (count == null) { //Map还没有这个字符数据 //第一次，加入map counts.put(b, 1); } else { counts.put(b, count + 1); } } //把每一个键值对转成一个Node 对象，并加入到nodes集合 //遍历map for (Map.Entry
                     
                       entry : counts.entrySet()) { nodes.add(new Node(entry.getKey(), entry.getValue())); } return nodes; } //(4) 可以通过List创建对应的赫夫曼树 private static Node createHuffmanTree(List
                      
                        nodes) { while (nodes.size() > 1) { //排序,从小到大 Collections.sort(nodes); //取出第一棵最小的二叉树 Node leftNode = nodes.get(0); //取出第二小的二叉树 Node rightNode = nodes.get(1); //创建一个新的二叉树，它的根结点parent，没有data，只有权值weight 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); }}//(1) Node{data (存放数据)， weight(权值)， left， right}//创建Node，带数据和权值//接口Comparable
                       
                         对Node类型的数据进行比较class Node implements Comparable
                        
                          { //存放数据（字符）本身，比如'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) { //Node类型的数据从小到大排序 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(); } }}