哈夫曼编码（上）

文章目录

- 问题引入
- 哈夫曼编码的编写
- - 总述
  - 步骤一
  - 步骤二
  - 步骤三
  - 步骤四
- 实现代码如下

问题引入

哈夫曼编码通常用于通信领域，是对较长信息进行压缩，然后发送到指定的位置，是为了节省发送信息占用的空间。
通常来说，如果信息中字符的重复次数越多，那么哈夫曼编码后所占的空间就越小，这也是我们为什么使用哈夫曼编码的原因，同时，哈夫曼编码还是天然的前缀编码，这让它与其他编码方式(定长编码，变长编码)相比，具有天然的优势。

哈夫曼编码的编写

总述

1.将字符串对应的字节数组变为list集合
2.创建list集合对应的哈夫曼树
3.得到对应的哈夫曼编码
4.根据哈夫曼编码得到最后压缩的byte[]

步骤一

首先我们需要一个字符串，此字符串将会用哈夫曼编码压缩为最后的byte数组。
比如为"i like like like java do you like a java"。
我们需要一个Node节点用来存储数据和对应的权值，这个节点为二叉树的节点。
我们将此字符串变为字节数组，然后统计各个字符出现的次数，将该字符作为Node节点的存储数据，
出现的次数作为Node节点对应的权值，统计之后将所有的节点放入List集合中保存。

//将对应字符串对应的byte数组转为list集合
private static List<Node2> getNodes(byte[] bytes){
        //创建一个List
        List<Node2> nodes = new ArrayList<Node2>();

        //存储每一个byte出现的次数
        Map<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 Node2(entry.getKey(),entry.getValue()));
        }
        return nodes;
    }
//创建Node，存数据和权值
class Node2 implements Comparable<Node2>{
    Byte data; //存放数据本身，比如'a' = 97
    int weight; //权值，表示字符出现的次数
    Node2 left;
    Node2 right;

    public Node2(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }

    @Override
    public int compareTo(Node2 o) {
        return this.weight - o.weight;
    }

    @Override
    public String toString() {
        return "Node2{" + "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();
        }
    }
}

步骤二

接下来我们就需要用我们刚刚得到的list集合来创建哈夫曼树了。
将list集合排序，把list集合的前两个节点拿出来，作为新树的两个子节点，然后将该新树放回list集合中，将原本拿出的两个子节点从list集合中移除，然后再次排序，重复上面步骤，就能得到一颗哈夫曼树。
当哈夫曼树构建完成，list集合就剩下一个节点，此节点就是哈夫曼树的根节点。
假设list集合中放的node节点的权值为1 2 4 5 6.
简述过程如下：

在这里插入图片描述

//通过list创建赫夫曼树
    private static Node2 createHuffmanTree(List<Node2> nodes){
        while (nodes.size() > 1){
            //排序
            Collections.sort(nodes);

            //取出前两个最小的二叉树
            Node2 left = nodes.get(0);
            Node2 right = nodes.get(1);

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

            parent.left = left;
            parent.right = right;
            nodes.add(parent);

            //将已经处理的两个二叉树从nodes删除
            nodes.remove(left);
            nodes.remove(right);
        }
        return nodes.get(0);
    }

步骤三

哈夫曼树我们已经构建完毕了，接下来我们需要得到对应的哈夫曼编码。
我们规定，哈夫曼树中的节点，从该节点到左子节点路径的值为0，到右子节点的值为1。
接下来就是递归的创建赫夫曼编码表了，此表我们用Map<Byte,String> buffmanCodes来表示，map的key表示对应的字符，map的value表示赫夫曼编码，还需要一个StringBuilder stringBuilder，用来存放某个叶子节点的路径。
从根节点开始，当我们遇到非叶子节点就递归处理，向左递归，将0加入stringBuilder，然后向右递归，将1加入stringBuilder。当我们遇到叶子节点时，stringBuilder已经将该路径的0或1收集完毕，将该节点的data作为key，stringBuilder里存储的字符串作为value存入buffmanCodes。
简述过程如下：
在这里插入图片描述

//1.将赫夫曼编码表存放Map<Byte,String>形式
static Map<Byte,String> buffmanCodes = new HashMap<Byte,String>();
//2.在生成赫夫曼编码表时，需要去拼接路径，定义一个StringBuilder 存储某个叶子节点的路径
static StringBuilder stringBuilder = new StringBuilder();
private static void getCodes(Node2 node,String code,StringBuilder stringBuilder){
        StringBuilder builder = new StringBuilder(stringBuilder);
        //将code加入builder
        builder.append(code);
        if(node != null){
            //判断当前节点是叶子节点还是非叶子节点
            if(node.data == null){ //非叶子节点
                //递归处理
                //向左递归
                getCodes(node.left,"0",builder);
                //向右递归
                getCodes(node.right,"1",builder);
            }else{
                //找到叶子节点
                buffmanCodes.put(node.data,builder.toString());
            }
        }
    }

步骤四

