哈夫曼压缩

大_圣

浏览: 17657 次
性别:
来自: 湖南

最近访客更多访客>>

博主相关

博客

微博

相册

留言

关于我

文章分类

全部博客 (20)

社区版块

存档分类

这几天完成了哈夫曼原理压缩文件的实现.. 虽然这个实现压缩的速度相当让人蛋疼.. 不过这也算是加深了对压缩原理的的理解吧. 话说. 我还用系统给的类写了个Zip格式的压缩.. 比较之下才发现自己写的那些代码实在是不及他人的皮毛啊. 同样是一个类. 我的效率比起系统的来说...... 这根本就是没法比啊. 前路漫漫. 自己要学的,要改的还有很多啊.. 先谈谈自己的这个上不了眼压缩.. 首先是统计各个字节出现的次序

// 创建映射集,每个字节对应其出现的次数.
		HashMap<Byte, Integer> map = new HashMap<Byte, Integer>();
		try {// 文件地址正确的时候创建文件输入流
			FileInputStream fis = new FileInputStream(path);
			// 封装成缓冲流
			BufferedInputStream bis = new BufferedInputStream(fis);

			int len = bis.available();
			// 每次读取一个字节
			byte data;
			file = new byte[len];
			int i = 0;
			while (len > 0) {
				data = (byte) bis.read();
				// System.out.println(data);
				file[i] = data;
				// 如果字节在映射中不存在,则放入1
				if (map.get(data) == null) {
					map.put(data, 1);
				} else {// 如果字节在映射中已经存在,则value值在原来基础上加1
					map.put(data, map.get(data) + 1);
				}
				i++;
				len = bis.available();
			}
			fis.close();

		} catch (Exception ef) {
			ef.printStackTrace();
		}

然后再根据各字节出现过的次数大小(即各个字节出现的频率)来构造哈夫曼树,并通过这棵哈夫曼树来为每个字节编码,于是每个字节都有一个唯一的哈夫曼编码与之对应.然后再通过文件中各个字节的顺序来得到整个文件的所有字节的哈夫曼编码,再将这些编码分割成8位8位的.. 然后就能将这些字符串变成字符串写到文件中去了.

// 创建文件输出流
			FileOutputStream fos = new FileOutputStream(des);

			// 包装成基本类型数据流将字节长度写入文件
			DataOutputStream dos = new DataOutputStream(fos);
			// String转化成的字节数组的长度
			dos.writeInt(str.length() / 8 + 1);

			byte[] by;
			// 字符串的长度
			int slen = str.length();
			if (slen % 8 == 0) {// 如果字符串长度正好是8的整数倍,即说明最后没有补0,byte数组的最后一个数放0,表示没有补0
				dos.writeInt(1);// 字符串大小正好是8的整数倍
				by = new byte[slen / 8 + 1];
				String s;
				int c = 0;
				// 循环,每次得到一个8位的01串
				while (str.length() >= 8) {
					// 得到8位01串
					s = str.substring(0, 8);
					BigInteger bi = new BigInteger(s, 2);// 将01串转换为BigInteger类型
					String s1 = bi.toString(10);// 转换为10进制结果
					int i = Integer.valueOf(s1);
					by[c] = (byte) i;
					strlist1.put(by[c], s);

					// 将得到的8位01串丢掉.
					str = str.substring(8);
					c++;
				}
				by[c] = 0;
				dos.write(by);
			} else {// 如果字符串长度不是8的整数倍,则说明要多留出一位来存放那个不满8zz位的"字节",同时还要多一位来存放补上的0的个数.
				dos.writeInt(0);// 字符串的长度不是8的整数倍
				by = new byte[slen / 8 + 2];
				String s;
				int c = 0;
				// 循环,每次得到一个8位的01串
				while (str.length() > 8) {
					// 得到8位01串
					s = str.substring(0, 8);
					BigInteger bi = new BigInteger(s, 2);// 将01串转换为BigInteger类型
					String s1 = bi.toString(10);// 转换为10进制结果
					int i = Integer.valueOf(s1);
					by[c] = (byte) i;
					strlist1.put(by[c], s);
					// 将得到的8位01串丢掉.
					str = str.substring(8);
					c++;
				}
				// 往字符串后面补0.
				int sl = str.length();
				for (int k = 0; k < 8 - sl; k++) {
					str += 0;
				}
				BigInteger bi = new BigInteger(str, 2);// 将01串转换为BigInteger类型
				String str1 = bi.toString(10);// 转换为10进制结果
				int i = Integer.valueOf(str1); // 将字符串转成int类型
				by[c] = (byte) i; // 强制转型成byte类型.放入数组,写到文件中.
				strlist1.put(by[c], str);
				by[c + 1] = (byte) (8 - sl);
				dos.write(by);
			}
			// 包装成对象输入流将码表直接以对象的形式写入文件
			ObjectOutputStream oos;
			oos = new ObjectOutputStream(fos);
			oos.writeObject(writemap);
			oos.writeObject(strlist1);

			oos.flush();

			// 强制输出
			dos.flush();
			fos.close();

