对于我们的日常操作压缩文件来说，通常都是将文件中的字符转换成压缩后的格式，但为什么能够解压回来，那是因为压缩后的数据形式总是和原字符唯一对应的。因为计算机总是以0/1保存文件，那编码过程中也是将文件转化成更小的0/1序列，起到压缩的作用。比如：
对于一个字符a来说，计算机是用8bit来保存字符的，如果我们可以唯一用一个bit的0来表示这个a，那这一个字符就为计算机节省了7bit的空间。
哈夫曼树唯一标识字符
在给定一些字符的时候，我们需要用二进制编码f(x)表示字符x，且在识别的过程中不会产生冲突，那很容易理解的一点是对于任意f(a)来说绝对不会出现一个f(b)使得f(a)可以作为f(b)的前缀。
example：
a: 110表示
b: 1100表示
那么对于一个压缩后的编码1101100来说当识别到110的时候，无法判断这个是否已经是a了还是否继续识别，因为是存在b的可能性的，这就是所谓的编码冲突。
将这个放到树上来理解，从根节点出发0表示向左子树走，1表示向右子树走，最后走到最低端的叶子节点就是对这个叶子节点字符对应的编码。
按照上述，那么在这个树上一定不可能出现在朝一个叶子上的字符往下走的过程中遇到其他编码的字符，因为这样的结果一定会产生前缀。
所以这是哈夫曼树的一个重要特性。
哈夫曼树的基本原理
哈夫曼树上每一个点都对应一个权值，这个权值希望的是最后编码出来的结果尽可能用到的0/1数目少。那么我们在这里也就把权值理解成对于一个编码字符串的每一个字符出现的个数，简单理解就是出现越多的字符希望编码结果尽可能短，那么它总的结果就会尽可能短。
那么根据哈夫曼树的定义就是：
一棵二叉树要使其WPL值最小，必须使权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。
哈夫曼根据这一点提出了一种构造最优二叉树的方法，基本思想如下：
- 根据给定的n个权值{w1 , w2 , w3 , ... , wn},构造n棵只有根节点的二叉树，令其权值为wi。
- 在森林中选取两棵根节点权值最小的树作为左右子树，构造一棵新的二叉树，置新的二叉树的权值为左右子树的权值和。
- 在森林中删去这两棵已被合并的树，将新得到的二叉树加入到森林中。
- 重复以上两步，直到最后森林中只含有一棵树，那么这棵树就是哈夫曼树。
下面用huffman算法构造一棵树的过程实例：
Huffman算法
哈夫曼树在编码中的应用
在电文传输中，需要将电文中出现的每个字符进行二进制编码。在设计编码时需要遵守两个原则：
（1）发送方传输的二进制编码，到接收方解码后必须具有唯一性，即解码结果与发送方发送的电文完全一样；
（2）发送的二进制编码尽可能地短。下面我们介绍两种编码的方式。
-
等长编码
这种编码方式的特点是每个字符的编码长度相同（编码长度就是每个编码所含的二进制位数）。假设字符集只含有4个字符A，B，C，D，用二进制两位表示的编码分别为00，01，10，11。若现在有一段电文为：ABACCDA，则应发送二进制序列：00010010101100，总长度为14位。当接收方接收到这段电文后，将按两位一段进行译码。这种编码的特点是译码简单且具有唯一性，但编码长度并不是最短的。 -
不等长编码
在传送电文时，为了使其二进制位数尽可能地少，可以将每个字符的编码设计为不等长的，使用频度较高的字符分配一个相对比较短的编码，使用频度较低的字符分配一个比较长的编码。例如，可以为A，B，C，D四个字符分别分配0，00，1，01，并可将上述电文用二进制序列：000011010发送，其长度只有9个二进制位，但随之带来了一个问题，接收方接到这段电文后无法进行译码，因为无法断定前面4个0是4个A，1个B、2个A，还是2个B，即译码不唯一，因此这种编码方法不可使用。
因此，为了设计长短不等的编码，以便减少电文的总长，还必须考虑编码的唯一性，即在建立不等长编码时必须使任何一个字符的编码都不是另一个字符的前缀，这宗编码称为前缀编码（prefix code）
（1）利用字符集中每个字符的使用频率作为权值构造一个哈夫曼树；
（2）从根结点开始，为到每个叶子结点路径上的左分支赋予0，右分支赋予1，并从根到叶子方向形成该叶子结点的编码
哈夫曼编码的实现
下方的Java代码实现当中用到了对自定义的HuffmanNode为了做到有序排列放到了HashSet容器中保存，要注意的一点是不能放到LinkedHashSet中，这个对象是根据存储顺序保存的。
因为这个顺序和hash值有关，所以要自定义对象的hash值获取函数,这下方的两个函数都是定义在对象当中的。
不用到这个的话可以根据我内容中写到的用普通的vector容器进行保存，当然vector的效率比set会慢很多。
//下方两个函数是自定义对象保存在有序容器中所必须的
public boolean equals(Object other){
HuffmanNode obj = (HuffmanNode)other;
if(obj.value != this.value || obj.left != this.left ||
obj.right != this.right || obj.ch != this.ch)
return false;
return true;
}
//最后HashSet中是根据对象hashCode()得到的hash码来排序
public int hashCode(){
return value;
}
/**
* Created by ganjun on 2017/5/26.
*/
import java.util.*;
public class Huffman {
class HuffmanNode{
public int value;
public HuffmanNode left;
public HuffmanNode right;
char ch ;
HuffmanNode(){
this.value = 0;
this.ch = '\0';
}
HuffmanNode(int value , char ch){
this.value = value ;
this.ch = ch ;
left = null;
right = null;
}
HuffmanNode(int value , HuffmanNode lf , HuffmanNode rg , char ch){
this.value = value ;
this.ch = ch ;
left = lf;
right = rg;
}
//下方两个函数是自定义对象保存在有序容器中所必须的
public boolean equals(Object other){
HuffmanNode obj = (HuffmanNode)other;
if(obj.value != this.value || obj.left != this.left ||
obj.right != this.right || obj.ch != this.ch)
return false;
return true;
}
//最后HashSet中是根据对象hashCode()得到的hash码来排序
public int hashCode(){
return value;
}
}
public int [] count = new int[256]; //计算每个字符出现的次数
public String article;
//用不同的容器保存节点，效果上一样，用不同的方法计算，效率上会有差距
public Vector<HuffmanNode> existConnectNodes = new Vector<HuffmanNode>(); //还未有父亲连接的所有节点集合
public Set<HuffmanNode> existConnectNodesSet = new HashSet<HuffmanNode>(); //还未有父亲连接的所有节点集合
public void calCharCounts(String str){
for(int i=0 ; i<str.length() ; i++){
count[str.charAt(i)] ++;
}
for(int i=0 ; i<256 ; i++){
if(count[i]>0){
existConnectNodes.add(new HuffmanNode(count[i] , (char)i));
existConnectNodesSet.add(new HuffmanNode(count[i] , (char)i));
}
}
System.out.println("当前字符出现对应的数量如下");
Iterator<HuffmanNode> iter = existConnectNodesSet.iterator();
while(iter.hasNext()){
HuffmanNode obj = iter.next();
System.out.println("字符"+obj.ch+"有"+obj.value+"个");
}
}
//通过vector来保存哈夫曼树的节点，返回哈夫曼树的根节点
public HuffmanNode generateTreeByVector(){
while(existConnectNodes.size() > 1){
//找到最小的前两名的Huffman节点
int minv = 0 , secMinv = 0;
int minIndex = 0 , secMinIndex = 0;
if(existConnectNodes.get(0).value > existConnectNodes.get(1).value){
minv = existConnectNodes.get(1).value;
secMinv = existConnectNodes.get(0).value;
minIndex = 1 ;
secMinIndex = 0;
}
else{
minv = existConnectNodes.get(0).value;
secMinv = existConnectNodes.get(1).value;
minIndex = 0;
secMinIndex = 1;
}
for (int i=2 ; i<existConnectNodes.size() ; i++){
if(existConnectNodes.get(i).value < minv){
secMinv = minv;
secMinIndex = minIndex;
minv = existConnectNodes.get(i).value;
minIndex = i;
}
else if(existConnectNodes.get(i).value < secMinv){
secMinv = existConnectNodes.get(i).value;
secMinIndex = i;
}
}
//形成新的节点
HuffmanNode nodelf = existConnectNodes.get(minIndex);
HuffmanNode noderg = existConnectNodes.get(secMinIndex);
HuffmanNode unionNode = new HuffmanNode(
nodelf.value+noderg.value , nodelf , noderg , '\0');
existConnectNodes.remove(nodelf);
existConnectNodes.remove(noderg);
existConnectNodes.add(unionNode);
}
//最后里面就只剩下一个元素了
return (HuffmanNode)(existConnectNodes.get(0));
}
//通过Set来保存哈夫曼树的节点，返回哈夫曼树的根节点
public HuffmanNode generateTreeBySet(){
while(existConnectNodesSet.size() > 1){
//找到最小的前两名的Huffman节点
//形成新的节点
Iterator<HuffmanNode> iter = existConnectNodesSet.iterator();
HuffmanNode nodelf = iter.next();
HuffmanNode noderg = iter.next();
HuffmanNode unionNode = new HuffmanNode(
nodelf.value+noderg.value , nodelf , noderg , '\0');
existConnectNodesSet.remove(nodelf);
existConnectNodesSet.remove(noderg);
existConnectNodesSet.add(unionNode);
}
//最后里面就只剩下一个元素了
Iterator<HuffmanNode> iter = existConnectNodesSet.iterator();
return (HuffmanNode)(iter.next());
}
public void viewTree(HuffmanNode root , String code){
if(root.ch != '\0'){
System.out.println("字符"+root.ch+" --> "+code);
}
else{
if(root.left != null)
viewTree(root.left , code+"0");
if(root.right != null)
viewTree(root.right , code+"1");
}
}
public static void main(String [] args){
Huffman sol = new Huffman();
sol.calCharCounts("512511344");
HuffmanNode root = sol.generateTreeBySet();
// HuffmanNode root = sol.generateTreeByVector(); //这种方法是通过Vector容器来保存的，原理都是一样的
System.out.println("最后编码结果为");
sol.viewTree(root , "");
}
}
网友评论