先说编码是怎样一回事，我们都知道，计算机本质上来说，只能储存两种东西，即数字0和1。但是你在电脑上却可以存储文字、图片、声音、视频等等。其实你存储在计算机内部的并不是文字和图片，而是一串一串的0和1。这些特定顺序的0和1通过某种映射一一对应到你要保存到文字等，这样这串01串在你面前就变现出了文字或者是图片的样子。这也可以解释，为啥你用一个软件编写好的文档，用另一个软件打开就全是乱码，其本质是这个一一映射不同。
假如说我们现在要储存一串字符:“interesting”
在计算机中，西文字符都是用ASCII编码来存储的，在ASCII码的编码表中一共定义了256个不同的字符，由于，所以按道理来说至少需要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编码就要花费。但是你会发现，ASCII码中定义了256个字符，而你在这个字符串中，只定义了7个字符，所以用ASCII码来编码是一种很浪费的方法。一种更好的压缩方法是用对每个你要编码的字符，用三位二进制数来表示。因为，所以其实三位二进制足够表示这些字符了。
以下给出一种一一对应的方式（其实还有很多种对应方式）
| 字符 | 出现次数 | 三位二进制编码 |
|---|---|---|
| i | 2 | 000 |
| n | 2 | 001 |
| t | 2 | 010 |
| e | 2 | 011 |
| r | 1 | 100 |
| s | 1 | 101 |
| g | 1 | 110 |
用这种方法来编码的话，你只需花费就可以了，大小仅为ASCII编码的大小的37.5%。
但是很快你会发现两个问题
事实上，上面二者都属于不可变长度编码(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就找到了这种方法，虽然当时的他初衷其实是为了逃避考试。
1951年，哈夫曼和他在MIT信息论的同学需要选择是完成学期报告还是期末考试。Huffman在划水划了一学期自认为啥也没学到不敢考试，自然就选择了用论文的方式逃避考试。导师Robert M. Fano给他们的学期报告的题目是，寻找最有效的二进制编码。由于无法证明哪个已有编码是最有效的，哈夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。由于这个算法，学生终于青出于蓝，超过了他那曾经和信息论创立者香农共同研究过类似编码的导师。哈夫曼使用自底向上的方法构建二叉树，避免了次优算法Shannon-Fano编码的最大弊端──自顶向下构建树。
我们开始今天的主角终于登场了：Huffman编码
先说说Huffman编码的一般过程，首先我们的输入是一串字符串
然后我们就可以找到每一个字符对应的编码啦
下面就以“interesting”为例使用Huffman编码压缩
首先我们找到了出现次数最少的两个字符：“g”和“r”各出现了一次，我们把它们组成一颗二叉树，“g”和“r”所在的为叶节点，节点对应数据为1和1，他们的父节点表示的值为。
现在我们相当于还剩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 |
这种编码所占空间大小为，看，是不是比原来的33少一些了，而且也没有发生上述开头重复的问题。
首先我们创建一个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
本文地址：https://blog.csdn.net/qq_44941745/article/details/107370818
如对本文有疑问， 点击进行留言回复！！
网友评论