hafuman.java

哈夫曼编码（哈夫曼编码(Huffman Coding)是一种编码方式,哈夫曼编码是可变字长编码(VLC)的一种。）

import java.io.*;
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import java.util.*;

public class Hafuman extends JFrame
{
	int length;
	byte ch[] = new byte[8000];
	byte countPart[] = new byte[8000];
	int alpha[] = new int[25];
	MyTree tree[] = new MyTree[31];
	char zimu[] = new char[26];
	StringBuffer buffer = new StringBuffer();
	String charToString[] = new String[26];
	Hashtable connection = new Hashtable();
	
	public Hafuman()
	{
		super("Hafuman");
		outLook();
		events();
	}
	private void outLook()
	{
		Container contain = getContentPane();
		super.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
		super.setBounds(50,50,200,200);
		super.setVisible(true);
	}
	private void events()
	{
		for(int i=0;i<tree.length;i++)
		{
			tree[i] = new MyTree();
		}
		for(int i=0;i<countPart.length;i++)
		{
			countPart[i] = -1;
		}
		for(int i=0;i<charToString.length;i++)
		{
			charToString[i] = new String("-1");
		}
		String al = "abcdefghijklmnopqrstuvwxyz";
		zimu = al.toCharArray();
	}
	private void read()
	{
		try
		{
			FileInputStream input = new FileInputStream("哈夫曼编码实验数据.dat");
			length=input.read(ch);
			input.close();
			for(int j=0;j<length;j++)
			{
				alpha[ch[j]-97]+=1;
			}
			int k=0;
			for(int i=0;i<alpha.length;i++)
			{			
				if(alpha[i]!=0)
				{
					tree[k] = new MyTree(alpha[i],zimu[i]);
					k++;
				}	
			}
			int change = 0;
			for(int i=16;i<31;i++)
			{
				sort(tree,i-16+change,i);
				for(int j = i-16+change;j<i;j++)
				{
					System.out.println(j + "  :  "  + tree[j].nodeChar + "  :  " + tree[j].weight);
				}
				
				tree[i].weight = tree[i-16+change].weight + tree[i-15+change].weight;
				tree[i-16+change].zeroOrOne = 0;
				tree[i-15+change].zeroOrOne = 1;
				tree[i-16+change].parent = i;
				tree[i-15+change].parent = i;
				tree[i].lChild = i-16+change;
				tree[i].rChild = i-15+change;
				change++;
			}
			for(int i=0;i<tree.length;i++)
			{
				System.out.println(tree[i].nodeChar + "   :   " + tree[i].weight);
			}
			
			for(int i=0;i<tree.length;i++)
			{
				MyTree tempTree = tree[i];
				
				if(tempTree.nodeChar != '0')
				{
					StringBuffer temp = new StringBuffer("") ;
					temp.append(String.valueOf(tempTree.zeroOrOne));
					while(tempTree.parent!=0)
					{
						tempTree = tree[tempTree.parent];
						temp.append(String.valueOf(tempTree.zeroOrOne));
					}
					temp.delete(temp.length()-2,temp.length());
					temp.reverse();
					tree[i].result = temp.toString();
					System.out.println("result : " + i + " " + tree[i].nodeChar + " : " + tree[i].weight + ": " + tree[i].result);
					
				}
			}	
		}
		catch(Exception e)
		{}
		dealCharToString();
	/*	for(int i=0;i<tree.length;i++)
			System.out.println("\n" + tree[i].nodeChar + ","+i+"'s parent : " + tree[i].parent+"\n");
			*/
	}
	public void yaSuo()
	{
		for(int i=0;i<ch.length;i++)
		{
			if(ch[i]!=0)
			{
				buffer.append(tree[treeNumber(zimu[ch[i]-97])].result);
			}						
		}
		System.out.println("\n\n\nsave should be : "+buffer.length()%8);
		buffer.insert(0,toBinary((byte)(buffer.length()%8),true));	
		String tempString ="";//= buffer.substring(0,8);
		//tempChar = buffer.toString().toCharArray();
	//	System.out.println("\n\n"+tempString);
	//System.out.println("\n"+buffer.toString()+"\n");
		int count = 0;
		while((count*8 +8)<buffer.length())
		{
			tempString = buffer.substring(count*8,count*8 + 8);
			countPart[count] =toByte(tempString);
			count++;	
		}
		if(count*8<buffer.length())
		{
			tempString = buffer.substring(8*count,buffer.length());
			count++;
			countPart[count] = toByte(tempString);
		}
		try
		{
			FileOutputStream fileOut = new FileOutputStream("压缩结果.dat");
			fileOut.write(countPart,0,count);
			fileOut.flush();
			fileOut.close();
		}
		catch(Exception ex)
		{
		}
		JOptionPane.showMessageDialog(null,"压缩成功");
	}
	public void jieYa()
	{
		int length2=0;
		int save = 0;
		StringBuffer tempBuffer = new StringBuffer();
		StringBuffer tempBuffer2 = new StringBuffer();
		try
		{
			FileInputStream fileIn = new FileInputStream("压缩结果.dat");
			save = fileIn.read();
			System.out.println("\n\n\n\nsave length:"+save);
			length2 = fileIn.read(countPart);
		}
		catch(Exception ex)
		{
		}
		
		for(int i=0;i<length2-1;i++)
		{
			tempBuffer.append(toBinary(countPart[i],true));
		}
		tempBuffer.append(toBinary(countPart[length2-1],false));
		char originalChar=' ';
		
		while(tempBuffer.length()!=0)
		{
			
			for(int i=1;i<=10;i++)
			{
			
				if(i<=tempBuffer.length()&&connection.get(tempBuffer.substring(0,i))!=null)
				{
					tempBuffer2.append((Character)connection.get(tempBuffer.substring(0,i)));
					if(i<tempBuffer.length())
						tempBuffer.delete(0,i);
					else 
						tempBuffer.delete(0,tempBuffer.length());
				}
				if(i>tempBuffer.length())
				{
					if((Character)connection.get(tempBuffer.substring(0,tempBuffer.length()))!=null)
						tempBuffer2.append((Character)connection.get(tempBuffer.substring(0,i)));
					tempBuffer.delete(0,tempBuffer.length());
				}		
			}
		}
		byte tempByte[] = new byte[tempBuffer2.length()];
		char tempChar2[] = new char[tempBuffer2.length()];
		tempBuffer2.getChars(0,tempBuffer2.length(),tempChar2,0);
		for(int i=0;i<tempByte.length;i++)
		{
			tempByte[i] = (byte)tempChar2[i];
		}
		try
		{
			FileOutputStream fileOutput = new FileOutputStream("解压结果.dat");
			fileOutput.write(tempByte);
			fileOutput.flush();
			fileOutput.close();
		}
		catch(Exception ex)
		{
		}
		System.out.println("result:  "+tempBuffer2.toString()+"\n");
		System.out.println("\n\n"+tempBuffer2.length());
	}
	private byte toByte(String str)
	{
		byte result = 0;
		char tempCh[] = str.toCharArray();
		for(int i=0;i<tempCh.length;i++)
		{
			result += Integer.parseInt(tempCh[i]+"")<<(7-i);
		}
		return result;
	}
	private void dealCharToString()
	{
		for(int i=0;i<tree.length;i++)
		{
			if(tree[i].nodeChar!='0')
			{
				connection.put(tree[i].result,tree[i].nodeChar);
			}
		}
	}
	
