
//哈夫曼
class Node implements Comparable<Node> {
    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) {
        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();
        }
    }
}
private static Node createHuffmanTree(List<Node> nodes) {
    /**
         *@MethodName createHuffmanTree
         *@Description TODO 创建哈夫曼树
         *@Author SSRS
         *@Date 2020-10-31 13:21
         *@Param [nodes]
         *@ReturnType Java_note.Algorithm.HuffmanCode.Node
         */
    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.remove(leftNode);
        nodes.remove(rightNode);
        //加入新节点
        nodes.add(parent);
    }
    return nodes.get(0);
}

哈夫曼树特点

1）每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大。

2）构造过程中共新建了n-1个结点（双分支结点），因此哈夫曼树的结点总数为2n- 1 。

3）每次构造都选择 2 棵树作为新结点的孩子，因此哈夫曼树中不存在度为1 的结点。

例如，权值｛7, 5, 2, 4｝的哈夫曼树的构造过程如图所示。

二、Huffman编码

在数据通信中，若对每个字符用相等长度的二进制位表示，称这种编码方式为固定长度编码。若允许对不同字符用不等长的二进制位表示，则这种编码方式称为可变长度编码。

可变长度编码比固定长度编码要好得多，其特点是对频率高的字符赋以短编码，而对频率较低的字符则赋以较长一些的编码，从而可以使字符的平均编码长度减短，起到压缩数据的效果。哈夫曼编码是一种被广泛应用而且非常有效的数据压缩编码。

若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码。哈夫曼编码是前缀编码。


class HuffmanCode {
    public static void main(String[] args) {
        String str = "I like like like java Do you like a java";
        byte[] strBytes = str.getBytes();
        System.out.println(str + "的原长度是" + strBytes.length);
        HuffmanCode huffmanCode = new HuffmanCode();
        System.out.println("转成哈夫曼编码为：");
        String huffmanstr = huffmanCode.createHuffmanCode(strBytes);
        System.out.println(huffmanstr);
        System.out.println("其长度为：" + huffmanstr.getBytes().length);
        byte[] bytes = huffmanCode.zipbytes(strBytes);
        System.out.println("压缩后的结果是：" + Arrays.toString(bytes));
        System.out.println("其长度为：" + bytes.length);
        System.out.println("解压缩：" + new String(huffmanCode.rezip(bytes)));
 
    }
 
