霍夫曼编码

问题: 请设计一个算法，给一个字符串进行二进制编码，使得编码后字符串的长度最短

思路：使用霍夫曼编码构造字符串编码，字符串中字母出现的频率为权重，最后每一个字母的霍夫曼编码长度总和即为最短长度

源码

import java.util.*;

/**
 * Created by gaowenfeng on 2017/10/9.
 */
public class Huffman {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        System.out.println(createHuffman(s));
    }

    private static int createHuffman(String s) {

        //1.构造字符频率集
        Map<Character,Integer> map = new HashMap<>();
        char[] chars = s.toCharArray();
        for(char c:chars){
            if(map.containsKey(c))
                map.put(c,map.get(c)+1);
            else
                map.put(c,1);
        }
        //2.构造由权重值为比较依据的优先队列(最小堆，每次等到weight最小的节点)
        PriorityQueue<HuffmanNode> queue = new PriorityQueue<>(
                map.size(), Comparator.comparingInt(t->t.weight)
        );
        //3.构造霍夫曼树
        for(Map.Entry<Character,Integer> entry:map.entrySet()){
            queue.offer(new HuffmanNode(entry.getValue(),entry.getKey()));
        }
        //构建霍夫曼树并合并两个权重最小的节点，直至只剩根节点
        while (queue.size()>1){
            //1.弹出两个权重最小的节点
            HuffmanNode leftNode = queue.poll();
            HuffmanNode rightNode = queue.poll();
            //2.合并为一个新节点
            HuffmanNode fatherNode = new HuffmanNode(leftNode.weight+rightNode.weight);
            fatherNode.leftChild=leftNode;
            fatherNode.rightChild=rightNode;
            //3.将新节点放入队列
            queue.offer(fatherNode);
        }
        HuffmanNode treeRoot = queue.poll();
        //4.计算霍夫曼树的长度，初始深度为0，因为最后弹出的一定是合并过的
        return getLength(treeRoot,0);
    }

    /**
     * 获取霍夫曼节点的长度
     * @param root 节点
     * @param depth 当前深度
     * @return
     */
    private static int getLength(HuffmanNode root, int depth) {
        if(root==null)
            return 0;
        return (root.ch==null?0:root.weight)*depth+getLength(root.leftChild,depth+1)+getLength(root.rightChild,depth+1);
    }


}
class HuffmanNode{
    int weight;  //字符串中字母出现的频率即为权重;
    Character ch;  //若为组合字符串，则为null，否则为原字符；
    HuffmanNode leftChild;
    HuffmanNode rightChild;

    public HuffmanNode(int weight) {
        this.weight = weight;
    }

    public HuffmanNode(int weight, Character ch) {
        this.weight = weight;
        this.ch = ch;
    }
}

摘自 http://www.cnblogs.com/GumpYan/p/5861605.html