java代码实现-哈弗曼编码

    哈弗曼的原理，相信在任何一本数据结构书上都有，就是那么点东西，左0右1叶子串，前缀不能有重复，重者码短轻者长

1、 哈夫曼算法的应用?
   主要应用是编码和译码。编码可降低数据的冗余，可节省大约20%的空间（来自网络，说不定是和我一样的菜鸟统计出来的），一般对文件进行压缩与解压缩。 利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。

2、哈夫曼编码生成步骤：

  ①扫描要压缩的文件，对字符出现的频率进行计算。
  ②把字符按出现的频率进行排序，组成一个队列。
  ③把出现频率最低（权值）的两个字符作为叶子节点，它们的权值之和为根节点组成一棵树。
  ④把上面叶子节点的两个字符从队列中移除，并把它们组成的根节点加入到队列。
  ⑤把队列重新进行排序。重复步骤③④⑤直到队列中只有一个节点为止。
  ⑥把这棵树上的根节点定义为0（可自行定义0或1）左边为0，右边为1。这样就可以得到每个叶子节点的哈夫曼编码了。

 （此总结来自vegbird）

下面是java代码实现

public class HuffmanTree {
	//①以一段字符串模仿要压缩的文件，扫面，统计出每个字符出现的频率
	//返回字符队列
	public List<TreeData> countData(String s){
		//存放TreeData统计结果的list
		List<TreeData> datasList=new ArrayList();
		for(int i=0;i<s.length();i++){//顺序遍历字符串中的每个字符
			char c=s.charAt(i);//获取当前字符
			String cs=""+c;//将该字符转换为字符串
			boolean isExist=false;
			for(int t=0;t<datasList.size();t++){//遍历TreeData中的值
				TreeData tempData=new TreeData();
				tempData=datasList.get(t);//获取当前队列中的值
				if(tempData.getS().equals(cs)){//TreeData队列中已经存在cs字符
					tempData.setRate(tempData.getRate()+1);
					isExist=true;
					break;
				}
			}
			//如果不存在,创建一个TreeData对象，添加到队列中去
			if(!isExist){
				TreeData newData=new TreeData();
				newData.setS(cs);
				newData.setRate(1);
				datasList.add(newData);
			}
		}
		return datasList;
	}
	//将统计好的TreeData存放到TreeNode中去
	//返回TreeNode队列
	public List<TreeNode> change_to_TreeNode(List<TreeData> datas){
		List<TreeNode> nodeList=new ArrayList();
        for(int i=0;i<datas.size();i++){
        	TreeData data=datas.get(i);//获取datas当前的数据
        	TreeNode<TreeData> temp=new TreeNode();//新建一个TreeNode
        	temp.setElem(data);//将TreeData加入到新的TreeNode中
        	nodeList.add(temp);//将新的TreeNode加入到队列中去
        }
		
		return nodeList;
	}
	//②把字符按出现的频率进行排序，放入队列中
	//将统计好的TreeNode根据data的rate进行排序
	public void sort_Node(List<TreeNode> nodes){
		TreeNode<TreeData> temp=new TreeNode();
		for(int i=0;i<nodes.size();i++){
			TreeNode<TreeData> node_i=nodes.get(i);
			for(int j=i+1;j<nodes.size();j++){
                TreeNode<TreeData> node_j=nodes.get(j);
                temp.setLeft(node_j.getLeft());
                temp.setRight(node_j.getRight());
                temp.setElem(node_j.getElem());
				//如果rate_i>rate_j
                if(node_i.getElem().getRate()>node_j.getElem().getRate()){
                	node_j.setElem(node_i.getElem());
                	node_j.setLeft(node_i.getLeft());
                	node_j.setRight(node_i.getRight());
                	
                	node_i.setElem(temp.getElem());
                	node_i.setLeft(temp.getLeft());
                	node_i.setRight(temp.getLeft());
                }
			}
		}
	}

	//根据排序好的TreeNode建立哈弗曼树，返回树根节点
    public TreeNode create_Huff(List<TreeNode> nodes){
    	
    	while(true){
    		//⑤把队列重新进行排序。重复步骤③④⑤直到队列中只有一个节点为止。
    		sort_Node(nodes);
	    	//创建父节点
	    	TreeNode<TreeData> root=new TreeNode();
	    	//新建两个节点
	    	//③把出现频率最低（权值）的两个字符作为叶子节点，它们的权值之和
	    	//④把上面叶子节点的两个字符从队列中移除，并把它们组成的根节点加入到队列。
	    	TreeNode<TreeData> left=nodes.remove(0);//获取队列中当前首个节点
	    	TreeNode<TreeData> right=nodes.remove(0);//获取队列中当前首个节点
	    	TreeData data=new TreeData();
	    	data.setRate(left.getElem().getRate()+right.getElem().getRate());
	    	data.setS("我是内部节点");
	    	root.setElem(data);
	    	//建立关系
	    	root.setLeft(left);
	    	root.setRight(right);
	    	
	    	left.setParent(root);
	    	right.setParent(root);
	    	if(nodes.size()==0){//如果是最后一个节点
	    	   root.getElem().setS("我是根节点！");
	    	   return root;
	    	}
	    	//将父节点放入队列中
	    	nodes.add(0,root);
	    }
	    
    }	
	
