compress.java

huffman字符编码的java实现

package Huffman;

import java.io.*;
import java.util.*;
import javax.imageio.stream.*;


public class Compress{
	private byte [] input,output;
	private byte []table=new byte[10000];//symbol table
	private int length=0,filelength;//length of table  
	private int [] count=new int [10000];
	private Vector[] HC;
	private File inname,outname;
	
	public Compress (File in,File out){
		inname=in;
		outname=out;
	}
	
	private void readFile(){
		try{
			filelength=(int)inname.length();
			input=new byte[filelength+1];
			FileInputStream infile=new FileInputStream(inname);
			infile.read(input,1,filelength);
			infile.close();
			}
		catch(FileNotFoundException e){
			}
		catch(IOException e){
		} 
	}
	
	private int lookup(byte c){
		for(int i=1;i<=length;i++){
			if(c==table[i]) return i;
		}
		return 0;
	}
	
	private void check(){
		byte c;
		int j;
		for(int i=1;i<=filelength;i++){
			c=input[i];
			j=lookup(c);
			if(j==0)
			{
				table[++length]=c;
				//System.out.print(c+" ");
				count[length]=1;
			}
			else{
				count[j]++;
			}
		}
		//System.out.print(length+" ");
		//for(int h=1;h<=length;h++)
		//System.out.print(table[h]+","+count[h]+" ");
	}
	
	private void HuffmanCoding(){
		int n=length;
		int m=2*n-1;
		int i;
		//System.out.print(n+" "+m+" ");
		HTNode [] HT=new HTNode[m+1];
		for(i=1;i<=n;i++) HT[i]=new  HTNode(count[i],0,0,0);
		for(;i<=m;i++) HT[i]=new HTNode(0,0,0,0);
		
		for(i=n+1;i<=m;i++) {
			int s1=0,s2=0;
			int w1=10000,w2=10000;
			for(int j=1;j<=i-1;j++)
			{
				if(HT[j].parent==0)
				{
					if(HT[j].weight<w1) 
					{
						w2=w1;
						w1=HT[j].weight;
						s2=s1;
						s1=j;
						//System.out.print(j+" "+s1+","+w1+" ");
					}
						
					else if(HT[j].weight<w2)
					{
						s2=j;
						w2=HT[j].weight;
						//System.out.print("kk ");
					}
				}
			}
			//System.out.print(s1+","+s2+" ");
			HT[s1].parent=i;
			HT[s2].parent=i;
			HT[i].lchild=s1;
			HT[i].rchild=s2;
			HT[i].weight=HT[s1].weight+HT[s2].weight;
		}//create HuffTree
		
		//for(i=1;i<=m;i++)
		//System.out.print(HT[i].weight+" ");
		
		HC=new Vector[n+1];
		for(i=1;i<=n;i++){
			int c,f;
			
			HC[i]=new Vector();
			Vector v=HC[i];
			for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
			{
				if(HT[f].lchild==c) 
				v.insertElementAt(0,0);	//HC 0...size
				else v.insertElementAt(1,0);
			}
			
		}
		/*for(i=1;i<=n;i++)    //code detect
		{
			System.out.print(table[i]+":");
			for(int j=0;j<HC[i].size();j++)
			System.out.print(HC[i].elementAt(j));
		}*/
		
	}
	
	private void binWrite(){
		try{
		FileImageOutputStream outfile=new FileImageOutputStream(outname);
		//System.out.print(length+" ");
		//for(int h=1;h<=length;h++)
		//System.out.print(table[h]+","+count[h]+" ");
		outfile.writeInt(length);
		outfile.write(table,1,length);
		outfile.writeInts(count,1,length);	//file header
		outfile.writeInt(filelength);
		byte c;
		int j,k,p;
		Vector v;
		for(int i=1;i<=filelength;i++)
		{
			c=input[i];
			j=lookup(c);
			v=HC[j];
			for(k=0;k<v.size();k++)
			{
				p=(Integer)v.elementAt(k);
				outfile.writeBit(p);
			}
					
		}
		outfile.flush();
		}
		catch(IOException e){
		} 
	}
	
	public void process(){
		readFile();
		check();
		HuffmanCoding();
		binWrite();
	}
	
	//public static void main(String [] args){
	//	Compress c=new Compress(new File("sam.txt"),new File("h.dat"));
	//	c.process();
	//}
}