textzip.txt

来自「JAVA语言便编写的基于哈夫曼算法的压缩代码」· 文本 代码 · 共 306 行

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

/**
	@author  	李宁
	@version	2007年6月5日
**/

public class TextZip {
	private static final String ID = "20617027";		
	public static TreeNode abracadbraTree() {
		TreeNode n0 = new TreeNode(new CharFreq('!', 1));
		TreeNode n1 = new TreeNode(new CharFreq('c', 1));
		TreeNode n2 = new TreeNode(new CharFreq('\u0000', 2), n0, n1);
		TreeNode n3 = new TreeNode(new CharFreq('r', 2));
		TreeNode n4 = new TreeNode(new CharFreq('\u0000', 4), n3, n2);
		TreeNode n5 = new TreeNode(new CharFreq('d', 1));
		TreeNode n6 = new TreeNode(new CharFreq('b', 2));
		TreeNode n7 = new TreeNode(new CharFreq('\u0000', 3), n5, n6);
		TreeNode n8 = new TreeNode(new CharFreq('\u0000', '7'), n7, n4);
		TreeNode n9 = new TreeNode(new CharFreq('a', 5));
		TreeNode n10 = new TreeNode(new CharFreq('\u0000', 12), n9, n8);
		return n10;
	}

	public static void decompress(BitReader br, TreeNode huffman, FileWriter fw) throws Exception {

		int count1=0;
		int count2=0;
		TreeNode node=huffman;
		PrintWriter pw=new PrintWriter(fw);
		while(br.hasNext()){	//通过读取的1或是0来遍历哈夫曼树，到叶子结点时写入源文件		           
			if(node.getLeft()!=null||node.getRight()!=null)
			{
				boolean bit=br.next();
				count2++;
				if(bit)
				{
					node=node.getRight();					
				}
				else{
					node=node.getLeft();
				}
			}
			if(node.getLeft()==null&&node.getRight()==null)
			{
				char c=((CharFreq)node.getItem()).getChar();
				String cstring=c+"";
				pw.write(cstring);
				pw.flush();
				node=huffman;
				count1=count1+8;
			}						
		}
		count1=count1/8;
		count2=count2/8+2;
		double ratio=(double)count2*100/(double)count1;
		System.out.print("Size of the compressed file:"+count2+" bytes"+"\n"+
				"Size of the original file:"+count1+" bytes"+"\n"+
				"Compressed ratio:"+ratio+"%");		
	}

	public static void traverse(TreeNode t, String code) {

		if(t.getLeft()==null&&t.getRight()==null)
		{
			System.out.println(((CharFreq)t.getItem()).getChar()+":"+code);
		}		
		if(t.getLeft()!=null&&t.getRight()!=null)
		{
			traverse(t.getLeft(),code+"0");
			traverse(t.getRight(),code+"1");
		}
	}
	public static ArrayList traverseArray(TreeNode t, String code,ArrayList list) {
          //为了实现通过遍历获得链表，增加一个类似traverse的递归方法
		if(t.getLeft()==null&&t.getRight()==null)
		{
			((ArrayList)list.get(0)).add((int)((CharFreq)t.getItem()).getChar());
			((ArrayList)list.get(1)).add(code);
			return list;
		}
		
		if(t.getLeft()!=null&&t.getRight()!=null)
		{
			traverseArray(t.getLeft(),code+"0",list);
			traverseArray(t.getRight(),code+"1",list);
		}
		return list;
	}
		
	public static TreeNode removeMin(ArrayList a) {
		int minIndex = 0;
		for (int i = 0; i < a.size(); i++) {
			TreeNode ti = (TreeNode)a.get(i);
			TreeNode tmin = (TreeNode)a.get(minIndex);
			if (((Comparable)(ti.getItem())).compareTo(tmin.getItem()) < 0)
				minIndex = i;
		}
		TreeNode n = (TreeNode)a.remove(minIndex);
		return n;
	}

	public static ArrayList countFrequencies(FileReader fr, PrintWriter pw) throws Exception {

		int chr_name=fr.read();
		ArrayList<Integer>listAsc=new ArrayList<Integer>();
		ArrayList<Integer>listFre=new ArrayList<Integer>();
		ArrayList<TreeNode>list=new ArrayList<TreeNode>();
		while(chr_name!=-1)
		{
			boolean isfound=false;
			if(listAsc.size()==0)
			{
				listAsc.add(chr_name);
				listFre.add(1);
			}
			else
			{
				for(int k=0;k<listAsc.size();k++)
				{
					if(chr_name==listAsc.get(k))
					{
						listFre.set(k,listFre.get(k)+1);
						isfound=true;
						break;
					}
				}
				if(isfound==false)
				{
					listAsc.add(chr_name);
					listFre.add(1);
				}
			}
			chr_name=fr.read();
		}
		for(int q=0;q<listAsc.size();q++)
		{
			char wr=(char)((int)listAsc.get(q));
			int pinlv=listFre.get(q);
			pw.write(wr+":"+pinlv+"\n");
			pw.flush();
		}
		pw.close();
		for(int p=0;p<listAsc.size();p++)
		{
			TreeNode td=new TreeNode(new CharFreq((char)(int)listAsc.get(p),(int)listFre.get(p)));
			list.add(td);
		}
		return list;
		
	}

