温馨提示：这篇文章是基于哈夫曼树的构建之上，来说说哈夫曼树的应用，强烈建议在学习http://124.222.190.191:8090/archives/%E5%93%88%E5%A4%AB%E6%9B%BC%E6%A0%91%E7%9A%84%E6%9E%84%E5%BB%BA—%E5%9F%BA%E4%BA%8Ejava
后再来阅读这篇博文哦
## 哈夫曼树的应用
哈夫曼树可以用于优化编码，这里先了解一下等长编码和不等长编码
等长编码
例如一段电文为 ‘A B A C C D A’, 它只有4种字符，只需要两个字符的串就可以分辨， 所以我们可以按等长编码的设计原则， 将A，B，C，D表示为00、01、10、11, 'A B A C C D A’就被编码为‘00010010101100’， 共14位。 它的优点是： 因为间隔相同， 译码时不存在二义性的问题。 但缺点在于， 有些字符本可以被设计为更短的编码， 也就是说，设计为等长编码， 我们实际上浪费了一部分编码的空间（长度）
不等长编码
同上， 如果采用不等长编码， 可以把A，B，C，D表示为0、00、1、01, 那么 'A B A C C D A’就可以被编码为‘000011010’， 总长只要9就够了！ 比起等长编码我们节约了5位的长度。 但问题是： 由于长度间隔不一致， 译码时可能存在二义性，这导致无法翻译，例如 ‘00‘，到底是看成’00’还是’0‘ + ’0‘呢？ 前者被翻译为B，而后者被翻译为A。
前缀编码
为了解决不等长编码产生的二义性问题，引出了前缀编码，即任意一个字符的编码都不是另一个字符的编码的前缀。
哈夫曼树编码
哈夫曼树就是一种前缀编码，它能解决不等长编码时的 译码问题，通过它，我们可以尽可能减少编码的长度，同时还能够避免二义性，实现正确译码
哈夫曼树如何实现前缀编码？
假设有一棵如下图所示的二叉树， 其4个叶结点分别表示A，B，C，D这4个字符，且约定左分支表示字符’0’, 右分支代表字符’1’, 则可以从根结点到叶子结点的路径上的各分支字符组成的字符串作为该叶子结点字符的编码。 从而得到A，B，C，D的二进制编码分别为0， 10， 110， 111。
哈夫曼编码实现
-
我们编写一个HuffmanCode内部类用于存放字符（data实例变量）和它对应的二进制字符串（bit实例变量）
-
要求所有字符对应的编码时，如果采用从根结点下行到叶结点的思路处理，逻辑会相对复杂一些， 所以我们用逆向的方式获取： 按照从叶子结点到根结点的路径累加二进制字符串
-
因为 2 的原因， 累加二进制字符串的时候也必须反向累加，例如写成bit= “0” + bit; 而不是写成bit= bit+ “0”;
-
上溯时候要做的工作是： 判断当前经过的是 0 还是 1， 判断的方法如下图所示：
假设P是X的父节点：
如果P.left==X在HT中的下标，则说明X是P的左分支，说明经过的是 0
如果P.right==X在HT中的下标，则说明X是P的右分支，说明经过的是 1
## 代码如下：
import java.util.Arrays;
public class HuffmanTree {
private class HuffmanCode {
char data; // 存放字符，例如 'C'
String bit; // 存放编码后的字符串, 例如"111"
public HuffmanCode (char data, String bit) {
this.data = data;
this.bit = bit;
}
}
/**
* 构建赫夫曼树
*/
public Node[] buildTree (Node [] nodes) {
// 具体代码见哈夫曼树的构建--基于java这篇博文
}
/**
* 进行赫夫曼编码
*/
public HuffmanCode [] encode(Node [] nodes) {
Node [] HT = buildTree(nodes); // 根据输入的nodes数组构造赫夫曼树
int n = nodes.length;
HuffmanCode [] HC = new HuffmanCode [n];
String bit;
for (int i=0;i<n;i++) { // 遍历各个叶子结点
bit = "";
for (int c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) { // 从叶子结点上溯到根结点
if(HT[f].left == c) bit= "0" + bit; // 反向编码
else bit= "1" + bit;
}
HC[i] = new HuffmanCode(HT[i].data,bit); // 将字符和对应的编码存储起来
}
return HC;
}
/**
* encode方法的用例
*/
public static void main (String [] args) {
Node [] nodes = new Node[4];
nodes[0] = new Node('A',7);
nodes[1] = new Node('B',5);
nodes[2] = new Node('C',2);
nodes[3] = new Node('D',4);
HuffmanTree ht = new HuffmanTree();
HuffmanCode[] hc = ht.encode(nodes);
// 对A，B，C，D进行编码
for (int i=0;i<hc.length;i++) { // 将赫夫曼编码打印出来
System.out.println(hc[i].data + ":" +hc[i].bit);
}
}
}
输出结果：
A:0
B:10
C:110
D:111
应用二
## 哈夫曼树译码
根据给定的字符和权值， 将输入的赫夫曼编码翻译回原字符串
译码的时候，从根结点HT[HT.length -1] 开始, 向下行走， 通过charAt方法取得字符串当前的字符， 如果为 '0’则向左走， 为’1’则向右走， 当下行到叶子结点时候，取得叶子结点包含的字符， 添加到当前的译码字符串中，同时回到根结点，继续循环。
代码如下：
import java.util.Arrays;
public class HuffmanTree {
int selectStart = 0;
private class HuffmanCode {
char data; // 存放字符，例如 'C'
String bit; // 存放编码后的字符串, 例如"111"
public HuffmanCode (char data, String bit) {
this.data = data;
this.bit = bit;
}
}
/**
* @description: 构建赫夫曼树
*/
public Node[] buildTree (Node [] nodes) {
// 代码见哈夫曼树构建--基于java博文
}
/**
* @description: 进行赫夫曼译码
*/
public String decode (Node [] nodes, String code) {
String str="";
Node [] HT = buildTree(nodes);
int n =HT.length -1;
for (int i=0;i<code.length();i++) {
char c = code.charAt(i);
if(c == '1') {
n = HT[n].right;
}
else {
n = HT[n].left;
}
if(HT[n].left == 0) {
str+= HT[n].data;
n =HT.length -1; //回到根结点
}
}
return str;
}
/**
* @description: decode方法的用例
*/
public static void main (String [] args) {
Node [] nodes = new Node[4];
nodes[0] = new Node('A',7);
nodes[1] = new Node('B',5);
nodes[2] = new Node('C',2);
nodes[3] = new Node('D',4);
HuffmanTree ht = new HuffmanTree();
// 对 010110111 进行译码
System.out.println(ht.decode(nodes,"010110111"));
}
}
输出
ABCD
之后会继续更新哈夫曼树在深度学习中的应用~~~~~~~
参考博文：
哈夫曼树（赫夫曼树、最优树）及C语言实现
哈夫曼（huffman）树和哈夫曼编码-白红宇的个人博客
构造哈夫曼树和生成哈夫曼编码_静能生悟的博客-CSDN博客_构造哈夫曼树和生成哈夫曼编码
【算法】赫夫曼树（Huffman）的构建和应用（编码、译码） - 外婆的 - 博客园
