赫夫曼码是 可变字长编码(VLC) 的一种。Huffman 于 1952 年提出一种编码方法,称之为最佳编码.
在练习中需要注意以下几点:

  • 赫夫曼树 根据排序方法不同,也可能不太一样,这样对应的 赫夫曼编码 也不完全一样,但是 WPL 是一样的,都是最小的,最后生成的赫夫曼编码的长度是一样。
  • 在初学时,不要秀技,把几行代码放在一行写完。保持一个清晰简明的逻辑结构是最重要的。

相对于前面所学,难度上升地有些大,部分内容涉及到二进制和集合。需要花点时间再回顾一下代码。

package Tree.huffmenCode;

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";
        byte[] contentBytes = content.getBytes();
        System.out.println(contentBytes.length); // 打印byte数组的长度
        byte[] huffmanCodeBytes = huffmanzip(contentBytes);
        /*
         * List<Node> nodes = getNodes(contentBytes); System.out.println("nodes = " +
         * nodes);
         * 
         * // 测试创建的二叉树 System.out.println("赫夫曼树"); Node huffmanTreeRoot =
         * createHuffmanTree(nodes); System.out.println("前序遍历");
         * preOrder(huffmanTreeRoot);
         * 
         * // 测试是否生成了赫夫曼编码: Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);
         * System.out.println("生成的赫夫曼编码表" + huffmanCodes);
         * 
         * // 测试 byte[] huffmanCodeBytes = zip(contentBytes, huffmanCodes);
         */
        System.out.println(
                "huffmanCodeBytes =" + Arrays.toString(huffmanCodeBytes) + "length " + huffmanCodeBytes.length);
        byte[] sourceBytes = decode(huffmanCodes, huffmanCodeBytes);
        System.out.println("原来的字符串:"+ new String(sourceBytes));
    }

    // 使用一个方法,将前面的方法封装起来,便于调用

    /**
     * 
     * @param bytes 原始的字符串对应的字节数组,即contentBytes
     * @return 经过赫夫曼编码处理后的字节数组
     */
    private static byte[] huffmanzip(byte[] bytes) {
        List<Node> nodes = getNodes(bytes);
        // 根据nodes创建赫夫曼树,返回根节点
        Node huffmanTreeRoot = createHuffmanTree(nodes);
        // 根据赫夫曼树创建对应的赫夫曼编码
        Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);
        // 根据生成的赫夫曼编码,压缩得到压缩后的赫夫曼编码字节数组
        byte[] huffmanCodeBytes = zip(bytes, huffmanCodes);

        return huffmanCodeBytes;
    }

    /*
     * 完成数据的解压 思路: 1.将huffmanCodeByte[] 重新转成赫夫曼编码对应的二进制字符串
     * 2.将赫夫曼对应的二进制字符串对照赫夫曼编码重新转写成原始文件
     */

    /**
     * 将一个byte转换成一个二进制字符串
     * 
     * @param flag
     * @param b    标识是否需要补高位,如果是true,表示需要补高位,如果是false,表示不补,如果是最后一个字节,无需补高位
     * @return 是该byte 对应的二进制字符串,是按补码返回的
     */
    private static String byteToBitString(boolean flag, byte b) {
        // 使用变量保存b
        int tmp = b; // 将 b转成int
        // 如果是正数,我们还需要补高位
        if (flag) {
            tmp |= 256; // 按位或256 1000 0000 按位或 0000 0001 => 1000 0001
        }
        String str = Integer.toBinaryString(tmp); // 返回的是temp对应的二进制的补码
        if (flag) {
            return str.substring(str.length() - 8);
        } else {
            return str;
        }
    }

    /**
     * 
     * @param huffmanCodes 赫夫曼编码表
     * @param huffmanBytes 赫夫曼编码得到的字节数组
     * @return 原来的字符串对应的数组
     */
    private static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) {
        // 1.先得到huffmanBytes 对应的二进制字符串,形式如:10101001
        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));
        }
        // 把字符串按照指定的赫夫曼编码进行解码
        // 把赫夫曼编码表进行调换以便于进行反向查询
        Map<String, Byte> map = new HashMap<String, Byte>();
        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) {
                // 递增的取出key
                String key = stringBuilder.substring(i, i + count);// i不动,让count移动,直到匹配到一个字符
                b = map.get(key);
                if (b == null) { // 说明没有匹配到
                    count++;
                } else { // 匹配到了
                    flag = false;
                }
            }
            list.add(b);
            i += count; // i直接移动到count
        }
        // 当for循环结束后,list中就存放了所有的字符
        // 把list中的数据放入到byte[]并返回
        byte[] b = new byte[list.size()];
        for (int i = 0; i < b.length; i++) {
            b[i] = list.get(i);
        }
        return b;
    }

    /**
     * 将字符串对应的byte[]数组,通过生成的赫夫曼编码表, 返回一个赫夫曼编码压缩后的byte[]
     * 
     * @param bytes        原始的字符串对应的byte[]
     * @param huffmanCodes huffmanCodes 生成的赫夫曼编码Map
     * @return 返回赫夫曼编码后的byte[]
     * 
     *         举例:传入 contentBytes 返回的是 "10101000101111……"对应的byte[],即
     *         8位对应一个byte,放入byte[]
     * 
     *         10101000(补码) -> 10100111(反码[符号位不变]) -> 11011000(原码[符号位不变])
     */
    private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
        // 先利用huffmanCode 将bytes转成赫夫曼编码对应的字符串
        StringBuilder stringBuilder = new StringBuilder();
        // 遍历byte[]组
        for (byte b : bytes) {
            stringBuilder.append(huffmanCodes.get(b));
        }

        // 将赫夫曼编码后的数据转成byte[]
        // 下列语句也可以一句话完成:int len = (stringBuilder.length()+7) /8)
        int len;
        if (stringBuilder.length() % 8 == 0) {
            len = stringBuilder.length() / 8;
        } else {
            len = stringBuilder.length() / 8 + 1;
        }
        // 创建一个存储压缩后的byte[]
        byte[] huffmanCodeBytes = new byte[len];
        // 步长为8,每8位对应一个byte,所以步长+8
        int index = 0;// 记录第几个byte
        for (int i = 0; i < stringBuilder.length(); i += 8) {
            String strByte;
            if (i + 8 > stringBuilder.length()) { // 说明不够8位
                strByte = stringBuilder.substring(i);
            } else {
                strByte = stringBuilder.substring(i, i + 8);
            }
            // 将strByte转成一个byte,放入到by;
            huffmanCodeBytes[index] = (byte) Integer.parseInt(strByte, 2);
            index++;
        }
        return huffmanCodeBytes;

    }

    /*
     * 生成赫夫曼树对应的赫夫曼编码表 思路:
     * 
     * 1.将赫夫曼编码表存放在Map<Byte,String> 形式如:“ ”->01 97-> 100 100-> 11000 不一定完全如上
     */

    static Map<Byte, String> huffmanCodes = new HashMap<Byte, String>();
    /*
     * 2.在生成赫夫曼编码表时,需要去拼接路径,需要定义一个StringBuilder 存储某个叶子结点的路径
     */
    static StringBuilder stringBuilder = new StringBuilder();

    // 为了调用方便,我们重载getCodes
    private static Map<Byte, String> 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) {
        // 将code加入到stringBuilder2
        StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
        stringBuilder2.append(code);
        if (node != null) { // 如果node==null不处理
            // 判断当前node是叶子结点还是非叶子节点
            if (node.data == null) { // 非叶子结点
                // 递归处理
                // 向左递归
                getCodes(node.left, "0", stringBuilder2);
                // 向右递归
                getCodes(node.right, "1", stringBuilder2);
            } else { // 说明是叶子结点
                // 表示找到了某个叶子结点的最后
                huffmanCodes.put(node.data, stringBuilder2.toString());
            }
        }
    }

    /**
     * 先序遍历二叉树
     * 
     * @param root 根节点
     */
    private static void preOrder(Node root) {
        if (root != null) {
            root.preOrder();
        } else {
            System.out.println("赫夫曼树为空");
        }
    }

    /**
     * 接收一个字节数组,并返回List
     * 
     * @param bytes 接收字节数组
     * @return 返回的是List形式 [Node[data =97,weight =5],Node[data = 32,weight = 9],……]
     */
    private static List<Node> getNodes(byte[] bytes) {
        // 创建一个ArrayList
        ArrayList<Node> nodes = new ArrayList<Node>();

        // 遍历bytes,统计每一个byte 出现的次数
        Map<Byte, Integer> counts = new HashMap<Byte, Integer>();
        for (byte b : bytes) {
            Integer count = counts.get(b);
            if (count == null) { // Map还没有存储这个字符数据
                counts.put(b, 1);
            } else {
                counts.put(b, count + 1);
            }
        }
        // 把每个键值对,转换成一个Node对象,并加入到nodes集合
        // 遍历Map
        for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
            nodes.add(new Node(entry.getKey(), entry.getValue()));
        }
        return nodes;
    }

    /**
     * 创建一个赫夫曼树
     * 
     * @param nodes
     * @return 返回赫夫曼树的根节点
     */
    private 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;
            // 将已经处理过的两颗二叉树从nodes中删除
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            // 将新的二叉树加入到nodes
            nodes.add(parent);

        }
        // nodes 最后的结点就是哈夫曼树的根节点
        return nodes.get(0);
    }
}

// 创建Node,带数据和权值
class Node implements Comparable<Node> {
    Byte data; // 存放数据本身,比如'a' => 97 ' '=>32
    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();
        }
    }

}
Last modification:December 30th, 2020 at 01:26 am
如果觉得我的文章对你有用,请随意赞赏