问题
- 给定一串字符串：
abcd，如何压缩？
我们知道每个字节在计算机中占8bit，
假使我们定义二进制 00 表示 a， 01 表示b ， 10 表示c ， 11 表示d
那么abcd转为二进制后就变成了00011011，看，原本占4*8=32bit的一串字符串，现在只占8bit了，是不是压缩了4倍，nice!
- 给定一串字符串：
aaaaaabcd，如何压缩？
如果我们再用上面的做法，就变成了00000000000000011011，我们发现前面有一大串0,那么我们有没有更好的办法进行优化呢？
比如定义a的二进制位0,咦，好像又缩短了一些，但是我们碰到001这样的应该怎么解码呢？首先来了个0解码为a，再来个0，解码为a，然后是1，我们发现没有对应的码值，解码失败了。这是为什么呢？
这里引出一个前缀的问题，这里明显a的二进制位是b的前缀，如果想保证解码成功，就必须保证没有前缀的情况发生，不然就会出现上面的问题。
说了那么多，现在我们正式看看什么是哈夫曼树吧~
定义
给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
那么这个哈夫曼树和压缩又有什么关系呢？
二叉树：二叉，这时候你要想到二进制，二叉分左右嘛。左节点的边设置为0，右节点的边设置为1
哈夫曼编码
在上图的最优二叉树中我们给每一条边加上一个权值，指向左子节点的边我们标记为0，指向右子节点的边标记为1，那从根节点
到叶节点的路径就是我们说的哈夫曼编码；
哈夫曼编码.png
构建过程
核心思想：贪心算法：利用局部最优推出全局最优，把频率出现多的用短码表示，频率出现小的就用长一点。而且，任何一个字符的编码都不是另一个的前缀，在解压缩的时候，我们每次会读取尽可能长的可解压的二进制串，所以在解压缩的时候也不会产生歧义。
具体实现思路：
1.每次取数值最小的两个节点，将之组成为一颗子树。
2.移除原来的两个点
3.然后将组成的子树放入原来的序列中
4.重复执行1 2 3 直到只剩最后一个点
代码实现
package com.algorithm.tree; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.PriorityQueue; public class HFMTree { private final PriorityQueue<Node> priorityQueue; private final List<Node> nodeList; private final Map<Character, String> dictionary; private final Map<String, Character> deDictionary; private Node root; public HFMTree(Map<Character, Integer> dictionary) { priorityQueue = new PriorityQueue<>(dictionary.size()); nodeList = new ArrayList<>(dictionary.size()); this.dictionary = new HashMap<>(dictionary.size()); this.deDictionary = new HashMap<>(dictionary.size()); dictionary.forEach((chars, weight) -> { Node node = new Node(chars.toString(), weight); priorityQueue.add(node); nodeList.add(node); }); } public String decode(String binary) { char[] chars = binary.toCharArray(); StringBuilder message = new StringBuilder(); StringBuilder sb = new StringBuilder(); for (Character aChar : chars) { sb.append(aChar); Character character = deDictionary.get(sb.toString()); if (character != null){ message.append(character); sb = new StringBuilder(); } } return message.toString(); } public String encode(String message) { char[] chars = message.toCharArray(); StringBuilder sb = new StringBuilder(); for (char aChar : chars) { sb.append(dictionary.get(aChar)); } return sb.toString(); } public void code() { nodeList.forEach(node -> { String chars = node.chars; String code = ""; do { if (node.parent.left == node) { code = "0" + code; } else code = "1" + code; node = node.parent; } while (node.parent != null); dictionary.put(chars.charAt(0), code); deDictionary.put(code, chars.charAt(0)); System.out.println(chars + ":" + code); }); } public void create() { int length = priorityQueue.size(); for (int i = 0; i < length - 1; i++) { Node node1 = priorityQueue.poll(); Node node2 = priorityQueue.poll(); Node parent = new Node(node1.chars + node2.chars, node1.weight + node2.weight); parent.left = node1; parent.right = node2; node1.parent = parent; node2.parent = parent; priorityQueue.add(parent); } root = priorityQueue.poll(); } private static class Node implements Comparable<Node> { Node left; Node right; Node parent; int weight; String chars; public Node(String chars, int weight) { this.chars = chars; this.weight = weight; } @Override public int compareTo(Node o) { return this.weight - o.weight; } } public static void main(String[] args) { //a:7 b:10 c:3 d:20 e:6 f:15 g:22 Map<Character, Integer> dictionary = new HashMap<>(); dictionary.put('a', 7); dictionary.put('b', 10); dictionary.put('c', 3); dictionary.put('d', 20); dictionary.put('e', 6); dictionary.put('f', 15); dictionary.put('g', 22); HFMTree hfmTree = new HFMTree(dictionary); hfmTree.create(); hfmTree.code(); String binary = hfmTree.encode("abcdefg"); System.out.println(binary); System.out.println(hfmTree.decode(binary)); } }
