哈夫曼压缩

这次压缩做的时间比较长。主要因为考试和课程设计，在暑假里要做通信，不用备考，可以一心一意的学习java了。

现在对压缩做一下总结。

 

首先就要扫描文件，将字节一个一个 读出来，统计每一个字节的权值（字节出现的频率）存入HashMap对象map中；

 

                        FileInputStream fis = new FileInputStream(path);
			BufferedInputStream bis = new BufferedInputStream(fis);
			int t = bis.read();
			while (t != -1) {// 如果未到达文件结尾
				byte b = (byte) t;
				if (map.containsKey(b)) {// 如果map里面有b
					int value = map.get(b);// 通过get()得到b出现的次数
					value++;// 次数加1
					map.put(b, value);
				} else {// 如果map里面没有包括b
					map.put(b, 1);
				}
				t = bis.read();// 读取下一个
			}
		} catch (Exception e) {
			e.printStackTrace();
		}

 

创建优先级队列 ,使用指定的初始容量创建一个 PriorityQueue，将结点对象放入优先队列中， 并根据指定的比较器对元素进行排序。

 

		PriorityQueue<treeNode> tree = new PriorityQueue<treeNode>(10,
				new Comparator<treeNode>() {
					public int compare(treeNode o1, treeNode o2) {
						return o1.count - o2.count;
					}
				});
		// 遍历
		Set<Byte> key = map.keySet();// keySet()返回map的视图		
		// 得到迭代器
		Iterator<Byte> iter = key.iterator();
		 //将节点加入队列中
			while (iter.hasNext()) {
			byte k = iter.next();// 取k
			int value = map.get(k);// 根据k得到value值 ，即次数			
			treeNode node = new treeNode(k, value);
			tree.add(node);
			
		}

 构建哈夫曼树

while (tree.size() > 1) {

			int u = 0;
			treeNode n1 = tree.poll();
			tree.size();
			treeNode n2 = tree.poll();// 获取并移除;
			u = n1.getCount() + n2.getCount();
			treeNode su = new treeNode((byte) 0, u);
			su.setLchild(n1);
			su.setRchild(n2);
			tree.add(su);
			root = su;
		}

根据哈夫曼树得到哈夫曼编码，存入map1码表中

static HashMap<Byte, String> map1 = new HashMap<Byte, String>();//码表

 if (root.rchild == null && root.lchild == null) {// 叶子结点

 

			map1.put(root.data, s);
		}
		if (root.lchild != null) {
			bianma(root.lchild, s + "0");
		}
		if (root.rchild != null) {
			bianma(root.rchild, s + "1");
		}

 