	public static TreeNode buildTree(ArrayList trees) throws IOException {

		TreeNode head=null;
        while(trees.size()>=2)
        {
        	TreeNode n1=removeMin(trees);
        	TreeNode n2=removeMin(trees);
        	TreeNode t1=new TreeNode(new CharFreq('\u0000',((CharFreq)n1.getItem()).getFreq()+((CharFreq)n2.getItem()).getFreq()),n1,n2);
        	head=t1;
        	trees.add(t1);
        }
        	return head;
		
	
	}

	public static void compress(FileReader fr, TreeNode huffman, BitWriter bw) throws Exception {

		int count1=0;
		int count2=0;
		ArrayList<ArrayList>list=new ArrayList<ArrayList>();//其中元素也是ArrayList，一共俩个
		ArrayList<Integer>listchar=new ArrayList<Integer>();//保存字符
		ArrayList<String>listcode=new ArrayList<String>();//保存对应的字首码
		list.add(listchar);
		list.add(listcode);
		list=traverseArray(huffman,"",list);
		ArrayList<Integer>charinfo=list.get(0);
		ArrayList<String>codeinfo=list.get(1);
		int readtxt=fr.read();
		while(readtxt!=-1)
		{
			count1=count1+8;//读出一个字符就加1 用来保存源文件大小
			for(int i=0;i<charinfo.size();i++)
			{
				if(readtxt==(int)charinfo.get(i))
				{
					String code=codeinfo.get(i);
					for(int k=0;k<code.length();k++)
					{
						int in=code.charAt(k)-48;
						
						bw.writeBit(in);
						count2++;//写到压缩文件一个bit就加1，用来保存压缩文件大小
					}
					break;
				}
			}
			readtxt=fr.read();
		}
		bw.close();
		count1=count1/8;
		count2=count2/8+2;
		double rate=(double)count2*100/(double)count1;
		System.out.print("file.txt compresed by "+ID+"\n"+"Size of the compressed file:" +
				count2+"\n"+"Size of the original file:"+count1+"\n"+"Compressed ratio:"+
				rate+"%");
						
	}

	public static ArrayList readFrequencies(String inputFreqFile) throws Exception {

		FileReader fr=new FileReader(inputFreqFile);
		ArrayList<TreeNode>tr=new ArrayList<TreeNode>();//返回的TreeNode链表
		ArrayList<Integer>listname=new ArrayList<Integer>();//保存出现的字符
		ArrayList<Integer>listfreq=new ArrayList<Integer>();//保存出现字符对应的频率
		int chaname=fr.read();
		listname.add(chaname);
		chaname=fr.read();
		while(chaname!=-1)
		{
			if(chaname==':')//频率文件存储的格式为：字符:频率（空格）+字符:频率.......故按这种格式读取
			{
				chaname=fr.read();
				int temp1=chaname-48;
				String temp2=String.valueOf(temp1);
				chaname=fr.read();
				while(chaname!='\n')
				{
					
					int temp3=chaname-48;
					String temp4=String.valueOf(temp3);
					temp2=temp2+temp4;
					chaname=fr.read();
				}
				listfreq.add(Integer.parseInt(temp2));								
			}
			if(chaname=='\n')
			{
				chaname=fr.read();
				if(chaname!=-1)
				{
					listname.add(chaname);
				}
				else
				{
					break;
				}				
			}
			chaname=fr.read();
		}
		for(int i=0;i<listname.size();i++)//根据字符和频率创造结点并添加到链表中
		{
			TreeNode td=new TreeNode(new CharFreq((char)(int)listname.get(i),(int)listfreq.get(i)));
			tr.add(td);
		}
		return tr;
	}
	public static void main(String[] args) throws Exception {

		if (args[0].equals("-a")) {

		    BitReader br = new BitReader(new File("a.txz"));
			FileWriter fw = new FileWriter("a.txt");
			TreeNode tn = abracadbraTree();
			System.out.println("a.txz depressed by "+ID);
			decompress(br, tn, fw);
			fw.close();
		}
		else if (args[0].equals("-f")) {
			FileReader fr = new FileReader(args[1]);
			PrintWriter pw = new PrintWriter(new FileWriter(args[2]));
			ArrayList trees = countFrequencies(fr, pw);
			fr.close();
			pw.close();
			TreeNode n = buildTree(trees);
            System.out.println("a.txt prefix codes by "+ID+"\n"+"character code:");
			traverse(n, "");		
		  }
		else if (args[0].equals("-c")) {

			FileReader fr = new FileReader(args[1]);
			PrintWriter pw = new PrintWriter(new FileWriter(args[2]));
			BitWriter bw = new BitWriter(new File(args[3]));
			ArrayList trees = countFrequencies(fr, pw);
			TreeNode n = buildTree(trees);
			FileReader fi = new FileReader("file.txt");
			compress(fi,n,bw);							
			fr.close();
			pw.close();
		}

		else if (args[0].equals("-d")) {
			ArrayList a = readFrequencies("file.freq");
			TreeNode tn = buildTree(a);
			BitReader br = new BitReader(new File("file.txz"));
			FileWriter fw = new FileWriter("file.txt");
			System.out.println("file.txz depressed by "+ID);
			decompress(br, tn, fw);
			fw.close();		
		}
	}
}