huffmancoding.java

根据huffman树的一个压缩程序

import java.io.*;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.RandomAccessFile;
public class HuffmanCoding {//统计频率，建树，编码的类
	public int i=0;
	public int [] dat=new int[256];//以每一个byte作索引存该byte出线频率
	private HuffmanNode HuffmanTree;//根节点
	public HuffmanNode[] node=new HuffmanNode[256];//以每一个byte作索引创建huffmanNode的数组
	public HuffmanCoding(){//构造函数，初始化两个数组
		for(int m=0;m<256;m++){
			dat[m]=0;
			node[m]=new HuffmanNode((byte)0,0,0,null,null);
		}
	}
	
    protected int[] freq(DataInputStream fin)throws IOException{//统计频率
		byte ch1;
		try{
			while(true){
				ch1=fin.readByte();
				dat[ch1+128]++;//对应的数组位置加一
			}
		}catch(EOFException n){
		}
		return dat;
	}
	
	protected HuffmanNode createHuffmanTree(int[] dat){//建树
		int []tmp=new int[256];
		System.arraycopy(dat, 0, tmp, 0, 256);//复制原统计数组
		LinkedListNode p,newNode,head,tail;
		head=tail=new LinkedListNode();//创建链表的头和尾，用于排序
		for(int i=0;i<256;i++){
			int min=tmp[0];
			int minIndex=0;
			for(int j=1;j<256;j++){//每次找到频率最小的，得到min和minIndex
				if(tmp[j]<=min) {
					min=tmp[j];
					minIndex=j;
				}				
			}
			tmp[minIndex]=2000000000;//把找到的最小频率元素赋值最大，以防止之后循环时候再被搜索到
			tail.next=new LinkedListNode(null,tail);//在tail的后面创建一个节点
			tail=tail.next;//尾节点指向他
			if(min!=0){//如果min不为零，也就是出现过，那么新建一个每次频率最小的HuffmanNode
				tail.tree=new HuffmanNode((byte)(minIndex-128),min,0,null,null);
				if (head.tree==null) head=tail;//头节点赋值
				else if (head.next.tree==null) head.next=tail;//第二个节点赋值
				}
		}
		while(head!=tail){
			int newFreq=head.tree.frequency+head.next.tree.frequency;//把最小的两个频率相加
			for(p=tail;p!=null&&p.tree.frequency>=newFreq;p=p.prev);//找到第一个比这个大的频率，并插在前面
			newNode=new LinkedListNode(p.next,p);
			p.next=newNode;
			if (p==tail) tail=newNode;
			else newNode.next.prev=newNode;
			newNode.tree=new HuffmanNode((byte)0,newFreq,0,head.tree,head.next.tree);//同时新建一个HuffmanNode,前后指向刚才最小的频率的节点
			head=head.next.next;
			head.prev=null;
		}
		HuffmanTree=head.tree;
		return HuffmanTree;//返回首节点
	}
	protected void createCode(HuffmanNode p,int code,int level){//创建编码
		if (p.left==null&&p.right==null){
			p.code=code;
			p.codewordLen=level;
			node[p.sign+128].code=code;//对HuffmanNode节点赋编码值
			node[p.sign+128].codewordLen=level;//对HuffmanNode节点赋编码长度值
		}
		else{
			createCode(p.left,2*code+1,level+1);//递归遍历树以创建节点
			createCode(p.right,2*code,level+1);
		}
	}
	
}