huffmantree.java

对文本信息进行哈夫曼加密

package wlf;


import java.io.*;
import java.util.*;

public class HuffmanTree implements Serializable{
	
	private static final long serialVersionUID = 6451783175978325130L;
	//	根节点
	public HuffmanNode root;
	//	保存编码用的对照表
	private Hashtable<Character,String> table;
	
	public HuffmanTree()
	{
		table=new Hashtable<Character,String>();
	}
	
	/**
	 * 生成哈夫曼树
	 * @param letters: 元素数组
	 * @param counts:  元素对应的频率数组
	 */
	public void generateTree(char[] letters,int[] counts)
	{
		Queue<HuffmanNode> q=new ArrayDeque<HuffmanNode>();
		//将字符出现的频率表加入队列中
		for(int i=0;i<letters.length;i++)
		{
			q.add(new HuffmanNode(letters[i],counts[i]));
		}
		while(true)
		{
			sort(q);//对队列排序
			HuffmanNode a=q.remove();//删除当前count最小的节点
			//a是该树的根节点
			if(q.isEmpty())
			{
				root=a;
				return;
			}
			HuffmanNode b=q.remove();//删除当前count第二小的节点
			q.add(new HuffmanNode(a,b));//增加新的节点（由a、b得到）
		}
	}
	/**
	 * 对队列进行冒泡排序
	 * @param q：保存元素频率的数组
	 */
	private void sort(Queue<HuffmanNode> q)
	{
		int i,j;
		int size=q.size();//得到队列大小
		HuffmanNode[] elements=new HuffmanNode[size];//建立暂存数组
		HuffmanNode temp=new HuffmanNode('?',0);//临时变量
		/**
		 * 记录并清空队列
		 */
		for(i=0;i<size;i++)
		{
			elements[i]=(HuffmanNode)q.remove();
		}
		//冒泡排序
		for(i=0;i<size;i++)
			for(j=0;j<size-i-1;j++)
			{
				if(elements[j].compareTo(elements[j+1])>0)
				{
					temp=elements[j];
					elements[j]=elements[j+1];
					elements[j+1]=temp;
				}
			}
		//将排序后的元素（HuffmanNode类型）重新加入到空队列中
		for(i=0;i<size;i++)
			q.add(elements[i]);
	}
	
	/**
	 * 产生哈夫曼编码
	 *
	 */
	public void generateCodes()
	{
		generateCodes(root,"");
	}
	/**
	 * 递归产生哈夫曼编码
	 *
	 */
	private void generateCodes(BinaryNode<Character> root,String code)
	{
		if(root.isLeaf())
		{
			table.put(root.getItem(),code);
		}else{
			generateCodes(root.getLeft(),code+"0");
			generateCodes(root.getRight(),code+"1");
		}
	}
	/**
	 * 对源信息进行哈夫曼编码
	 * @param message
	 * @return 信息的哈夫曼编码
	 */
	public String encode(String message)
	{
		StringBuilder result=new StringBuilder();
		//JDK5.0的新特性，增强的for循环
		for(char c : message.toCharArray())
		{
			result.append(table.get(c));
		}
		return result.toString();
	}
	/**
	 * 对哈夫曼编码进行解码
	 * @param codes
	 * @return 当前编码对应的源信息
	 */
	public String decode(String codes)
	{
		StringBuilder result=new StringBuilder();
		BinaryNode<Character> node=root;
		//JDK5.0的新特性，增强的for循环
		for(char c : codes.toCharArray())
		{
			if(c=='0')
			{
				node=node.getLeft();
			}else if(c=='1'){
				node=node.getRight();
			}
			if(node.isLeaf())
			{
				result.append(node.getItem());
				node=root;
			}
		}
		return result.toString();
	}
}