    private static List<Node> getNodes(byte[] bytes) {
        /**
         *@MethodName getNodes
         *@Description TODO 获得构建哈夫曼树的Node
         *@Author SSRS
         *@Date 2020-10-31 13:07
         *@Param [bytes]
         *@ReturnType java.util.List<Java_note.Algorithm.HuffmanCode.Node>
         */
        ArrayList<Node> nodes = new ArrayList<Node>();//要返回的nodes集合
        Map<Byte, Integer> counts = new HashMap<>();
        //统计每一个byte出现的次数
        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> each : counts.entrySet()) {
            nodes.add(new Node(each.getKey(), each.getValue()));
        }
        return nodes;
    }
 
    private static Node createHuffmanTree(List<Node> nodes) {
        /**
         *@MethodName createHuffmanTree
         *@Description TODO 创建哈夫曼树
         *@Author SSRS
         *@Date 2020-10-31 13:21
         *@Param [nodes]
         *@ReturnType Java_note.Algorithm.HuffmanCode.Node
         */
        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.remove(leftNode);
            nodes.remove(rightNode);
            //加入新节点
            nodes.add(parent);
        }
        return nodes.get(0);
    }
 
    static Map<Byte, String> codes = new HashMap<Byte, String>();
 
    private static Map<Byte, String> getCodes(Map<Byte, String> codes, Node node, String code, StringBuilder stringBuilder) {
        StringBuilder stringBuilder1 = new StringBuilder(stringBuilder);
        stringBuilder1.append(code);
        if (node != null) {
            if (node.data == null) {
                getCodes(codes, node.left, "0", stringBuilder1);
                getCodes(codes, node.right, "1", stringBuilder1);
            } else {
                codes.put(node.data, stringBuilder1.toString());
            }
        }
        return codes;
    }
 
    private static byte[] bytesArrays(String string) {
        int len;//bytes数组长度
        if (string.length() % 8 == 0) {
            len = string.length() / 8;
        } else {
            len = string.length() / 8 + 1;
        }
        int index = 0;//bytes角标
        byte[] huffmanCodeBytes = new byte[len];
        for (int i = 0; i < string.length(); i += 8) {
            String strTemp;
            if (i + 8 > string.length()) {
                strTemp = string.substring(i);
            } else {
                strTemp = string.substring(i, i + 8);
            }
            //转换
            huffmanCodeBytes[index] = (byte) Integer.parseInt(strTemp, 2);
            index++;
        }
        return huffmanCodeBytes;
    }
 
    public static String createHuffmanCode(byte[] bytes) {
        /**
         *@MethodName createHuffmanCode
         *@Description TODO 得到哈夫曼转码
         *@Author SSRS
         *@Date 2020-10-31 20:15
         *@Param [bytes]
         *@ReturnType java.lang.String
         */
        Node root = createHuffmanTree(getNodes(bytes));
 
        StringBuilder stringBuilder = new StringBuilder();
 
        getCodes(codes, root, "", stringBuilder);
 
        String str = "";
        for (Byte each : bytes) {
            str += codes.get(each);
        }
        return str;
    }
 
    public byte[] zipbytes(byte[] bytes) {
        return bytesArrays(createHuffmanCode(bytes));
    }
 
    //解压缩
    private String byteToBitString(boolean flag, byte b) {
        /**
         *@MethodName byteToBitString
         *@Description TODO 将一个byte转成二进制字符串
         *@Author SSRS
         *@Date 2020-10-31 20:56
         *@Param [flag 正数为true要补高位, b]
         *@ReturnType java.lang.String
         */
        int temp = b;//转int
        //如果是正数还要补高位
        if (flag) {
            temp |= 256;//按位与 256 是 1 0000 0000 | 0000 0001=》1 0000 0001
        }
        String str = Integer.toBinaryString(temp);//返回的是二进制的补码
 
        if (flag) {
            return str.substring(str.length() - 8);
        } else {
            return str;
        }
 
    }
 
    public byte[] rezip(byte[] huffmanbytes) {
        StringBuilder stringBuilder = new StringBuilder();//储存二进制字符串
        //全部转成二进制字符串
        for (int i = 0; i < huffmanbytes.length; i++) {
            //如果是最后一个可能不满8位就转码的那个就不用补高位无论正负，因此要判断
            boolean flag = (i == huffmanbytes.length - 1);
            stringBuilder.append(byteToBitString(!flag, huffmanbytes[i]));
        }
 
        //把哈夫曼编码表反向
        Map<String, Byte> map = new HashMap<String, Byte>();
        for (Map.Entry<Byte, String> each : codes.entrySet()) {
            map.put(each.getValue(), each.getKey());
        }
 
        List<Byte> list = new ArrayList();//解压缩后的语句的储存位置
        for (int i = 0; i < stringBuilder.length(); ) {
            int count = 1;//计数,计每一个字符的二进制字符位数
            boolean flag = true;
            Byte b = null;
 
            //找字符对应哈夫曼编码
            while (flag) {
                String key = stringBuilder.substring(i, i + count);
                b = map.get(key);
                if (b == null) {
                    count++;
                } else {//匹配成功
                    flag = false;
                }
            }
            list.add(b);
            i = i + count;
        }
        byte b[] = new byte[list.size()];
        for (int i = 0; i < b.length; i++) {
            b[i] = list.get(i);
        }
        return b;
    }
 
    public void preOrder(Node root) {
        if (root != null) {
            root.preOrder();
        } else {
            System.out.println("二叉树为空。");
        }
    }
}

本文所有概念性描述及图示均来自王道考研数据结构一书

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小丑西瓜9/article/detail/693604