文件压缩总结（哈夫曼压缩）
  在学习哈弗曼压缩之前，还是首先来了解什么是哈夫曼树，哈夫曼编码。
  1.哈夫曼树是一种最优二叉树，它的带权路径长度达到最小。树的带权路径长度为所有叶子结点带权路径长度之和。
而结点的带权路径长度是结点的路径长度乘以结点的权值。
  2.哈夫曼编码是依据字符出现概率来构造异字头的平均长度最短的码字。从哈弗曼树的根结点开始，按照左子树代码为“0”，右子树代码为“1”的规则，直到树的叶子结点，每个叶子结点的哈弗曼编码就是从根结点开始，将途中经过的枝结点和叶子结点的代码按顺序串起来。
 
  哈夫曼压缩是字节符号用一个特定长度的01序列替代，在文件中出现频率高的符号，使用短的01序列，而出现频率少的字节符号，则用较长的01序列表示。
  这里的文件压缩，我还只能做简单的 文件A-->压缩为文件B--->解压为文件C，看文件A和文件C是不是相同。
那么就要分两个大步骤，小步骤：
  不过，根据哈弗曼树的特点，我们首先还是要定义结点类型
 
结点类型代码
1. public class TreeNode {   
2.     public TreeNode  parent; //双亲结点   
3.     public TreeNode   left;  //左孩子结点   
4.     public TreeNode   right; //右孩子结点   
5.        
6.     public byte con;// 结点的数据   
7.     public int  rate;   
8.     public  String  bian="";   
9.     public int count=0;   
10.     public TreeNode(byte con, int rate) {   
11.         super();   
12.         = con;   
13.         this.rate = rate;   
14.        }   
15.      } 
public class TreeNode {
    public TreeNode  parent; //双亲结点
    public TreeNode  left;  //左孩子结点
    public TreeNode  right; //右孩子结点
   
    public byte con;// 结点的数据
    public int  rate;
    public  String  bian="";
    public int count=0;
    public TreeNode(byte con, int rate) {
        super();
        = con;
        this.rate = rate;
      }
    }
 
 
 然后分两大步骤
一. 首先压缩文件
1. 将源文件A中数据按字节读取，然后用MAP统计每个字节出现的次数（Key--不同的字节，value--次数）。
   
统计频率代码  
1. while (t != -1) {// 如果未到达结尾   
2.     byte b = (byte) t;   
3.        
4.     if (ainsKey(b)) {// 如果map里面包含number键   
5.      int value =&(b);// 就可以通过get函数得到number对应的value的值   
6.      value++;// 使次数加1 
7.         
8.      map.put(b, value);   
9.     } else {// 如果map里面不包含number键   
10.      map.put(b, 1);// number的次数只有一次   
11.     }   
12.     // 继续读取下一个   
13.     t =&ad();   
14.  
15.    } 
while (t != -1) {// 如果未到达结尾
    byte b = (byte) t;
   
    if (ainsKey(b)) {// 如果map里面包含number键
    int value = (b);// 就可以通过get函数得到number对应的value的值
    value++;// 使次数加1
   
    map.put(b, value);
    } else {// 如果map里面不包含number键
    map.put(b, 1);// number的次数只有一次
    }
    // 继续读取下一个
    t = ad();
  }
 
  2. 将Map中的value值作为权值，建哈夫曼树，并得到每个字节的哈弗曼编码。
   
创建哈树代码
哈夫曼编码树的带权路径长度1. /**   
2.   * 创建哈树   
3.   * @param nodeQueue  已经得到的优先队列   
4.   * @return     创建哈树后，返回树的根结点   
5.   */   
6.  public static TreeNode creatTree(PriorityQueue<TreeNode> nodeQueue){   
7.   byte a=0;  //定义一个byte，用来表示  枝节点的 字节   
8.   TreeNode  root=null;   //用来表示树的根结点   
9.   while(nodeQueue.size()>=2){  //当优先队列中 的元素大于2 时，还可以使它们组成新的跟结点   
10.    TreeNode left=nodeQueue.poll();        //获取当前队列中的最小元素，并将队列中的该元素删除  。是该节点作为左孩子   
11.    TreeNode right=nodeQueue.poll();           //获取当前队列中的最小元素，作为右孩子   
12.    root=new TreeNode(a,left.rate+right.rate);     //左右孩子的频率之和作为 根结点的 频率   
13.    root.left=left;                              //连接孩子结点和根结点的关系   
14.    root.right=right;   
15.    if(nodeQueue.size()==0){           
16.     return  root;   
17.    }   
18.    nodeQueue.add(root);   
19.   }   
20.   return root;   
21.  } 
/**
  * 创建哈树
  * @param nodeQueue  已经得到的优先队列
  * @return    创建哈树后，返回树的根结点
  */
public static TreeNode creatTree(PriorityQueue<TreeNode> nodeQueue){
  byte a=0;  //定义一个byte，用来表示  枝节点的 字节
  TreeNode  root=null;  //用来表示树的根结点
  while(nodeQueue.size()>=2){  //当优先队列中 的元素大于2 时，还可以使它们组成新的跟结点
  TreeNode left=nodeQueue.poll();        //获取当前队列中的最小元素，并将队列中的该元素删除  。是该节点作为左孩子
  TreeNode right=nodeQueue.poll();          //获取当前队列中的最小元素，作为右孩子
  root=new TreeNode(a,left.rate+right.rate);    //左右孩子的频率之和作为 根结点的 频率
  root.left=left;                              //连接孩子结点和根结点的关系
  root.right=right;
  if(nodeQueue.size()==0){       
    return  root;
  }
  nodeQueue.add(root);
  }
  return root;
}
 
得到哈夫曼编码代码
1. /**   
2.  * 得到哈树 叶子结点的哈弗曼编码   
3.  * @param node   哈树的根结点   
4.  * @return      将叶子结点的  《字节，编码》存放入 map 中返回   
5.  */   
6. public  static HashMap<Byte,String>  getCode(TreeNode  node){   
7.  !=(byte)0){   
8.      System.out.println((+"--zuo--"+node.bian);   
9.      codemap., node.bian);   
10.     }   
11.  TreeNode  left=node.left;    // 获得左孩子结点   
12.     if(left!=null){              //若为非空  则获得它的 哈弗曼编码   
13.        left.bian=node.bian+"0";   
14.       &unt++;   
15.        getCode(left);   
16.     }   
17.     TreeNode  right=node.right;      // 获得右孩子结点   
18.     if(right!=null){                   //若为非空  则获得它的 哈弗曼编码   
19.      right.bian=node.bian+"1";   
20.     &unt++;   
21.      getCode(right);   
22.     }   
23.  return  codemap;   
24. } 
/**
  * 得到哈树 叶子结点的哈弗曼编码

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。