由于上次在实现自定义画板的文件保存时,用了对象数据流, 尝到了甜头.. 于是我这次的码表就直接用对流输出流来写.. 这个方法虽然省事.. 但是会产生"副作用":会降低压缩比率.. 貌似对读写的时间也有影响..

接下来就是解压了.. 其实就是压缩的逆过程吧,, 只要好好注意.. 自己是怎么样把各个字节写入的,再一步一步将其还原回来就是了.

// 得到文件地址
			FileInputStream fis = new FileInputStream(src);
			FileOutputStream fos = new FileOutputStream(des);

			// 包装成数据流
			DataInputStream dis = new DataInputStream(fis);
			DataOutputStream dos = new DataOutputStream(fos);

			int arraylen;
			// 读取字节数组的长度
			arraylen = dis.readInt();
			int flag = dis.readInt();// 此处a为标志,1表示被压缩的源文件的哈夫曼编码总长度是8的整数倍
			// 0表示被压缩的源文件的哈夫曼编码的总长度不是8的整数倍

			// 被压缩文件的源文件的哈夫曼编码长度是8的整数倍,即只多了一位放0.(arraylen==slen%8+1)
			if (flag == 1) {
				by = new byte[arraylen - 1];// 最后一位直接丢弃
				dis.read(by);
				dis.read();
				ObjectInputStream ois = new ObjectInputStream(fis);
				maps = (HashMap) ois.readObject();
				m = (HashMap) ois.readObject();
				// 将字节数组转成字符串
				String s1 = "";
				for (int k = 0; k < by.length; k++) {
					s1 += m.get(by[k]);
				}
				String s2;
				int s2l = 0;
				int sl = 1;
				int s1l = s1.length();
				while (s1l > 0) {
					// 首先从一位开始找匹配,找到就写文件
					s2 = s1.substring(s2l, sl);
					while (maps.get(s2) == null) {
						sl++;
						s2 = s1.substring(s2l, sl);
					}
					dos.write(maps.get(s2));
					s1 = s1.substring(sl);
					s2l = 0;
					sl = 1;
					s1l = s1.length();
				}
			} else {// 不是8的整数倍..(arraylen==slen%8+1)
				by = new byte[arraylen];
				dis.read(by);
				byte num = dis.readByte();// 读出最后一个记录补0个数的字节
				ObjectInputStream ois = new ObjectInputStream(fis);
				maps = (HashMap) ois.readObject();
				m = (HashMap) ois.readObject();
				String s = "";
				for (int k = 0; k < by.length; k++) {
					s += m.get(by[k]);
				}
				int initlen = s.length();
				s = s.substring(0, initlen - (int) num);// 截取第一位到补0的第一位.
				String s2;
				int s2l = 0;
				int sl = 1;
				int s1l = s.length();
				while (s1l > 0) {
					// 首先从一位开始找匹配,找到就写文件
					s2 = s.substring(s2l, sl);
					while (maps.get(s2) == null) {
						sl++;
						s2 = s.substring(s2l, sl);
					}
					dos.write(maps.get(s2));
					s = s.substring(sl);
					s2l = 0;
					sl = 1;
					s1l = s.length();
				}

			}
			dos.flush();
			fos.close();

鉴于压缩一个大文件实在是太慢了.. 就选了一个比较小的文件来示例了.. 压缩的比率也的确不高啊....