霍夫曼编码(Java实现)

1. 代码

public class HuffmanTree {
    //树的所有数据
    private int[] elem;
    //树的所有权重
    private int[] weight;
    //存储霍夫曼树
    private Node[] huffmanTree;
    //HuffmanCode
    private Map<String, String> huffmanCode;


    private class Node implements Comparable<Node> {
        //当前索引
        private Integer index;
        //权值
        private Integer weight;
        //数据
        private String elem;
        //父节点
        private Integer parent;
        //左孩子
        private Integer lChildren;
        //右孩子
        private Integer rChildren;

        public Node(Integer weight, String elem, Integer parent, Integer lChildren, Integer rChildren, Integer index) {
            this.weight = weight;
            this.elem = elem;
            this.parent = parent;
            this.lChildren = lChildren;
            this.rChildren = rChildren;
            this.index = index;
        }

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

    HuffmanTree createHuffmanTree(int[] weight, String[] elem) {
        int size = elem.length * 2 - 1;
        huffmanTree = new Node[size];
        int p = 0;
        PriorityQueue<Node> priorityQueue = new PriorityQueue<>(elem.length);
        while (p < elem.length) {
            Node node = new Node(weight[p], elem[p], null, null, null, p);
            huffmanTree[p] = node;
            priorityQueue.add(node);
            p++;
        }
        
        while (p < huffmanTree.length) {
            Node minNode = priorityQueue.poll();
            Node secondMinNode = priorityQueue.poll();
            Node node = new Node(minNode.weight + secondMinNode.weight, null, null,
                    Math.min(secondMinNode.index, minNode.index), Math.max(secondMinNode.index, minNode.index), p);
            priorityQueue.add(node);
            huffmanTree[p] = node;
            minNode.parent = p;
            secondMinNode.parent = p;
            p++;
        }


        return this;
    }

    void printHuffmanTree() {
        if (huffmanTree == null) {
            throw new UnsupportedOperationException("霍夫曼树没有初始化");
        }
        System.out.println("weight\t" + "parent\t" + "lChildren\t" + "rChildren");
        for (int i = 0; i < huffmanTree.length; i++) {
            System.out.println(huffmanTree[i].weight + "\t" + huffmanTree[i].parent + "\t" + huffmanTree[i].lChildren + "\t" + huffmanTree[i].rChildren);
        }
    }

    HuffmanTree createHuffmanCode(int[] weight, String[] elem) {
        createHuffmanTree(weight, elem);
        huffmanCode = new HashMap<>(elem.length);
        createHuffmanCode(huffmanTree.length - 1, "");
        return this;
    }

    /**
     * 构造霍夫曼编码
     * 从上往下递归遍历
     *
     * @param current 当前节点索引
     */
    private void createHuffmanCode(Integer current, String code) {
        Node currentNode = huffmanTree[current];
        if (currentNode.rChildren == null && currentNode.lChildren == null) {
            huffmanCode.put(currentNode.elem, code);
        } else {
            createHuffmanCode(currentNode.lChildren, code + "0");
            createHuffmanCode(currentNode.rChildren, code + "1");
        }
    }

    void printHuffmanCode() {
        if (huffmanCode == null) {
            throw new UnsupportedOperationException("霍夫曼树没有初始化");
        }
        for (String key : huffmanCode.keySet()) {
            System.out.println("key : " + key + ",value:" + huffmanCode.get(key));
        }
    }
}

2. 测试

    @Test
    public void testHuffmanTree() {
        HuffmanTree huffmanTree = new HuffmanTree();
        int[] w = {5, 29, 7, 8, 14, 23, 3, 11};
        String[] elem = {"A", "B", "C", "D", "E", "F", "G", "H"};
        huffmanTree.createHuffmanTree(w, elem).printHuffmanTree();
        huffmanTree.createHuffmanCode(w, elem).printHuffmanCode();
    }

3. 测试结果

weight  parent  lChildren   rChildren
5   8   null    null
29  13  null    null
7   9   null    null
8   9   null    null
14  11  null    null
23  12  null    null
3   8   null    null
11  10  null    null
8   10  0   6
15  11  2   3
19  12  7   8
29  13  4   9
42  14  5   10
58  14  1   11
100 null    12  13
key : A,value:0110
key : B,value:10
key : C,value:1110
key : D,value:1111
key : E,value:110
key : F,value:00
key : G,value:0111
key : H,value:010