	//查找指定字符对应的权值与huffman码辅助函数
    public String getHTRateHelp(String keyCode,String Hcode,TreeNode Hroot){
    	String hcode="";
    	TreeData data=new TreeData();
    	if(Hroot!=null){//递归结束条件
    		data=(TreeData) Hroot.getElem();//确保data不为空
    		if(Hroot.getLeft()==null&&Hroot.getRight()==null){//遍历到了叶节点
    			data.setHcode(Hcode);//将生成的huffman码赋值给叶节点的Hcode
    			if(keyCode.equals(data.getHcode())){
    				System.out.println("keyCode:"+keyCode+"--huffmanCode:"+Hcode);
    				hcode=Hcode;//将获取的哈弗曼码赋给hcode
    			}
    		}
    		//递归调用，在查找的同时生成哈弗曼码
    		//⑥把这棵树上的根节点定义为0（可自行定义0或1）左边为0，右边为1。
    		//这样就可以得到每个叶子节点的哈夫曼编码了。
    		getHTRateHelp(keyCode,Hcode+"0",Hroot.getLeft());
    		getHTRateHelp(keyCode,Hcode+"1",Hroot.getRight());
    	}
    	return hcode;
    }
    //输入指定字符，查找该字符对应的权值与huffman码
    public String getHTRate(String keyCode,TreeNode Hroot){
    	return getHTRateHelp(keyCode,"",Hroot);
    }
	//遍历打印出全树
    public void printTree(TreeNode Hroot){
    	TreeData data=new TreeData();
    	if(Hroot!=null){//递归结束条件
    		data=(TreeData) Hroot.getElem();
    		System.out.println("s:"+data.getS()+"--rate:"+data.getRate());
    		printTree(Hroot.getLeft());
        	printTree(Hroot.getRight());
    	}
    	
    }
    //遍历打印出H树
    public void printHTree(String hcode,TreeNode Hroot){
    	TreeData data=new TreeData();
    	if(Hroot!=null){//递归结束条件
    		data=(TreeData) Hroot.getElem();
    		if(Hroot.getLeft()==null&Hroot.getRight()==null){
    	    data.setHcode(hcode);//将获取的哈弗曼码赋给data的hcode
    		System.out.println("s:"+data.getS()+"--rate:"+data.getRate()
    				+"--hcode:"+data.getHcode());
    	        
    		}
    		printHTree(hcode+"0",Hroot.getLeft());
        	printHTree(hcode+"1",Hroot.getRight());
    	}
    	
    }
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		HuffmanTree ht=new HuffmanTree();
		String s="iwannllabefyyyyyfffeeeeeefffreeanwannwwwwwatofbrrtttoooolylalalalalalal";
		List<TreeData> datas=ht.countData(s);
        System.out.println("排序前：");
        for(int i=0;i<datas.size();i++){
        	TreeData data=datas.get(i);
        	System.out.println(i+": "+data);
        }
        
        List<TreeNode> nodes=ht.change_to_TreeNode(datas);//将datas的队列转存到nodes队列中去
        ht.sort_Node(nodes);//对队列进行排序
        System.out.println("排序后：");
        for(int i=0;i<nodes.size();i++){
        	TreeNode node=nodes.get(i);
        	System.out.println(i+": "+node.getElem());
        }
        
        TreeNode Hroot=ht.create_Huff(nodes);
        System.out.println("整个树为：");
        ht.printTree(Hroot);
        System.out.println("哈弗曼树叶节点编码为：");
        ht.printHTree("", Hroot);//需要传入一个空串！！代表根节点路径
        String findcode="s";//查找字符findcode的哈弗曼码
        ht.getHTRate(findcode,Hroot);
        
	}

}

 

 

   这段代码之前照本宣科的写了一遍，但前几天总结时再写一遍才真正的闻到到一点这段代码所实现的逻辑和功能的味道。

   3、解码就是把编码的过程反过来执行一遍。

 

 

评论

2 楼 Adminduan 2013-03-26  

Adminduan 写道

你好，请问一下文中的treeNode是什么？还望指教

我觉的该类中有 treedate elem ,left，right，但是在排序的时候突然冒出来 left和right这个值是什么那？

1 楼 Adminduan 2013-03-26  

你好，请问一下文中的treeNode是什么？还望指教