霍夫曼编码/解码

一.简介

把信息转换成计算机能够识别的二进制形式，被称为编码。按编码位数长度是否固定分为：定长编码、变长编码。

定长编码容易设计，运行效率高。如果要对数据信息压缩就需要采用变长编码，把出现频率高的用位数少的编码，出现频率低的用更多位编码便可以实现数据压缩。

霍夫曼树是一种WPL(树的带权路径) 最小的二叉树，二叉树刚好有左/右节点，可以方便映射为2进制（如左节点方向表示0，右节点方向表示1）。

霍夫曼编码是一种可变长编码方式，依据字符出现频率作为霍夫曼树节点的权重构建霍夫曼树。

二.实现

package com.vincent;




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

public class Main {
    public static void main(String[] args) throws Exception {
        String msg = "I love coding,I love java too!";

        Map<Byte,String> encodingTable = HuffmanTree.encodingTable(msg.getBytes());

        System.out.println(encodingTable);

        System.out.println(Arrays.toString(msg.getBytes()));

        byte[] encodingBytes = HuffmanTree.encode(msg.getBytes(),encodingTable);
        System.out.println(Arrays.toString(encodingBytes));

        System.out.println(Arrays.toString(HuffmanTree.decode(encodingBytes,encodingTable)));
    }
}


class HuffmanTree{
    /**
     * 霍夫曼树节点
     * @param <T>
     */
    private static class Node<T> implements Comparable<Node<T>>{
        //存储的节点数据
        private T item;
        //节点权重
        private int weight;
        private Node<T> left;
        private Node<T> right;

        public Node(T item,int weight){
            this.item = item;
            this.weight = weight;
        }

        @Override
        public int compareTo(Node<T> o) {
            return this.weight - o.weight;
        }

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



    /**
     * 获取数据编码表
     * @return
     */
    public static Map<Byte,String> encodingTable(byte[] datas){
        //解析字节数组信息
        Map<Byte,Integer> counter = new HashMap<>(512);
        for(byte data : datas){
            int count = counter.getOrDefault(data,0) + 1;
            counter.put(data,count);
        }

        //构建编码树
        LinkedList<Node<Byte>> items = new LinkedList<>();
        for(Map.Entry<Byte,Integer> entry : counter.entrySet()){
            items.add(new Node<>(entry.getKey(),entry.getValue()));
        }

        while(items.size()>1){
            Collections.sort(items);
            Node<Byte> left = items.removeFirst();
            Node<Byte> right = items.removeFirst();

            Node<Byte> node = new Node<>(null,left.weight+right.weight);
            node.left = left;
            node.right = right;
            items.addFirst(node);
        }

        Map<Byte,String> table = new HashMap<>();
        encodingTable(items.removeFirst(),"",table);
        return table;
    }


    /**
     * 获取霍夫曼树节点的编码，左节点方向表示0，右节点方向表示1
     * @param node
     * @param orientation
     * @param dst
     */
    private static void encodingTable(Node<Byte> node,String orientation,Map<Byte,String> dst){
        if(node.left == null && node.right == null){
            dst.put(node.item,orientation);
            return;
        }
        if(node.left != null){
            encodingTable(node.left,orientation+"0",dst);
        }
        if(node.right != null){
            encodingTable(node.right,orientation+"1",dst);
        }
    }



    /**
     * 对字节数组霍夫曼编码
     * 把二进制位解析为字节数组，最后一次可能没有8位，故为了能记录最后一次的编码信息(二进制位长度)，再增加一个字节记录最后一个有效编码的长度
     * @param datas
     * @param encoder     编码表
     * @return
     */
    public static byte[] encode(byte[] datas,Map<Byte,String> encoder){
        StringBuilder encoding = new StringBuilder();
        for(byte data : datas){
            encoding.append(encoder.get(data));
        }

        int count = (encoding.length()+7)/8 + 1;
        byte[] rst = new byte[count];
        for(int i=0; ;i+=8){
            if(i+8<=encoding.length()){
                rst[i/8] = (byte)Integer.parseInt(encoding.substring(i,i+8),2);
            }
            else{
                String data = encoding.substring(i);
                byte len = (byte)data.length();
                rst[i/8] = (byte)Integer.parseInt(data,2);
                rst[i/8+1] = len;
                break;
            }
        }
        return rst;
    }


    /**
     * 对霍夫曼编码数据还原
     * @param datas         霍夫曼编码的数据
     * @param decoder       霍夫曼解码码表
     * @return
     */
    public static byte[] decode(byte[] datas,Map<Byte,String> decoder){
        StringBuilder origin = new StringBuilder();
        for(int i=0;i<datas.length-1;i++){
            String data = Integer.toBinaryString(datas[i] | 256);
            if(i < datas.length-2) {
                origin.append(data.substring(data.length() - 8));
            }
            else{
                //解析最后一个有效编码数据
                byte len = datas[datas.length - 1];
                origin.append(data.substring(data.length()-len));
            }
        }

        //由于编码表key/value 都是唯一对应
        Map<String,Byte> table = new HashMap<>(512);
        for(Map.Entry<Byte,String> entry : decoder.entrySet()){
            table.put(entry.getValue(),entry.getKey());
        }

        ByteArrayOutputStream bos = new ByteArrayOutputStream();
        for(int i=0;i<origin.length();i++){
            for(int j=i+1;j<=origin.length();j++) {
                Byte data = table.get(origin.substring(i, j));
                if (data != null) {
                    bos.write(data);
                    i = j-1;
                    break;
                }
            }
        }
        return bos.toByteArray();
    }
}

效果:

三.总结

1.霍夫曼编码是一种无损压缩方式

2.对字节数据构建霍夫曼树编码，重复数据越多压缩效率越高