读取文件，将文件中的字节转化成01字符串

 String s = "";

		try {
			// 根据文件地址创建文件输入流
			FileInputStream fis = new FileInputStream(path);
			// 将文件输入流转成缓冲流
			BufferedInputStream bis = new BufferedInputStream(fis);
			int t = bis.read();
			while (t != -1) {// 如果未到达文件结尾
				byte b = (byte) t;
				if (map.containsKey(b)) {// 如果map里面有b
					s += map.get(b);
					n++;
				}
				t = bis.read();// 读取下一个
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
		return s;

 

将01字符串每次取8位，按照2进制转10进制，转成byte，（在不是8的整数倍的 01String 后面补0，记录写了多少个 0，方便解压缩）

 

		int l=s.length();//字符串的长度
		int z=0;//字节数组数
		//如果长度是8 的整数倍，z+1,否则，补0，z+2(z的最后一个是存储补0 的个数，)		
		if(l%8==0) z=l/8+1; 
		else z=l/8+2;
		byte[] b=new byte[z];//定义一个byte数组，存储字节，最后一个是存储补0 的个数
		for(int i=0;i<l/8;i++){
			String st=s.substring(8*i, 8*i+8);
			//返回一个新字符串，它是此字符串的一个子字符串。
			//该子字符串从指定的 8*i 处开始，直到索引 8*i+8 处的字符。  读取8位字符长度
			b[i]=(byte)changeString(st);//将字符串转变成byte存入数组中
		}		
		if(l/8!=0){
			String sr=s.substring( 8*z-16, l);//剩下不足8位的字符01串
			for(int j=0;j<8*z-l-8;j++) sr+='0';
			b[z-2]= (byte)changeString(sr);
		}//将该不足8位的01串在末尾补0		 
		b[z-1]=(byte) (8*z-l-8);	//数组最后一位存储补0个数	
		return b;		

将01字符串转化成十进制数的方法

private static int changeString(String s) 
		int i = 0;			
		i = ( ((int) s.charAt(1) - 48) * 64
				+ ((int) s.charAt(2) - 48) * 32 + ((int) s.charAt(3) - 48) * 16
				+ ((int) s.charAt(4) - 48) * 8 + ((int) s.charAt(5) - 48) * 4
				+ ((int) s.charAt(6) - 48) * 2 + ((int) s.charAt(7) - 48));
			if( s.charAt(0)=='1') i=i*(-1);	
		return i;

 

 将码表和数组写到文件

FileOutputStream fos=new FileOutputStream("C:\\Documents and Settings\\芳儿\\桌面\\新建文件夹\\hh.txt");
			ObjectOutputStream ob=new ObjectOutputStream(fos);	
			ob.write(b);
			ob.writeObject(map);

 

 读取码表和数组

static Object map22=new HashMap<Byte, String>();//解压缩的码表

 FileInputStream fos=new FileInputStream("C:\\Documents and Settings\\芳儿\\桌面\\新建文件夹\\hh.txt");

 

			ObjectInputStream ob=new ObjectInputStream(fos);		
			int l=ob.available();//不受阻塞的读取的字节长度
			byte[] b = new byte[l];
			System.out.println("数组长度l="+l);
			int i=0;
			byte a =(byte) ob.read();
			while(a!=-1){
				b[i]=a;
				i++;			
				a =(byte) ob.read();//再读取一个								
			}			
			map22=ob.readObject();	
			Set<Byte> key = ((HashMap<Byte, String>) map22).keySet();// keySet()返回map的视图
			// 得到迭代器
			Iterator<Byte> iter = key.iterator();		
			while (iter.hasNext()) {
				byte k = iter.next();// 取k
				String va= ((HashMap<Byte, String>) map22).get(k);// 根据k得到value值 ，即对应的01串	

 

将十进制转变成01字符串

 

	String s="";
	for(int i=0;i<b.length-2;i++){	
	    s+=to01s(b[i]);	  
	}
	if(b[b.length-1]!=0) s+=to01s(b[b.length-2]).substring(0, 8-b[b.length-1]);
	else s+=to01s(b[b.length-2]);	
	return s;

 

 将十进制数转变成8位01串

	String s="";
	int tt;
	byte[] b = new byte[8];
	int i=7;
	if(t==0) s="00000000";
	if(t>0){
		tt=t;
		while(tt!=0){
			b[i]=(byte) (tt%2);			
			tt=tt/2;
			i--;		
		}				
		for(int t2=0;t2<8;t2++){
			if(b[t2]==0) s+="0";
			else s+="1";
		}			
	}
	if(t<0){
		b[0]=1;
		tt=(-1)*t;		
		while(tt!=0){ 		
		b[i]=(byte) (tt%2);					
		tt=tt/2;
		i--;		
		}		
		for(int t2=0;t2<8;t2++){
		if(b[t2]==0) s+="0";
		else s+="1";		
		}				
	}
	return s;

 

写入文件

 

		String st; 
		try{
			FileOutputStream fos=new FileOutputStream("C:\\Documents and Settings\\芳儿\\桌面\\新建文件夹\\jie.txt");
			BufferedOutputStream ob= new BufferedOutputStream(fos);	
			int j=0;
			for(int i=1;i<s.length()+1;i++){
				 st=s.substring(j, i);
				Set<Byte> key = ((HashMap<Byte, String>) map22).keySet();// keySet()返回map的视图
				Iterator<Byte> iter = key.iterator();// 得到迭代器		
				while (iter.hasNext()) {
					byte k = iter.next();// 取k
					String va= ((HashMap<Byte, String>) map22).get(k);// 根据k得到value值 ，即对应的01串	
				   if(st.equals(va)){					
					   ob.write(k);
					   j=i; 
				   }//码表中存在该01字符串
				  
				}				

 

这是被压缩的文件

 下面是被解压的文件