从0开始实现Huffman编码
- 哈夫曼(Huffman)编码实现压缩
- 前戏：编码
- 正文：Huffman编码实现压缩
- Java代码实现
哈夫曼(Huffman)编码实现压缩
前戏：编码
先说编码是怎样一回事，我们都知道，计算机本质上来说，只能储存两种东西，即数字0和1。但是你在电脑上却可以存储文字、图片、声音、视频等等。其实你存储在计算机内部的并不是文字和图片，而是一串一串的0和1。这些特定顺序的0和1通过某种映射一一对应到你要保存到文字等，这样这串01串在你面前就变现出了文字或者是图片的样子。这也可以解释，为啥你用一个软件编写好的文档，用另一个软件打开就全是乱码，其本质是这个一一映射不同。
假如说我们现在要储存一串字符:“interesting”
在计算机中，西文字符都是用ASCII编码来存储的，在ASCII码的编码表中一共定义了256个不同的字符，由于 256 = 2 8 256=2^8 256=28，所以按道理来说至少需要8个bit才能使得存储的二进制数与这256个字符一一对应。所以在这套编码里面，每一个字符要花费一个字节(Byte)，也就是8个bit。
| 字符 | 出现次数 | ASCII编码 |
|---|---|---|
| i | 2 | 0110 1001 |
| n | 2 | 0110 1110 |
| t | 2 | 0111 0100 |
| e | 2 | 0110 0101 |
| r | 1 | 0111 0010 |
| s | 1 | 0111 0011 |
| g | 1 | 0110 0111 |
那么这一串字符串如果按ACSII编码就要花费 11 × 8 = 88 ( b i t ) \ 11\times 8 = 88(bit) 11×8=88(bit)。但是你会发现，ASCII码中定义了256个字符，而你在这个字符串中，只定义了7个字符，所以用ASCII码来编码是一种很浪费的方法。一种更好的压缩方法是用对每个你要编码的字符，用三位二进制数来表示。因为 7 < 8 = 2 3 \ 7<8=2^3 7<8=23，所以其实三位二进制足够表示这些字符了。
以下给出一种一一对应的方式（其实还有很多种对应方式）
| 字符 | 出现次数 | 三位二进制编码 |
|---|---|---|
| i | 2 | 000 |
| n | 2 | 001 |
| t | 2 | 010 |
| e | 2 | 011 |
| r | 1 | 100 |
| s | 1 | 101 |
| g | 1 | 110 |
用这种方法来编码的话，你只需花费 11 × 3 = 33 ( b i t ) \ 11\times 3 = 33(bit) 11×3=33(bit)就可以了，大小仅为ASCII编码的大小的37.5%。
但是很快你会发现两个问题
- 这种三位二进制编码最多可以定义8个不同的字符，而我们这里只定义了7个，这是不是一种浪费？
- 在编码中，i、n、t、e都出现了两次，而剩下三个均只出现了一次，有没有一种编码方式让前面几个所花费的存储空间更少而后面的可以大一些，这样在倍数的作用下使得总内存占用最少？
事实上，上面二者都属于不可变长度编码(ASCII编码都是8位，后者都是3位)。为了解决第二个问题，我们可能会想使用可变长度编码，比如用下面这种办法
| 字符 | 出现次数 | 编码A |
|---|---|---|
| i | 2 | 0 |
| n | 2 | 1 |
| t | 2 | 01 |
| e | 2 | 10 |
| r | 1 | 001 |
| s | 1 | 010 |
| g | 1 | 011 |
这种方法其实是不可行的，因为计算机e在读取的时候是一位一位读取的，假如0表示i的话，在读入01本应该表示t的时候，这套编码读出来的效果却是“in”，同样的在读入10本应该表e的时候，这套编码读出来的效果却是“ni”。但是根据我们的感觉，应该是存在一种类似于这也的编码方式，却又不存在开头重复的问题。而1952年Huffman就找到了这种方法，虽然当时的他初衷其实是为了逃避考试。
正文：Huffman编码实现压缩
1951年，哈夫曼和他在MIT信息论的同学需要选择是完成学期报告还是期末考试。Huffman在划水划了一学期自认为啥也没学到不敢考试，自然就选择了用论文的方式逃避考试。导师Robert M. Fano给他们的学期报告的题目是，寻找最有效的二进制编码。由于无法证明哪个已有编码是最有效的，哈夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。由于这个算法，学生终于青出于蓝，超过了他那曾经和信息论创立者香农共同研究过类似编码的导师。哈夫曼使用自底向上的方法构建二叉树，避免了次优算法Shannon-Fano编码的最大弊端──自顶向下构建树。
我们开始今天的主角终于登场了：Huffman编码
先说说Huffman编码的一般过程，首先我们的输入是一串字符串
- 对字符串统计每一个字符出现的频率
- 根据频率排序，弹出频率最小的两个，组成一颗二叉树的两个子节点，他们的父节点表示的值为这两个频率之和
- 重复2直到最后只剩下一颗二叉树，这个树我们成为Huffman树，也叫最优二叉树
- 这颗二叉树的每一个非叶节点，对节点的左右两个方向编0或1(左边编0右边编1，或者左边编1右边编0，我们这里采用前者来示范)
然后我们就可以找到每一个字符对应的编码啦
下面就以“interesting”为例使用Huffman编码压缩
首先我们找到了出现次数最少的两个字符：“g”和“r”各出现了一次，我们把它们组成一颗二叉树，“g”和“r”所在的为叶节点，节点对应数据为1和1，他们的父节点表示的值为 1 + 1 = 2 1+1=2 1+1=2。
现在我们相当于还剩6个节点，找出其中值最小的两个，其一是我们上一步得到的2(这里选择代表“n”的2或者代表“i“的2都是可以的，达到的效果是一样的)，还一个是代表“s”的1。我们把它们作为两个子节点组成二叉树，新的父节点的值为3。
现在我们发现”n“和”i“都是2，这是最少的两个，把它们重复上述操作得到一个值为4的节点。这时”e“和”t“都是2，这是最少的两个，把它们重复上述操作得到一个值为4的节点。然后上一段得到的3，和”n“和”i“得到的4是最小的两个，得到7，再与”e“和”t“得到的4合并，得到值为11的节点。至此，我们的Huffman树建好了，这个树的每一个叶节点代表一个字符。接下来我们进行第四步—赋值。
这里我们假设左边赋值为0，右边赋值为1，我们就得到了如下编码
| 字符 | 出现次数 | Huffman编码 |
|---|---|---|
| i | 2 | 111 |
| n | 2 | 110 |
| t | 2 | 01 |
| e | 2 | 00 |
| r | 1 | 1011 |
| s | 1 | 100 |
| g | 1 | 1010 |
这种编码所占空间大小为 2 × 3 + 2 × 3 + 2 × 2 + 2 × 2 + 1 × 4 + 1 × 3 + 1 × 4 = 31 ( b i t ) \ 2\times 3+2\times 3+2\times 2+2\times 2+1\times 4+1\times 3+1\times 4=31(bit) 2×3+2×3+2×2+2×2+1×4+1×3+1×4=31(bit)，看，是不是比原来的33少一些了，而且也没有发生上述开头重复的问题。
Java代码实现
首先我们创建一个Huffman树类，由于要第二步我们要进行排序比较大小，所以这个类要实现Comparable接口。本类对象包含六个个属性，count为节点的值，s为节点表示的字符，code为节点对应的编码，注意，后面两个属性只有叶节点才有。另外三个属性则是左子节点、右子节点、父节点（注，一般来说二叉树是只用设计左右节点即可，这里为了下文编写方便也设了父节点）
//定义这个类是为了把字符串转换成一个String数组和一个int数组，其中int数组存放的是对应string在字符串中的出现的次数（其实这里把String数组改成char数组更好，但是我懒得改了嘿嘿）
class TransferString{
int[] nl;
String[] sl;
public TransferString(int[] nl,String[] sl){
this.nl = nl;
this.sl = sl;
}
}
//这个就是Huffman树节点类啦
class HTreeNode implements Comparable<HTreeNode>{
Integer count;
String s;
String code = "";
HTreeNode left;
HTreeNode right;
HTreeNode parent;
//构造方法1
public HTreeNode(int count){
this.count = count;
}
//构造方法2
public HTreeNode(int count,String s){
this.count = count;
this.s = s;
}
@Override
public int compareTo(HTreeNode h) {
return this.count.compareTo(h.count);
}
}
ps：注意到count的类型是Integer而不是int，读者可自行查找一下两个数据类型的关系，int是不能compareTo的，但是Integer可以
下面是主体
import java.util.PriorityQueue;
import java.util.Queue;
public class Test {
//输入字符串，返回上述两个数组
private static TransferString transferString(String s){
char[] cl = s.toCharArray();
int[] counts = new int[26];
//数出每一个字母的频率
for(int i = 0; i < cl.length; i++) {
counts[cl[i] - 'a']++; // 'b' - 'a' = 1
}
//创建字母标准表
String[] std = "abcdefghijklmnopqrstuvwxyz".split("");
//数出不存在字母个数
int Number_Of_Zero=0;
for(int i=0;i<counts.length;i++){
if(counts[i]==0){
Number_Of_Zero++;
}
}
//定义新数组
int[] nl = new int[counts.length-Number_Of_Zero];
String[] sl = new String[counts.length-Number_Of_Zero];
int j=0; // 新数组的索引
for(int i=0;i<counts.length;i++){ // 遍历原来旧的数组
if(counts[i]!=0){ // 假如不等于0
nl[j]= counts[i];
sl[j]= std[i];// 赋值给新的数组
j++;
}
}
return new TransferString(nl,sl);
}
//通过两个数组，创建以Huffman树节点为元素的优先队列
private static Queue<HTreeNode> init(TransferString ts){
int[] ca = ts.nl;
String[] sa = ts.sl;
Queue<HTreeNode> q = new PriorityQueue<HTreeNode>();
for(int i=0;i<ca.length;i++){
HTreeNode h = new HTreeNode(ca[i],sa[i]);
q.add(h);
}
return q;
}
//更新，对应于第三步
public static void update(Queue<HTreeNode> q){
HTreeNode a = q.poll();
HTreeNode b = q.poll();
HTreeNode c = new HTreeNode(a.count+b.count);
c.left = a;
c.right = b;
a.parent = c;
b.parent = c;
q.add(c);
}
//左边编0右边编1，对树进行编码
private static void printTreeCode(HTreeNode t){
if(t.left!=null){
t.left.code += t.code+"0";
printTreeCode(t.left);
}
if(t.right!=null){
t.right.code += t.code+"1";
printTreeCode(t.right);
}
}
//用来输出树的节点对应的编码
private static void traversing(HTreeNode t){
if(t.s!=null){
System.out.println(t.s+" 的Huffman编码为："+t.code);
}
if (t.left!=null){
traversing(t.left);
}
if (t.right!=null){
traversing(t.right);
}
}
//主函数
public static void main(String[] args){
//输入字符串”interesting”
TransferString ts = transferString("interesting");
Queue<HTreeNode> q = init(ts);
while (q.size()>1){
update(q);
}
HTreeNode t = q.poll();
printTreeCode(t);
traversing(t);
}
}
代码执行效果
e 的Huffman编码为：00
t 的Huffman编码为：01
s 的Huffman编码为：100
g 的Huffman编码为：1010
r 的Huffman编码为：1011
n 的Huffman编码为：110
i 的Huffman编码为：111
