共计 4732 个字符，预计需要花费 12 分钟才能阅读完成。
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);
}
}
日志打印如下所示：
图片
从日志能够看出，跟咱们下面所说的后果，依据赫夫曼编码转化成二进制码是一样的；这里说的是赫夫曼编码，下一篇会写赫夫曼解码，敬请期待。