根据赫夫曼编码将数据压缩得到最后的byte[]。
首先利用buffmanCodes 将 bytes转成赫夫曼编码对应的字符串，用StringBuilder stringBuilder来接收。
接下来我们统计我们要压缩byte的长度int len，如果stringBuilder的长度恰好为8的倍数，则len = stringBuilder.length / 8,否则就是len = stringBuilder.length / 8 + 1，如果基础好的话很容易想到
int len = (stringBuilder.length() + 7) / 8。
最后我们创建压缩后的byte数组byte[] huffmanCodeBytes = new byte[len]。
读取stringBuilder的值，每八位作为一个字节，将该字节放入huffmanCodeBytes，当len的长度为8的倍数时，我们就按上述处理方法即可，但是当len的长度不为8的倍数，则最后几位的取法应有所不同。
简述过程如下：
在这里插入图片描述

 private static byte[] zip(byte[] contentBytes,Map<Byte,String> huffmanCodes){
        //1.利用huffmanCodes 将 bytes转成 赫夫曼编码对应的字符串
        StringBuilder stringBuilder = new StringBuilder();
        for (byte b : contentBytes) {
            stringBuilder.append(huffmanCodes.get(b));
        }

        int len;
        if(stringBuilder.length() % 8 == 0){
            len = stringBuilder.length() / 8;
        }else {
            len = stringBuilder.length() / 8 + 1;
        }
        //创建存储压缩后的bute数组
        byte[] huffmanCodeBytes = new byte[len];
        int index = 0; //记录是第几个byte
        //因为每8位对应一个byte，所以步长 + 8
        for (int i = 0; i < stringBuilder.length(); i+=8) {
            String strByte;
            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);
        }
        return huffmanCodeBytes;
    }

实现代码如下

public class HuffmanCode {
 public static void main(String[] args) {
        String str = "i like like like java do you like a java";
        byte[] bytes = str.getBytes(StandardCharsets.UTF_8);
        byte[] huffmanCodeBytes = huffmanZip(bytes);

        System.out.println("压缩后的结果为 : " + Arrays.toString(huffmanCodeBytes));
	}
    
    private static byte[] huffmanZip(byte[] contentBytes){
        List<Node2> nodes = getNodes(contentBytes);
        //根据nodes创建的赫夫曼树
        Node2 root = createHuffmanTree(nodes);

        //得到对应的赫夫曼编码
        Map<Byte, String> huffmanCodes = getCodes(root);

        //根据赫夫曼编码huffmanCodes得到最后压缩的byte[]
        byte[] huffmanCodeBytes = zip(contentBytes, huffmanCodes);
        return huffmanCodeBytes;
    } 
	
	private static byte[] zip(byte[] contentBytes,Map<Byte,String> huffmanCodes){
        //1.利用huffmanCodes 将 bytes转成 赫夫曼编码对应的字符串
        StringBuilder stringBuilder = new StringBuilder();
        for (byte b : contentBytes) {
            stringBuilder.append(huffmanCodes.get(b));
        }

        int len;
        if(stringBuilder.length() % 8 == 0){
            len = stringBuilder.length() / 8;
        }else {
            len = stringBuilder.length() / 8 + 1;
        }
        //创建存储压缩后的bute数组
        byte[] huffmanCodeBytes = new byte[len];
        int index = 0; //记录是第几个byte
        //因为每8位对应一个byte，所以步长 + 8
        for (int i = 0; i < stringBuilder.length(); i+=8) {
            String strByte;
            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);
        }
        return huffmanCodeBytes;
    }
     
     //为了调用方便，我们重载getCodes
    private static Map<Byte,String> getCodes(Node2 root){
        if(root == null){
            return null;
        }else {
            getCodes(root.left,"0",stringBuilder);
            getCodes(root.right,"1",stringBuilder);
            return buffmanCodes;
        }
    }

    static Map<Byte,String> buffmanCodes = new HashMap<Byte,String>();
    static StringBuilder stringBuilder = new StringBuilder(); 
    private static void getCodes(Node2 node,String code,StringBuilder stringBuilder){
        StringBuilder builder = new StringBuilder(stringBuilder);
        //将code加入builder
        builder.append(code);
        if(node != null){
            //判断当前节点是叶子节点还是非叶子节点
            if(node.data == null){ //非叶子节点
                //递归处理
                //向左递归
                getCodes(node.left,"0",builder);
                //向右递归
                getCodes(node.right,"1",builder);
            }else{
                //找到叶子节点
                buffmanCodes.put(node.data,builder.toString());
            }
        }
    }

	private static List<Node2> getNodes(byte[] bytes){
        //创建一个List
        List<Node2> nodes = new ArrayList<Node2>();

        //存储每一个byte出现的次数
        Map<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 Node2(entry.getKey(),entry.getValue()));
        }
        return nodes;
    }

	private static Node2 createHuffmanTree(List<Node2> nodes){
        while (nodes.size() > 1){
            //排序
            Collections.sort(nodes);

            //取出前两个最小的二叉树
            Node2 left = nodes.get(0);
            Node2 right = nodes.get(1);

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

            parent.left = left;
            parent.right = right;
            nodes.add(parent);

            //将已经处理的两个二叉树从nodes删除
            nodes.remove(left);
            nodes.remove(right);
        }
        return nodes.get(0);
    }
}

//创建Node，存数据和权值
class Node2 implements Comparable<Node2>{
    Byte data; //存放数据本身，比如'a' = 97
    int weight; //权值，表示字符出现的次数
    Node2 left;
    Node2 right;

    public Node2(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }

    @Override
    public int compareTo(Node2 o) {
        return this.weight - o.weight;
    }

    @Override
    public String toString() {
        return "Node2{" + "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();
        }
    }
}