	public String toBinary(byte b,boolean isNotLast)
	{
		StringBuffer tempBuffer = new StringBuffer();
		int tempInt;
		if(b<0)
			tempInt = b + 256;
		else
			tempInt = b;
	
		while(tempInt>0)
		{
			tempBuffer.append(tempInt%2);
			tempInt = tempInt/2;
		}
		while(isNotLast&&tempBuffer.length()<8)
		{
			tempBuffer.append(0);
		}
		tempBuffer.reverse();
		return tempBuffer.toString();
	}
	public int treeNumber(char ch)
	{
		for(int i=0;i<tree.length;i++)
		{
			if(tree[i].nodeChar == ch)
				return i;
		}
		return -1;
	}
	
	public void sort(MyTree []tree,int a,int b)
	{
		MyTree min = new MyTree();
		for(int i=a;i<b;i++)
		{
			min = tree[i];
			for(int j = i+1;j<b;j++)
			{
				if(min.weight>tree[j].weight)
				{
					int temp1,temp2;
					if(min.lChild!=-1&&min.rChild!=-1&&tree[j].lChild!=-1&&tree[j].rChild!=-1)
					{
						temp1 = tree[min.lChild].parent;
						temp2 = tree[min.rChild].parent;
						tree[min.lChild].parent = j;
						tree[min.rChild].parent = j;
						tree[tree[j].lChild].parent = temp1;
						tree[tree[j].rChild].parent = temp2;
					}
					else if(min.lChild!=-1&&min.rChild!=-1)
					{
						tree[min.lChild].parent = j;
						tree[min.rChild].parent = j;
					}
					else if(tree[j].lChild!=-1&&tree[j].lChild!=-1)
					{
						tree[tree[j].lChild].parent = i;
						tree[tree[j].rChild].parent = i;
					}
					min.swap(tree[j]);
					
				}
			}
		}
	}
	public static void main(String args[])
	{
		Hafuman h = new Hafuman();
		h.read();
		h.yaSuo();
		h.jieYa();
		System.out.println("bijiao"+h.length+" : " );
		/*byte b = -1;
		System.out.println(b.intValue());*/
		/*if(h.ch[0]!='0')
		{
			System.out.println("\n\n"+h.ch[0]);
		}*/
		//System.out.println("\n\n::"+h.countPart[0]);
	
	}
	class MyTree
	{
		int parent;
		int rChild;
		int lChild;
		int weight;
		char nodeChar;
		int zeroOrOne;
		String result;
		
		public MyTree()
		{
			parent = 0;
			lChild = -1;
			rChild = -1;
			weight = -1;
			zeroOrOne = -1;
			nodeChar = '0';
			result = "-1";
		}
		public MyTree(int w,char node)
		{
			parent = 0;
			lChild = -1;
			rChild = -1;
			weight = w;
			zeroOrOne = -1;
			nodeChar = (char)node;
			result = "-1";
		}
		public MyTree(int p,int l,int r,int w,int z,char node)
		{
			parent = p;
			lChild = l;
			rChild = r;
			weight = w;
			zeroOrOne = z;
			nodeChar = (char)node;
			result = "-1";
		}
		public boolean swap(MyTree tree)
		{
			int p,l,r,w,z;
			char node;
			p = this.parent;
			l = this.lChild;
			r = this.rChild;
			w = this.weight;
			z = this.zeroOrOne;
			node = this.nodeChar;
			this.lChild = tree.lChild;
			this.rChild = tree.rChild;
			this.nodeChar = tree.nodeChar;
			this.parent = tree.parent;
			this.weight = tree.weight;
			this.zeroOrOne = tree.zeroOrOne;
			tree.lChild = l;
			tree.rChild = r;
			tree.nodeChar = node;
			tree.parent = p;
			tree.weight = w;
			tree.zeroOrOne = z;
			return true;
		}
	}
}