霍夫曼压缩

hwfantasy

浏览: 21495 次
性别:
来自: 长沙

最近访客更多访客>>

18292807328

zhuzhezhe

250452300

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

java Huffman 压缩

经过几天的努力终于把霍夫曼压缩弄好了，其中几经波折，2度误删，幸好每一天的备份都在，并不是重头再来。
霍夫曼压缩是根据霍夫曼编码，将源文件中的字节编码重组的压缩。即将所有字节通过霍夫曼树转化为01串，由于霍夫曼树的特性，频数多的字节必定只有很短的霍夫曼编码，所以文件得以压缩。它的压缩效率主要在于你的压缩信息文件的大小和文件自身。
霍夫曼压缩基于前篇文章的二叉树类编写，故部分代码略去。
根据映射建立霍夫曼树的方法

public void creatHuffmanTree(HashMap<Byte,Integer> hmap) {

		if (hmap.isEmpty()) {
			throw new RuntimeException("空映射，无法建树");
		} else {
			// 得到K的Set集合
			java.util.Set<Byte> set = hmap.keySet();
			int len = set.size();
			int arr[] = new int[len];
			byte mem[] = new byte[len];
			// 遍历K的集合，得到set的迭代器
			java.util.Iterator<Byte> iter = set.iterator();
			int i=0;
			while (iter.hasNext()) {
				// 取出一个key
				byte num = iter.next();
				// 根据key得到对应的Value
				int name =  hmap.get(num);
				mem[i] = num;
				arr[i] = name;
				i++;
//				System.out.println(num + "\t" + name);
			}
			// 创建优先队列对象
			PriorityQueue<TNode> que = new PriorityQueue<TNode>(arr.length,
					new MyComparator());
			// 将数组中的元素建立结点对象并加入到优先队列中去
			for (int j = 0; j < arr.length; j++) {
				TNode node = new TNode(arr[j]);
				node.setByt(mem[j]);
				que.add(node);
			}
			System.out.println("size="+que.size());
			while (que.size() > 1) {
				// 将两个结点连成树
				TNode ltree = que.poll();
				TNode rtree = que.poll();
				TNode node = new TNode((Integer) ltree.getObj()
						+ (Integer) rtree.getObj());
				node.setLeft(ltree);
				node.setRight(rtree);
				ltree.setParent(node);
				rtree.setParent(node);

				// 加入子结点
				que.add(node);
			}
			root = que.poll();
		}
	}

计算文件中字节出现的频数，便于建立霍夫曼树

public int count(String path) {
		java.io.File file = new java.io.File(path);
		boolean b = file.isDirectory();
		if (b) {
			System.out.println("错误！给予的路径为文件夹");
			return 0;
		}
		Boolean b1 = file.exists();
		if (!b1) {
			System.out.println("错误！给予的路径不存在");
			return 0;
		}
		try {
			// 根据原始文件路径创建文件输入流对象
			java.io.FileInputStream fis = new java.io.FileInputStream(path);
			java.io.BufferedInputStream bis = new java.io.BufferedInputStream(fis);

			// 从fis中读取一个字节
			int data = bis.read();
			byte dat = (byte)data;
			while (data != -1) {
				if (amap.get(dat) == null) {
					amap.put( (byte)data, 1);
				} else {
					amap.put( (byte)data, amap.get(dat) + 1);
				}
				data =bis.read();
				dat = (byte)data;
			}

			// 关闭输出与输入流
			fis.close();

		} catch (Exception e) {
			e.printStackTrace();
		}
		return 1;
	}

读取目标文件并转换成霍夫曼编码的方法

public void readfile(String path, HashMap<Byte, String> hcmap) {

		// 根据原始文件路径创建文件输入流对象

		try {
			java.io.FileInputStream fis = new java.io.FileInputStream(path);
			java.io.BufferedInputStream bis = new java.io.BufferedInputStream(
					fis);

			// 从fis中读取一个字节
			int data = bis.read();
			byte dat = (byte) data;
			while (data != -1) {
				if (code == null) {
					code = hcmap.get(dat);
					// System.out.println("first "+code);
					// System.out.println();
				} else {
					// System.out.println();
					// System.out.println(dat + "     " + hcmap.get(dat));
					code = code.concat(hcmap.get(dat));
					// System.out.println("concat "+hcmap.get(dat));
				}
				data = bis.read();
				dat = (byte) data;
			}

			// 关闭输出与输入流
			fis.close();
		} catch (Exception e) {
			e.printStackTrace();
		}

	}

将压缩后的数据与压缩信息写入文件中的方法

