PS：本文系转载文章，浏览原文可读性会更好，文章开端有原文链接
目录
1、赫夫曼编码
1、1 赫夫曼编码的根本介绍 1、2 通信畛域中信息的解决形式 1、2、1 定长编码 1、2、2 变长编码 1、2、3 赫夫曼编码1、赫夫曼树编码
1、1 赫夫曼编码的根本介绍
赫夫曼编码是一种编码方式，也是—种程序算法；赫夫曼编码是赫夫曼树在电讯通信中的经典的利用之—；赫夫曼编码宽泛地用于数据文件压缩，其压缩率个别在20%~90%之间；赫夫曼码是可变字长编码的一种，Huffman于1952年提出一种编码方法，称之为最佳编码。
1、2 通信畛域中信息的解决形式
1、2、1 定长编码
咱们列举通信畛域中信息的解决形式-定长编码，假如我要发送一句话给他人 “the virus mutated and became weaker and weaker” ，依照定长编码的形式，这句话转化成二进制编码后长度是多少呢？咱们先给出一张 Ascill 编码表，如图1所示；
图片
图1
空格（图1未给出空格）的十进制 Ascill 编码是 32，二进制 Ascill 编码是 00100000 ； 看图1，a 的十进制 Ascill 编码是 97，二进制 Ascill 编码是 01100001 ；看懂了图1的 a 字符 Ascill 编码，其余字符的Ascill 编码也应该能看懂了吧？图1中的其余字符 Ascill 编码我不再一一形容，但不管怎么看图1中的字符，它的二进制 Ascill 编码都是8位。咱们把下面要发送的一句话放在记事本统计一下字符数，如图2所示；
图片
图2看图2，发送的这句话字符长度是46个；而后再看图1字符二进制的 Ascill 码，一个字符占8位，所以发送的这句话换成二进制，长度就是 46 X 8 = 368 。
1、2、2 变长编码
假如我要发送一句话给他人也是 “the virus mutated and became weaker and weaker”，要进行传输的过程，必定是要转换成二进制编码的，用变长编码的形式能够缩小字节所占用的内存；好，咱们当初开始进行变长编码剖析，咱们先把 “the virus mutated and became weaker and weaker” 这句话中每个字符呈现的个数用表格列举进去，如下表1所示；
图片
好，咱们当初对表1的字符进行二进制编码，原则上呈现次数越多的，编码就越小；例如，字符 e ，呈现的次数是最多的，咱们把它的编码弄成0，好了，当初咱们也把表1的字符弄一个编码表进去，如表2所示；
图片
咱们把 “the virus mutated and became weaker and weaker” 这句话，全副转换成用表2中的二进制编码表示，失去表3；
图片
表3中的字符装不下那么多，我就省略了；“the virus mutated and became weaker and weaker” 这句话依照表2的规定转换成二进制编码就是 1001101011011110011111111011000111100101000101110110101111110100001010000110010101010011110110101110010101010011 ；把这串二进制编码放入记事本总计其长度，失去如图3的长度统计；
图片
图3二进制长度为112，绝对于定长编码来说，“the virus mutated and became weaker and weaker” 这句话的压缩率为 （368-112）/ 368 X 100% = 70% ，然而咱们解码的时候就麻烦了，比方结尾的编码是解码成10呢还是101，如果是解码成10就变成字母 a 了，就解码错了。
1、2、3 赫夫曼编码
赫夫曼编码应用了定长编码和变长编码的一些长处，例如它要用到十进制的 Ascill 码和用到字符呈现的次数作为二进制编码，这样就能够做到压缩字节码又能够解码无损失。好，咱们当初先画一棵含有赫夫曼编码的一棵树，不便上面说的内容好了解，如图3所示；
图片
看图3，节点右边的门路就用0示意，左边的门路用1示意，a 字符的编码是 10 。
咱们持续应用 “the virus mutated and became weaker and weaker” 这句话进行传输，这次咱们用赫夫曼编码，步骤如下所示；
（1）还是应用表1中字符。
（2）将表1中字符呈现的次数作为权值构建赫夫曼树（构建赫夫曼树的过程能够看Java版赫夫曼树这篇文章）。
（3）依据赫夫曼树，向左的门路为0，向右的门路为1，咱们要发送的字符串中字符二进制编码如表2所示。
（4）用十进制的 Ascill 码作为叶子节点的 data 值，用节点的权值转化为二进制码。
（5）构建成赫夫曼编码的这棵树必定是赫夫曼树，最初依据赫夫曼编码使得 “the virus mutated and became weaker and weaker” 这句话转化成二进制码是：1000101111001100011101111010110110000010000100100010101000101001010111100
好，咱们当初代码实现一把；
（1）创立一个节点类 Node ：
/**
- Node 实现 Comparable 是为了让Node 对象继续排序 Collections 汇合排序
*/
public class Node implements Comparable<Node>{
private Byte data;//寄存十进制的 Ascill 码，比 'a' 字符，那么 Ascill 码就是97
private int weight;//权值
private Node left;//左孩子
private Node right;//右孩子
@Override
public int compareTo(Node arg0) {
// 从小到大排序return this.weight - arg0.weight;}
public Node(Byte data, int weight) {
super();this.data = data;this.weight = weight;}
public Byte getData() {
return data;}
public Node getLeft() {
return left;}
public void setLeft(Node left) {
this.left = left;}
public Node getRight() {
return right;}
public void setRight(Node right) {
this.right = right;}
public int getWeight() {
return weight;}
}
（2）创立一个生成赫夫曼编码的类 Test ：
public class Test {
Node root;public static void main(String[] args) {
String s = "the virus mutated and became weaker and weaker";byte[] bs = s.getBytes();System.out.println("s的长度为：" + s.length());Test test = new Test();List<Node> list = test.getNode(bs);test.root = test.createHuffmanTree(list);//生成赫夫曼编码表，将 赫夫曼编码表 寄存到 huffumanCodes 中test.getCodes(test.root, "", test.sb);s = "";for (Map.Entry<Byte, String> map : test.huffumanCodes.entrySet()){ s = s + map.getValue();}System.out.println("s依据赫夫曼编码而生成对应的二进制码是" + s);}
//拼接赫夫曼树的节点的门路，节点的左门路用“0” 示意，右门路用“1”示意
StringBuilder sb = new StringBuilder();
Map<Byte,String> huffumanCodes = new HashMap<Byte,String>();
//生成赫夫曼编码表
/**
- @param node 传入的节点
- @param code 节点的左门路用“0” 示意，右门路用“1”示意
- @param sb 拼接code
- @return
*/
private void getCodes(Node node,String code,StringBuilder sb) {
StringBuilder sb2 = new StringBuilder(sb);//将code 退出到 sb2 中sb2.append(code);if (node != null) { //非叶子节点 if (node.getData() == null) { //向左递归解决 getCodes(node.getLeft(), "0", sb2); //向右递归解决 getCodes(node.getRight(), "1", sb2); //是叶子节点 } else { huffumanCodes.put(node.getData(), sb2.toString()); }}}
private List<Node> getNode(byte[] bs) {
ArrayList<Node> list = new ArrayList<Node>();//统计byte呈现的次数Map<Byte,Integer> map = new HashMap<Byte,Integer>();for (int i = 0; i<bs.length; i++) { Integer count = map.get(bs[i]); //第一次寄存该字节 if (count == null) { map.put(bs[i],1); } else { map.put(bs[i], count + 1); }}for (Map.Entry<Byte, Integer> entry : map.entrySet()) { Byte data = entry.getKey(); int weight = entry.getValue(); Node node = new Node(data,weight); list.add(node);}return list;}
//创立赫夫曼树
private Node createHuffmanTree(List<Node> list) {
while (list.size() > 1) { // 排序，从小到大排序 Collections.sort(list); // System.out.println("list = " + list); /** * 这个肯定是权值最小的节点 */ Node minNode = list.get(0); /** * 除了 minNode 节点，该节点就是权值最小的节点，只是该节点比 minNode 节点大， 比其余节点都小 */ Node secondMinNode = list.get(1); /** * 构建一棵新的二叉树 */ Node parentNode = new Node(null,minNode.getWeight() + secondMinNode.getWeight()); parentNode.setLeft(minNode); parentNode.setRight(secondMinNode); /** * 从 list 汇合中删除2棵曾经构建成一棵二叉树的2个节点 */ list.remove(minNode); list.remove(secondMinNode); /** * 将新的二叉树的父节点退出到 list 汇合中 */ list.add(parentNode); } /** * 构建完哈夫曼树后，list 汇合中的第一个节点必定是根节点 */ return list.get(0);}}
日志打印如下所示：
图片
从日志能够看出，跟咱们下面所说的后果，依据赫夫曼编码转化成二进制码是一样的；这里说的是赫夫曼编码，下一篇会写赫夫曼解码，敬请期待。