哈弗曼算法简介及应用

        哈夫曼算法就是应用哈夫曼树对对象进行编码的方法，哈夫曼算法的主要应用是文件压缩与解压。在介绍如何用java实现哈夫曼算之前先说一下路径和路径长度、结点的权及带权路径长度,树的带权路径，哈夫曼树的构造和哈夫曼编码。

1、路径和路径长度

　　在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。

2、结点的权及带权路径长度

　　若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。

3、树的带权路径长度

　　树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。

4、哈夫曼树的构造

　　

   假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、…、wn，则哈夫曼树的构造规则为：

　　(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；

　　(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；

　　(3)从森林中删除选取的两棵树，并将新树加入森林；

(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。^[

5、哈夫曼的编码

   哈夫曼编码(Huffman Coding)是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。uffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。

6、用java实现哈夫曼树的建立

1.给定一段字符串，统计每一个字符出现的频率

2.根据这个频率，生成一个哈树，

3.当输入其中一个字符时，输出其在哈树上对应的哈码

 

1.首先构建数中的元素

//哈夫曼树的结点类型

 

public class HTreeNode<E> {

public HTreeNode parent;//父节点

public HTreeNode left;  //左节点

public HTreeNode right; //右节点

public  E Hdata;  //数据

}

1.  指定数据类型的内容

//树节点上的数据对象

public class TreeData {

 

public String s;//字符

  public int count;//出现频率

  }

3.import java.util.ArrayList;

import java.util.List;

public class HTreeTest {

//1.给定一段字符串，统计每一个字符出现的频率

public List<TreeData> getDatas(String s){

      List<TreeData>  datas=new ArrayList();

     

       for(int i=0;i<s.length();i++){

             char c=s.charAt(i);

             String cs=""+c;

             boolean exits=false;

             for(int t=0;t<datas.size();t++){

                   TreeData tem=datas.get(t);

                   if(tem.s.equals(cs)){//队中己有啦!

                        tem.count++;//出现了一次,累加吧

                        exits=true;

                        break;

                   }

             }

             if(!exits){

             //在创建对象,向队列中加入之前,要先查看队中是否己有?

             TreeData data=new TreeData();

             data.count=1;

             data.s=cs;

             datas.add(data);

             }

             

             

       }

     

      return datas;

}

public static void main(String[] args) {

      HTreeTest ht=new HTreeTest();

       String s="abcdefgaaaaaabbcccccccccccceff";

       List<TreeData> datas= ht.getDatas(s);

       System.out.println("排序前: ");

       for(int i=0;i<datas.size();i++){

             TreeData d=datas.get(i);

             System.out.println(d);

       }

       System.out.println("**********排序后: ");

       List<TreeNode> nods= ht.getNodes(datas);//转为节点队列了

       

       

         ht.sortNodes(nods);//排序

       for(int i=0;i<nods.size();i++){

             TreeNode<TreeData> td=nods.get(i);

             System.out.println(" "+td.data.s+" -- "+td.data.count);

         }

       //创建树:

       TreeNode root =ht.createHTree(nods);

       //打印哈码输出

       ht.pt(root,"");

       

 

        }

//将统计的Treedata对象队列,转为treeNode对象队列

public List<TreeNode> getNodes(List<TreeData> datas){

       List<TreeNode> nodes=new ArrayList();

      for(int i=0;i<datas.size();i++){

            TreeData data=datas.get(i);

             //创建node对象,将data加入这个node

            TreeNode node=new TreeNode();

            node.data=data;

            //将node(包含有data)放入队列中

            nodes.add(node);

      }

      return nodes;

}

//对节点对象队列根据权值排序,由小到大

public void sortNodes(List<TreeNode> nods){

      for(int i=0;i<nods.size();i++){

            for(int j=i+1;j<nods.size();j++){

                  TreeNode<TreeData> ni=nods.get(i);

                  TreeNode<TreeData> nj=nods.get(j);

                  //临时变量

//                     TreeNode<TreeData> tem=new TreeNode<TreeData>();

//                     TreeData temData=new TreeData();

//                     temData.s=nj.data.s;

//                     temData.count=nj.data.count;

//                     tem.data=temData;

                  int count=nj.data.count;

                  String s=nj.data.s;

                 

                  if(ni.data.count>nj.data.count){

                       nj.data.count=ni.data.count;

                       nj.data.s=ni.data.s;

                      

                       ni.data.count=count;

                       ni.data.s=s;

                  }

            }

      }

     

}

//根据生成的数据对象，创建一个哈树,返回树的根节点

public TreeNode createHTree(List<TreeNode> datas){

          while(true){

               //先要对节点队列排序

               sortNodes(datas);

              

      //假设传入队列数据权值都己排好了序,而且不用二次排序

      TreeNode<TreeData> left=datas.remove(0);

      TreeNode<TreeData> right=datas.remove(0);

      //创建一个父节点

      TreeNode<TreeData> root=new TreeNode();

      //给父节点设数据:

      TreeData td=new TreeData();

      td.count=left.data.count+right.data.count;

      td.s="父节";

      root.data=td;

      //关联关系

      root.left=left;

      root.right=right;

      left.parent=root;

      right.parent=root;

      if(datas.size()==0){//是最后一个了，根节点，反回

            return root;

      }

      //将父节放入队中首位:

      datas.add(0, root);

      }

       

}

/**

 * 根据输入的字符input,取得其在哈树上的哈码返回

 * @param input:输入的字符

 * @param hRoot:哈树的根节点

 * @return:从树上取得的哈夫曼编码

 */

public String getHM(String input,TreeNode hRoot){

      return null;

}

//遍历树来打印,输出叶的哈码

public void pt(TreeNode<TreeData> root,String hm){

       if(null!=root){

             if(root.left==null&&root.right==null){

             TreeData d=root.data;

             System.out.println(d+" 哈码是:"+hm);//打印

             }

             TreeNode<TreeData> left=root.left;

             String m=hm+="0";

             pt(left,m);

             

             TreeNode<TreeData> right=root.right;

             pt(right,hm+="1");

       }

}

}