public void Outtofile(String path, HashMap<Byte, String> hcmap) {

		try {
			// 建立输出流对象
			java.io.FileOutputStream fos = new java.io.FileOutputStream(path);
			DataOutputStream bos = new java.io.DataOutputStream(fos);

			// 将字符串的装换规则写入文件的开头

			// 得到K的Set集合
			java.util.Set<Byte> set = hcmap.keySet();
			// 先写入拥有的转换规则的个数
			int len = set.size();
			System.out.println("len1= " + len);
			bos.writeInt(len);
			// 遍历K的集合，得到set的迭代器
			java.util.Iterator<Byte> iter = set.iterator();
			while (iter.hasNext()) {
				// 取出一个key
				byte key = iter.next();
				int resu;
				// 根据key得到对应的Value
				String result = hcmap.get(key);
				// if (result.length() <= 8) {
				bos.writeByte(key);
				int b = result.length();
				BigInteger bi = new BigInteger(result, 2);
				String res = bi.toString(10);
				resu = Integer.valueOf(res);
				bos.writeInt(b);
				bos.writeInt(resu);
			

			}

			// 数据的长度
			int length;
			if (code.length() % 8 == 0) {
				length = code.length() / 8;
			} else {
				length = code.length() / 8 + 1;
			}
			// 将长度写入文件中
			bos.writeInt(length);
			BigInteger value;
			// 将01字符串转换为字节写入文件中
			while (!code.isEmpty()) {
				// 如果字符串大于8，则将前8个写入，并将前面的截去
				if (code.length() >= 8) {
					String s = code.substring(0, 8);
					value = new BigInteger(s, 2);
					String r = value.toString(10);
					int j = Integer.valueOf(r);
					bos.write(j);
					code = code.substring(8);
				} else {// 如果字符串小于8，则将前n个读取，并在后面补0补足8个，然后写入
					String s = code.substring(0, code.length());
					int time = 0;
					while (s.length() != 8) {
						s = s.concat("0");
						time++;
					}
					value = new BigInteger(s, 2);
					String r = value.toString(10);
					int j = Integer.valueOf(r);
					bos.write(j);
					bos.writeInt(time);
					code = "";
				}

			}

			fos.flush();
			fos.close();
		} catch (Exception e) {
			e.printStackTrace();
		}

解压缩的方法

public int anticomp(String opath, String path) {
		// 判断给予的元素文件路径是否是文件夹，是否存在
		java.io.File file = new java.io.File(opath);
		boolean b = file.isDirectory();
		if (b) {
			System.out.println("错误！给予的路径为文件夹");
			return 0;
		}
		Boolean b1 = file.exists();
		if (!b1) {
			System.out.println("错误！给予的路径不存在");
			return 0;
		}

		try {
			// 根据原始文件路径创建输入流对象
			java.io.FileInputStream fis = new java.io.FileInputStream(opath);
			java.io.DataInputStream bis = new java.io.DataInputStream(fis);
			// 根据目标文件路径创建输出流对象
			java.io.FileOutputStream fos = new java.io.FileOutputStream(path);
			java.io.DataOutputStream bos = new java.io.DataOutputStream(fos);
			// 创建映射用于解码
			HashMap<String, Byte> hmap = new HashMap<String, Byte>();
			// 读取长度
			int len = 0;
			len = bis.readInt();
			System.out.println("len2= " + len);
			String value;
			//读取映射的信息
			while (len != 0) {
				byte key = bis.readByte();
				int num = bis.readInt();
				int v = bis.readInt();
				value = Integer.toBinaryString(v);
				while (num > value.length()) {
					value = "0" + value;
				}
				hmap.put(value, key);
				len--;
			}

			// 得到K的Set集合
			java.util.Set<String> set = hmap.keySet();
			// 遍历K的集合，得到set的迭代器
			java.util.Iterator<String> iter = set.iterator();
			while (iter.hasNext()) {
				// 取出一个key
				String num = iter.next();
				// 根据key得到对应的Value
				byte name = hmap.get(num);
			}
			System.out.println("size=" + set.size());

			// 开始解码
			String data = "";

			int length = bis.readInt();
			//用byte数组接受数据
			byte arr[] = new byte[length + 1];
			bis.read(arr);
			//将数组所有数据全部转化为string加到data上
			for (int k = 0; k < length; k++) {
				int result = arr[k] & 0xff;
				String wdata = Integer.toBinaryString(result);
				while (wdata.length() < 8) {
					wdata = "0" + wdata;
				}
				data = data + wdata;
			}
			System.out.println(" data = " + data.substring(0, 8));
			System.out.println(" data = " + data.substring(8, 16));
			int time = arr[length] & 0xff;
			data = data.substring(0, data.length() - time);
			int flag = 1;
			String s = data.substring(0, flag);
			//通过建立的映射解码
			while (data.length() != 0) {
				if (hmap.get(s) == null) {
					flag++;
					if (data.length() != 0) {
						s = data.substring(0, flag);
					}
				} else {
					bos.write(hmap.get(s));
					data = data.substring(flag, data.length());
					flag = 1;
					if (data.length() != 0) {
						s = data.substring(0, flag);
					}
				}
			}

			// 刷新此输出流并强制写出所有缓冲的输出字节
			fos.flush();
			// 关闭输出与输入流
			fis.close();
			fos.close();
			hmap.clear();
		} catch (Exception e) {
			e.printStackTrace();
		}
		return 1;
	}
}